CIS 675: Algorithms – Spring 2019
Homework 7

Version 1   (8 March 2019)




  1. (12 points) DPV, Problem 5.11.

  2. (12 points) DPV, Problem 5.13.

  3. (20 points) DPV, Problem 5.23.
    Each part is worth 5 points.

    You are given a graph G=(V,E) with positive edge weights, and a minimum spanning tree T=(V,E') with respect to these weights; you may assume G and T are given as adjacency lists. Now suppose the weight of a particular edge e\in E is modified from w(e) to a new value w_*(e). You wish to quickly update the minimum spanning tree T to reflect this change, without recomputing the entire tree from scratch. There are four cases. In each case give a linear-time algorithm for updating the tree.

    1. e\notin E' and w_*(e)>w(e).
    2. e\notin E' and w_*(e)<w(e).
    3. e\in E' and w_*(e)<w(e).
    4. e\in E' and w_*(e)>w(e).
  4. (12 points) DPV. Problem 5.26.

    Hint: Union-find.

    Here is a problem that occurs in automatic program analysis. For a set of variables x_1,\dots,x_n, you are given:

    • some equality constraints, of the form “x_i=x_j” and
    • some disequality constraints, of the form “x_i\not=x_j”.

    Decide: Is it possible to satisfy all of them?

    For instance, the constraints

    x_1 = x_2,\, x_2 = x_3,\, x_3 = x_4,\, x_1 \not= x_4

    cannot be satisfied. Given an efficient algorithm that takes as input m constraints over n variables and decides whether the constraints can be satisfied.
  5. (20 points) PG, Supplemental Problems, Page 45, Problem 3.
    Each part is worth 10 points.

    Hint: For (b) use a replacement argument.

  6. (12 points) PG, Problems 395, 396, and 397.

    Hint: Each of my answers uses S=4 and n=3.

  7. (12 points) DPV Problem 6.1.

    Note: A continuous subsequence maximum sum ending exactly at position j must include a_j in the sum. (Hint: But the sum might not include a_{j-1}.)