There are 6 problems for a total of 20 points. Most of them are easier than they look at first.
Please consider: The homework is really “worth” a lot more than 20 points because exams have similar problems. If you have not practiced with the homeworks, you’ll do worse on the exams. So, if you think these problems are not worth the time for the points, think again.
Please list the names of the other members of your peer group for this week and the number of extra credit points you think they deserve for their participation in group work on Tuesday and Thursday combined.
Using the truth-condition definition of big-O, prove that 3_n_2 + 9 = O(_n_2).
The definition is the one that starts with “f(n) = O(g(n)) iff …”. You will have to choose suitable c and n_0, plug them into the definition in “…”, and argue that the condition is met.
The 4 points are: (1) identification of _c and n_0 that work; (1) writing out the definition, and (2) demonstrating that it is satsified as _n grows beyond n_0 (not just for _n = _n_0).
Continuing in the style of Tuesday’s class exercise, fill in the table for these pairs of functions with “Yes” or “No” in each empty box. Then, for each row, justify your choice, preferably by showing mathematical relationships (e.g., transforming one expression into another, or into expressions that are more easily compared).
| f(n) | g(n) | O? | o? | Ω? | ω? | Θ? | |
|---|---|---|---|---|---|---|---|
| e. | 4n2 | 4lg n | |||||
| f. | 2lg n | lg2n | |||||
| g. | √n | nsin n |
For each of the four types of lists in the following table, what is the
asymptotic worst-case running time for predecessor and maximum?
Assume that k is the key, d the data associated with the key, and p a
position in the data structure. This version of the ADT is similar to the
book’s, but abstracts list elements x to positions (returned by search).
predecessor and maximum are with respect to ordering of keys in the set
under “<”, NOT ordering of the data structure. Sorted lists are sorted in
ascending order. This continues your in-class work, which you may want to
review for correctness first.
| Unsorted, Singly Linked (no tail pointer) | Sorted, Singly Linked (no tail ponter) | Unsorted, Doubly Linked with Sentinel and Tail pointer | Sorted, Doubly Linked with Sentinel and Tail pointer | |
|---|---|---|---|---|
| ... others done in class here ... | ||||
| predecessor(p) | ||||
| maximum() | ||||
In class you wrote a recursive procedure for traversal of a binary tree in O(n) time, printing out the keys of the nodes. Here you write two other tree traversal procedures. The first is a variation of what you wrote in class; the second is on a different kind of tree that you read about pages 248-249 and in my lecture notes and screencast.
(a) Write an O(n)-time non-recursive procedure that, given an n-node binary tree, prints out the key of each node of the tree in whatever order you wish. Assume that trees consist of vertices of class TreeNode with instance variables parent, left, right, and key. Your procedure takes a TreeNode as its argument (the root of the tree). Use a stack as an auxiliary data structure.
printBinaryTreeNodes(TreeNode root) {
(b) Write an O(n)-time procedure that, given an n-node rooted tree with arbitrary number of children using the left-child, right-sibling representation, prints out the key of each node of the tree in whatever order you wish. Assume that for economy of code we are re-using our TreeNode class. The instance variable left points to the left child as before, but now right points to the right sibling instead of the right child (which is no longer unique). Your procedure takes a TreeNode as its argument (the root of the tree). You may choose to use either the recursive or non-recursive approach.
printLCRSTreeNodes(TreeNode root) {
Although MergeSort runs in Θ(n lg n) worst-case time and InsertionSort runs in Θ(_n_2) worst-case time, the constant factors in insertion sort (including that fact that it can sort in-place) can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the MergeSort recursion tree by using InsertionSort within MergeSort when subproblems become sufficiently small.
Consider a modification to MergeSort in which n/k sublists of length k are sorted using InsertionSort and are then merged using the standard merging mechanism, where k is a value to be determined in this problem. In the first two parts of the problem, we get expressions for the contributions of InsertionSort and MergeSort to the total runtime as a function of the input size n and the cutoff point between the algorithms k.
(a - 1pt) Show that InsertionSort can sort the n/k sublists, each of length k, in Θ(nk) worst-case time. To do this:
(b - 3pts) Show that MergeSort can merge the n/k sublists of size k in Θ(n lg (n/k)) worst-case time. To do this:
Putting it together: The asymptotic runtime of the hybrid algorithm is the sum of the two expressions above: the cost to sort the n/k sublists of size k, and the cost to divide and merge them. You have just shown this to be
Θ(n__k + n lg (n/k))
In the second two parts of the question we explore what k can be.
(c - 2pts) The bigger we make k the bigger lists InsertionSort has to sort. At some point, its Θ(n_2) growth will overcome the advantage it has over MergeSort in lower constant overhead. How big can _k get before InsertionSort starts slowing things down? Derive a theoretical answer by proving the largest value of k for which the hybrid sort has the same Θ runtime as a standard Θ(n lg n) MergeSort. This will be an upper bound on k. To do this:
(d - 1pt) Now suppose we have implementations of InsertionSort and MergeSort. How should we choose the optimal value of k to use for these given implementations in practice?