(12 pts) In this problem you will practice insertion and deletion in binary heaps (default min heap).
Show how to insert 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13 and 2 into an initially empty binary heap. Insert each value, one at a time, NOT WITH buildHeap and show each of the 15 steps as separate trees (pictorially with nodes and edges). (8 pts)
Show the results of two consecutive deleteMin of the heap above. (Show each one.) (4 pts)
(8 pts) Exercise 9.1. (Fig. 9.79, same for the C++ book) Find the topological ordering of the given graph (ignoring the given weights on the edges) using the topological sort algorithm. NOTE: if there is a tie, the alphabetic order of a node serves as its priority. At each step, show the contents of the queue and what node is output.
(8 pts) Exercise 9.5a. (Same for the C++ book) Use Dijkstra's algorithm to find the shortest path to each of the nodes, starting from node A in the graph of Figure 9.80. At each step, show the distance value for each node and indicate which is the chosen node.
| Step | Chosen | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|---|
| 1 | ? | 0 | inf | inf | inf | inf | inf | inf |
(10 pts) For the same graph (Fig 9.79, ignoring the given weights on the edges) as Exercise 9.1, starting from the node s, give the ordering of nodes that will be visited by:
DFS. (5 pts)
BFS. (5 pts)
NOTE: if a node has several successive nodes to visit, the alphabetic order of a successive node serves as its priority.