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

Next revision | Previous revision | ||

cs-312:hw4 [2014/12/31 15:55] ringger created |
cs-312:hw4 [2015/01/16 13:15] (current) ringger [Questions 3-7] |
||
---|---|---|---|

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</math>. 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. |