# Programming Problems 15

April 8, 2010 Leave a comment

1. In the shortest-path algorithm we are concerned with the total length of the path between a source and every other node. Suppose instead that we are concerned with the length of the longest edge between the source and every node. That is, the bottleneck of a path is defined to be the length of the longest edge in the path. Design an efficient algorithm to solve the single source smallest bottleneck problem; i.e. find the paths from a source to every other node such that each path has the smallest possible bottleneck.

2. Consider the shortest paths problem in the special case where all edge costs are non-negative integers. Describe a modification of Dijkstra’s algorithm that works in time O(|E|+|V|m), where m is the maximum cost of any edge in the graph.

3. Suppose you are given a weighted graph G = (V,E) and an edge e (belongs to) E. You are asked whether e is in some minimum spanning tree of G. Give a linear time algorithm for the problem.

4. A challenge that arises in databases is how to summarize data in easy-to-display formats, such as a histogram. A problem in this context is the minimal imbalance problem. Again suppose we have an array A containing n numbers, this time all positive, and another input k. Consider k indices j1, j2, . . . jk that partition the array into k+1 subarrays A[1, j1],A[j1 + 1, j2], . . . ,A[jk + 1, n]. The weight w(i) of the ith subarray is the sum of its entries. The imbalance of the partition is

That is, the imbalance is the maximum deviation any partition has from the average size. Give an algorithm for determining the partition with the minimal imbalance given A, n, and k. (This corresponds to finding a histogram with k breaking points, giving k + 1 bars, as close to equal as possible, in some sense.)

5. Let P be a convex polygon with n vertices. A diagonal is a line segment that connects two vertices of P and lies in the interior of P. A decomposition of P into triangles by a maximal set of non-intersecting diagonals is called a triangulation of the polygon. Describe a O(n3) time algorithm to compute a triangulation of P such that the sum of the lengths of the diagonals included in the triangulation is minimized.

6. A palindrome is any string that is exactly the same as its reverse, e.g. I, DEED,RACECAR. Any string can be decomposed into a sequence of palindromes. For example, the string BUBBASEESABANANA (Bubba sees a banana) can be broken into plaindromes in many ways;here are a few examples:

BUB + BASEESAB + ANANA

B+U+BB+A+SEES+ABA+NAN+A

B+U+BB+A+SEES+A+B+ANANA

Describe and analyze an efficient algorithm to find the smallest number of palindromes into which an input string can be decomposed. The algorithm should return the sequence of palindromes into the resulting decomposition.

## Recent Activity