CS 330, Spring 2025, Homework 6

Due: March 26th 2025, at 11:59 pm on Gradescope

Collaboration policy Collaboration on homework problems is permitted, you are allowed to discuss each problem with at most 3 other students currently enrolled in the class. Before working with others on a problem, you should think about it yourself for at least 45 minutes.   Finding answers to problems on the Web or from other outside sources (these include anyone not enrolled in the class) is strictly forbidden.

You must write up each problem solution by yourself without assistance, even if you collaborate with others to solve the problem. You must also identify your collaborators. If you did not work with anyone, you should write “Collaborators:  none.”  It is a violation of this policy to submit a problem solution that you cannot orally explain to an instructor or TA.

Typesetting Solutions should be typed and submitted as a PDF file on Gradescope.

Solution guidelines For problems that require you to provide an algorithm, you must provide:

1.  pseudocode and, if helpful, a precise description of the  algorithm in English. As always, pseudocode should include

• A clear description of the inputs and outputs

• Any assumptions you are making about the input (format, for example)

• Instructions that are clear enough that a classmate who hasn’t thought about the prob- lem yet would understand how to turn them into working code.  Inputs and outputs of any subroutines should be clear, data structures should be explained, etc.

If the  algorithm is not clear enough for graders  to understand easily, it may not be graded.

2.  a proof of correctness,

3.  an analysis of running time and space.

You may use algorithms from class as subroutines. You may also use facts that we proved in class.

You should be as clear and concise as possible in your write-up of solutions.

A simple, direct analysis is worth more points than a convoluted one, both because it is simpler and less prone to error and because it is easier to read and understand.

Problem 1. Transporting an Oversized Painting

A famous art museum, the Isabella Stewart Gardner Museum, in Boston is undergoing ren- ovations, and you have been tasked with safely moving various enormous and delicate paintings from between the galleries.  The museum has n rooms connected by corridors, each corridor e ∈ E having a maximum width ce  (think of it as the narrowest point in that corridor).  The corridors are undirected (they are hallways after all!), and all widths ce are distinct.

If you plan a route through several corridors, the clearance of that route is the minimum corridor width along the chosen path (the painting can be no taller or wider than that bottleneck corridor). A maximum-clearance route between two rooms i and j is a route that maximizes this minimum corridor width among all paths from i to j.  Intuitively, it tells you how large an artwork can be transported from i to j without getting stuck in a too-narrow corridor.

You want an algorithm that computes, for a given starting room s, a spanning tree of corridors that ensures maximum-clearance routes from s to all other rooms. You suspect this task is closely related to constructing a maximum spanning tree (MaxST) with corridor widths as edge weights.

Recall:  a maximum spanning tree of a graph G is a subset of edges forming a tree  (i.e., no cycles) that touches all vertices (spanning) while maximizing the sum of its edge weights, in contrast to a minimum spanning tree that would minimize it.

(a)  You will start by stating the cut and cycle property for maximum spanning trees (MaxST).

(a.1)  Recall the cut property of a Minimum Spanning Tree (MinST) states that for any cut of the graph G the minimum weight edge in that cut must be in any possible MinST. Now state the MaxST property.

(a.2)  Recall the cycle property of a MinST states that for all cycles in the graph  G, the maximum weight edge in that cycle can not be in the MST.  Now  state  the  MaxST property.

(b)  Show that in any graph G with unique corridor widths ce, the path given by using edges from the maximum spanning tree of G (with respect to ce) yields the maximum-clearance route between any two rooms.  [Hint:  Try a proof by contradiction:  if there were a strictly better route, combining it with the MaxST edges would form a cycle that contradicts the cycle property from part (a).]

(c)  Give a polynomial-time algorithm that takes a graph G with distinct corridor widths and outputs the maximum spanning tree.  [Hint:  You may modify a standard minimum-spanning-tree algorithm from class.]

(d)  State and justify your algorithm's running time.

(e)  Prove that your algorithm is correct.   [Hint:  If your algorithm indeed returns the MaxST, part (b) applies directly.  So your proof can be an argument you return the MaxST and a reference to your proof of (b).]