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]
Khâwrázmî
• •
wrote two influential books:
Ál-maqhaléh fi hésab ál-jábr wál-moqhabéléh
An essay on arithmetic restoration & reduction
Kétab ál-jáma wál-táfreeqh bél hésab ál-Hindi
Book of addition & subtraction á la Hindu arithmetic
According to math historians the true origin of the word algorism: comes from a famous Persian author named ál-Khâwrázmî.
Latin translation of these books coined the words:
algorithm = algorizmi = ál-Khâwrázmî
algebra = ál-já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
Khâwrázmî
(780-850 A.D.)
A stamp issued September 6, 1983 in the Soviet Union, commemorating Khâwrázmî’s 1200th birthday.
Statue of Khâwrázmî
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 0S {0}S 1S {0,1}S 2S {0,1,2}S 3S {0,1,2,3}S 4S {0,1,2,3,4}S 5S {0,1,2,3,4,5}S 6S {0,1,2,3,4,5,6}S 7S {0,1,2,3,4,5,6,7}S 8S {0,1,2,3,4,5,6,7,8}S 9S : : : :
True 0S 0S 1S 1S 2S 2S 3S 3S 4S 4S 5S 5S 6S 6S 7S 7S 8S 8S 9S
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
AB
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. AB
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. AB
§……………….. 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. AB
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. AB
4. TH(n–1, C, B, A) end
recursion is invoked in pre-order
(1,A,C,B) (0,A,B,C) AC
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)
AB
(1,C,B,A)
(0,C,A,B) CB (0,A,B,C)
(0,B,C,A)
Non-empty leaves in pre-order (i.e., from left to right):
AC , AB , CB . 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
AB
2,3
1
2
1c
AC
3
1
2
3
2a
BC
3
1,2
4
2c
AB
3
1,2
5
3a
CA
1
3
2
6
3c
CB
1
2,3
7
4a
AB
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
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 nn/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 . 2x 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/11/11/22/11/33/22/33/11/44/33/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 hH 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