CIS 675: Algorithms – Spring 2019 Homework 7

Abbreviations

• DPV = Algorithms, by S. Dasgupta, C. Papadimitriou, and U. Vazirani, McGraw-Hill, 2007.
• PG = Problems on Algorithms, 2/e, by Ian Parberry and William Gasarch.

• Chapters 5 and 6 of DPV

Problems

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).
3. $e\in E'$ and $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}$.)