数据结构与算法|动态规划DP|

CS 170, Spring 2020 HW 7 A. Chiesa & J. Nelson

CS 170 HW 7

Due 2020-3-9, at 10:00 pm

1 Study Group

List the names and SIDs of the members in your study group. If you have no collaborators,

you must explicitly write none.

DP solution writing guidelines

Try to follow the following 3-part template when writing your solutions.

• Dene a function f() in words, including how many parameters are and what they

mean, and tell us what inputs you feed into f to get the answer to your problem.

• Write the \base cases” along with a recurrence relation for f.

• Prove that the recurrence correctly solves the problem.

• Analyze the runtime and space complexity of your nal DP algorithm? Can the bottom-

up approach to DP improve the space complexity?

2 No Backtracking

Let G = (V;E) be a simple, undirected, and unweighted n-vertex graph, and let AG be its

adjacency matrix, dened as follows:

AG[i; j] =

(

1 if there is an edge between i and j

0 otherwise

We call a sequence of vertices W = (u0; u1; : : : ; u`) a walk if for every i < `, fui; ui+1g is an

edge in E, and we call ` the length of W. Call a walk nonbacktracking if for every i < ` 􀀀 1,

ui 6= ui+2, i.e., the walk does not traverse the same edge twice in a row. In this problem,

we will see a dynamic programming-based algorithm to compute the number of length-`

nonbacktracking walks in G between every pair of vertices.

(a) Prove that A`

G[i; j] = # of length-` walks from i to j.

(b) Let I be the identity matrix (diagonal matrix of all-ones), DG be the degree matrix of

G, i.e., the matrix dened as follows:

DG[i; j] :=

(

degree(i) if i = j

0 otherwise

CS 170, Spring 2020 HW 7 A. Chiesa & J. Nelson

and let NB(`) be the matrix such that NB(`)[i; j] contains the number of length-` non-

backtracking walks between i and j. Prove that NB(`) satises the following recurrence

relationship.

NB(1) = AG

NB(2) = A2

G 􀀀 DG

NB(`) = NB(`􀀀1) AG 􀀀 NB(`􀀀2) (DG 􀀀 I):

NB(T) where n! is the time it takes to multiply two n n matrices and ! 2.

(d) (Cool problem but worth no points) Given T, give a O(n3 log T)-time algorithm to output

NB(T).

3 Walks in an innite tree

Let Kd+1 be the undirected and unweighted complete graph on vertex set f0; : : : ; dg. Let Td

be the undirected innite tree with vertex and edge set

Vd = fW : W is a nonbacktracking walk starting at 0 in Kd+1g

Ed = ffW;W0g : W0 = (W; u) for some u 2 Kd+1g:

Figure 1: Finite piece of 3-regular innite tree

Let u be an arbitrary vertex of Td. In this problem, we will see a dynamic programming-based

algorithm to compute the number of walks in Td from u to u.

(a) Let u and v be two vertices in Td such that fu; vg is an edge. Call a walk u;w1; : : : ;wt; v

from u to v in Td a rst visit walk if v =2 fw1; : : : ;wtg, i.e., if v is visited for the rst time

CS 170, Spring 2020 HW 7 A. Chiesa & J. Nelson

in the last step.

Let F(`) be the number of length-` rst visit walks from u to v. Write a recurrence for

F(`) and consequently give a dynamic programming algorithm that takes in ` as input

and produces F(`) as output. Your algorithm should run in O(`2) time.

Hint: Suppose in the rst step of a u ! v rst visit walk, u steps to v0 6= v, the walk can

be decomposed into 3 parts: (1) a single step from u to v0, (2) a rst visit walk from v0

to u, (3) a rst visit walk from u to v.

(b) We call a walk u;w1; : : : ;wt; u from u to u a rst revisit walk if u =2 fw1; : : : ;wtg, i.e.,

if the only times u is visited are at the start and the end. Let G(`) be the number of

length-` rst visit walks from u to u. Give an O(`2)-time algorithm that takes in ` as

input and computes G(`).

Hint: You may want to use the algorithm from part (a).

recurrence for H(`) and consequently give a dynamic programming algorithm that takes

in ` as input and produces H(`) as output. Your algorithm should run in O(`2) time.

Your recurrence may also involve the function G dened in part (b).

4 GCD annihilation

Let x1; : : : ; xn be a list of positive integers given to us as input. We repeat the following

procedure until there are only two elements left in the list:

Choose an element xi in fx2; : : : ; xn􀀀1g and delete it from the list at a cost equal to the

greatest common divisor of the undeleted left and right neighbors of xi.

We wish to make our choices in the above procedure so that the total cost incurred is min-

imized. Give a poly(n)-time dynamic programming-based algorithm that takes in the list

x1; : : : ; xn as input and produces the value of the minimum possible cost as output. You may

assume that we are given an n n sized array where the i; j entry contains the GCD of xi

and xj , i.e., you may assume you have constant time access to the GCDs.

5 Counting Targets

We call a sequence of n integers x1; : : : ; xn valid if each xi is in f1; : : : ;mg.

(a) Give a dynamic programming-based algorithm that takes in n;m and \target” T as input

and outputs the number of distinct valid sequences such that x1 + + xn = T. Your

algorithm should run in time O(m2n2).

(b) Give an algorithm for the problem in part (a) that runs in time O(mn2).

Hint: let f(s; i) denotes the number of length-i valid sequences with sum equal to s.

Consider dening the function g(s; i) :=

t=1 f(t; i).

6 Box Union

There are n boxes labeled 1; : : : ; n, and initially they are each in their own stack. You want

to support two operations:

CS 170, Spring 2020 HW 7 A. Chiesa & J. Nelson

• put(a; b): this puts the stack that a is in on top of the stack that b is in.

• under(a): this returns the number of boxes under a in its stack.

The amortized time per operation should be the same as the amortized time for nd() and

union(; ) operations in the union nd data structure.

Hint: use \disjoint forest” and augment nodes to have an extra eld z stored. Make sure

this eld is something easily updateable during \union by rank” and \path compression”, yet

useful enough to help you answer under() queries quickly. It may be useful to note that your

algorithm for answering under queries gets to see the z values of all nodes from the query

node to its trees root if you do a nd.

Published by admin

Leave a Reply Cancel reply