程序代写代做代考 C algorithm decision tree game data structure go graph computational biology AI EECS 3101

EECS 3101
Prof. Andy Mirzaian

Welcome
to the beautiful and wonderful
world of algorithms!
2

STUDY MATERIAL:
• [CLRS] chapter 1 • Lecture Note 1
NOTE:
• Material covered in lecture slides are as self contained as possible
and may not necessarily follow the text book format.
3

Origin of the word
 Algorithm = algorism (old English version)
 = arithmetic process by Arabic numerals
 Algorithmus Infinitesimalis = calculus by infinitesimals  Euclid’s algorithm: greatest common divisor
“algorithm”
[Oxford English Dictionary] [Webster’s New World Dictionary]
[by Leibnitz and Newton] [Euclid’s Elements: Book VII.1-2]
Khâwrázmî
• •
wrote two influential books:
Ál-maqhaléh fi hésab ál-jábr wál-moqhabéléh
An essay on arithmetic restoration & reduction
Kétab ál-jáma wál-táfreeqh bél hésab ál-Hindi
Book of addition & subtraction á la Hindu arithmetic
According to math historians the true origin of the word algorism: comes from a famous Persian author named ál-Khâwrázmî.
Latin translation of these books coined the words:
algorithm = algorizmi = ál-Khâwrázmî
algebra = ál-jábr [restoration by equational calculus]
4

Euclid of Alexandria ( ~ 300 B.C.)
Euclid of Alexandria
Euclid in Raphael’s painting
Courtesy of Wikipedia
Statue of Euclid in the Oxford University
Museum of Natural History
Euclid’s “Elements” proof of
Pythagoras Theorem
5

Khâwrázmî
(780-850 A.D.)
A stamp issued September 6, 1983 in the Soviet Union, commemorating Khâwrázmî’s 1200th birthday.
Statue of Khâwrázmî
in front of the
Faculty of Mathematics, Amirkabir University of Technology, Tehran, Iran.
A page from his book.
Courtesy of Wikipedia
6

Computational Landscape
Design Methods:
Iteration & Recursion
 pre/post condition, loop invariant  Incremental
 Divide-&-Conquer
 Prune-&-Search
 Greedy
Dynamic programming
 Randomization
Reduction …
Analysis Methods:
 Mathematical Induction
 pre/post condition, loop invariant Asymptotic Notation
 Summation
 Recurrence Relation
Lower and Upper Bounds Adversarial argument
Decision tree
 Recursion tree
Reduction …
Data Structures:
 List, array, stack, queue Hash table
 Dictionary
Priority Queue Disjoint Set Union
 Graph …
Computational Models:
 Random Access Machine (RAM) Turing Machine
Parallel Computation Distributed Computation
 Quantum Computation …
7

Mathematical Induction
In the field of algorithms induction abound.
The following are equivalent for any 𝑆  𝑁 = 0,1,2,3, … ∶ (1) 𝑆 = 𝑁.
(2) 𝑛𝑁 𝑛𝑆 .
(3) 𝑾𝒆𝒂𝒌𝑰𝒏𝒅𝒖𝒄𝒕𝒊𝒐𝒏: (𝑖) 𝐵𝑎𝑠𝑒 𝐶𝑎𝑠𝑒:
𝑖𝑖 𝐼𝑛𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑆𝑡𝑒𝑝:
(4) 𝑺𝒕𝒓𝒐𝒏𝒈𝑰𝒏𝒅𝒖𝒄𝒕𝒊𝒐𝒏:
0𝑆
𝑛𝑁– 0 𝑛 – 1𝑆  𝑛𝑆 .
𝑛𝑁 [ 0,1,2,…,𝑛–1 𝑆  𝑛𝑆]. [ 𝑁𝑜𝑡𝑒: “𝑛 = 0𝑁 [𝑆  0𝑆 ]” 𝑖𝑚𝑝𝑙𝑖𝑒𝑠 𝑡h𝑒 𝐵𝑎𝑠𝑒 𝑐𝑎𝑠𝑒 0𝑆 ].
(5) 𝑷𝒓𝒊𝒏𝒄𝒊𝒑𝒍𝒆𝒐𝒇𝑴𝒊𝒏𝒊𝒎𝒂𝒍𝒊𝒕𝒚:
𝒏𝒐𝒏-𝒆𝒙𝒊𝒔𝒕𝒆𝒏𝒄𝒆 𝒐𝒇 𝒔𝒎𝒂𝒍𝒍𝒆𝒔𝒕 𝒄𝒐𝒖𝒏𝒕𝒆𝒓-𝒆𝒙𝒂𝒎𝒑𝒍𝒆:
𝑛𝑁[ 0,1,2,…,𝑛–1 𝑆 𝑎𝑛𝑑 𝑛𝑆].
8

