本次Java代写是完成数据结构中的二叉树和有向图等相关的程序

CS 2c03 Assignment #3.

1.[5] a.[3] 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.[2] Represent the graph below as adjacency matrix.

2.[6] a.[3] 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.[3] Also, draw the tree represented by edgeTo[].

3.[6] a.[3] 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.[3] Also, draw the tree represented by edgeTo[].

2

4.[10] 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.[5] a.[3] 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.[2] Represent the graph below as adjacency matrix.

6.[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.[6] 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.[8] Show that if a graph’s edges all have distinct weights, the Minimum Spanning Tree is

unique, but not vice versa.

9.[12] Consider the graph below.

3

a.[4] Find Minimum Spanning Tree using Greedy Algorithm. Show all steps.

b.[4] Find Minimum Spanning Tree using Kruskal’s Algorithm. Show all steps.

c.[4] Find Minimum Spanning Tree using Prim’s Algorithm. Show all steps.

10.[8] 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[7] 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.[10]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.[7] 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.[12]a.[4] 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.[4] 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.[4] 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.[8] 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.[8] 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.[8] 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.[8] 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.[5] 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.[8] 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.[9] 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

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** [email protected] **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。