Homework 11 Solution

Programming Question 1 and Written Questions 1-9 Question 2

Written Questions 12 & 13



















Be sure to include your name at the beginning of each le! Assignment 11 include a programming por-tion and a written part. The programming portion must compile and consist of two les ( hw11a.cpp and hw11b.cpp). The typewritten portion should consist a le in a .pdf format. Be sure to include your name at the beginning of each le! You must hand in the les via NYU Classes.




Programming Part:




Write a function, call print kth largest that takes two parameters, a vector and an int. The function will print out the the kth largest items in the vector. Your algorithm must be e cient and must use a priority queue



template<class Comparable




void print kth largest(const vector<Comparable & a, int k)




Write the code to nd how to go from one subway station to another subway station where you have the smallest number of hops (i.e. travel through the smallest number of subway stops or transfers.)



To do this you need to perform the following steps:




Use the code you have previously written to create the adjacency list.1 This will be the graph you use in the algorithm, shortestpaths.




Modify the shortest path algorithm, shortestpaths, so that it now computes the shortest path to go from one stop_id to another stop_id and uses the graph you created.




To do this, you will need to change the parameters of the algorithm, shortestpaths and part of the code.




Modify the code so it prints out the shortest path to go from the one stop_id to other stop_id. Remember to print out the stop_id’s.




Up to 1 point extra credit towards nal grade. Create a class that cleanly uses all the MTA code you have written and adds some other useful methods that improve the usability of the class2. To receive this credit, you must explain your code to me.












5% extra credit if you turn in the assignment on Tuesday Dec 13th by 11:00 p.m.




1You may use the solution to the previous homework problem if you provide a comment telling where you got the code from.

2Be creative! What additional functionality would be useful to have. To receive the full 1 point extra credit you have to add some signi cant additional options to the your menu.




1
Written Part:




What is the big-Oh running time of your code in programming problem 1? Use n and k in your answer, where n is the size of the vector and k is the number of items you print.



If we implemented3 the ADT priority queue using a unsorted vector, how long would it take to per-form the following operations of a priority queue? Write your answer using Big-Oh notation.






insert(x); // Average case time: deleteMin(); // Average case time: findMin(); // Average case time:




Consider the following array representation of a binary heap:






[sentinel, 190,
380,
200,
388,
401,
277, 270, 1000, 399,
432]



Show the tree representation of the binary heap.



Insert 197 into the binary heap; show both the tree representation and the array representation after 197 has been inserted.



Consider the following tree representation of a binary heap:















2




3




4


6
8
70
5
9
7
19
27








Show the array representation.



Show what happens when the root is removed by giving the tree representation of the binary heap.



Rewrite the BinaryHeap insert routine where the items are stored in position 0 through theSize 1.



Show the result of using the linear-time algorithm to build a binary heap on input



10; 12; 1; 14; 6; 5; 8; 15; 3; 7; 4; 11; 10; 0. In your answer, provide the vector representation of the heap.



















3Remember for any ADT there are many choices of how it could be implemented. Some choices are more e cient than others.




2
Illustrate the execution of the single source shortest path algorithm for an unweighted graph (breadth rst search) on the (undirected) graph below:









G F E D





































A B C










At each phase, show the node being visited in that phase, and the relevant data at the end of the phase, including:




the distance to each vertex that has been discovered (including those already visited) the predecessor of each discovered node on a shortest path from the source




the queue of nodes that have been discovered but not yet visited




The answer at the end of the rst phase is shown in the table below. It indicates that at the end of the rst phase, we have visited G and have discovered A and F, each with estimated distance 1 and with predecessor G. Complete the table. (continue until all the nodes have been removed from the queue.)




phase distance/predecessor visiting queue




G A B C D E F (front at queue on the left)




-------------------------------------------------------------------------------




init 0/- G




-------------------------------------------------------------------------------




1 0/- 1/G 1/G G F A




-------------------------------------------------------------------------------




2




------------------------------------------------------------------------------




.




.




.




Use the chart you have created to determine a shortest path from G to C.




8. For the graph in written question 9 show the adjacency matrix and the adjacency list representation.































3
9. Illustrate the execution of Dijkstra’s algorithm on the weighted (undirected) graph below:







D




3

3 12




0




6




A B C F




5

5




14




1 18




E G




19




Show all the steps using the following chart:




phase distance/predecessor visiting discovered




A B C D E F G




------------------------------------------------------------------------------




init 0 inf inf inf inf inf inf A




------------------------------------------------------------------------------




1 0 6/A inf 3/A 1/A inf inf A B D E




------------------------------------------------------------------------------




2




------------------------------------------------------------------------------




.




.




.










i.e. at each phase, show:




which phase your are in




the node being visited in that phase




the current estimate of distance to each vertex (via nodes already visited)




the predecessor of the node (on a shortest path via nodes already visited, i.e. the current estimate of the predecessor)




all the nodes that have been discovered, but not yet visited.




Continue the chart until all the nodes have been visited.







Using the chart you created, determine a shortest weighted path from A to G.






















4
Give an example where Dijkstra’s algorithm gives the wrong answer in the presence of a negative edge but no negative-cost cycle.



Explain how to modify Dijkstra?s algorithm to produce a count of the number of di erent minimum paths from v to w.



Consider the following graph:






D



















A B C F



















E G










Show the order you rst discover the vertices when starting at node A




if you do a DFS traversal of the graph if you do a BFS traversal of the graph




Find a topological ordering for the graph given by the following adjacency list:



s :! a ! g




a :! b ! e




b :! c




c :! t




d :! e




e :! c ! f ! i




f :! t




g :! d ! h




h :! i




i :! f ! t t :








































5