##### Differences

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

 — cs-312:hw7 [2014/12/31 15:57] (current)ringger created 2014/12/31 15:57 ringger created 2014/12/31 15:57 ringger created Line 1: Line 1: + = Homework Assignment #7 = + + == Objective == + + To learn how to solve recurrence relations for typical divide-and-conquer algorithms, including the use of the "​change of variable"​ technique. + + == Exercises == + + '''​Show all work.  i.e., justify your answers.'''​ + + === Questions 1 and 2 === + * Part III (Section 3.2): exercises 1 and 2 in the [http://​faculty.cs.byu.edu/​~ringger/​CS312/​readings/​recurrences-notes.pdf Recurrence Relations notes]. + + === Question 3 === + * Analyze the running time of 3-part Mergesort (like traditional mergesort but involves dividing the problem into thirds rather than into halves) using Recurrence Relations solution techniques. ​ You may conclude with the general solution, since you have no initial conditions, or you can choose your own initial conditions. ​ (Do not use the Master Theorem.) + + === Question 4 === + * Exercise 2.4 in the text book (use the Master Theorem where possible) 