Sample Questions for Exam 1
[Solutions now complete]

In the programs below, "<--" means "left arrow."
In each case, assume that the array A has n elements,
n is at least 2, that each element is an integer, and that
the entries are distinct (no two are the same).

1.  What does the following program do:

x <-- 0;
for i <-- 1 to n
   x <-- x + A[n]		 This is what I intended

x <-- 0;
for i <-- 1 to n
   x <-- x + A[i]
The original computes n×A[n]. 

I intended it to compute the sum of the entries of the array,
2.  Use this loop invariant to prove that the
program in problem 1 does what you say it
will do:  At the start of each iteration of the
for loop, the variable x contains the sum of the
elements A[1] + A[2] + ... + A[i - 1].

 This solution is for my intended problem:

Initialization:  When i = 1, the condition is satisfied vacuously. 

Maintenance:  Suppose the loop invariant is true at the start of the i'th iteration of the loop.  Then x = A[1] + A[2] + ... + A[i - 1].  To show that it remains true at the start of the (i + 1)st iteration, observe that x will be incremented by A[i] during the i'th iteration, so that at the start of the (i + 1)st iteration, x = A[1] + A[2] + ... + A[i - 1] + A[i], which is what we want.

Termination:  When the loop terminates, i = n + 1, and the value of x is A[1] + A[2] + ... + A[n].  This is what we wanted to prove.
3.  What does the following program do:
(The expression "-infinity" means a quantity which
is formally less than any number.)

x <-- -infinity
y <-- -infinity
for i <-- 1 to n
   if A[i] > y
      if A[i] > x
         y <-- x
         x <-- A[i]
      else
         y <-- A[i]

 It fills the value x with the largest element of the array, and the value y with the second largest element of the array.
4.  Why doesn't this loop invariant suffice to
prove that this algorithm does what you say it will do?
At the start of each iteration, x contains the largest
element from among the elemenst in A[1 .. i-1].

 The problem is at termination.  At termination it asserts merely that x contains the largest element, but does not mention y.   It is therefore not powerful enough a loop invariant to show that x and y contain the largest and second largest elements respectively.
5.  Strengthen the loop invariant given above so that it
does suffice to prove that the algorithm does what you say
it will do.  Then write the proof.

 "At the start of each iterateion, x contains the largest element, and y contains the second-largeset element, from among the elements in the array A[1..i-1]."

This loop invariant is strong enough to prove that the algorithm works, because at termination it says what you want it to say.  It also is strong enough to prove the maintenance step.
6.  Do the exercises indicated in the calendar on the website.
(The ones that are not for hand in.)
7.  Prove that n3 + 1 is Theta(n3) by finding the
appropriate constants, as indicated on page 42 of the text.

 [Not on the test.]
We want to find c1, c2 and n0 so that for n > n0,
c1 × n3  <= n3 + 1 <= c2 × n3 
Clearly, n3 + 1 > n3, so that c1 = 1 suffices.
Also, for n >= 1, we have 1 <= n3, so that n3 + 1 <= 2n3.
Thus c2 = 2 suffices, with n0 = 1.
8.  What are the asymptotic running time (Theta bound) of
each of the algorithms given above, in problems 1 and 3?

 Both of them have a single loop which runs for n iterations, and each iteration takes a bounded amount of time. 

In the first program, each iteration takes the same amount of time, so the running time is c × n for some constant c. 

In the second program, each iteration takes one of three possible amounts of time, depending the results of the "if" statements.  Each of these is some fixed amount of time.  Suppose that c is the least of them and d is the greater.  Then each iteration takes time between c and d, and so the total running time T(n) is bounded by:
c × n <= T(n) <= d × n

