Policies


 If you feel a question is ambiguous, write on your exam sheet your interpretation of the question, and answer accordingly.
 Please label/number your pages clearly and staple them in order when handing in.
Midterm Exam (60pts) (solutions)
(3pts) : Prove or disprove: if `f in O(g(n))` and `g in O(f(n))`, then `f=g`
Solution: False: a counterexample is `f(n)=n` and `g(n)=2n`.
(4pts) : Prove: `n^10 e^n in o(3^n)`
Solution: Apply log (e.g., ln) to both sides (monotonic):
We want to show `10 ln n + n in o(n ln 3) = o(n)`.
Use limit definition of o(): `lim_(n>oo) (10 ln n + n)/n` = `lim_(n>oo) (10 ln n)/n + 1` = 0 (e.g., by applying L'Hôpital's rule)(6pts): Prove from definition: `n^2 + O(n log n) = O(n^2)`
Solution: Let `f in O(n log n)`, i.e., let `c_0, n_0` be such that `forall n > n_0, f(n) <= c_0 n log n`.
Since n > log n, we can let `n_1=n_0` and `c_1=1+c_0`, and we have `forall n > n_0`
`n^2 + f(n) <= n^2 + c_0 n log n` `<= n^2 + c_0 n^2` `= (1+c_0)n^2 = c_1 n^2`,
which proves the result.(6pts): Prove by induction, for all n ≥ 1: `sum_(k=1)^n k(k!) = (n+1)!1`
Solution: Base case: `sum_(k=1)^1 k(k!) = 1(1!) = 1 = 21 = (1+1)!1`.
Inductive step: `sum_(k=1)^n k(k!)` = `n(n!)+sum_(k=1)^(n1) k(k!)` (pulling out one term)
= `n(n!) + (n!)1` (by inductive hypothesis at n1)
= `n!(n+1)1` (factor out n!)
= `(n+1)!1`.(5pts): We have now learned 7 sorting algorithms: insertion, merge, heap, quick, counting, radix, bucket. For each, briefly summarise the pros/cons, assumptions, and key features.
Solution:
Insertion: Easy to code, fast on "approximately sorted" input, but average case slow `Theta(n^2)`
Merge: Always Θ(n lg n), but requires copying
Heap: Also Θ(n lg n), but often more swaps than Quicksort
Quick: Average/random case Θ(n lg n), worst case `Theta(n^2)`, few swaps on realworld input
Counting: Assumes items can only take on a small number k of values. Outofplace but stable. Θ(n+k)
Radix: Assumes items can be split into digits. Depends on a fast, stable sort like counting sort. Θ(d(n+k)), depends on choice of radix (i.e., how to split into digits)
Bucket: Assumes values uniformly distributed in [0,1)(8pts): Demonstrate QuickSort (Lomuto partitioning, nonrandomised) on the following input:
[ M T K D S F G L ]
. How many (nontrivial) swaps?Solution: Each line is just after a nontrivial swap (9 total).
lo hi piv spl cur M T K D S F G L 1 8 L 1 3 K T M D S F G L 1 8 L 2 4 K D M T S F G L 1 8 L 3 6 K D F T S M G L 1 8 L 4 7 K D F G S M T L 1 8 L 5  K D F G L M T S 1 4 G 1 2 D K F G L M T S 1 4 G 2 3 D F K G L M T S 1 4 G 3  D F G K L M T S 6 8 S 7  D F G K L M S T (6pts): Consider an array of 2D points `{(x_i, y_i)}_(i=1)^n` uniformly distributed within the unit disk (i.e., inside the circle of radius 1 centered at (0,0)).
Describe in words how you might efficiently sort this array in increasing order of distance from the origin (0,0).Solution: The critical thing to notice is that the points are not uniformly distributed in terms of distance from the origin.
One way to see this is by considering annular rings of fixed width dr, e.g., `{(x,y): r < sqrt(x^2+y^2) < r+dr}`. The area of the ring is `pi(r+dr)^2pi r^2` = `2pi r dr + pi (dr)^2`, which increases linearly with r.
From this, we can see that if we use the square of the distance as the key to determine buckets, rather than just the distance, then it is equivalent to dividing the unit disk into annular rings of equal area:
Each ring is `{(x,y): h < x^2+y^2 < h+dh}` = `{(x,y): sqrt(h) < sqrt(x^2+y^2) < sqrt(h+dh)}`.
The area of each ring is `pi(sqrt(h+dh))^2  pi(sqrt(h))^2` = `pi(r+dr)  pi(r)` = `pi dr`, which is constant.
So the solution is to use bucket sort on the square of the distance from the origin.(8pts): Demonstrate inserting the input
[ 7, 11, 16, 22, 36 ]
into a hashtable of size m=5, using (a) division hash,
 (b) division hash and linear probing, and
 (c) division hash and quadratic probing with `c_1=0.5, c_2=2.5` (round the result down).
bkt: 0 1 2 3 4 key: 7 11 16 22 36 mod5 2 1 1 2 1 div  11 7     16 22     36    lin 36 11 7 16 22 quad 22 11 7 36 16 (8pts): Identify the problem(s) in the following pseudocode for deleting a node from a singlylinked list.
Fix it (i.e, rewritedelete()
). Assume reasonable class definitions of LinkedList and Node.class LinkedList: def delete( self, key ): node = self.search( key ) if (!node): return # key not in list if node == self.head: self.head = node.next del node
Solution: The
next
pointer in the previous node needs to be updated to skip over the node to be deleted. But since we are a singlylinked list andsearch
brought us too far already, we can't do that. We need to extend the code forsearch
:def delete( self, key ): if self.head == None: return # empty list if key == self.head.key: # del head cur = self.head self.head = cur.next del cur return prev = self.head # search for key cur = prev.next while cur != None: if cur.key == key: # del cur node prev.next = cur.next del cur return prev = cur cur = cur.next
(6pts): Reconstruct the binary search tree whose postorder traversal is
D H M K F T X V R Y Q
.Solution: