Homework 15

General Comments

• For full credit, provide context for each problem, show all calculations, and justify all answers by providing enough comments to explain your reasoning.
• Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).
• You can get up to 50% credit on a problem if you get significant outside assistance. Thus, if you are totally stuck on a problem it might be worth getting help. However, you must indicate any assistance/collaboration (See the Homework Assistance section on the Policies page). Failure to do so could result in a failing grade for the course! Note that getting help from the Help Center or me does not count as significant outside assistance, but talking with your classmates or searching on the Internet does!
  
• If a problem asks for an algorithm, you should give the most efficient algorithm you can find to ensure full credit. You should also specify the complexity of the algorithm with justification, whether or not the problem asks for it.

Details

1. (10) Do the BRIDGES Mountain Path Assignment. Submit the code via you Google Shared Folder and the writeup in class.
2. (10) Use Floyd's algorithm to find the solution to the all-pairs shortest path problem for this graph whose adjacency matrix is given below. Be sure to show the matrix at every step of the computation, mark the relevant row/column of each, and highlight the cells that changed. \[ \begin{bmatrix} 0 & 3 & 8 & \infty & 1 & \infty \\ \infty & 0 & \infty & 1 & 7 & \infty \\ \infty & 4 & 0 & \infty & \infty & 9 \\ 2 & \infty & 2 & 0 & \infty & \infty \\ \infty & \infty & \infty & 6 & 0 & 3 \\ \infty & 10 & \infty & \infty & \infty & 0 \end{bmatrix} \]
3. Consider the following array: \([23, 87, 43, 21, 90, 54, 11, 74, 38, 41, 66, 32, 17]\). Perform the following variation of Heap Sort on the array:

   function heapSortVariation(A):
       B = new heap;        // Instead of buildHeap, do this:
       for i from 0 to n-1: // Insert the elements from the array into
           B.insert(A[i])   //  the heap in order, one at a time.
   
       for i from n-1 down to 1:  // continue the second half as normal
           swap B[0] with B[i]     // move max to end
           heapify(B, 0, i-1)      // restore heap property
       return B  

   Show the heap (drawn in tree form) at every step of insertion and deletion (which happens as i decreases in the second loop). As i decreases in the second loop, continue drawing the nodes, but disconnect nodes that are not logically in the heap anymore (the sorted elements).