[It's not on the test, but for future reference, let us observe implies that] T(n) = Theta(n).
9.  Suppose that someone took a sorted array with n elements,
removed one of the elements, and then put it back in the wrong
place, shifting the rest of the elements as needed to make room
for the new element.  Design a linear-time algorithm to put the
array back into sorted order.  Then prove that your algorithm
is correct.

 There are many possible solutions to this problem.  One way is to do a kind of two-directional bubble sort with one pass in each direction:

for i <-- 1 to n - 1
   do if A[i] > A[i + 1]
      then swap A[i] <--> A[i + 1]
for i <-- n - 1 downto 1
   do if A[i] > A[i + 1]
      then swap A[i] <--> A[i + 1]

Each of these loops makes n - 1 comparisons and at most n - 1 swaps, for a total number of 4n - 2 steps, which is linear in n.

To prove this correct,  we distinguish three cases.

Case 1:  The array is still sorted, since the misplaced element ended next to an element of equal value.  In this case both loops will leave the array unchaged, and it will stay sorted.

Case 2:  The misplaced element needs to be moved to the left in the array, to a position with a lower index.  In this case, the first loop will move that element one spot to the left, when it swaps it with the element before it.  If this results in a sorted array, then we are done.  Otherwise, the misplaced element needs to be moved further left in the array.

We now prove that the second loop will do that.  Our loop invariant (for the second loop) is: 

At the start of each iteration, the subarray A[i+1..n] is sorted, and the subarray A[1..i] has at most one element which is misplaced, and which needs to be moved to the left.

Proof:
Initialization:  Here i = n - 1, and the array A[n..n] is trivially sorted.  Also, since the whole array has at most one element misplaced, the subarray A[1..i] can have at most one misplaced element.

Maintenance:  Suppose that A[i+1..n] is sorted, and the subarray A[1..i] has at most one element which is misplaced, and which needs to be moed to the left.  We want to show that after another iteration, the subarray A[i..n] will be sorted, and A[1..i-1] has at most one misplaced element, which needs to be moved to the left. 

To see that A[i..n] is sorted after the iteration, observe that if we did not do a swap on that iteration, then A[i] <= A[i+1] held.  Thus A[i] could be added to the beginning of the sorted list A[i+1..n] to give a sorted list A[i..n].  If we did do a swap, then that means A[i] > A[i + 1] held, which could happen only if A[i + 1] held the misplaced element.  But then the array with A[i + 1] deleted would be sorted.  In particular, A[i] < A[i + 2] before the swap, so A[i]'s element, now in position A[i + 1] after the swap, could be added to the start of the already-sorted subarray A[i+2..n] to obtain the sorted A[i+1..n].  And becasue we did do the swap, we also have that A[i] <= A[i + 1] after the iteration.  Thus the entire subarray A[i..n] will be sorted.

To see that A[1..i-1] has at most one misplaced element after the iteration, again consider whether we swapped or not.  If we did not, then the misplaced element was not involved in the swap, and so the misplaced element, if any, would have to be among the elements in A[1..i-1].  If we did do the swap, then A[i+1] must contain the misplaced element, before the swap.  After the swap, that element will be in the A[i] position, so that the sub-array A[1..i-1] will be sorted.

Case 3:  The misplaced element needs to be moved to the right in the array, to a position with a higher index.  This case is similar to Case 2, except that the first loop will sort the array, and the second loop will do nothing.  (You can really say this in proofs, if you are sure the two cases are similar.)

[Note that this proof is not appropriate for an exam, as it is way too long.]
 
10.  Suppose that someone took a sorted array and "shook" it
a little bit, so that each element wound up no more than 3
positions from where it had been in the array.  Design a linear-time algorithm for putting this array back into sorted order.  Then prove that your algorithm is correct.
 Algorithm:
for i <-- 1 to n - 3
   do sort subarray A[i..i + 3]

Note that sorting a four-element array takes constant time.  Since our algorithm does this n - 3 times, the algorithm's running time  is linear in n.

Loop Invariant: 
At the start of each iteration, the subarray A[1..i-1] is sorted, and contains the least i-1 elements of the array A.

Proof of Correctness using the loop invariant:

Initialization:  At the start, i = 1, and there is nothing to show.

Maintenance:  Suppose that A[1..i-1] is sorted, and then we sort the subarray A[i..i + 3].  We want to show that A[1..i] will now be sorted.  This follows from the fact that each element in A[i..i + 3] is at least as big as A[i-1], and that the location of the element which belongs in the ith position could be no more than three positions to the right of A[i], and so will be "caught" when we sort A[i..i + 3], and moved to the A[i] position.

Termination:  When the loop ends, we have i = n - 2, so the loop invariant gives that the subarray A[1..n - 3] is sorted.  Observing further that the last thing our algorithm did was sort the subarray A[n-3..n], we see that the whole array will now be sorted.

[Note:  This algorithm is fair game for an exam.]



Sample Questionsn for Exam 2
For all recurrences, assume that T(x) = 1 for x <= 1.
1.  Use tree recursion to solve each of these recurrences:
a.  T(n) = 3T(n/2) + n
b.  T(n) = 2T(n/3) + n2
c.  T(n) = 4T(n/2) + n2
 I'll give answers along the lines of the tables shown here, on pages 2 and 4.  I'll give the "#" and "Total" sequences, and show how to add them, but you'll have to supply the picture of the tree yourselves.

a.   Height of tree = k = log2 n, and 2k = n.
# sequence:  1, 3, 9, 27, ..., 3k-1
Total sequence:  n, (3/2)n,  (9/4)n,  ...,  (3/2)k-1 n.
Sum in bottom row:  3k
Total cost:  n(1 + 3/2 + (3/2)2 + ... + (3/2)k-1 ) + 3k
  =  n ((3/2)k - 1) / (1/2) + 3k
  =  O(n * (3/2)log2 n) + 3 log2 n
  =  O(n * n log2(3/2)) + n log23
  =  O(n log2 3)
(Note that in the above solution, I made use, twice, of the very cool identity a logb c = c logb a.  Thank you Vicki for showing me that one!)

b.  Height of tree = k = log3 n.
# sequence = 1, 2, 4, 8, ..., 2k - 1
Total sequence:  n2, (2/9)n2, (2/9)2n2, ..., (2/9)k-1n2
Sum in bottom row:  2k
Final answer:  O(n2)

c.  Height of tree = k = log2 n.
# sequence = 1, 4, 16, 64, ..., 4k - 1
Total sequence:  n2, n2, n2, ..., n2
Sum in bottom row:  4k
Final answer:  O(n2 * log n)
2.  Use back substitution to solve these recurrences exactly:
a.  T(n) = T(n-1) + n
b.  T(n) = T(n/2) + 1  (That n/2 should be rounded down each time)
c.  T(n) = T(n-2) + 3
 a.  T(n) = T(n - 1) + n
   = T(n - 2) + (n - 1) + n
   = T(n - 3) + (n - 2) + (n - 1) + n
   = ...
   = T(1) + 2 + 3 + 4 + ... + n
   = 1 + 2 + 3 + 4 + ... + n
   = n(n + 1)/2

b.  T(n) = T(n/2) + 1
   = T(n/4) + 1 + 1
   = T(n/8) + 1 + 1 + 1
   = ...
   = T(1) + 1 + 1 + ... + 1
And the question is, now many steps do you have to go to get down to T(1)?  Answer:  The number of times that you have to cut n in half to get down to 1, which is log2 n.  So the answer is T(n) is about log base 2 of n.  But is it exactly that value?  Of course not, when n is not a power of 2.  So we have to figure out how to round.  For this, make a table:
n
 1
 2
 3
 4
 5
 6
T(n)
 1
 2
 2
 3
 3
 3
From this table, we see that the value of T(n) increases by 1 at each power of 2.  So T(n) = floor(log2 n) + 1.

c.  T(n) = T(n - 2) + 3
   = T(n - 4) + 3 + 3
   = T(n - 6) + 3 + 3 + 3
   = ...
   = T(0 or 1) + 3 + 3 + ... + 3.
where the "or" depends on whether n is odd or even.
If n is even, then we get down to 0, and if n is odd, then we get down to 1.  In either case, T(0) = T(1) = 1.
Now, how many 3s are there?  It's the number ot times that we have to subtract 2 from n in order to get down to 1.  This is n/2, roughly.
to get the exact answer, let's make a table again...
n
 0
 1
 2
 3
 4
 5
 6
T(n)
 1
 1
 4
 4
 7
 7
 10
From this table, we see that the value of T(n) increases by 3 at each even number, so that T(n) = 3*floor(n/2) + 1.
3.  Use the substitution method to show that T(n) is O(f(n)) in each case:
a.  T(n) = 2T(n/2) + 1, f(n) = n.  (Might need to assume T(n) = cn + b, and then find values of c and b which work.)
b.  T(n) = sqrt(n)T(n/2) , f(n) = n!
c.  T(n) = 4T(n/3) + n, f(n) = n2
 a.  Assume that for k < n, we have T(k) <= c*k + b, for values of c and b to be determined later.
Then T(n) = 2T(n/2) + 1
   <= 2 (c*n/2 + b) + 1
   = c*n + (2b + 1).
Now, we want this to be no more than c*n + b.  For this to happen, we need to find a b that satisfies:
2b + 1 <= b
which will be true as long as b <= -1.  Let's let b = -1.  c, as it turns out, can be arbitrary, so let's let c = 1.

We have thus proved that T(n) <= n - 1, for all n  >= 1.

b.  Assume that T(k) < c*k!, for all k < n.
Then T(n) = sqrt(n) T(n / 2)
   <= sqrt(n) (n/2)!
What do we do with this?  Well, we are trying to show that this will be less than n!, which equals 1*2*3*..*(n/2)*(n/2 + 1)*...*(n-1)*n. 
So we have a lot of "breathing room" there, since sqrt(n) is very small compared to n, and we need it to be smaller than just the product of the larger terms in our n! product.  In particular, if sqrt(n) is less than n/2 + 1, then we have our result.  So let's solve
   sqrt(n) < n/2 + 1.
This is clearly true if n > 4.  So that is our n0.  For n > n0, we have
   <= [(n/2) + 1] (n/2)!
   <= (n/2 + 1)!
   <= n!
which is what we wanted.

c.  This is the easiest of them.  Simply assume that for k < n, we have
T(k) < c*n2.  The rest follows as above, only more easily.
4.  For each of the recurrences above, state whether the master method applies.  If it does not, say why not.  If it does, use the master method to solve the recurrence.
 1.  Yes to all parts. 
2.  Only to part b.  for part a, the T(n-1) part does not fit the structure of the Master method, and for part c, the T(n-2) does not fit.
3.  Only to parts a and c.  For part b,  we have a  sqrt(n) "coefficient" to the T(n/2), and only constant coefficients are allowed there.
5.  Solve the recurrence:  T(n) = 3T(sqrt(n)) + log2(n)  (that's log base 2).
 For this one, we can make a few substitutions, and then use the Master Method. 

First of all, let n = 2k.  This is a good choice, because then sqrt(n) becomes sqrt(2k) = 2k/2, which has a similar form as n itself.   Substituting, we get:
   T(2k) = 3T( 2k/2) + log22k  =  3T( 2k/2) + k
Now let's do another substitution:  Let S(k) = T(2k)
   S(k) = 3T(k/2) + k
This can be solved by the Master Method: 
   S(k) = Theta(klog2 3).
Which gives T(n) = T(2k) = Theta(klog2 3) = Theta( (log2 n)log2 3)
6.  Heaps.
a.  Draw the tree diagram corresponding to the following array, thought of as a heap:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
b.  Run Build-Max-Heap on the heap, showing the heap, as an array, after each iteration of the Max-Heapify procedure.  Fill in this table:
1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12










































































1-12 heap
1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
1
 2
 3
 4
 5
 12
 7
 8
 9
 10
 11
 6
1
 2
 3
 4
 11
 12
 7
 8
 9
 10
 5
 6
1
 2
 3
 9
 11
 12
 7
 8
 4
 10
 5
 6
1
 2
 12
 9
 11
 6
 7
 8
 4
 10
 5
 3
1
 11
 12
 9
 10
 6
 7
 8
 4
 2
 5
 3
12
 11
 7
 9
 10
 6
 1
 8
 4
 2
 5
 3

7.  How many leaves does a heap with n elements have?
 Ceiling(n/2)
8.  Suppose I have an array containing a max heap.  If I reverse the order of all the elements in the array, will I have turned it into a min heap?
 No, as can be shown on an example with only 3 elements.
3-1-2 is a max heap, but its reverse, 2-1-3 is not a min heap.
9.  Suppose that arrays A and B each contain min heaps of the same size, and then I create array C, also of the same size, by adding the elements of arrays A and B.  That is, C[i] = A[i] + B[i], for i from 1 to heapsize.  Show that C will also be a min heap.
 To show that C will be a min heap, we need to show that for each element C[i], with i > 1, C[i] is no less than its parent.

Since A and B are already min heaps, we have:
   A[i] >= A[parent(i)]
   B[i] >= B[parent(i)]
which implies:
   A[i] + B[i] >= A[parent(i)] + B[parent(i)]
or
   C[i]  >= C[parent(i)],
which is what we wanted to prove.  
10.  Use Prim's algorithm to find a minimum weight spanning tree in the weighted graph below.
Weighted Graph
 Prim Answer
The red circle shows where I started Prim's algorithm, and the arrows indicate a "parent to child" relationship. 
11.  Now use Kruskal's algorithm to find the minimum weight spanning tree
 Same tree as above.
12.  Suppose I wanted to find a minimum weight cycle in a weighted graph.  That is, a cycle so that the sum of the weights of the edges in that cycle was as small as possible.
a.  Find a minimum weight cycle in the graph above
b.  Devise a greedy algorithm for finding a minimum weight cycle.  Note that this algorithm need not actually work; it just needs to be greedy, and be guaranteed to find a cycle.
 a.  It's 8 + 12 + 14 = 34.
b.  Lots of answers.
Solution 1:
Start at some vertex.
At each step, check to see if the vertex you are at has an already-visited neighbor.  If so, walk to it to complete a cycle. If not, walk to the nearest unvisited neighbor. 
Return the first cycle so created. 
For example, this algorithm yields a cycle of weight 34 in the graph above, if started at the red vertex, but a cycle of weight either 46 or 55, depending on how ties are broken, if you start with the rightmost vertex.

Solution 2:
Build a minimum weight spanning tree.  Then select the lowest-weight from among those edges not in the tree, add it to the tree, and return the unique cycle thus created.
For example, in the graph above, this would return a cycle of weight 39 or 46, depending on how you break the tie.
13.  Suppose that S and T are two spanning trees in a graph G, not necessarily minimum weight spanning trees, and suppose that e is some edge in S which is not in T.  Show that there is some edge f which is in T, but not in S, so that
T + {e} - {f} is another spanning tree of G.  Also draw an example of this situation, where G has 7 vertices and 10 edges.
 Proof:
Let us add edge e to tree T.  Then (T union {e}) will contain exactly one cycle, which we'll call C.  This cycle cannot lie entirely within S, since S is a tree, so let f be an edge of C which is not in S.  This is the desired edge.

To show that this works, we need to show that T + {e} - {f} is another spanning tree of G.  That it spans G is clear, since no vertices have been deleted.  To show that it is a tree, we will show that it is connected and has no cycles. 
Connectedness follows from the fact that T was connected, implying that T + {e} is connected.  Then since f was an edge on a cycle in T + {e}, its removal cannot disconnect the graph.
To show it is acyclic, note that T + [e} had exactly one cycle, and when we remove f, that cycle is broken. 

Note that in this proof, we used the following facts about trees from Wednesday's class:

1.  To prove that a graph on n vertices is a tree, we can show any two of
   a. It is connected
   b. It is acyclic
   c.  It has n - 1 edges

2. Removing an edge from a cycle in a graph cannot disconnect that graph

3.  There is exactly one path between any two vertices in a tree.

4.  Adding a single edge to a tree results in a connected graph with exactly one cycle.



here G has 7 vertices and 10 edges.