**CS557AL Homework-5**

Student’s Name: _____________________________________

All work must be your own. Turn ** in an electronic format (PDF or MS Word file)** and any supporting programs (source code and test cases).

__Show your work in detail__.

**NOTE: No extensions or late submissions for anything** other than major emergency.

**Q1** [15 pts.]: [The depth-first search tree] Solve Problem 7.4a from the Baase’s textbook (page 376).

Find the depth-first search tree for the graph used in Example 7.6 (see Figure 7.28, below) with **B as the starting vertex** under the assumption about the adjacency-list order:

- Each adjacency list is in
*alphabetical*order

**Q2** [15 pts.]: [The breadth-first search tree] Solve Problem 7.5b from the Baase’s textbook (page 376).

Find the breath-first search tree and breath-first distances for the graph used in Example 7.7 (see Figure 7.28, above) with **B as the starting vertex** under the assumption about the adjacency-list order:

- Each adjacency list is in
order.__reverse__alphabetical

**Q3** [25 pts.]: [Prim’s minimum spanning tree algorithm] Solve Problem 8.6b from the Baase’s textbook (page 416).

Execute Prim’s minimum spanning tree algorithm by hand on the graph in Figure 8.4(a) [see above], showing how the data structures evolve. Clearly indicate which edges become part of the minimum spinning tree and in what order.

**Start at vertex**.*I*

**Q4** [25 pts.]: [Dijkstra’s shortest-path algorithm] Solve Problem 8.15c from the Baase’s textbook (page 419).

Here is the adjacency list (with edge weights in parentheses) for the digraph shown in Figure 8.13 [see above]:

*A*: *B*(4.0), *F*(2.0)

*B*: *A*(1.0), *C*(3.0), *D*(4.0)

*C*: *A*(6.0), *B*(3.0), *D*(7.0)

*D*: *A*(6.0), *E*(2.0)

*E*: *D*(5.0)

*F*: *D*(2.0), *E*(3.0)

- Execute Dijkstra’s shortest-path algorithm by hand on this graph, showing how the data structures evolve, with
. Clearly indicate which edges become part of the shortest-path tree and in what order.__the starting node__*s*=*D*

**Q5** [20 pts.]: Show the Huffman tree and Encoding Table that results from the following distribution (frequency) of punctuation characters and digits: **colon (59), space (113), newline (40), comma (25), 1 (121), 2 (67), 3 (34), 5 (211), 6 (93)**.