×
Log in to StudySoup
Get Full Access to NYU - COM 122 - Study Guide - Final
Join StudySoup for FREE
Get Full Access to NYU - COM 122 - Study Guide - Final

Already have an account? Login here
×
Reset your password

NYU / OTHER / Computer Science 122 / nyu computer science

nyu computer science

nyu computer science

Description

School: New York University
Department: OTHER
Course: Design and Analysis of Algorithms
Professor: Lisa hellerstein
Term: Spring 2017
Tags:
Cost: 50
Name: Study Guide for Final
Description: Covers The Whole Semester
Uploaded: 05/04/2017
92 Pages 166 Views 1 Unlocks
Reviews


Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Lecture 1/26/17 Prof. Lisa Hellerstein Sections B and D Prof Aronov’s Section M-W 10:30-11:50am Office Hours: Tuesday and Thursday 4-5pm Lisa.hellerstein@nyu.edu 2 Midterms and a Final Final grade in course 15% HW 25% each Midterms 35% Final Algorithm Step by step procedure to solve problems.  Algorithms can’t: • They can’t run forever • Can’t be right only some of the time History of Algorithms: Al Khwarizmi in the 9th Century invented some algorithms such as: • Basic methods for +,-,/,*, sqrt , digits of  pi. Numerical Algorithms Fibonacci: 0, 1, 1, 2, 3, 5 �!, �!, �!, �!, �!, �! 0 �� � = 0 �! = 1 �� � = 1 �!!! + �!!! �� � ≥ 2 As n grows �!!! �!→ � = 1 + 5 2 �! ≈ 2!.!"#! How many n-bit binary strings are there that do not have two consecutive ones? Number of bits n Number of strings of length n without 2  consecutive ones 1 2


How many n-bit binary strings are there that do not have two consecutive ones?



If you want to learn more check out c) What is the range of this function?

Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 2 3 3 5 4 8 … … n �!!!

n=1 0 1 n=2 00 01 10 11 n=3 000 001 010 011 100 101 110 111

�! �! �! �! �! �! �! 2!.!"#! 0 1 1 2 3 5

Let � > 2 Suppose the number of n-bits without two consecutive ones is �!!! for i=1,2,…n-1.  Show that the number of n bit strings without two consecutive ones is �!!!. Base case For i=1         i=2 n- bit string Last bit Consider the n bit string. Last bit is either 0 or 1. Case 1: last bit is 0. 0 Last bitCould be any string of length n-1 without 2 consecutive ones. � !!! !! = �!!! Case 2: Last bit is 1. Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 No 2  consecutive  ones, so the  second to last one must be 0. � !!! !! = �! 0       1 Last bitTotal number of strings of length n without 2 consecutive ones is : �! + �!!! = �!!! To compute �! (nth Fibonacci number): Function fib1(n): If n=0: return 0 If n=1: return 1 Return fib1(n-1) + fib1(n-2); 1. Is it correct? Yes 2. How much time does it take as a function of n? 3. Can we do better? Yes Let T(n) be the number of steps if run fib1(n) �! 1 �� � = 0 2 �� � = 1 = � � − 1 (����� ��� ����) + � � − 2 (������ ��� ����) + 3(��������� �����) �� � > 1 0 �� � = 0 �! = 1 �� � = 1 �!!! + �!!! �� � > 1 �� � � > �! ≈ 2!.!"#! To compute �! using fib1 takes more than 8 steps. 2!.!"#! ≈ 1.6 ! �!"" fib1(200) to approx.  1.6 !""����� takes  2!" ������� → �� 40 �������� ����� ��� ������ Function fib2(n) If n=0: return o Create an array f[0…n] F[0]=0, f[1]=1 For i=2…n: Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17         F[i]=f[i-1]+f[i-2] Return f[n] Memoization- (recalling previous calculations instead of recalculated ). If �! � �� �ℎ� ������ �� ����� ����� �� ���2, Then �! � = � = �(�) Lecture- 1/26/17 Binary addition

32s 16s 8s 4s 2s 1s +

1 1 0 1 1

0 1 1 1 0

1 0 1 0 0 1


How much time does it take as a function of n?



We also discuss several other topics like beneceptive

Adding 2 n-bit binary numbers     �!�!�! … �! + �!�! … … �! ���� … … ��!���   n+1 bits (at most) It takes � � ���� If you “charge” for every bit operation In the “bit-model” where we charge for every bit operation, fib2(n) would take  about n-1 time, but it depends on how long the bits are. �! ≈ 2!.!"#!  Representation of numbers in binary 1 bit 0 to 1 2 bits 0 to 3 3 bits 0 to 7 4 bits 0 to 15 N bits 0 to 2! − 1

From this we can show that, to represent a number N in binary, takes  log! � + 1 bits �! ����� ≈ log! 2!.!"#! ���� (ignore ceiling and the +1) Rule log! �! = � So log! 2!.!"#! = 0.694nShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 In fib2(n) the numbers involved in adding � � − 1 + � � − 2 each are �(�) bits  (max of approx. 0.694n) Time to do each addition? � � − 1 + � � − 2 ����� � � ���� ������� �ℎ� ��� ������� �������� ℎ��� �����ℎ �� ���� 0.694� IN BIT MODEL In fibs(n) we do n-1 additions each taking time: �(�) Total time of all additions: �(�!) Run time of fib2(n) is �(�!) We often need to distinguish between a number and its binary representation. 5    101! We  will often use N to denote the number and n to denote the number of bits in  binary representation of N. N=5 n=3 � = log! � + 1 n is much smaller than N if N is big. Ex: � = 2!"" log! � + 1 ≈ log! �=log! 2!"" = 200 big-Oh   (asymptotic notation) big-Omega theta Big O ��� �: �! → �!         �: �! → �! � = � � , �� �ℎ��� �� � �������� � > 0 ���ℎ �ℎ�� � � ≤ �� � ��� ��� � ∈ �! Equivalently, there exists c>0 so that  � � � �≤ � ��� ��� � ∈ �! Big Omega Ω � = � � ����� � = �(�) � = � � ����� � = � � ��� � = �(�)Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Rules: 1. Multiplicative constants can be omitted. Ex: 3�! = �(�!) 2. �! ��������� �! �� � > �. Ex: �! = � �! (� �� ��� ����� ������) 3. In a polynomial, you can ignore the lower order terms. 3�! + 4�! + 17� = �(�!) 4. Any polynomial dominates any log or log raised to a constant power. Ex:  �! ��������� (log �)! , (log �)! = � �! , ��� ���� ����� Facts about log! � 1. It’s the power of 2 to which you raise the number 2 to get N. Ex: 2!"#$ = � 2. Repeated doubling.  Ex: Start with 1, and double:  

2 4 8 16 32 64 128 Number  of time  doubled 1 2 3 4 5 6 7


What time of day done?



If you want to learn more check out rerunning a program with the same data produces

log! � is the number of times I have to double to get a number that is ≥ N 3. Repeated Halving. Number of times you have to halve N to get ≤ 1 is   log! � 4. Number of bits in binary representation of N is  log!(� + 1) which is  approve log! � Multiplication of 2 n-bit binary numbers:

8s 4s 2s 1s *

1 1 0 1

1 0 1 1

1 1 0 1

1 1 0 1 0

0 0 0 0 0 0

1 1 0 1 0 0 0

1 0 0 0 1 1 1 1

Modify procedure For addition of 2 n-bit binary number, Add first 2 numbers (rows) Add third to result Add fourth to result And so on until you reach n Total of n-1 additions Each addition involves two numbers (first is either row 1 or result and second row  ≤ 2� − 1 ����) Row1 + Row2: When adding n bits and n+1 bits the most the result could be is n+2 bitsShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Result of Row 1&2+ Row 3: You add a result of n+2 bits row 3 of n+2 bits to get at  most n+3 bits. If you keep doing this, the final result is 2n bits at most. It takes � � time to add 2-n bit numbers And to add two numbers each of 2n-1 bits also takes �(�) So total time to multiply two n-bit numbers using our procedure is �(��) Lecture- 1/31/17 Al Khwarizmi- another way to multiply (in decimal) Ex: Take 13*11 To multiply 2 decimal numbers, you write them next to each other Repeat: Divide 1st number by 2 and round down result   Double the second number Until first number is 1 The cross off all rows where 1st is even Add numbers in column 2 That’s your answer Y X 11 13 5 26 2 52 1 104

143

We also discuss several other topics like is anthrax prokaryote or eukaryote

