This is the archived website of IC 312 from the Fall 2022 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Homework 10: Graph Search and Compression

Name: _____________________________________________ Alpha: ___________________

Describe help received: ________________________________________________________

Print this page

Due before class on Friday, December 9
This is a written homework - be sure to turn in a hard-copy of your completed assignment at the beginning of class on the deadline.

Consider the graph represented by the following adjacency matrix:
```
    A  B  C  D  E  F  G
A [          4          ]
B [       4       11  3 ]
C [             4  6  1 ]
D [ 2  5                ]
E [ 2              1    ]
F [ 2     3  4          ]
G [       2             ]
```
Remember the “from” vertex is on the left, and the “to” vertex is on the top, so for example there is a directed edge from B to F with length 11.

Run Dijkstra’s algorithm to determine the shortest path from B to D in this graph. Show all of your work neatly, and clearly indicate at the end:
1. The length of the shortest path from B to D
2. The sequence of nodes that forms this shortest path.

Using the same graph as above, run Floyd-Warshall’s algorithm to determine the lengths of the shortest paths between all pairs of vertices in the graph.

Show all of your work and clearly indicate at the end the final matrix of shortest path lengths.

Then answer this question: What pair of nodes in the graph is “farthest apart”, meaning that the shortest path from one node to the other, is the longest shortest path in the entire graph?

Encode the following 16-byte input using LZW:
```
OOPOPAPOPOPAPPPO
```
Show your work and clearly indicate the final encoded sequence. Write the result as a sequence of integers in base 10, like it is in the notes.

(Hint: use an online ASCII table or type man ascii in bash.)
What is the compression ratio for the encoding of the previous problem?

Decode the following sequence of LZW symbols:
```
85 83 65 256 258 257 71 79 263 264 259
```
Show your work and clearly indicate the final decoded sequence.

For the following input:
```
SENSELESSINCONVENIENCE
```
Do two things:
1. Calculate the letter frequencies and come up with a Huffman tree for this input. Show your work and clearly indicate the final tree.
  
  Note: There are over 2000 distinct valid Huffman trees that could be generated with the same frequencies, depending on “ties” in the priority queue and left/right ambiguity. So we will be suspicious if you happen to come up with the exact same tree as your classmates working independently.
2. Determine the number of bits that the input would be encoded into. Do not include the tree in the size of the encoding, just the actual translation of the characters above.
  
  (You do not actually have to write the full encoding, just say how many bits long it would be. You should be able to use your tree to help compute this!)

Decode the following sequence using Huffman. The encoding starts with a representation of the tree as specified in the course notes.
```
001i01t1e001n1v1s11011100110001000101000100001111
```
Show your work! It should decode to a valid English word.

IC 312 Fall 2022 / HWs