Mathematical Induction
We only prove the red implications “”. The end result is all the blue conclusions.
Weak Induction:
Strong Induction:
S  0S {0}S  1S {0,1}S  2S {0,1,2}S  3S {0,1,2,3}S  4S {0,1,2,3,4}S  5S {0,1,2,3,4,5}S  6S {0,1,2,3,4,5,6}S  7S {0,1,2,3,4,5,6,7}S  8S {0,1,2,3,4,5,6,7,8}S  9S : : : :
True  0S 0S  1S 1S  2S 2S  3S 3S  4S 4S  5S 5S  6S 6S  7S 7S  8S 8S  9S
9

A warm up example
Practice yourself, for heaven’s sake, in little things; and hence proceed to greater.
– EPICTETUS (Discourses IV, i)
10

Towers of Hanoi [Edouard Lucas 1883]
•
•
TH(n, A, B, C):
There are n disks on stack A in sorted order of size, stacks B and C are empty. Move all n disks from stack A to B, using C as intermediate storage.
•
 Move one disk at a time:
pop the top disk from any stack and push it on top of any other stack. “X  Y” means move top disk from stack X to stack Y.
 Never place a larger disk on top of a smaller one. To try an animation click here.
n
Rules:
Computational Model
ABC
11

Notes:
12

Pre-Condition:
n
The time when the largest disk moves … think RECURSIVELY:
n-1
TH(n-1,A,C,B)
ABC
ABC
13

Pre-Condition:
n
The time when the largest disk moves … think RECURSIVELY:
TH(n-1,A,C,B)
ABC
TH(n,A,B,C)
n-1
AB
ABC
The task remaining … think RECURSIVELY again:
TH(n-1,C,B,A)
n-1
Post-Condition:
ABC
14

TH: A recursive solution
Algorithm TH(n, A, B, C) begin
1. if n  0 then return
2. TH(n–1, A, C, B)
3. AB
4. TH(n–1, C, B, A) end
PreCond&ALG PostCond
Notation:
Algorithm Invariant (AI): holds throughout this algorithm:
Stacks A, B, C form a partition of {1..N}, and
each contains disks sorted by size, top-to-bottom.
In general, for any recursive call TH(n, A, B, C) :
Pre-Condition: AI, A = 1 .. n, A’, B = B’, C = C’, n  0. Post-Condition: AI, A = A’, B = 1 .. n, B’, C = C’, n  0 .
For the initial call TH(N, A, B, C): A’ = B’ = C’ = , n = N.
Disks are numbered 1,2, 3, … , N in increasing order of size.
Stack X =  xtop, … , xbottom .
15

PreCond & ALG  PostCond Algorithm TH(n, A, B, C)
§ PreCond: AI, A = 1 .. n, A’, B = B’ , C = C’ , n  0 begin
1. if n  0 then return § AI, A=A’, B=B’, C=C’, n = 0 §…………………. AI, A=1..n-1,n, A’, B=B’, C=C’, n-1  0
2. TH(n–1, A, C, B)
§………………. AI, A=n, A’, B=B’, C=1 .. n-1, C’, n-1  0
3. AB
§……………….. AI, A=A’, B=n, B’, C=1 .. n-1, C’, n-1  0
4. TH(n–1, C, B, A)
§………………..AI, A=A’, B= 1..n-1,n, B’, C=C’, n -1  0
end
§ PostCond: AI, A = A’ , B = 1..n, B’, C = C’ , n  0
16

TH: Analysis
Algorithm TH(n, A, B, C)  Recursive solution: simple and elegant.
1. if n  0 then return 2. TH(n–1, A, C, B)
3. AB
4. TH(n–1, C, B, A)
end
Correctness:
 Visualize sequence of individual disk moves!
1. Partial correctness: If the algorithm eventually halts, then we assert (by mathematical induction) that
PreCondition&ALGORITHM PostCondition.
2. Termination: the algorithm halts after a finite number of steps.
Work (or “Time”) Complexity:
𝑇(𝑛) = # disk moves performed by algorithm TH Recurrence relation:
0 𝑖𝑓 𝑛 ≤ 0 2𝑇𝑛−1+1 𝑖𝑓𝑛>0
𝑇𝑛=
Solution: 𝑇 𝑛 = 2𝑛– 1 𝑓𝑜𝑟𝑎𝑙𝑙𝑛≥0.
17

TH: Recursion Tree
Algorithm TH(n, A, B, C) 1. if n  0 then return 2. TH(n–1, A, C, B)
3. AB
4. TH(n–1, C, B, A) end
recursion is invoked in pre-order
(1,A,C,B) (0,A,B,C) AC
 Recursive solution: simple and elegant.
 Visualize sequence of individual disk moves!
 Recursion tree helps in many ways  Is there a simple iterative solution?
