×
Get Full Access to NYU - COM 122 - Study Guide - Final
Get Full Access to NYU - COM 122 - Study Guide - Final

×

NYU / OTHER / Computer Science 122 / nyu computer science

# nyu computer science Description

##### Description: Covers The Whole Semester
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

143

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

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