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

(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 with positive edge weights, and a minimum spanning tree with respect to these weights; you may assume and are given as adjacency lists. Now suppose the weight of a particular edge is modified from to a new value . You wish to quickly update the minimum spanning tree 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.

- and .
- and .
- and .
- and .

(12 points) DPV. Problem 5.26.

*Hint:*Union-find.Here is a problem that occurs in automatic program analysis. For a set of variables , you are given:

- some
*equality*constraints, of the form “” and - some disequality constraints, of the form “”.

For instance, the constraints**Decide:**Is it possible to satisfy all of them?- some
(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 and .(12 points) DPV Problem 6.1.

*Note:*A continuous subsequence maximum sum ending exactly at position must include in the sum. (*Hint:*But the sum might not include .)