University of California, Berkeley - CS 170hw07-sol./ CS 170, Spring 2020 Homework 7 A. Solutions

Document Content and Description Below

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 mu... st explicitly write \none". 2 DP solution writing guidelines Try to follow the following 3-part template when writing your solutions. • Define 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 final DP algorithm? Can the bottomup approach to DP improve the space complexity? 3 No Backtracking Let G = (V; E) be a simple, undirected, and unweighted n-vertex graph, and let AG be its adjacency matrix, defined as follows: AG[i; j] = (1 if there is an edge between 0 otherwise i and j 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 defined as follows: DG[i; j] := ( degree( 0 i) otherwise if i = j 1 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-‘ nonbacktracking walks between i and j. Prove that NB(‘) satisfies the following recurrence relationship. NB(1) = AG NB(2) = A2 G - DG NB(‘) = NB(‘-1) • AG - NB(‘-2) • (DG - I): (c) Given T as input, give an O(T n!)-time dynamic programming-based algorithm to output 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 ). Solution: 2 CS 170, Spring 2020 HW 7 A. Chiesa & J. Nelson 4 Walks in an infinite tree Let Kd+1 be the undirected and unweighted complete graph on vertex set f0; : : : ; dg. Let Td be the undirected infinite 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 infinite 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 first visit walk if v = 2 fw1; : : : ; wtg, i.e., if v is visited for the first time in the last step. Let F(‘) be the number of length-‘ first 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 first step of a u ! v first 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 first visit walk from v0 to u, (3) a first visit walk from u to v. (b) We call a walk u; w1; : : : ; wt; u from u to u a first 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-‘ first 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 (??). (c) Let u be a vertex in Td and let H(‘) denote the number of walks from u to u. Write a recurrence for H(‘) and consequently give a dynamic programming algorithm that takes 3 CS 170, Spring 2020 HW 7 A. Chiesa & J. Nelson in ‘ as input and produces H(‘) as output. Your algorithm should run in O(‘2) time. Your recurrence may also involve the function G defined in part (??). Solution: 5 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 minimized. Give a poly(n)-time dynamic programming-based algorithm that takes in the list 4 CS 170, Spring 2020 HW 7 A. Chiesa & J. Nelson 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. Solution: 6 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 (??) 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 defining the function g(s; i) := Ps t=1 f(t; i). Solution: 5 CS 170, Spring 2020 HW 7 A. Chiesa & J. Nelson 7 Box Union There are n boxes labeled 1; : : : ; n, and initially they are each in their own stack. You want to support two operations: • 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 find(•) and union(•; •) operations in the union find data structure. Hint: use \disjoint forest" and augment nodes to have an extra field z stored. Make sure this field 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 tree’s root if you do a find. Solution: [Show More]

Last updated: 2 years ago

Preview 1 out of 6 pages