CSE 373 Homework Assignment 4

Problem 1

(9 pts) In this problem you will practice insertion and deletion in binary heaps.

  1. Do insert and deleteMin of a binary heap have the same big-O time complexity? (1 pts)

  2. Show the final result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13 and 2 into an initially empty binary heap. (4 pts)

  3. Show the results of two consecutive deleteMin of the heap above. (4 pts)

Problem 2

(8 pts) Show the following regarding the maximum item in a min-heap with N distinct items:

  1. It must be at one of the leaves, and every leaf must be examined to find it. (3 pts)

  2. There are exactly N/2 (if N even) or (1+N)/2 (if N odd) leaves. (5 pts)

Problem 3

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

Problem 4

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

Problem 5

(10 pts) 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:

  1. DFS. (5 pts)

  2. BFS. (5 pts)

NOTE: if a node has several successive nodes to visit, the alphabetic order of a successive node serves as its priority.