This relies on recurrence � ∗ � = 2� − �2 �� � �� ���� � + 2 � ∗ �2 �� � �� ��� Pseudocode for binary multiplication Function multiply (x,y) Input: Two n-bit ints x and y,  �, � ≥ 0 Output: Their product If � = 0: ������ 0 � = �������� �,�2�2 = ���ℎ� − �ℎ��� �� � �� ����: ������ 2 ∗ � (���� �ℎ���)Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 else: return x+2Z  ����� � � Number of recursive calls: n Each taking time �(�) TOTAL TIME: �(��) Division Given x and y in binary (�, � ≥ 0, � ≠ 0) Find quotient q and remainder r where � = �� + � and 0 ≤ � < � � ÷ � ��: � �� ���� � = 18 � = 4 18 ÷ 4 Split into 9 and 9 9 ÷ 4 �! = 2 �! = 1 9 ÷ 4 �! = 2 �! = 1 � = 4 = 2�! � = 2 = 2�! �������� ������ (�, �) Input: 2 n-bit numbers, x and y,  �, � ≥ 0, � ≠ 0 Output: quotient and remainder If x=0: return (q,r)=(0,0) �!, �! = ������ !! , �   (right shift) � = 2�! � = 2�′ if x is odd: r=r+1 if � ≥ �: � = � − �, � = � + 1 return (q,r) Number of calls is nShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Time per call is �(�) (because is right shifted n times) Total time �(��) Our algorithm for binary division takes time � �! n is length (#bits) of x and of y Modular Arithmetic (clock arithmetic) Ex: 17 mod 3 = 2 Say x and y are “ congruent mod N” if they differ by a multiple N, we write � ≡ � ��� � �� � ������� � − � X is congruent to y, mod N For positive and negative numbers Ex: −1 ≡ 11 ��� 12 Because 12 divides (-1-11)=-12 In practice −3 ��� � Convert to  � − 3 ��� � � − 3 ≡ −3 ��� � �� � > 0 Ex: −3 ��� 13 = 9 Substitution Rules If � ≡ �! ��� �          13 ≡ 1 ��� 12    � ≡ �! ��� �          17 ≡ 5 ��� 12 then � + � ≡ �! + �! ��� �         13 + 17 (��� 12) �� ≡ �!�! ��� �                       1 + 5 ��� 12 = 6 ��� 12 Watch TV 25 episodes    each takes 3 hours Start at midnight What time of day done?   (AM + PM) 75 ��� 24 = 25 ��� 24 ∗ 3 ��� 24 = 3 ��� 24 = 3 �ℎ�� �� 2!"# ��� 31 2!"# = 2!∗!" = 2!!"= 32!" 32 32 … . . 32 − �� ����� ��� 31 = 1 ∗ 1 ∗ 1 ∗ 1 … 1 ��� 31 = 1Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 2 n-bit numbers represent two numbers between 0….2! − 1 ← ��� Let N=2! − 1 n=4, N=16  Ex: 1110+1000=10110 mod 16=22 mod 16 If x and y are both between 0 and N-1, To add x and y mod N Compute x + y If result ≥ N Subtract off N Addition mod N Biggest each number could be is N-1 ADDING 2 binary numbers, both between 0 and N takes time � ������ �� ���� �� ��������� ��� ������ = �(��� �) 2/2/17- Lecture Add 2 n-bit numbers mod N where N is an n-bit number Lets do it as a function of n Add the numbers (x and y) together to get an n+1-bit number.  We then compare it to N. If the result (n+1-bit number) is greater than N, then we  subtract N from the result and we get a new result, n bits which is the final answer. Otherwise if the result ≥ N, then the result is the final answer. Nothing gets much bigger than n+1 bits It takes O(n) time as a function of n-number bits Take N Write it in binary. Let n be the number of bits. � = log (� + 1) Suppose I have 0 ≤ �, � < � Write x and y in binary Number of bits in x and y (worst case) ≈ log (�) 1 ��� 5 x=1 N=5   (101 in binary) Write N in binary, takesShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 log (� + 1) = 3 n=3 in this case. X=1. (001 in binary) Time to add x+y(mod N) is O(n) as a function of n. Expressed as a function of N, time is O(log N). log! � = log!" � log!" 2 = � as a function of n ����� � ∗ log!" � Computing x+y modulo N Where 0 ≤ �, � < � Represent x,y,N in bits (x,y,N each have length  log (� + 1) ) Takes time �(��� �) Modular Multiplication Compute x*y modulo N Where 0 ≤ �, � < � represent x,y,N in binary (x,y,N each have length  log (� + 1) ) ex:      N=5  101             x=2        010             y=3 011 (all have  log (� + 1) �����ℎ) To compute x*y modulo N Multiply x * y Reduce modulo N which I can do by computing ������ ÷ � and reporting the  remainder Ex: 010 + 011 = 110 (2+3=6) Compute 6-5 [using binary division algorithm] Remainder of 1 Answer 2+3 modulo 5 =1 Running time: Let n be the number of bits of binary representation of N (also of x and y)Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 � = log (� + 1) Multiply x*y takes time O(�!)  as a function of n Result has at most 2n bits Dividing result (at most 2n bits) by N (n bits) takes time O(�!) as a function of n. Total time to compute x*y modulo N [ 0 ≤ �, � < �]  Takes time �(�!) as a function of n, Which is �(log! �) as a function of N Summary-time, mod N Modular addition: �(log �) Modular Multiplication: �(log! �) as a function of N. Compute �! ��� � 1. Naïve way to compute: Compute � ∗ � ∗ � ∗ � ∗ � ∗ … ∗ � (�������� �, ��� � �����) � − 1 ��������������� Reduce result modulo N 2. Less naïve: Use substitution rule: � ∗ � ������ � ≡ � ������ � ∗ � ������ � ��� � Calculate x*x Reduce mod N Multiply result by x Reduce Mod N Multiply result by x, etc. until all x’s multiplied together. Ex:  5! ��� 6 5 ∗ 5 ∗ 5 ∗ 5 ��� 6 5 ∗ 5 = 25 reduce modulo 6: 1 1 ∗ 5 = 5 reduce mod 6: 5 5 ∗ 5 reduce mod  6: 1 4. Even better:Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Use repeated squaring Ex: 32!" ��� 7 3! ≡ 3 ��� 7 3! ≡ 2 ��� 7 3! ≡ 4 ��� 7 3! ≡ 2 ��� 7 3!" ≡ 4 ��� 7 3!" ≡ 2 ��� 7 What about 3!" ������ 7? Write 29 in binary: 11101=16+8+4+1 3!" = 3!"!!!!!! = 3!" 3! 3! 3! = 4 ∗ 2 ∗ 4 ∗ 3 Multiply two terms together and then mod 7 and then multiply by the next term  and so on. The result is 5. Or recursive algorithm for modular exponentiation (does essentially same thing) Function  Modexp (x,y,N) �����: � − ��� �������� �, �, � ������: �! ��� � �� � = 0: ������ 1 � = ������ �,�2 , � (���ℎ� �ℎ���) �� � �� ���� ���� ��� �� � �� 0 ������ �! ��� � �� � �� ��� (���� ��� �� � �� 1) ������ �! ∗ � ��� � Runtime:             n recursive calls:             each takes time: �(�!) Total time �(�!) Computing GCD (Greatest common divisor) ���(140, 308) 140 = � ∗ � ∗ 5 ∗ � 308 = � ∗ � ∗ � ∗ 11 ��� �� 28 ������!� �������ℎ� �������� ������(�, �) �����: ��� ���� �, � ���ℎ � ≥ � ≥ 0 ������: ��� �, �Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 �� � = 0: ������ � ������ ������(�, � ��� �) ������ (50,30) ������ 30,20 ������ (20, 10) ������ 10, 10 ������ 10,0 GCD is 10 Extended-Euclid Fact: if d=GCD(a,b) Then there exists integers x and y such that  � = �� + �� Extended-Euclid computed GCD d and ints x,y such that d=ax+by Recursive algorithm in the textbook OR do this: Ex: To compute GCD(25, 11) Compute 25 mod 11 Bolded numbers are (a,b) �� = 2 ∗ �� + 3 �� = 3 ∗ � + 2 � = 1 ∗ � + 1 � = 2 ∗ � + 0 02/07/17- Lecture Euclid’s Algorithm Function Euclid(a,b) Input: two ints a,b with � ≥ � ≥ 0 (a, b are both n-bit numbers) Output: GCD(a,b) If b=0: return a Return Euclid (b, a mod b) (Euclid’s Rule) Correctness relies on lemma: If �, � ≥ 0 and � ≥ � Then GCD(a,b)=GCD(b,a) Running Time of Euclid’s Algorithm: Number of recursive calls: �(log �) Time per recursive call: �(�!) Need to compute a mod b in each recursive call Time to compute a mod b: �(�!)Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 ������ �, � → ������ �, � ��� � → ������ (� ��� �, … ) Within 2 recursive calls, first argument is reduced from a to a mod b Claim: Since � ≥ �, a mod b ≤ !! Case 1: � ≥ !! , you will have ≤ !!��������� ���� 2: � < !!then a mod b ≤ � − 1 Since � < !!→ � − � < !! − 1 By the claim, this means that within 2 recursive calls, the first argument is reduced  by at least a half. So: If I run Euclid(a,b), what is the max number of recursive calls: At most:  2 log � + 1 → �(log �) What is n? ������ �� ���� �� ������ �������������� �� �, �, � What is variable a, as a function of n? �(2!) Because a is a n-bit number so � ≤ 2! − 1 Therefore the number of recursive calls of Euclid’s algorithm as a function of n Is � log! 2! → �(�) To Summarize: Running Time of Euclid’s Algorithm: Number of recursive calls: �(��� �) → �(�) Time per recursive call: �(��) Total run time of Euclid’s algorithm: �(��) Extended Euclid: Computes GCD(a,b) AND integers (not necessarily positive) x and y such that  ��� �, � = �� + �� Ext-Euclid(a,b) Input: Two ints a and b, � ≥ � ≥ 0, a and b not both 0, where a and b are n-bits long.  Output: Integers (x,y,d) where � = ��� �, � , � = �� + �� If � = 0: ������ 1,0, � �!, �!, � = ��� − ������ �, � ��� � return (�!, �! − !! �!, �) I will show you a bottom up way to compute x,y,d. Since that’s correct, can see (with some thought) that the recursive algorithm is  correct.Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Ex: run of Ext Euclid (exE)          A    b       a     b   q   r 1. exE(25,11)  25=11*2+3 2. exE(11,3)      11=3*3+2 3. exE(3,2)           3=2*1+1 4. exE(2,1)           2=1*2+0 5. exE(1,0)           1=0*0+1 base case b=0, return a We want ints x and y so that  25� + 11� = 1 (��� 25,11 ) Multiplicative inverses mod N Def: x is the multiplicative inverse of a, modulo N if ax≡1 mod N Note: If GCD(a, N)=1, then extEuclid returns x and y such that  �� + �� = 1 → �� = 1 − �� → �� ≡1 mod N So, if GCD (a,N)=1, then running extE(a,N) Give: returns x,y,d Where x is a multiplicative inverse of a, modulo N If finish running ExtE(25,11) Get (4, -9, 1) 25*4 + 11*-9=1 So 4 is a multiplicative inverse of 25, modulo 11. Fact: a has a multiplicative inverse, modulo N, iff GCD(a,N)=1 Modular Division When working modulo N, we say that !! exists iff GCD(s, N) =1 If � ÷ � ������ �ℎ�� ��� ��� ������� �� �� ���� �(�!) using Euclids algorithm. It is defined to be � ∗ � ��� � where x is a multiplicative inverse of s mod N. 2/14/17- Lecture Primality Testing I give you an n-bit number and ask: Is it prime? (1101)! (13)!" An n-bit number for ex:Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 110110010100100101 The max size for the n-bit number is: 2! − 1 If we checked all numbers up to !! ∗ [� − ��� ������] In worst case, we’d check !!!! !numbers→ �(2!) And if we’re cleverer and only check up to the sqrt of the number 2! − 1 = � 2!! Rabin’s Primality Testing Alg: Input: n-bit number Output: “prime” if the number is prime. “not prime” with high probability if the number is not prime (composite) or “prime” with very small probability Fermat’s Little Theorem (1640) If p is prime, then for every integer a where 0 < � < � �!!! ≡ 1 ��� � Ex:  p=13  is prime Take: a=2  so by FLT 2!" ≡ 1 ��� 13 This suggests a way of testing primality: Given number N Choose a where 0 < � < � Compute �!!!��� � If �!!! ��� � ≠ 1 then we know that N is not prime. Suppose �!!! ��� � = 1, Then don’t know whether N is prime or not. Fermat’s Test (faulty) To test if N is prime, We pick an a, where 0 < � < � Then we ask is �!!! ��� � = 1? If the answer is No, then we can say that N is not prime If the answer is Yes, then N may or may not be prime (we don’t know) If answer is no, we say that N failed the Fermat Test.Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Idea: Choose “a” at random from numbers 1, 2,…., N-1 (Almost true) If N is a composite number, then for at least !!of the choices of a between 1 and N-1,  �!!!(��� �) ≠ 1 If my almost true statement was true, then the version of the Fermat test that you  choose “a” randomly has the following properties: If N is prime Then test outputs “Yes” which is correct If N is not prime then, With ����������� ≥ 50%, test outputs No (which is correct) And with probability<50%, outputs “yes” (Wrong) Assume: K>0 is a constant integer Function primality2(N) Input: Positive integer N Output: Yes or No For i=1 to k Choose random int between 1 and N-1 Call that integer a; For i=1 to N If �!!!(��� �) ≠ 1 Return No Return Yes Assume N is composite ! ! good “a”  (�!!! ��� � ≠ 1 ���� � �� ���������) 1 2 ��� (�!!! ��� � = 1 ���!� ���� � �� ���������) If pick k number of “a”s, what’s probability all bad? Probability that all “a”s are bad (if N composite) is ≤ !!!= !!! By taking example k=100, then the probability that Primality2 outputs the wrong  answer when N is composite is  ! !!"" This all relied on my “almost true” statement: If N is composite, then for at least half the “a”s between 0 and N-1, �!!! ��� � ≠ 1 It’s not true. It’s true for almost all composite numbersShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 There are nasty numbers called Carmichael numbers which are composite but don’t  have this property. Very rare. Rabin’s algorithm is almost same as our Primality2 But it has extra steps to handle Carmichael numbers. We will pretend Carmichael numbers don’t exist. Running time of Primality2. [k is constant, ex: k=100] Input: number N Assume it is n bits Express runtime as a function of n. 11011001001111000111 We do following k times: Choose random a, � < � < � − � Compute ��!� ��� � → ������� �������������� �(��) (how long do these two steps take?) If N is all 1s (changing to n-bit number) Generating single random “a” takes O(n) [like generating n random bits] (assuming constant time to generate 1 random bit) So primality2 takes time �(��) How do you generate a random n-bit prime number? Ex: n=4 4- bit primes: 2, 3, 5, 7, 11, 13 bin: dec: 0000 0 . . . . . . 1111 15 Idea: Repeat Generate a Random n-bit number Use primality2 to test if it is prime. If primality2 outputs yes, return the number.Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 “Lagrange’s” Prime Number Theorem: Let � � �� �ℎ� ������ �� ������ ≤ � Then � � ≈ ! !" ! ∗ �  or more precisely, lim!→∞! ! !" ! ∗! = 1 ! Fraction of numbers between 1 and N that is prime is ≈ ! !" ! ≈ !.!! of base formula) Change of base formula: !"#! ! ≈ !.!! !"#! ! (by the change  !.!! ! (where n is the number of bits needed to represent N). Lagrange’s Theorem tells us that the fraction of n-bit numbers that are prime is  ≈ !.!! ! �ℎ�� �� > !! To generate random n-bit prime Repeat Generate random n-bit number Test if prime If yes, return it Else continue  If I give coin, flip until get head H T, T, H T, H Expect to do 2 tosses Flip unfair coin Probability of heads is 1/5, and probability of tails is 4/5 How many flips do you expect to get heads? 5 Flips In general, if Probability of Heads is P, expect to do 1/P flips. Success: Randomly generated number is prime Probability of success P≈ !.!! ! So number of trials (iterations of repeat loop) we expect to do is  � ≈ 1 1 1.44 � < �Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Cryptography Basic Problem: ����� − − − − − −−→ ��� Msg is binary, � ���� → � Eve is trying to listen onto the message Alice encrypts x E(x)  (encryption of x) Another binary string ����� − − − − − −−→ ���  e(x) Bob decrypts e(x)  Compute d(e(x)=x How to encrypt? One-Time Pad Alice + Bob meet in private location [Eve can’t see] Generate Random n-bit string Z=10111010000101101  Eve ����� − − − − − −−→ ��� has z has z Alice sends  E(x)=bitwise XOR of x and z Ex: X= 11010 Z= 11100 E(x)= 00110 Public Key Crypto Alice + Bob don’t share any secret info. RSA Exploit that some things “easy” to compute Modular exp, GCD, primality testing.Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 �(�!) but factoring is hard to compute (we believe) Messages will be numbers Mod N (a number between 0 and N-1) Based on property: Let p and q be primes, and let N=p*q. Let “e” be a number such that  GCD(e, (p-1)(q-1)) is 1 Let d be the inverse of e mod (p-1)(q-1) Then 1. The mapping is a bijection onto the numbers {0,1,…N-1} � → �!��� � 2. For every x in {0,1,…N-1} �! ! ≡ � ��� � RSA Works as follows: Bob publishes (N,e) [Public keys] To send message x to Bob (� ∈ {0,1, … � − 1}) Alice encrypts x by computing �!��� � Bob computes �! ��� � ! ��� � Result is x Where do N and e come from? Where does d come from? Answer: Before publishing his public keys, Bob generates them: Generates 2 random primes. P and q Sets N=p*q Chooses e that is relatively (GCD of 1) prime to (p-1)(q-1) Computes multiplicative inverse of e [mod(p-1)(q-1)] using Ext. Euclid That is d.Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Bob publishes (N,e) He doesn’t publish p,q (or d) Bob’s private keys are p and q Example: N=55 5*11 (p*q) (p-1)(q-1)=40 Bob chooses e=3 (relatively prime to 40) Bob uses extEuc to compute multiplicative inverse of e=3 mod 40 Its d=27 (confirm 273 ≡ 1(��� 40) Suppose A wants to send X=9 She computes 9!��� 55 = 14 To decrypt, Bob computes 14!"��� 55 Answer: Before publishing his public keys, Bob generates them:  Generates 2 random primes p and q Sets N=p*q 02/21/17- Lecture Divide and Conquer Search through a sorted array Search for a key K in A. A[1…..n] K=32 Binary Search If array is empty return “Not found” Compare k to middle element of array.  If k=middle element, done. If k<middle element, recurse on left half of arrayShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 If k>middle element, recurse on right half of array Running time of Binary Search: Assume that the array has size 2! for some constant k and we always recurse on exactly  half the array. � = �/2 16, 8, 4, 2, 1 Let T(n) be the worst case run time on array size of n � � = 1 ∗ ��2 + �(1) � � = ������ �� ��������� ����� ∗ ���� �� ����� �� ��������� ���� + ���� ��� ����� ���� �� ���� ���� �����. � 1 = �(1) i.e. � � = 1 ∗ � !!+ � ∗ 1 where c is the constant from the big-oh notation Solve recurrence Locally, time C per recursive call � →�2→�4→ ⋯ ���� �� ����� → ����� ��� �������� ���� ����� �� ℎ��� → ���� ���� ��������� �� ℎ��� There are about ���! � + 1 levels in this progression. Time per calls on each level is C. Total time: � ∗ (���! � + 1) So binary search takes time �(log � ) in the unit cost model. Back to bit model  Multiplication of integers Multiply 2 n-bit ints. Standard school approach takes �(�!) Lets be faster!  Use divide and conquer!Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Consider x* y  1101 x * 1001 y __________ �! = 11 = (3 �� �������) �! = 01 = (1 �� �������) �! = 10 = (2 �� �������) �! = 01 = (1 �� �������) � = �! ∗ 2!! + �! � = �! ∗ 2!! + �! � ∗ � = �! ∗ 2!! + �! �! ∗ 2!! + �! = 2!�!�! + 2!!�!�! + 2!!�!�! + �!�! Recursive Multiplication Algorithm Recursively Compute �!�!, �!�!, �!�!, �!�! 4 recursive calls, each multiplying 2 − !!��� ������� Then do left shifts (� �� !!�����) and 3 additions Run time in bit model? Let T(n) be the time to multiply 2 n-bits numbers � � = 4 ∗ ��2 + � � � � = ������ �� ��������� ����� ∗ �����ℎ �� ������� ����� ���������� + ���� ��� ����� �ℎ������ ���� ��� �������� � � = 4 ∗ ��2 + �� n n n n n Cn 2Cn=4*C*(n/2) 4Cn=16*C*(n/4)Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Local time per recursive call (per node) is Cn Time spent locally on each level Base case: � 1 = � Time at level 0 Cn

1 2cn

2 4cn

3 8cn

….

i 2!��

We also discuss several other topics like sdsu mis

Total time:  !"#! ! � � = 2! ∗ �� !!! = �� + 2�� + 4�� + 8�� … . +2!"#! ! ∗ �� = �� 1 + 2 + 4 + 8 + 26 + 32 … . +� = ��(� +�2 +�4 + ⋯ + 1) � 2 +�4 + ⋯ + 1 = � − 1 = �� 2� − 1 = �(�!) Assuming that n is a power of 2. Couldn’t use ceilings of floors in recurrence Now be smarter! � ∗ � = 2!�!�! + 2!!�!�! + 2!!�!�! + �!�! = 2!�!�! + 2!! �!�! + �!�! + �!�! Note: �!�! + �!�! = (�! + �!)( �! + �!) − �!�!−�!�! = 2!�!�! + 2!!( �! + �! �! + �! − �!�!−�!�!) + �!�! need 3 recurrence calls (to multiply) (!! − ��� �������) �! ∗ �! �! + �! �! + �! (!!+ 1 ��� �������, ������� !!)  �! ∗ �! Recurrence Algorithm Add �! + �! Call it �!  Add �! + �! Call it �! Recursively computeShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 �! ∗ �!, �! ∗ �!, �! ∗ �! Then do shifts and subtractions and additions to get result. Now  � � = 3 ∗ ��3 + �� � � = ������ �� ��������� ����� ∗ ����ℎ� �� ������� + ����� ���� Time spent locally per recursive call (per node) Time at level 0 Cn

1 3��2

2 9��4

….

….

i 3!��2!

!"#! ! 3!��2! = 32!∗ �� = 32!∗ �� = �� 1 +32 +32!+ ⋯ +32!"#! ! = �� ∗ 3 2 !"#! !− 1 3 2 − 1 !!! Lowest level is still level ���! � Which is � � ∗ !!!"#! ! �! + �! + �! … . +�! = �!!! − 1 � − 1 2/23/17-Lecture MergeSort  9 7 2 1 5 4

Don't forget about the age old question of hyperpnic

 

9 7 2

1 5 4

Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Divide Array in Half �(1) Recursively sort left half � !! Recursively sort right half � !! Merge two halves so whole array is sorted  � � − ������ �� ����������� ���� �� ����� ≤ � Base case: Array has size 1, leave alone ���� ����: 9, 7, 2 → 2, 7, 9 ���ℎ� ����: 1,5,4 → 1,4,5 Merge  Takes 2 sorted lists  Combines them into a single sorted list ����� ������, ��� ����: 1, 2, 4, 5, 7, 9 [Unit cost Model] Running Time � � = 2 ∗ ��2 + �(�) � � = ������ �� ��������� ����� ∗ ���� �� ��������� ���� + ����� ���� Size of Input Level

n (1 of them) 0

n/2 (2 of them) 1

n/4 (4 of them) 2

….

� 2! (� �� �ℎ��) i

� � = 2��2 + �� Number of nodes at level i:2! Local work at node of level i: � ∗ !!! Size of input at node of level i: !!! Total local work at level i: (number of nodes at level i)(local work at node of level i)=Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 2! ∗��2! = �� Do Cn work at every level. Total time is: �� + �� + �� …. log � + 1 levels =�� log � + 1 = �(� log � ) Runtime of Mergesort is: � � log � The Master Theorem  If � � = � ∗ � !!+ � �! ��� ���� ��������� � > 0, � > 1, ��� � ≥ 0 �ℎ�� � �! �� � > log! � � � = � �! log � �� � = log! � � �!"#! ! �� � < log! � Weird Mergesort (Splits into 1/3 of array and 2/3 of array) � � = ��3 + �2�3 + �(�) ex:  � � = � !!+ �(1)  � 1 = �(�!) a=1, b=2, d=0 log! � = log! 1 = 0 Since d=log! �,  � � = � �! log � = �(log �) Mergesort Recurrence � � = 2��2 + �(�) a=2, b=2, d=1 log! � = log! 2 = 1 log! � = � Since d=log! �,  � � = � �! log � = �(� log �)Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Fast Integer Multiplication had recurrence (for runtime in bit model) � � = 3��2 + �(�) a=3, b=2, d=1 log! � = log! 3 ≈ 1.59 Since d<log! �,  � � = � �!"#! ! = �(�!.!") [Closest Pair is Incorrect] Closest Pair In 1 dimension Suppose I give you a sorted array of n numbers representing points on the number line. 2, 5, 8, 9, 14, 20 Divide Array in half Find Closest pair of points on the left side Distance �! Find Closest pair of points on the right side Distance �! Compare �! to �!. Whichever is smaller, return associated points. Doesn’t work:  Need to also compare distances of last point on left to first point on right. Now Consider Closest pair problem in 2 dimensions  Points given to you in an array, sorted by x-coordinate: 3,5 , 6,1 , 15,3 , (21,7) Easy Algorithm: Compute distance between all pairs of points.  Output pair that are closest. How many pairs (n points total) � 2 = �! � − 2 ! 2!= � � − 1 2 = �(�!) Divide and Conquer approach Divide the points by a vertical line so half are on the left and half are on the right. (Same  as dividing input argument into left and right, since sorted by x-coordinate). Do need to calculate the equation of the vertical line  Ex: x=10 because 6<10<15 3,5 , 6,1 , | 15,3 , (21,7)Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Recursively find the closest pair of points on the left. Let their distance be �! Recursively find the closest pair of points on the right. Let their distance be �! Idea: Let d=min (�!, �!)  If there is a point on left and a point on the right whose distance is <d, then they must  be located within the following strip: Dividing line  L RStrip is part  between L and  02/28/17- Lecture Closest Pair 2d d d R lines.  Ignore points  outside of the  strip Not necessary to check all pairs of points that straddle the dividing line and are in the  strip. Why? d d d Consider a point p in the  strip. Don’t need to  check all points in strip  on other side of line.  Only need to check the  points that could be at distance less than d from  this point. No 2 points on right can  be at distance ≤ � from  each other. Any point at distance < d  from point p would be in  this box. Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Because all points on right side are distance d or greater from each other, there are at  most 6 points on right side of line, in the box. (In fact, there are at most 6 points in the  while box other than p). Because of this, we can modify the algorithm as follows: Start: Assumed points sorted by x coordinate (otherwise sort them first) Assume no 2 point have same x coordinate or same y coordinate Divide point set in half into Left and Right O(1) Recursively find closes pair on right � �� Let �! �� �ℎ� �������� Recursively find closes pair on left � �� Let �! �� �ℎ� �������� Let d=min{�!, �!} Eliminate points at distance >d from dividing line. �(�) Sort remaining points by y coordinate � � ���� �� ��������� Calculate min distance of these. Call it �!. If �! < �, Return �! with associative pair of points  Else return d with its associative pair of points Compare each point in that list to 6 points that came after it. [This will compare all pairs  of points that could be in the same “box”] Ex: Input: [(3,7), (5,1), (17,9)|| (23,4), (32,6), (64,9)] Recurse Left Recurse Right  Compute Middle element of Array (ex: x=20) Run Time: � � = 2� !!+ � � log �  � � ���� � �� � ������ Can get runtime down to � � log � by returning lists of points sorted by y coordinate  in each recursive call and merging (like in merge sort) [Closest Pair is Incorrect- See Powerpoint for correct explanation]Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Closest Pair Algorithm: Divide point set into L and R halves Recurse L Recurse R Let d be min of 2 distances returned. Eliminate points at distance >d from dividing line. Sort by y coordinate For each point in sorted list, Compute its distance to next 7 points in list. Return smallest distance associated pair AND list of points sorted by y coordinate (result of merge). � � = ��� + � � → �(� ��� �)Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Selection  Input: Unsorted array S of numbers, int k>0. Output: kth smallest element of S.  Ex: k=1 ask for min. Assume all numbers in array are distinct Ex: [2, 36, 5, 21, 8, 13, 11, 20, 7, 4, 1] Find Min: Can do in O(n) [Select for k=1] Find Max: Can do in O(n) [Select for k=n, when n is size of array] Find median: Select problem for � = !! Can do by sorting and then returning middle entry. Time � � log � [with mergesort] Randomize Algorithm to solve Select problem. Expected running time is �(�) Idea: Shorter array than previous  S contains: 2,5,8,9,11,12,7,10,3 Choose Random element in S: 8( call this v) Partition into elements: <8  >8  =8 �! = 5,2,3,7 (4 ��������) �! = 8 (1 �������) �! = 11,19,12,10 (4 ��������) Suppose k=2 Because � ≤ �! Recursive do select on �! with k=2 Suppose k=5  Return v [Because �! < � ≤ �! + �! ] Suppose k=7← ������� � > �! + �! Recurse on �! with k=2 (i.e. � − �! − �!Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 If I’m lucky, v splits the elements so �! ≈ �! That is, v is the median value in the array. Suppose I’m always lucky, on every recursive call. Runtime if lucky � � = 1��2 + � � ������� ���ℎ ������� �� � ��� ������ �� �� ���� �� �! �� �! � +�2 +�4 +�5 + ⋯ � � (�� �����) Unlucky (ex: v=12, i.e v is min or max) �! = 5,2,3,7, 11,19,10 (7 ��������) �! = 12(1 �������) �! = ����� Recursive call is an array of size n-1 Runtime: � � = 1� � − 1 + � � The solution: � + � − 1 + � − 2 + ⋯ �(��) But what is expected time? Call v good if v is in the 25th through 75th percentile of elements in array S. If choose random element in array, it has 50 percent change of being good. If pick a good v, recurse on set if size at most ¾ of the size of S. 3/2/17- Lecture If K< �!  Recurse on �! with same k If �! < � ≤ �! + �!  Return V If K> �! + �!  Recurse on �! with new k equal to  k=k- �! − �! If chosen v is always medianShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17  � � ≤ � !!+ � �  So � � = � � If Chosen v is always max,  � � = � � − 1 + � �  Solving: = � ! !!! ! = � �! (��� �� ������� ���� 1 �� � ��:! !!! ! Repeat Randomly choose element v in S Divide S into �!, �!, �!  Check whether v is good (by looking at size of �!, �!) until get good v  Proceed with v But what is the expected run time? [we’re choosing v randomly!] Call v good if it is between the 25th and 75th percentiles. The probability that a random is good is 50% Expected number of times need to execute repeat loop to get good v: 2 Expected time to run repeat loop:2 ∗ �(�) which is �(�) Let �(�) denote the expected time taken by the modified algorithm on a set of size n. � � ≤ �34 � (������� � �� ����) + � � (�������� ���� �� ����� ����) Using fact that for 2 random variables X and Y � � + � = � � + �[�] Solve:  � � = � !!� + � � (using Master Method)  � � = �� !!+ � �! , � = 1, � = 1, � = !! Solution: �(�) Expected time of modified algorithm is O(n) Expected time of original algorithm is also O(n)Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Sometimes called Quick Select.  It’s like Randomized Quick Sort: To sort an array S of size n Randomly choose element v in S Form sets �!, �!, �! by comparing all elements to v. Recursively sort �! Recursively sort �! Return Sorted elements of �!, �! , ������ �������� �! Since good v ensures that �! ≤ !!� and �! ≤ !!� �! + �! ≤ � Can show that Expected Runtime of randomized Quicksort is �(� log �) If v is median every time Runtime: � � = 2��2 + � � Solution: O(n log n) If v is max/min every time Runtime: � � = � �! Recall: Fast Integer Multiplication Fast Matrix Multiplication (Unit Cost model) Matrix Multi:Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Result Matric C is mxn Entry i,j is the dot product (inner product) of row I of A and column j of B Dot Product: Multiply corresponding entries and add results Ex: Dot product of [3,2,4] and would be 3*1+2*0+4*2 1 0 2 If A is nxn B is nxn Result of A*B is matrix C which is nxn C has ��! entries How long to compute each entry (unit cost model). N multiplications and then n-1 additions: Time: � � So to compute C Compute �! entries Each take time �(�) to compute Total time to compute C is �(�!) 3/7/17- Lecture Matrix Mult. [x][y]=[z] (each matrix is nxn) Time to multiply in usual way �(�!) unit cost model.  X * Y nxn nxn � = ���� � = ���� � 2 ∗�2 �������� Straightforward to show � ∗ � = �� + �� �� + �� �� + �� �� + �� Suggest Recursive approach Recursively compute AE, BG, AF, BH, CE, DG, CF, DHShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Ex: After compute AE, BG then compute AE+BG (AE and BG have !! !������� �� �ℎ�� �������� ����� !!! )  A E = ! ! ∗ !! !! ∗ !! !! ∗ !! How many entries in the result? !!! Add corresponding entries 3 6 4 1 +6921 = 3 + 6 6 + 9 4 + 2 1 + 1 = 91562 Time to multiply nxn matrices using this recursive approach � � = 8� !!+ �(�!) Base case: � 1 = �(1) � � = 8 �������� ����� �� ������� ��, ��, ��, ��� + 4 Solution: � � = �(�!) Strassen �! = � � − � ∗�!4 ���������, ��:�!4 ��� �� + �� �! = � + � � �! = � + � � �! = �(� − �) �! = (� + �)(� + �) �! = (� − �)(� + �) �! = � − � � + � �� = �! + �! − �! + �! �! + �! �! + �! �! + �! − �! − �! Suggest recursive algorithm � � = 7��2 + �(�!)(�� ������� ��: � − � ��� �! + �! ��� Before  � � = 8� !!+ �(�!) a=8, b=2, d=2 log! � = 3 So d<log! �Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 So �(�!) Now  7��2 + �(�!) a=7, b=2, d=2 log! � = 2.81 � �!.!" Fast Fourier Transform FFT Multiply 2 polynomials 1 + 5� + 7�! ∗ 3 + 2� + 4�! = 3 + 2� + 4�! + 15� + 10�! + 20�! + 21�! + 14�! + 28�! = 3 + 17� + 35�! + 34�! + 28�! Abstractly � � = �! + �!� + �!�! + ⋯ + �!�! � � = �! + �!� + �!�! + ⋯ + �!�! The let � � = � � ∗ � � � � = �! + �!� + ⋯ + �!!�!! where: !!!!  �! = �!�! + �!�!!! + ⋯ + �!�! = �!�!!! for k=1, ….,2d for i>d in product �!�!!! take �! = 0 and if k-i>d take �! = 0 Suppose A(x) and B(x) are degree d polynomials. Suppose want to compute � � = � � ∗ � � ��� ���� ���������� � I want to know � 17 = � 17 ∗ � 17 Straightforward way to do it: Multiply � � ∗ �(�) in standard way To get C(x) Then commute C(17) Standard way to multiply 2 degrees of polynomials takes time [unit cost model] �(�!) How to do better?  Alternative representation of a polynomial Ex: Degree 1 polynomialShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17  � � = �! + �!� Linear function  Equation of a line 2 points determine a line. If you have two points of the line, then you can figure out �! and �!. � 1 = 3, � 5 = 6 �! + �! ∗ 1 = 3 �! + �! ∗ 5 = 6  Solve for �! ��� �! d+1 points determine a degree d polynomial. [if d=1 this says 2 points determine a line] Ex: for a degree 3 polynomial, 4 points determine the polynomial � � = �! + �!� + �!�! + �!�! Given (1,3) and (0,1), the equation of the line is � � = 2� + 1 These two points can uniquely represent this line. Representation by points->Value representation of A(x) Representation by equation of line-> Coefficient representation of A(x) Converting from value representation of A(x) to the coefficient representation of x is  called interpolation. Pretend we already have fast way to do interpolation. Suppose want to compute: � � = � � ∗ � � for some particular x ex: C(17) Suppose we have value representation of A(x) and B(x) i.e. Value of A(x) on d+1 values for x: �!, �!, … , �! (d+1 values) d+1 points  (�!, �(�!))  (�!, �(�!))  .  .  .  (�!, �(�!)) Ex: A(x)=2x+1 coefficient representationShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 A value rep of A(x) (0,1) (1,3) d=1 �! = 0 �! = 1 Similarly for B(x) Value of B(x) at x=�!, … , �! For distinct values  �!, … , �! How do we get a value representation for C(x) From the value representation of A(x) and B(x)? First: No need to use different values of x for A(x) and B(x)! 3/21/17- Lecture Multiply 2 polynomials 1 + 5� + 7�! 3 + 2� + 4�! ��� �� �� ����? Coefficient Representation Can Represent a polynomial of degree by giving its value on d+1 points x. Ex: Linear function is a polynomial of degree 1. Ex: F(x)=3x+2 Coefficient representation Value representation X F(x) 1 5 3 11

For degree d polynomials: Can convert between a value representation of a polynomial and the coefficient  representation. Converting from value representation to coefficient representation is called  “Interpolation” Ex: Interpolate the degree 1 polynomial represented in this value representation X F(x) 2 5 6 3

5 = �! + 2�!Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 3 = �! + 6�! Solve for �! & �! � � = �! + �!� There is a way to interpolate degree d polynomials for all � ≥ 1. We won’t cover this.  Treat it as a magic algorithm (black box). Multiplying 2 polynomials using (extended) value representation is easy. Suppose A(x) and B(x) are polynomials of degree d. � � = �! + �!� + �!�! … + �!�! � � = �! + �!� + �!�! … + �!�! Suppose they are given in an (extended) value representation that specifies their value on  2d+1 points. �!, �!, … , �!! (Extended means more than d+1 points) Ex: d=1, A(x) and B(x) are linear functions X A(x) 4 5 0 1 5 6

x B(x) 4 9 0 1 5 11

�! = 4 �! = 0 �! = 5 Value Representation of A(x)*B(x) x A(x)*B(x) 4 5*9=45 0 1*1=1 5 11*6=66

This is a value representation of A(x)*B(x) A(x) and B(x) have degree 1Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 When you multiply A(x)*B(x), The resulting function will be of degree 2 Idea: To quickly multiply 2 polynomials of degree d, A(x) and B(x) (Given in coefficient  representations) Ex:  � � = 3 + 2� + 5�! � � = 7 − 4� + 6�! d=2 1. Choose 2d+1 points (�!, … , �!!) 2. Evaluate A(x) on �!, … , �!! to get an extended value representation of A(x) Evaluate B(x) on �!, … , �!! to get an extended value representation of B(x) 3. Generate a value representation of A(x)*B(x) by computing  � �! ∗ � �! ��� � = 0 �� 2� − 1 using previously computed � �! & � �! values. 4. Interpolate to produce coefficient representation of A(x)*B(x) How long does it take to multiply 2 degree d polynomials (given in coefficient  representation) using ordinary multiplication approach �! + �!� + �!�! … + �!�! ∗ �! + �!� + �!�! … + �!�! Takes �(�!) We want to beat this! Evaluating A(x) on 2d+1 points takes time O(d) per point, for a total of �(�!). Same for B(x) In order to beat �(�!) need to speed up step 2:  Evaluating A(x) on 2d+1 points and B(x) To speed up step 2, we will be very careful about which points you choose in step 1. Ex: � � = 2 + 5� + 3�! + 8�! + 4�! + �! d=5, want to evaluate at 2d+1=11 points. Split A(g) into even and odd powers of x: Even part: 2 + 3�! + 4�! Odd Part: 5� + 8�! + �! = �(5 + 8�! + �!) Both the parts have only even powers Define 2 new polynomials using coefficients of those 2 polynomials: �! � = 2 + 3� + 4�! e for even �! � = 5 + 8� + 1�! o is for odd Notice: � � = �! �! + ��!(�!) � 2 = �! 4 + 2�!(4) � −2 = �! 4 − 2�!(4)Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Idea to save a little time For the 11 points, use ± pairs. Ex: �! = 1, �! = 2, �! = 7, �! = 52, �! = 21, �!" = 3  �! = −1, �! = −2, �! = −7, �! = −52, �! = −21  To calculate A(x) on 11 points. Calculate �! �! ��� �! �! �� �ℎ� �������� ������  �! �! ��� �! �! have smaller degree. Ex: �! 1! , �! 2! , �! 7! Do the same for �! 1! … Then calculate  �! �! + �! �!  AND �! �! − �! �! On all positive �!!� Gives � �! ��� �(−�!) High Level Idea: To evaluate A(x) [degree d] on n points, that we get to choose, Choose them as !! ± �����. ±�!, ±�!, ±�!, … , ±�!! Recursively calculate  �! �!! and �! �!! ��� � = 1 … !! (Calculating value of polynomial of degree d/2) Then return  �! �!! + �!�! �!! for i=1….n/2 �! �!! − �!�! �!! Suppose (just for simple thought experiment), n=d seems like runtime will be � � = 2 ��2 + �(�) � � = �� ������� �! ��� �! �� !! ������ + calculate __+x*___ and ____-x*____ for  each �! BUT in recursive call don’t have ± ����� Ex: X �! ±1 1 ±2 4 ±7 49

Imaginary numbers to the rescue!Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 If need to evaluate A(x) on 4 numbers,  Choose: ±1, ±� ±1 ! = −1 ±1 ! = 1 Recursive call, evaluate �! and �! on 1 ��� − 1 ± ����! Evaluate A(x) on 8 numbers? Choose: ±1, ±�, ± !!+ !!� , ± !! − !!� Recurse on   1, -1, i, -i Recurse on  1, -1 Take n to be a power of 2. When choose n points, choose nth “roots of unity” The n solutions to �! = 1 3/28/17- Lecture Graph Set of vertices and a set of edges between selected pairs of vertices. Undirected Graphs Directed graphs (Digraphs) Edge is a subset containing 2 vertices (if graph is undirected) Edge is an ordered pair of 2 vertices (if graph is directed) A B D C V={A,B,C,D} E={{A,B}, {B, C}Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Directed Graph  V={A, B, C, D} E= {(A,B), (B,A), (A,C) ,(D,C)} A B D C Is D reachable from A? NO Explore (G,A) will visit A, B, C but not D We’ll assume no “self loops” Given choice choose first in alphabetical order A DFS 1 2 B C 3 D 4 E 5 6F G Procedure Explore(G, V) Input: G=(V,E) graph; � ∈ � (start vertex)  (visited (v)= false for all “unvisited” vertices in G)  (visited(v)= true for all visited vertices in G) Note: Pseudocode works for directed and undirected graphs We’ll write (u, v) for edge in both cases.  [For undirected, this should really be {u, v}] Output: Visited(u) set to true for all nodes u “reachable” fro v. Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 U reachable from v:  Undirected Graph: ∃ Path from v to u. Directed Graph: ∃ directed path from V to U (directed edges are like one-way  streets) Visited (v)= true. For each (v, u) ∈ E  If not visited (u):  Explore(G, U). Prove: Explore(G, V) (starting with all vertices NOT visited yet) will visit all vertices  reachable from V. Proof by contradiction. Suppose u is reachable from v, but Explore(G, V) never visits u. Consider the  path from v to u. Consider the first unvisited vertex or path from v to u. (Might be u or might be earlier  vertex on the path). Consider the vertex that preceded it. u z w …………….. u visited First unvisited on  path(Maybe w=u, maybe not). So Z was visited, u wasn’t. Since Z was visited, there was a recursive call. Explore (G, Z)  it would have checked if w was visited, and it would have called Explore(G, W) and then  visited w. CONTRADICTION. So u was visited. DFS- Depth First Search (Visit ALL vertices in graph) 1. for all � ∈ �: visited(v)=false 2. for all � ∈ �: if not visited(v): Explore(G, V) Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 A B D C DFS(G) Run Explore (G, A) Visits A, B, C Run Explore (G, D) Skips B, C Visits D Digraph Say vertex b is adjacent to vertex a if (a,b) is an edge. [there is an edge from a to  b]. Also say b is a “neighbor” of a. a b Undirected graph Say vertex b is adjacent to a (is a neighbor of a) if {a,b} is an edge a bAnalyze the runtime of DFS. Outer DFS loop- Step 2 of DFS. (for all � ∈ �, �� ��� ������ � : �������(�, �)) Time spent just in this outer loop, and in step 1 of DFS: �(|�|) We will be sloppy and write O(v) instead of O(|v|) How much time do we spend in all the recursive calls to Explore? Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Explore(G, V)  Visited(v)=true (during entire DFS, executed V times. O(1) per execution.  Total: O(v) time running this line during DFS)  For all (v, u)∈ �: If not visited(u): Explore(G, U) Want to determine total time spent running for loop of Explore during DFS. Depends on how graph G was given as input to the algorithm. We will assume G given in an adjacency list representation A B D C Ex: A B C D B C A C Neighbor lists,  adjacency lists, list of  all neighbors of the  vertexTime spent in for loop explore over lifetime of DFS: �(� + �) �(���� ��� ���� �� ����ℎ��� �� ���ℎ ������ + ���� ����� ���������� �ℎ� ����ℎ��� ����� �� ��� ��������) Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Total time of DFS (assuming adjacency list of representation of G) is � � + � � + �(� + �) Total O(V+E) 3/30/17- Lecture This Tues- Began DFs Thursday- Application of DFS Wednesday Makeup- Began Shortest Path, Review BFS Next Tuesday- Continue Shortest Path Undirected Graph  3 Connected Components The Connected Component of an undirected graph is a set of vertices in the graph where  there is a path from every vertex to every other vertex (and this wouldn’t be true if you  added any other vertices to it). DFS can be used to count the number of Connected Components in an undirected graph. DFS on undirected graph Tree edge of the DFS: Say (v,u) is a tree edge if  Explore(G, V) calls Explore (G,U) “Walk” along that edgeShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 A T B B T BC T T D E Edge (v,u) is a back edge of the DFS, if Explore(G,V) did not call Explore (G,U)  (because u was already visited). Directed Graph: 1. Tree Edges [Same definition] 2. Back Edges 3. Cross Edges Undirected (v,u) is a back edge if v is an ancestor of u in the DFS tree. (The tree formed by the DFS  containing u and v edges are tree edges, root is start vertex. Directed Graph Back edge: (v,u) is a back edge of the DFS if it is an edge of the graph and v is an  ancestor of u (in the same tree). Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Forward Edge: Edge (v,u) is a forward edge if u is a descendant of v, but not its  child (in same DFS Tree). Cross edge is any edge that is not a back edge or a forward edge or a tree edge. G T B D T T C A DFS Forest A T C F CF T H C D B GH Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Start/Finish F C11/12 T 1/8 A 9/10 E 2/7 B F T T 3/4 5/6 C C D C (Root Vertices are bolded- there are 3 different trees here) Alphabetically Clock Tick every time enter a vertex for the first time (start i) Exit the vertex forever (finish it) Define  Pre(v) Start time of v Post(v) finish time of v Modify DFS so it assigns correct value to pre(v) and post(v) for every vertex v. Define another variable clock At start of DFS  Clock=0 Explore (G,V) Visited(v)=true Clock=clock+1; Pre(v)=clock; For all (v,u)∈ E If not visited (u):  Explore(G, U) Clock=clock+1; Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Post(v)=clock; Property For any nodes u and v, the intervals [pre(u), post(u)] and [pre(v), post(v)] are  either disjoint or one is contained within another. Ex: A= [1,8], D=[5,6] D is within A. While F=[11,12] and it is disjoint from them. Edge (w, z) W Z It is either a tree or forward edge: [ [ ] ] w z z w It is a back edge: [ [ ] ] z w w z It is a cross edge: [ ] [ ] w w z z A directed cycle is a directed path from a vertex back to itself. Ex: A B CShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Directed Acyclic Graph- A directed graph that has no directed cycles. Topological Sort of a DAG  Linearization of a DAG (number from 1 to V) It’s an ordering of the vertices so that every edge in the graph goes from lower numbered  vertex to a higher numbered one. To check whether a directed graph is acyclic (A DAG)? Do DFS. If DFS finds back-edge, then no a DAG. Else it IS a DAG.  Topological Sort If directed graph is a DAG: Run DFS Output vertices in descending order of post times. F C11/12 T 1/8 A 9/10 E 2/7 B F C 4/3/17- Makeup Session T T 3/4 5/6 C D C Find Shortest Paths in a Graph Length of a Path- is the number of edges in the path. Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Algorithm to: Compute the length of the shortest path from start vertex s to every vertex  in the graph. Breadth First Search Used on unweighted graphs. No “weights” on edges. Distance From vertex u to vertex v in an unweighted graph is the length of the shortest  path. (Measure in number of edges from u to v). (The number represent shortest number of edges to reach that point from the origin). Implementation of BFS (which uses a queue) has a running time of �(� + �). BFS vs. DFS BFS- Computes the distance from the start vertex to every vertex in the graph. Only visits  vertices reachable from the start vertex. DFS- It doesn’t compute distance. It discovers/visits all the vertices in the graph because  of the outer loop. Can also run BFS on a directed graph. For a weighted graph:Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Notation: L(u,v)=6 “L” refers to length For a weighted graph, the length of a path in the graph is the sum of the lengths of edges  in the path. Find length of path from � → � → �: From � → � = 1, ���� � → � = 4, �ℎ������� �ℎ� �����ℎ �� 5. Put a Predecessor node on the shortest path to this vertex:Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Shortest Path Tree has edge from pred of every vertex to that vertex. . From pred info can construct the shortest path from source to any desired vertex  (destination). Dijkstra’s Algorithm Idea behind Dijkstra’s : Find vertex closest to s. Then find the next closest vertex (Assume all edge lengths are greater than 0). Then find next closest  And next closest And so on At each stage: Know the k vertices closest to S AND their shortest path distances from S. (Call  these vertices the Known Region) (KR). Find k+1st closest vertex and its distance from s How to find the k+1st closest? K.R: Contains K closest vertices. The only vertices that could be the K+1st closest are the vertices that are outside K.R. and  adjacent to a vertex in K.R. Estimate of length of shortest path to vertex adjacent to a vertex in K.R. For each vertex u adjacent to a vertex v in the known region, we (over) estimated the  shortest path distance to u as min, over all vertices v in K.R., of dist(s,v) + l(v,u). If u not adjacent to v we treat l(v,u) as ∞. 4/4/17- Lecture Today • Answer 2 of the WHY questions from last lecture • Strongly Connected Components • Proceed with material after makeup lecture (Shortest Path). RecallShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 To determine whether a directed graph has a directed cycle. Run DFS and see if it finds a  back-edge. Why does this work? If the DFS finds a back-edge, clear it has a directed cycle. Back-edge forms cycle with tree edges. Now suppose graph has a directed cycle. WV Consider run of the DFS on the graph. Let w be the first vertex discovered in the cycle. Let v be the predecessor of w on the cycle. Consider edge (v,w) Know the pre and post time intervals for v and w are either disjoint or one is contained  within another. Either [ ] [ ] w w v v OR [ [ ] ] w v v w Explore (G,W) can’t finish before visiting v, before visiting v, since v is reachable from  w. Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 So [ ] [ ] not possible   w w v v So must be [ [ ] ] which means (v,w) is a back edge.  w v v w Edge(v,w) [ [ ] ] Tree/Forward Edge v w w v [ [ ] ] Back Edge w v v w [ ] [ ] Cross Edge w w v v Why does topological sort (linearization) sort algorithm work? Input: DAG (Directed Acyclic Graph) To do topological sort Run DFS Output vertices in decreasing order of post times Consider DAG G. Suppose run topological sort on it. Suppose for contradiction that the output is an invalid order. Ex: there is an edge (v,w) in graph, shortest time w was output before v. That means post(w)>post(v)→ ] ]  v w But that means DFS found a back-edge (v,w) is a back edge. But G was a DAG, so this is  impossible.  Contradiction. So algorithm must have outputted the vertices in a VALID order.Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Undirected graph Connected Components Ex: 4 Connected Components: For directed graphs, talk about strongly connected components. Def: A set of vertices is a strongly connected component of G if  1. There is a directed path from each vertex u in the set to every other vertex in the  set. Equivalently for every pair of vertices u,v in the subset, there is a directed  path from u to v and from v to u. 2. The set is “maximal” with respect to Property 1. That is, property 1 doesn’t hold  for any superset of the set. Ex: 2 Strongly Connected Components A CBG Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Algorithm for finding the SCC’s of a directed graph. Step 1: Form �!, the graph produced by reversing the directions of all the edges in G. Step 2: Run DFS on �! recording pre and post numbers Step 3: Run DFS on G, breaking ties in decreasing order of post times. (prefer higher post  time). While we do this, run the extra code used in computing CC’s of an undirected graph. Every DAG has at least 1 sink node (can’t leave). 4/6/17- Lecture Dijkstra’s Algorithm Computes shortest paths in a weighted graph, where weights are non-negative. Computes  shortest paths from a source vertex s. Works for both Directed or Undirected graphs. Idea behind Dijkstra’s Algorithm: At each stage, know length of shortest path from S to every other vertex in the K.R. For vertices outside KR, have estimate of length of the shortest path to that vertex.  Estimate is in the length of the shortest path to that vertex that uses only vertices in the  K.R. [All edges are between vertices in KR except for the last edge] K+1st closest vertex is the vertex outside the K.R. with the smallest estimate of the  shortest path length. Why? Suppose some other vertex was closer (both vertices are right outside the K.R starting from s) Vertex v with smallest estimate Vertex w (could this be the k+1st closest (closer to s than v even with a higher estimate?)) A path that only uses vertices in the K.R.→ No, because we’ve already considered paths  that only use vertices in the K.R. and among those paths, the shortest path to v was  shorter than the shortest path to w.Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 So the shortest path to w, if it’s closer to s than v, couldn’t be of this type. That means it  would have to go from s, through vertices (maybe none of them) in K.R., so some vertex  v’ outside KR and then later to w. But then, v’ would be closer to s than w, meaning w can’t be k+1st closest. So no way for a vertex w with higher estimate than v to be k+1st closest.  V is the k+1st closest. Also, length of shortest path to v from s is just the current estimate. Want to add v to KR and repeat. When add v to KR, have to update any affected estimates. Dijkstra(G,l,s) ______________ Input : G=(V,E) directed or undirected and edge lengths l(u,v) for each (u,v)∈ �,  l(u,v)≥0. Vertex s in V. Output: ∀ �������� �, ����ℎ���� ���� �, ���� � �� ��� �� �. �. �������� ���� � �� �. If unreachable, dist(u) is set to ∞. In pseudocode, we will use,  Priority Queue Data Structure  Every element has key(priority)  Supports operations: InsertShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Delete min Decrease key Make queue For all u∈ �.  Dist(u)=∞  Prev(u)=NIL Dist(s)=0 H=MakeQueue(V) While H not empty (H is unknown region vertices) u=deletemin(H) For all (u,v)∈ � //all neighbors v of that are outside KR If dist(v)>dist(u)+l(u,v) Dist(v)=dist(u)+l(u,v) Prev(v)=u Decreasekey (H,v) //Update key of v in PQ to new value of  dist(v). Runtime depends PQ implementation # Delete Mins: � # Decrease Keys: ≤ � Negative Edge Weights But no negative weight cycles Ex: S.P.=4-4-7+3=-4 4 3-4 -7 Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Bellman-Ford For all � ∈ �  Dist(v)=∞ For all i=1 to |�|  For all (u,v)∈ �  [if dist(v)>dist(u)+l(u,v)  dist(v)=dist(w)+l(u,v)] Easy algorithm that also works for graphs with negative with edges (no negative weight  cycles) 4/11/17- Lecture  3 A C 2 -3 S 6 4 1 B -1 2 D (C,D), (C,B), (A,C), (D,B), (B,D), (B,A), (S,B), (S,A) Node 0 1 2 3 4 S 0 0 0 0 0 A ∞ 2/S 2/S 2/S 2/S B ∞ 4/S 4/S 2/c 2/c C ∞ ∞ 5/A 5/A 5/A D ∞ ∞ 3/B 1/B 1/B

Negative Cycle Detection For each edge (u,v) ∈ �  �� ���� � > ���� � + �(�, �)  output “negative cycle” s U1 U2 U3 Uk TShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Good: (S,U1), (u1, u2), ….(uk-1, uk), (uk, t) Bad: (uk, t), (uk-1, uk),… (u1, u2), (S,U1) Linearize(topological sort) For U∈ � in topological order For each (u, v) ∈ �  Dist(v)>dist(u) + l(u,v):  Dist(v)=dist(u)+ l(u, v) Prev(v)=u Minimum Spinning Tree Given a graph G=(V,E) and edge weights W(e), find a connected  subgraph � = �, �! with �! ≤ � �ℎ��� !∈!! � � �� ��������� Kruskal’s Algorithm: Repeatedly choose the minimum weight edge that doesn’t produce  a cycle. Cut Property Let x be a subset of edges of a Minimum Spinning Tree T. Let s be a set of vertices such  that x has no edge between S and V-S. Let E be the edge with minimum weight between  S and V-S. � ∪ � �� � ������ �� ����� �� � ������� �������� ����. Kruskal’s Algorithm Correctness: At each step, choose edge E of minimum weight. E  connects 2 trees T1 and T2. Let s=7, E is min weight edge between S and V-SShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Prim’s Algorithm X=0 (egdes picked so far) S= �! (�������� �� ����) Repeat until S=V Pick minimum weight edge (u,v) ∈ � s.t. � ∈ � ��� � ∈ � − � Add (u,v) to X Add v to SShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 4/13/17- Lecture Exam Tuesday Room to be announced Covers material up through Dijkstra’s  but NOT running time of Dijkstra’s. Run times of Dijkstra’s and Prim’s Run time of Krustal’s Dijkstra’s uses a Priority Queue to implement the algorithm. When we call makequeue, the vertices that haven’t been visited are set in ∞ other than  the start vertex, which is set to zero. We then keep calling deletemin and update the vertex to be in the known region and give  it its new distance. Then we decreasekey, update vertices with their new shorter distances. Call Number of times executed Makequeue 1 Deletemin V Decrease Key ≤ � Insert V

Time per Operation for unsorted array implementation Delete Min �(�) Decrease Key � � �� ���� ���� ��� ����� Insert �(�) Total time of Dijkstra’s with current PQ implementation  � ∗ � � + � ∗ � � + � ∗ � � = �(�(� + �) Can we do better? One way to do better is by improving the speed of Decrease Key by using a second array. Store position of each vertex in the key array. Let’s modify key array also. List all vertices in order of their numberShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Put special “mark” if vertex is no longer in queue. Revised time for new PQ implementation using one array (Key of vertex i is stored in  vertex i): DeleteMin �(�) Decrease Key �(1) Insert �(1) (New) Time for Dijkstra’s  � ∗ � � + � ∗ � 1 + � ∗ � 1 = � �! + � Which is �(�!) Because � ≤ �! Or implementation PQ using Binary Heap (Min-Heap) Where key in node is always ≤ ���� �� ��� �ℎ������ 3 217 100 62Tree “shape” Every level of tree has max possible number of nodes except maybe the bottom  level, which has nodes filled in from left to right. Heap has size ≤ � Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Binary Min Heap Time per Op Delete Min �(log �) Decrease Key �(log �) Insert �(log �) Array implement of heap: Second array which gives position of every vertex in array implementation of heap. Time for Dijkstra’s with binary heap implementation of PQ �( � + � log �)) Compare to runtime of array implementation �(�!) Undirected Graphs Max number of edges is !! = ! !!! ! = �(�!) If number of edges is �(�!) then say graph is dense. Min number of edges in connected graph on V vertices V-1 If number of edges is �(�) say graph is sparse. For dense graphs, array implementation of PQ gives better bound for Dijkstra’s  �(�!) vs. � �! log � for heap. If graph is spares, head implementation is better � � log � vs. �(�!) for array. 4/20/17-Lecture Dijkstra’s with Binary Heap Implementation � � + � log � PQ: (Makequeue)  Insert  Decrease key  Delete min MST:  Prim’sShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17  Krustal’s Prim’s Choose start vertex Grow tree by choosing least weight edge that connects node outside tree to the tree. One tree at all times, grow it out. 562 A F 5 B 3 10 D 7 9 C E 234 Let A be start vertex Or- think of algorithm as adding a vertex to the tree at each step. A, B, C, D, F, E Always add vertex connected to tree by min possible weight edge (edge is added to tree). To implement this efficiently, with each vertex not yet in tree, keep value cost(v) [for  vertex v] which is min weight of an edge connecting that vertex to the tree. Ex: Middle of Prim’s 562 3 A F 5 3 B 10 D 7 9 C E 9234 Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 A, B, C, D in tree so far. At each step,, we choose the vertex not in the tree having minimum cost. Add it to tree.  Update costs of its neighbors not in tree. Can use essentially same code as Dijkstra’s.  Dist vs. cost Update of dist vs. of cost operation does different calculation. So, can also write Prim’s using PQ operations and implement PQ with binary heap to get  runtime of � � + � log � Often, people say runtime with binary heap of Prim’s is � � log � When run MST algorithm, we assume input graph is connected???? E≥ � − 1 Which means: V+E is �(�) Krustal’s Algorithm Sort edges in increasing order of weight For each edge in increasing weight order: Add it to tree if it doesn’t form cycle with previously added edges. Sorted Edges: DF, AB, BC, DE, BD, CE, AF 562 A F 5 B 3 10 D 7 9C E 234 In middle of Krustal’s,  Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 3 CC’s A, B, C [one tree CC] D, F [one tree CC] E [one tree CC] Continuing, add DE 2 CC’s A, B ,C D, F, E Union-Find data structure Operations: Makeset(x)- takes element x and makes set containing only x Find(x)- Takes element x and returns “name” of set containing x. Union(x,y)- Takes two elements x and y and combines the set containing x with  the set containing y To check whether an edge (v,w) will form a cycle with the edge’s chosen. So far, check  whether v and w are in the same CC [tree]. If so, (v,w) forms cycle, otherwise not. Proc Krustal(G,W) [G is weighted connected graph, G=(V,E). W is array containing weights of edges.  Forms MST of G] for all u∈ � makeset(u) X={} //contains edges in MST Sort edges of E by weight for all �, � ∈ � in increasing order of weight:  If Find(x)≠Find(v):  Add {u,v} to X  Union(u,v) Union-find data structure Union-by-rank Idea: Each set is represented by a tree. Elements in set are nodes of tree.Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Each node has pointer up to its parent. Ex: Suppose Q, S, T, R in same set. Might represent as: Q S R TName of set is the element at root of tree. This is set Q, since Q is at root. To do Find(T). Walk up pointers in starting at node T until get to root. Return element at root. To control height of trees formed, each tree will have associated with it a number, called  its rank. Rank will be equal to height of the tree.  Do unions based on rank. Inductive Definition: A single node is a tree of rank 0. Given 2 trees, one of rank �!and other of rank �!, We form a larger tree with them as follows: If �! > �! make root of Tree 2 point up to root of Tree 1 and say resulting tree has rank  �!. [�� �! > �!, �������������, ���� ���� �� �! ����� �� ���� �� �! ��� ���� �� ��������� ���� �� �!] Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 If �! = �!, ���� ��� ���� ����� �� ��ℎ��, ��� ��������� ���� ℎ�� ���� �! + 1 (�ℎ��ℎ ������ �! + 1) Ex:  Rank 0 Rank 0 Rank 0 Rank 0 Q R S T Union of Q and R R Q Rank 0 Rank 0 Rank 1 S T Now make union of  R Rank 1 Q Rank 0 With  Equals: Q S R Rank 1 SShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Unioned with T R Rank 1 Q S TIn Union Find Data Structure Form unions according to these rank rules. Proposition: Any 2 trees of rank k has at least 2! nodes Proof: By induction If tree has rank 0, has 1 node. 2! = 1 Suppose take union of two trees, one of rank �! ��� �ℎ� ������ �� ���� �! Assume inductively that first tree has ≥ 2!! �����, ������ ℎ�� ≥ 2!! �����. If �! = �!, union of two trees has rank �! + 1 (equals �! + 1) and it has ≥ 2!! + 2!! nodes. 2!! + 2!! = 2 ∗ 2!! = 2!!!! (since �! = �!)  So new tree has ≥ 2!!!! ����� ��� �ℎ�� �� 2!"#$ !" !"# !"## If �! > �!, union of trees has rank �!. It has at least 2!! + 2!! nodes, which is  >2!!��� 2!! �� 2!"#$ !" !"# !"##. This proves the proposition. Useful because if a tree (set) has n elements, rank k of tree  satisfies � ≥ 2! → � ≤ ���!� 4/25/17- Lecture Krustal’s Time With Union-Find data structure Main components of algorithm contributing to runtime Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 1. Sort Edges in increasing weight order �(� log �) with mergesort But, � ≤ !! = ! !!! So � = � �! ! So instead of � � log � , ��� ���� ����� � � log � [������� log �! = 2 log �] 2. Disjoint Data Set Operations

Times Executed Time per op MakeSet(v) V �(1) Find(v) 2E O(log v) Union(v, u) V-1 O(log v)

Union operation actually calls Find . Union(v,u) Executes Find(v)  Find(u)  To find names of sets containing v and u so it can union them (or discover that  v,u are in the same set). Tree of rank k has ≥ 2! ����� ???? in Krustal’s, max rank of a tree is log! � rank of tree is equal to its height ???? every Find operation takes �(log �) So Disjoint Data Set Operations take time : �(� ��� �) Total runtime of Krustal’s with our implementation of data structure (union by  rank)  �(� ��� �) Can speed up “average” (amortized) time per op over whole algorithm disjoint set  operations using a variant of union-by-rank, which also does “path compression” during  Find operations.  In the textbook, but we will SKIPShlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 Gives better runtime for krustal’s if input already has edges in sorted order (No Step 1). We will skip Huffman encoding  Satisfiability of Horn Formulas We covered Set Cover in HW. Dynamic Programming �! = �!!! + �!!! (Base Cases) Longest Increasing Subsequence Problem Given: Input sequence of numbers: �!, �!, … , �! Ex: 5,2,3,1,9,4,6 (�!, �!, �!, �!, �!, �!, �!) Find: Length of longest increasing subsequence of this sequence Subsequence of �!, �!, … , �! is sequence:  �!!, �!!, … , �!! When 1 ≤ �! < �! < ⋯ < �! ≤ � And say its increasing if �!! < �!! < �!! … < �!! Ex:  2,3,9 (�!, �!, �!) is an increasing subsequence of our example sequence  6,9 is not a subsequence  3,9,4 is a subsequence, but not increasing How to compute LLIS (length longest increasing subsequence): A bit differently than in the textbook Suppose little birdie tells you the length of the longest increasing subsequence whose last  element is  �! �! �! �!!!Shlomi Oved CS2413- Design and Analysis of Algorithms 2/21/17 and you want to know the length of the longest increase subsequence whose last element  is �! Let L[i]=LLIS whose last element is �! Ex: 5,2,3,1,9,4,6 (�!, �!, �!, �!, �!, �!, �!) (j=5) We want to find value of L(5) L(1)=1 L(2)=1 L(3)=2 L(4)=1 �!, �!, �!, … … … . , �!!!, �! � 1 , � 2 , � 3 , … �(� − 1) L(j)=max {L(i)+1}  0≤ � ≤ � − 1  such that �! > �! Initialize L(0)=0 PseudoCode for fill in Table L Let L[0….n] be array L[0]=0 Max=L[0] For j=1 to n: For i=0 to j-1 If �! < �! and L[i]>max  Max=L[i] End for Return max+1 �������: �(��)
Page Expired
5off
It looks like your free minutes have expired! Lucky for you we have all the content you need, just sign up here