Final Review Questions - Set 2

1. Figure 1 represents a directed graph in an adjacency list format. The adjacency lists actually list the vertices in the successor vertex sets, Succ(x) for each vertex x in the graph G. For example, the successors of vertex 1 are those is the set Succ(1) = {2,3}, meaning there are directed edges from vertex 1 to vertices 2 and 3. Describe how to compute lists of the predecessor vertices, Pred(x) for each x in the graph G, starting with an adjacency matrix, T[i,j] for G.

   Figure 1

   Vertex Number	Adjacency List
   1	2, 3
   2	3, 4, 5
   3	4
   4
   5	1

2. Draw the Huffman coding tree for the character frequencies in Figure 2.

   Figure 2

   Character	A	B	C	D	E	F	G
   Frequency	7	3	8	10	1	2	6

3. Figure 3 is a table of mileage distances between 7 cities. Suppose you want to build a pipeline that links all these cities using the minimum amount of pipe. List the city-pairs that would be linked in building this pipeline.

   Figure 3

   City	Denver	Salt Lake	Albuquerque	Oklahoma City	Cheyenne	Omaha
   Salt Lake	512
   Albuquerque	422	611
   Oklahoma City	615	1108	525
   Cheyenne	102	462	522	706
   Omaha	540	955	895	454	493
   Dodge City	301	682	425	212	355	336

4. 1. Explain how to modify Dijkstra's algorithm to produce a count of the number of different minimum paths from v to w.

   2. Explain how to modify Dijkstra's algorithm so that if there is more than one minimum path from v to w, a path with the fewest number of edges is chosen.