1. 1. Find the median of the first 3 elements in the array (notice: the elements are distinct.) The median is neither the maximum nor the minimum of the array. Time complexity is Theta(1).
   2. Find the minimum of the first k+1 elements in the array A. The time is Theta(k).
      (another solutions: Use a selection algorithm to find the (n-k)'th largest element, then partition around it. Return one of the elements to the left of the pivot. Time: Theta(n).)
      another solution: use the tournament method to find the max. Second to max is a loser to max, third is a loser to secondmax, etc. Time: Theta(n +klogn).
      The worst and easiest answer is to sort the array and return a beginning element that is not in A[n-k...n].
2. 1. Edge (C,E). Fringe vertics are G, F, H more specifically: (G,E)1, (F,C),4, (H,E),2
   2. (A,D), (A,B), (B,C), (C,F), (D,E), (E,G), (E,H)
3. 1. ABECFGD (assumes alphabetical order of adjacency lists)
   2. ADBEFGC (others were accepted)
   3. ABCDEFG
4. 1. The best pivot would be 5 since 5 is the median, and it would partition the array exactly in half. Balanced partitioning yields an overall Theta(n log n) time complexity, which is optimal.
      
      The quicksort that we saw always chooses the first element of the array as the pivot, so it would choose the 10.
   2. No. The median of the first three could be the second to minimum of the entire array, which would give a BAD (i.e. uneven) split of sizes 2 and n-2.
   3. The advantage of the partition is that it is INPLACE (i.e. done inside the array, using a constant amount of extra space.)
5. (a) Call fixheap on each node. Note: fixheap returns when a node is larger than its 2 children. So, while you have not encountered the "bad" node, each call to fixheap will take constant time. Upon calling fixheap on the "bad" node, the node will be moved down to its proper location. This one call will take Theta(log n) time. Thus, the total time is Theta(n + log n) = Theta(n).
   
   (b) Yes. A heap can be stored in an array, in which the children of element i are stored in locations 2i and 2i+1. Each time you remove the max, it is placed in the empty location at the end. You have to keep track of the "heapsize," that is, the location where the heap ends, and the sorted output begins. This is actually the reason that we use max-heaps (and not min-heaps).
6. (a) Iterate through row v of the adjacency matrix, and count the number of 1's.
   Let n = |V|. degree=0;
   for i=1 to n
   if M[v][i]==1 degree++
   Time: Theta(n).
   
   (b) Outdegree is easy -- simply count the number of elements in v's adjacency list. Time: Theta(|E|).
   
   Indegree: must iterate through all adjacency lists, and count the number of times v occurs (i.e. the number of nodes that have v on their adj list). Time: Theta(|E|).