« lecture 5 | Main | Lecture 6 »
May 15, 2006
Homework 6
Homework #7: Due Wed May 17 (More intense)
7.10 (write down how you became convinced)
7.12 (be sure that your proof of the correct big-O bound is solid)
7.14
7.15
7.23
Posted by tonglaga at May 15, 2006 04:15 PM
Comments
Question 7.14 asks us to come up with a new merge algorithm "without using an auxillary array", yet it later says "you hae to sort the whole array T[1..n] using only a fixed amount of ADDITIONAL storage."
So, if we ARE allowed to use a fixed amount of additional storage, how is that any different than using an auxillary array? As far as I can tell the normal merge algorithm uses two fixed-sized auxillary arrays.
Posted by: brockj ![[TypeKey Profile Page]](http://vv.cs.byu.edu/cs312-spring2006/nav-commenters.gif)
at May 16, 2006 11:31 PM
The difference is that the size of the array used by normal merge sort depends on n, but the fixed-size additional storage does not depend on n.
Posted by: tonga at May 17, 2006 10:05 AM
Post a comment
Thanks for signing in, . Now you can comment. (sign out)
(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)