(Without simulating recursion stack please!) (2,A,B,C)
AB
(1,C,B,A)
(0,C,A,B) CB (0,A,B,C)
(0,B,C,A)
Non-empty leaves in pre-order (i.e., from left to right):
AC , AB , CB . 2n – 1 = 3 moves (n = 2).
18

Cyclic direction:
An Iterative Solution
Algorithm IterTH(n, A, B, C) § assume n > 0 Loop:
(a) Move smallest disk one step in cyclic direction (b) if two stacks are empty then exit loop
(c) Make the only possible non-smallest disk move
end
AB
C
If n is odd
AB
C
If n is even
Iteration step
disk move
A
B
C
0
1,2,3


1
1a
AB
2,3
1

2
1c
AC
3
1
2
3
2a
BC
3

1,2
4
2c
AB

3
1,2
5
3a
CA
1
3
2
6
3c
CB
1
2,3

7
4a
AB

1,2,3

4b
nil
HALT
19

Algorithm TH(n, A, B, C)
1. if n  0 then return
2. TH(n–1, A, C, B)
3. A  B
4. TH(n–1, C, B, A)
end
The recursive solution:
Algorithm IterTH(n, A, B, C) § assume n > 0 Loop:
(a) Move smallest disk one step in cyclic direction (b) if two stacks are empty then exit loop
(c) Make the only possible non-smallest disk move
end
Iterative vs Recursive Solution
1. Execution:
2. Termination:
3. Correctness:
4. Complexity:
5. Design:
Easy for a computer; it uses recursion stack.
We, humans, can visualize the macro not the micro picture!
OK. Recursive calls are made to strictly smaller instances.
OK. From pre- to post-condition by induction.
Optimal! Less than 2n –1 disk moves is impossible! Induction again (or principle of minimality)!
Conceptually simple; just think recursively (inductively).
20

Iterative vs Recursive Solution
Algorithm IterTH(n, A, B, C) § assume n > 0 Loop:
(a) Move smallest disk one step in cyclic direction (b) if two stacks are empty then exit loop
(c) Make the only possible non-smallest disk move
end
The human brain is an iterative processor, but the human mind is an inductive thinker.
1. Execusion: ……………Micro steps OK. Macro “picture”? … hemmm!
2. Termination: ………….Can it get into an infinite loop?
3. Correctness: ………….Does post-cond hold upon termination? Wrong stack?
4. Complexity: …………..How many disk moves does it make?
5. Design:………………..How does one design such a solution any way?!
6. The Loop: What is going on ???
Loop Invariant: What general pattern does it maintain in each iteration?
This corresponds to the concept of induction hypothesis.
EXERCISE: Using induction, show the two solutions make exactly the same sequence of disk moves.
Algorithm TH(n, A, B, C)
1. if n  0 then return
2. TH(n–1, A, C, B)
3. A  B
4. TH(n–1, C, B, A)
end
The iterative solution:
21

Time-Space Trade off
 3 stacks, n disks: 2n –1 moves necessary and sufficient.
 What if we had more stacks available?
 Tk(n) = # disk moves needed
to move n disks using k stacks.
 T3(n) = 2n –1 (exponential in n).
 For n < k: Tk(n) = 2n –1 (linear in n). Method: move each disk to a separate stack, then reassemble them on the destination stack.  T4(n) = ? T5(n) = ? ... In general, Tk(n) = ? Example: 𝑇3 15 = 215 − 1 = 32767, 𝑇4 15 ≤129. 22 GTH: Generalized Recursive Solution Algorithm GTH(n disks, k stacks) 1. if n < k then in 2n –1 moves “disassemble” then “reassemble” return 2. m  an integer between 1 and n –1 what is the optimum choice? 3. GTH(n – m, k) 4. GTH(m, k – 1) 5. GTH(n – m, k) end use all k stacks to move the n-m smallest disks to an intermediate stack use the k –1 available stacks to move the m largest disks to destination stack use all k stacks to move the n-m smallest disks to destination stack n–m m 23 GTH: Analysis Algorithm GTH(n disks, k stacks) 1. if n < k then in 2n –1 moves “disassemble” then “reassemble” return 2. m  an integer between 1 and n –1 what is the optimum choice? 3. GTH(n – m, k) use all k stacks to move the n-m smallest disks to an intermediate stack 4. GTH(m, k – 1) use the k –1 available stacks to move the m largest disks to destination stack 5. GTH(n – m, k) use all k stacks to move the n-m smallest disks to destination stack end Tk(n)=2n–1 if n 1, then reverse the ordering of the top n cards on the deck and iterate.
