Differences

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

Link to this comparison view

cs-312:hw7 [2014/12/31 22:57] (current)
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)
  
cs-312/hw7.txt ยท Last modified: 2014/12/31 22:57 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0