# 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 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.

1. and .
2. and .
3. and .
4. and .
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 , you are given:

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

Decide: Is it possible to satisfy all of them?

For instance, the constraints

cannot be satisfied. Given an efficient algorithm that takes as input constraints over 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 and .

7. (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 .)