## Description

Be sure to include your name at the beginning of each ﬁle! Assignment 10 include a programming portion and a written part. The programming portion must compile and consist of a single ﬁle ( hw10.cpp). The written portion should consist of two ﬁle (hw10awritten & hw10bwritten) in a .pdf format. Be sure to include your name at the beginning of each ﬁle! You must hand in the ﬁle via NYU Classes.

Programming Part:

1. 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

2. 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.

3. 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.

∗10% extra credit if you turn in the assignment on Tuesday May 3rd 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.

1

Written Part:

1. 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.

2. If we implemented3 the ADT priority queue using a unsorted vector, how long would it take to perform 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:

3. Consider the following array representation of a binary heap:

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

(a) Show the tree representation of the binary heap. (b) Insert 197 into the binary heap; show both the tree representation and the array representation after 197 has been inserted.

4. Consider the following tree representation of a binary heap:

2

3

6

9 7

8

19 27

4

70 5

(a) Show the array representation. (b) Show what happens when the root is removed by giving the tree representation of the binary heap.

5. Rewrite the BinaryHeap insert routine where the items are stored in position 0 through theSize−1. 6. 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

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

A B C

DEFG

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:

A B C F

D

E G

0

14

6

5

3

19

5

3 12

1 18

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 5/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

10. Consider the following graph:

A B C F

D

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 11. 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