Example: 42153  51243  34215  24315  42315  13245.
Is this game guaranteed to eventually terminate? Prove your answer.
b) Collatz Conjecture [1973]: Does the loop below terminate on every input?
Algorithm Puzzle(n) Pre-Condition: n is integer
while n > 1 do
if niseven then nn/2
end-while
return “done” end
else n  3n + 1
34

12. Induction puzzles:
The King’s wise men: The King called the three wisest men in the country to his court to decide who would become his new advisor. He placed a hat on each of their heads, such that each wise man could see all of the other hats, but none of them could see their own. Each hat was either white or blue. The king gave his word to the wise men that at least one of them was wearing a blue hat – in other words, there could be one, two, or three blue hats, but not zero. The king also announced that the contest would be fair to all three men. The wise men were also forbidden to speak to each other. The king declared that whichever man stood up first and announced the color of his own hat would become his new advisor. The wise men sat for a very long time before one stood up and correctly announced the answer. What did he say, and how did he work it out?
Queen Josephine’s Kingdom: In Josephine’s Kingdom every woman has to take a logic exam before being allowed to marry. Every marrying woman knows about the fidelity of every man in the Kingdom except for her own husband, and etiquette demands that no woman should tell another about the fidelity of her husband. Also, a gunshot fired in any house in the Kingdom will be heard in any other house. Queen Josephine announced that unfaithful men had been discovered in the Kingdom, and that any woman knowing her husband to be unfaithful was required to shoot him at midnight following the day after she discovered his infidelity. How did the wives manage this?
35

13. Rational numbers and infinite binary trees:
A rational number in reduced form is a fraction r/s where s  0, and r and s are relatively prime integers, i.e., their greatest common divisor is 1.
[We will study Euclid’s GCD algorithm in Lecture Slide 4.]
One way to enumerate all non-negative reduced rational numbers is by the Calkin-Wilf sequence. Consider the infinite binary tree (with no root) as follows. 0/1 appears at every node on the left shoulder of the tree. In general, left and right children of a node r/s are, respectively, r/(r+s) and (r+s)/s. The figure on the next page shows a portion of this tree.
a) Show that every rational number that appears in this tree is in reduced form. [Use induction down the tree and the fact that gcd(r,s) = gcd(r, r+s) = gcd(s, r+s).]
b) Show that every non-negative reduced rational number r/s appears in this tree. [Use induction on r+s or the principle of minimality.]
c) Show that every level of the tree gives you the same left-to-right sequence, called the Calkin-Wilf sequence, of non-negative rational numbers starting with 0/1.
d) Show that the successor of the rational number x in the Calkin-Wilf sequence is
s(x)  1 . 2x  x  1
[Compare x and its successor with their lowest common ancestor.]
e) Show that the Calkin-Wilf sequence generated by “x  s(x)” starting with x = 0/1, i.e., 0/11/11/22/11/33/22/33/11/44/33/5… contains every non-negative reduced rational number exactly once.
[Use induction on “r+s” or the principle of minimality.]
f) What is the (n+1)st number in the sequence? [Write n in binary. Descend on the tree path from a 0/1 node: with each 0-bit descend to left-child, with each 1-bit descend to right-child.]
36

0 1
…
0 1
…
1 1
…
112 121
121323 213231
1 3 2 3 1 43 53 52 2 5 3 4 32314 5341
14352534 43525341
…
…
37

14. The pigeon-hole principle: if p pigeons are placed in h pigeon-holes, where p > h, then at least one of the pigeon-holes contains more than one pigeon.
More generally, consider any mapping f: P  H, where P and H are finite sets.
Then there exists an hH such that |f -1(h)| > |P|/|H| . Use this principle to prove the following claims:
a) Consider the 2n numbers 1,2,3, …, 2n, and take any n+1 of them. Then there are two among these n+1 that are relatively prime. [Consider the mapping f(a) = a/2 .]
b) Consider the 2n numbers 1,2,3, …, 2n, and take any n+1 of them. Then there are two among these n+1 such that one divides the other. [Consider the mapping f(a) = b, where b is the largest odd divisor of a.]
c) In any sequence a1 , a2 , … , an of n not necessarily distinct integers there is a contiguous subsequence ai+1 , ai+2 , … , aj
whose sum ai+1 + ai+2 +  + aj is a multiple of n.
[Consider the mapping f(j) = (a1 + a2 +  + aj) mod n.]
d) In any sequence a0 , a1 , … , amn of mn+1 distinct real numbers
there exists an increasing subsequence
ai0 aj1 >…>ajn (j0

Related Posts