Differences

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

 cs-312:hw4 [2014/12/31 16:28]ringger cs-312:hw4 [2015/01/16 13:15] (current)ringger [Questions 3-7] Both sides previous 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 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 15: Line 15: === 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.