to the beautiful and wonderful
world of algorithms!
Copyright By PowCoder代写 加微信 powcoder
STUDY MATERIAL:
• [CLRS] chapter 1 • Lecture Note 1
• Material covered in lecture slides are as self contained as possible
and may not necessarily follow the text book format.
Origin of the word
Algorithm = algorism (old English version)
= arithmetic process by Arabic numerals
= calculus by infinitesimals Euclid’s algorithm: greatest common divisor
“algorithm”
[Oxford English Dictionary] [Webster’s 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]
Euclid of Alexandria ( ~ 300 B.C.)
Euclid of 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
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
Computational Landscape
Design Methods:
Iteration & Recursion
pre/post condition, loop invariant Incremental
Divide-&-Conquer
Prune-&-Search
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 …
Mathematical Induction
In the field of algorithms induction abound.
The following are equivalent for any 𝑆 𝑁 = 0,1,2,3, … ∶ (1) 𝑆 = 𝑁.
(2) 𝑛𝑁 𝑛𝑆 .
(3) 𝑾𝒆𝒂𝒌𝑰𝒏𝒅𝒖𝒄𝒕𝒊𝒐𝒏: (𝑖) 𝐵𝑎𝑠𝑒 𝐶𝑎𝑠𝑒:
𝑖𝑖 𝐼𝑛𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑆𝑡𝑒𝑝:
(4) 𝑺𝒕𝒓𝒐𝒏𝒈𝑰𝒏𝒅𝒖𝒄𝒕𝒊𝒐𝒏:
𝑛𝑁– 0 𝑛 – 1𝑆 𝑛𝑆 .
𝑛𝑁 [ 0,1,2,…,𝑛–1 𝑆 𝑛𝑆]. [ 𝑁𝑜𝑡𝑒: “𝑛 = 0𝑁 [𝑆 0𝑆 ]” 𝑖𝑚𝑝𝑙𝑖𝑒𝑠 𝑡h𝑒 𝐵𝑎𝑠𝑒 𝑐𝑎𝑠𝑒 0𝑆 ].
(5) 𝑷𝒓𝒊𝒏𝒄𝒊𝒑𝒍𝒆𝒐𝒇𝑴𝒊𝒏𝒊𝒎𝒂𝒍𝒊𝒕𝒚:
𝒏𝒐𝒏-𝒆𝒙𝒊𝒔𝒕𝒆𝒏𝒄𝒆 𝒐𝒇 𝒔𝒎𝒂𝒍𝒍𝒆𝒔𝒕 𝒄𝒐𝒖𝒏𝒕𝒆𝒓-𝒆𝒙𝒂𝒎𝒑𝒍𝒆:
𝑛𝑁[ 0,1,2,…,𝑛–1 𝑆 𝑎𝑛𝑑 𝑛𝑆].
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
A warm up example
Practice yourself, for heaven’s sake, in little things; and hence proceed to greater.
– EPICTETUS (Discourses IV, i)
Towers of Hanoi [ 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.
Computational Model
Pre-Condition:
The time when the largest disk moves … think RECURSIVELY:
TH(n-1,A,C,B)
Pre-Condition:
The time when the largest disk moves … think RECURSIVELY:
TH(n-1,A,C,B)
TH(n,A,B,C)
The task remaining … think RECURSIVELY again:
TH(n-1,C,B,A)
Post-Condition:
TH: A recursive solution
Algorithm TH(n, A, B, C) begin
1. if n 0 then return
2. TH(n–1, A, C, B)
4. TH(n–1, C, B, A) end
PreCond&ALG PostCond
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 .
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
§……………….. 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
§ PostCond: AI, A = A’ , B = 1..n, B’, C = C’ , n 0
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)
4. TH(n–1, C, B, A)
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.
TH: Recursion Tree
Algorithm TH(n, A, B, C) 1. if n 0 then return 2. TH(n–1, A, C, B)
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)
(0,C,A,B) CB (0,A,B,C)
Non-empty leaves in pre-order (i.e., from left to right):
AC , AB , CB . 2n – 1 = 3 moves (n = 2).
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
If n is odd
If n is even
Iteration step
Algorithm TH(n, A, B, C)
1. if n 0 then return
2. TH(n–1, A, C, B)
4. TH(n–1, C, B, A)
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
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).
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
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)
4. TH(n–1, C, B, A)
The iterative solution:
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.
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)
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
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
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
return “done” end
else n 3n + 1
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?
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 Calki
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com