# Java代写 | CS 2c03 Assignment #3.

CS 2c03 Assignment #3.

1. a. Draw, in the style of the figure in the text (page 524), the adjacency lists built by
Graph’s input stream constructor for the file tinyGex2.txt depicted below.
b. Represent the graph below as adjacency matrix.
2. a. Show, in the style of the figure on page 533, a detailed trace of the call dfs(0) for
the graph built by Graph’s input stream constructor for the file tinyGex2.txt and
graph above.
b. Also, draw the tree represented by edgeTo[].
3. a. Show, in the style of the figure on page 533, a detailed trace of the call bfs(0) for
the graph built by Graph’s input stream constructor for the file tinyGex2.txt and
graph above.
b. Also, draw the tree represented by edgeTo[].
2
4. Prove the following, known as the cycle property: Given any cycle in an edge weighted
graph (all edge weights distinct), the edge of maximum weight in the cycle
does not belong to the Minimum Spanning Tree of the graph.
5. a. Draw, in the style of the figure in the text (page 524), the adjacency lists built by
Digraph’s input stream constructor for the file tinyDGex2.txt depicted below.
b. Represent the graph below as adjacency matrix.
6. Consider the connected graph above that has the set of vertices V={0,2,5,6,3,10}. Find all
its strongly connected components. Use Kosaraju-Sharir algorithm. Illustrate all steps.
7. Consider the DAG below:
Assume that the order of vertices on the list of adjacent vertices is the alphabetical order.
For example the list of adjacent vertices for the vertex m looks as follows:
m → q → r → x
Provide topological order for the above DAG.
8. Show that if a graph’s edges all have distinct weights, the Minimum Spanning Tree is
unique, but not vice versa.
9. Consider the graph below.
3
a. Find Minimum Spanning Tree using Greedy Algorithm. Show all steps.
b. Find Minimum Spanning Tree using Kruskal’s Algorithm. Show all steps.
c. Find Minimum Spanning Tree using Prim’s Algorithm. Show all steps.
10. Consider the weighted directed graph below.
Use the Dijkstra’s algorithm to find the shortest paths from a to the other vertices. Assume that
the order of vertices on the list of adjacent vertices is the alphabetical order.
Also construct the P array (recovering the paths) step by step. Recover all paths.
Assume the list of adjacent vertices implementation and with alphabetic ordering of each list.
Use heap to implement the set V– S. Show all steps.
11 Consider the weighted graph with negative weights below.
Use the Bellman-Ford algorithm to find the shortest paths from a to the other vertices.
Show all steps.
4
12.The diameter of a digraph is the length of the maximum-length shortest path connecting
two vertices. Write a DijkstraSP client that finds the diameter of a given
EdgeWeightedDigraph that has nonnegative weights.
13. Consider the weighted directed acyclic graph below.
Topological sort has already been applied and the result is: r, s, t, x, y, z.
Apply the second part of the algorithm for the shortest paths in DAGs, and find all shortest paths
from the source r.
14.a. Give a trace for LSD string sort for the keys:
no is th ti fo al go pe to co to th ai of th pa
b. Give a trace for MSD string sort for the keys:
no is th ti fo al go pe to co to th ai of th pa
c. Give a trace for MSD string sort for the keys:
now is the time for all good people to come to the aid of
15. Draw the R-way trie that results when the keys:
now is the time for all good people to come to the aid of
are inserted in that order into an initially empty trie (do not draw null links).
16. Consider the pattern P = abbababaaabab and the string
S = abaababaababbababaaababaabaababb
Compute the failure function for P, and then use Knuth-Morris-Pratt algorithm, as
described in Lecture Notes 18, to verify if P appears in S. Show all steps. How many
character comparisons are required by the KMP algorithm?
17. Consider the pattern P = a b a c a b and the string
S = b a c a a b a c c a b a c a b a a b b
Use Boyer-Moore algorithm to verify if P appears in S. Show all steps. How many
character comparisons are required by the Boyer-Moore algorithm?
5
18. Consider the pattern P = a b a c a b and the string
S = b a c a a b a c c a b a c a b a a b b
Assume the following numerical codes for the letters a, b, and c, code(a)=1, code(b)=2,
and code(c)=3, so the pattern P = a b a c a b is represented by the number 121312.
Use Rabin-Karp algorithm to verify if P appears in S. Use modular hashing with R = 10
and hash(s) = s mod 997 (as in the textbook and lecture notes). How many character
comparisons are required by the Rabin-Karp algorithm?
19. Consider the four variable-length codes shown in the table below. Which of the codes are
prefix-free? Uniquely decodable? For those that are uniquely decodable, give the
encoding of 1000000000000.
20. In the style of the figure in the text, show the Huffman coding tree construction process
when you use Huffman for the string “it was the age of foolishness”. How many bits does
the compressed bitstream require?
21. What is the LZW encoding of the following inputs?
a. T O B E O R N O T T O B E
b. Y A B B A D A B B A D A B B A D O O
c. A A A A A A A A A A A A A A A A A A A A A E-mail: [email protected]  微信:itcsdx 