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

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