Using Huffmans algorithm, construct an optimal prefix code tree for the following letters and frequencies. Show each step of the algorithm (similar to Fig 16.5, page 432 in the book).
letter b a t o l f s
frequency 1 13 2 5 8 10 3
Using the optimal prefix encoding you found in Problem 1a, encode each string.
fat = _______________________________________
lab = _______________________________________
falls = _______________________________________
Using the optimal prefix encoding below, decodeeach encoded string.
letter a o t b s f l
variable-length codeword 000 001 01 100 101 110 111
11000100101 =______ ______ ______ ______ ______ ______ ______
10000001101 = ______ ______ ______ ______ ______ ______ ______
100000111111 = ______ ______ ______ ______ ______ ______ ______
Representeach of the graphs below using both adjacency-list representation and adjacency-matrix representation. See image.
For the given adjacency-matrix representation below, draw a directed graph.
u v x w
u 0 0 1 0
v 0 1 0 1
x 1 1 0 0
w 1 0 0 1
For the given adjacency-list representation below, draw anun-directed graph.
u x /
v x w /
x v u /
w v /
Examine the BFS algorithm (page 595). Argue that the algorithms correctness does not change, even if we delete line 18 and never set any nodes color to BLACK.
Show the discovery(on left) and finishing(on right) times of each vertex of the graph below after running the DFS algorithm (page 604) on the graph. Do not show intermediate steps -- only show the final result. See image.