CIS 675: Algorithms – Spring 2019
Homework 7

Version 1 (8 March 2019)

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.

Reading

Chapters 5 and 6 of DPV

Problems

(12 points) DPV, Problem 5.11.
(12 points) DPV, Problem 5.13.
(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)$ .
(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 constraints over variables and decides whether the constraints can be satisfied.
(20 points) PG, Supplemental Problems, Page 45, Problem 3.
Each part is worth 10 points.

Hint: For (b) use a replacement argument.
(12 points) PG, Problems 395, 396, and 397.

Hint: Each of my answers uses $S=4$ and $n=3$ .
(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}$ .)