##### Differences

This shows you the differences between two versions of the page.

 cs-312:hw4 [2014/12/31 15:55]ringger created cs-312:hw4 [2015/01/16 13:15] (current)ringger [Questions 3-7] 2015/01/16 13:15 ringger [Questions 3-7] 2015/01/16 13:15 ringger [Question 2] 2014/12/31 16:28 ringger 2014/12/31 15:55 ringger created Next revision Previous revision 2015/01/16 13:15 ringger [Questions 3-7] 2015/01/16 13:15 ringger [Question 2] 2014/12/31 16:28 ringger 2014/12/31 15:55 ringger created Line 11: Line 11: Problem 1.27 in the textbook. Problem 1.27 in the textbook. - Use the [http://​faculty.cs.byu.edu/​~ringger/​CS312/​readings/​ExtendedEuclidExample.pdf Extended Euclid algorithm] to find the secret key <​math>​d​.  Be sure to decrypt your message also to verify that everything is working. + Use the [http://​faculty.cs.byu.edu/​~ringger/​CS312/​readings/​ExtendedEuclidExample.pdf Extended Euclid algorithm] to find the secret key $d$.  Be sure to decrypt your message also to verify that everything is working. === Question 2=== === Question 2=== - In the textbook 2.1 (down to two-bit numbers; i.e., threshhold = 2) + In the textbook: exercise ​2.1 (Karatsuba divide and conquer multiplication). + * You may use the threshhold value of 2.  i.e., stop recursing when the arguments ​to multiple are both two-bit numbers. + * Tip: to make running the Karatsuba divide and conquer multiplication algorithm more straightforward, you may 0-pad (on the left) the function'​s arguments so that both arguments are always of even length. === Questions 3-7 === === Questions 3-7 === - Exercises 2.5(a-e) in the textbook: find asymptotic bounds using only the Master Theorem ​-- Big-O is sufficient. + Exercises 2.5(a-e) in the textbook: find asymptotic ​Big-O bounds using only the Master Theorem.