Introduction

Math 455

Murray Eisenberg

Math 455 introduction

Example 1

Speak["A medical study is going to test the interactions of the four substances tyramine, phenylethylamine, monosodium glutamate (MSG), and papain in causing migraine headaches."]

A medical study is going to test the interactions of the four substances tyramine, phenylethylamine, monosodium glutamate (MSG), and papain in causing migraine headaches.

According to the study's design:

• each of the substances is to be ingested by 56 subjects (some of whom may also ingest one or more of the other three substances);

• each pair of the substances is to be ingested by 24 subjects (some of whom may also also ingest one or two of the other two substances);

• each triple of the substances is to be ingested by 8 subjects (some of whom may also also ingest the fourth substance); and

• all four substances are to be ingested by 4 subjects.

How many subjects are required in order to carry ouy the study?

Math 455 introduction: combinatorics

Example 2

A deranged mailman randomly distributes 100 differently-addressed letters to the mailboxes of the 100 residents in your dorm.

What's the probability that nobody gets his/her own letter?

Math 455 introduction: combinatorics

Tiny version of problem—4 letters, 4 dorm residents.

Some examples of letter arrangements:

{{Residents,1,2,3,4},{Letters,2,3,4,1}}//Grid[#,Dividers->Center]&

{{Residents,1,2,3,4},{Letters,2,4,3,1}}//Grid[#,Dividers->Center]&

Math 455 introduction: combinatorics

Solve problem for n=4:

numberOfLetters=4;
letters=Range[numberOfLetters]

allWays=Permutations[letters]

numberOfAllWays=Length[allWays]

numberOfLetters!

Select[allWays,And@@MapThread[Unequal,{#,letters}]&]

Needs["Combinatorica`"]

derangedWays=Derangements[4]

numberOfDerangedWays=Length[derangedWays]

(numberOfDerangedWays/numberOfAllWays)

Math 455 introduction: combinatorics

Solve original problem (n=100):

numberOfLetters=100;

numberOfAllWays=numberOfLetters!

numberOfLetters

numberOfDerangedWays=Length[Derangements[numberOfLetters]]

numberOfDerangedWays=NumberOfDerangements[numberOfLetters]

(numberOfDerangedWays/numberOfAllWays)

N[%]

Math 455 introduction

Example 1

How can you calculate, e.g., (78390^91025) mod 18077 — and why might you want do to so?

bigNumber=(78390^91025)

divisor=18077;

remainder=Mod[bigNumber,divisor]

What does the answer mean?

quotient=Quotient[bigNumber,divisor]

bigNumber==quotient×divisor+remainder

Math 455 introduction: number theory

Example 2

Alice sends a message to Bob using a Rivest-Shamir-Adelman (RSA) public-key cryptosystem.

What prevents somebody who intercepts the message from decipering it?

Math 455 introduction

Example

A program calls 7 different procedures. Each accesses one or more of 6 data files in read/write mode.  No two procedures must access the same file at the same time.

Which procedures accesse which files is indicated in the following table.

Question: What is the minimum number of time slices required for scheduling all the procedures, and how should the procedures be scheduled?

Math 455 introduction: graph theory

Data

({{Proc\File, 1, 2, 3, 4, 5, 6}, {1,  , ✓,  , ✓,  ,  }, {2, ✓,  , ✓, ✓, ✓,  }, {3,  , ✓, ✓,  ,  , ✓}, {4, ✓,  , ✓, ✓,  ,  }, {5,  , ✓, ✓,  ,  , ✓}, {6, ✓,  ,  ,  ,  , ✓}, {7,  , ✓,  , ✓, ✓,  }})

Represent the data as a graph

allAccesses = {
{2,4}, {2,6}, {4,6}, 
{1,3}, {1,5}, {1,7}, {3,5}, {3,7}, {5,7},
 {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}, 
{1,2}, {1,4}, {1,7}, {2,4}, {2,7}, {4,7}, 
{2,7}, 
{3,5}, {3,6}, {5,6}
};

theEdges = Union[allAccesses]

g=FromOrderedPairs[theEdges,Type->Undirected]; ShowGraph[g,VertexNumber->True,BaseStyle->{FontSize->16}]

Math 455 introduction: graph theory

A prettier rendering of the graph:

RuleListFromGraph[Graph[edges_,vertices_,___]]:=Module[{vrules},vrules=DeleteCases[Thread[Range[Length[vertices]]->(VertexLabel/.vertices[[All,2;;]])],_->VertexLabel];
Replace[Transpose[{Rule@@@(edges[[All,1]]/.vrules),EdgeLabel/.edges[[All,2;;]]}],{a_,EdgeLabel}->a,{1}]]
GetVertexCoordinates[Graph[edges_,vertices_,___]]:=vertices[[All,1]]

g=FromOrderedPairs[theEdges,Type->Undirected]; 
g=
SetVertexLabels[g,Range[7]];
GraphPlot[RuleListFromGraph[g],VertexLabeling->True,VertexCoordinateRules->GetVertexCoordinates[g],EdgeRenderingFunction->({Blue,Thick,Line[#]}&),VertexRenderingFunction->({EdgeForm[{Purple,Thick}],Yellow,Disk[#,0.1],Black,Style[Text[#2,#1],18,FontWeight->"Bold"]}&)]

Math 455 introduction: graph theory

• How interpret the question as a problem about this graph?

• How solve that graph-theoretic problem?