Final Exam Solution
What are the adjacent vertices of in the following graph? Answer: and
Use recursion tree to compute the runtime of the recurrence ( ) = ( & ) + where 1, >0
Q3 (15 points)
Copyright By PowCoder代写 加微信 powcoder
& = 1 =
( ) = + ( $ ) + ( $ 2 ) + … + 1
= + ( $ ) + ( $ 2 ) + … + ( $ $ 1
The height of the tree is roughly
= ( + 1) $ (1 + 2 + … + $ 1) = $ + $ ( $1)
= + $ ( $ ) 2 2
= + 2 2 2
( ) is ( 2). Q4 (15 points)
Given an undirected, connected and weight graph G in which all edge weights are distinct. Prove that the minimum-spanning tree of G excludes the max-weight edge in every cycle.
Let ( , ) be the max-weight edge on some cycle of G and the MST of G.
Proof by contradiction: Assume ( , ) is included in .
By removing the edge ( , ) from , we get two subtrees 1 and 2.
Since ( , ) belongs to some cycle, 1 and 2 can be connected through some edge ( , ) other than
( , ) ( , )
Then 1 + {( , )} + 2 formas a minimum-spanning tree of G and its weight is smaller than .
Contradiction.
So does include ( , ).
Q5 (17 points)
Perform depth-first search on the graph.
Indicate the start time and finish time for each vertex and the classification of each edge.’
Easier to tell why (e, b) and (e,d) are cross edges instead of forward edges if drawn in this way:
Q6 (10 points)
Modify the Bellman-Ford algorithm such that the algorithm might terminate early if there is no negative cycle. Write down the pseudo-code.
BellmanFord(G, s):
Initialize-Single-Source(G, s)
for i = 1 to |V| – 1:
updated = False
for each edge u->v:
if v.d > u.d + w(u,v):
v.d = u.d + w(u, v)
updated = true
if updated == False:
return True
for each edge u->v:
if v.d > u.d + w(u,v):
return False
return True
Q7 (20 points)
Consider the print neatly problem in the homework. We want to print the 4 words
holiday, merry, december, christmas
In the solution, we defined [ ] as the total cost of printing words 1 to (inclusive).
Use the dynamic programming algorithm given in the solution to answer the following questions. (3 points) Compute [0]
(3 points) Compute C[1]
(3 points) Compute C[2]
(3 points) Compute C[3]
(3 points) Compute C[4]
(5 points) How should the 4 words be printed?
[1]= [0]+ [0,1]=0+8 =512
[2] = ( [0] + [0, 2], [1] + [1, 2]) = (0 + 23, 512 + 103) = 8
[3] = ( [0] + [0, 3], [1] + [1, 3], [2] + [2, 3]) = (0 + , 512 + 13, 8 + 73) = 351
[4] = ( [0] + [0, 4], [1] + [1, 4], [2] + [2, 4], [3] + [3, 4]) = (, , , 351 + 0) = 351 Line 1: holiday merry; Line 2: december; Line 3: christmas
neatly and each line can fit at most 15 characters.
[ , ] = & + + 1 & 6 = +1 hadatypointhesolutionanditbecame [ , ]= & + &1&6 .Ifyoudid-1insteadof
The formula for the number of remaining spaces should be = +1 . I
[1]= [0]+ [0,1]=0+63 =216
[2] = ( [0] + [0, 2], [1] + [1, 2]) = (0 + 0, 216 + 83) = 0
[3] = ( [0] + [0, 3], [1] + [1, 3], [2] + [2, 3]) = (0 + , 216 + , 0 + 53) = 125
[4] = ( [0] + [0, 4], [1] + [1, 4], [2] + [2, 4], [3] + [3, 4]) = (, , , 125 + 0) = 125 Line 1: holiday merry; Line 2: december; Line 3: christmas
+1, then your answer should be:
Let = [ , , , ] be an optimal solution to the longest increasing subsequence problem when 12
Q8 (10 points)
the input is an array [1… ] of integers. In other words, 1, 2, …, is a longest possible sequence 1¨ 1 < 2 <...< ¨ [ ]< [ +1]
Prove or disprove: = [ 1 , 2 , ..., &1 ] is a longest increasing subsequence of [1... &1 ]
Disprove. Counter example:
Let [1...6] = [4,1,5,6,5,6] and = [1,5,6].
Then [1...5] = [4, 1, 5, 6, 5] and = [1, 5]. But the longest increasing subsequence of [1...5] [2, 3, 4]
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com