Algorithms Core 15-750  PROBLEM SET # 3  Spring 1999

DUE: 1:00PM Wednesday March 3 1999

1 Backwards Analysis for Quicksort

Consider the following randomized version of quicksort: Given an array of n keys as input, it first picks a pivot element at random from among the n keys. It then reorders the keys so that those less than the pivot are first, followed by those equal to the pivot, followed by those greater than the pivot. It does this by comparing the pivot with each of the n−1 other elements. It then recursively sorts the stuff less then the pivot and the stuff greater than the pivot.

(a) Suppose that the n keys to be sorted are distinct. Using backwards analysis show that the expected number of comparisons done by this version of quicksort is at most 2n(H_{n} − 1). (Here H_{n} is the nth harmonic number, which satisfies H_{n} = ln n + γ + o(1), and γ is Euler’s constant γ = .57721 · · ·.

(b) (Optional) Show a lower bound on the expected number comparisons of

2n ln n − O(n)

Hint: Modify the algorithm (without changing the expected number of comparisons) by capturing all of the randomness of the algorithm in a random permutation, A = a_{1}, …, a_{n} of the keys. In the forward direction the algorithm runs through the keys a_{1}, a_{2}, …, a_{n} sequentially, using each of these in turn as a pivot element within the appropriate sub-array. You may also assume that the input is sorted since this does not change the number comparisons performed.

2 Hamiltonian Planar Graphs

Let G = (V, E) an undirected graph with no multiple edges or self-loops. A simple cycle in G is called Hamiltonian if includes every vertex of G.

A graph G is called 3-regular if every node has degree 3.

Give an O(n) time algorithm takes as input a 3-regular graph G and a Hamiltonian cycle in G, and determines if the graph G is planar.

Note: An edge e with respect to a simple cycle C is called a cord if it is not an edge of C but both of its nodes are on C. Thus, this problem boils-down to the following problem: Given a simple cycle of size n and a collection of cords determine if the cords can be embedded with no crossing using either the outside face or the inside face.

Hint: Suppose the vertices are on the cycle in order are v_{1}, …, v_{n}. Let V_{i} be the vertices v_{1}, …, v_{i} and E_{i} be the edges from V_{i} to V − V_{i} not including the edge from v_{n} to v_{1}. Give a data structure which represents all possible arrangements of the edges in E_{i} as we consider all planar embeddings of G restricted to V_{i}.

3 Series-Parallel Graphs

A directed acyclic graph G with two distinguished vertices s, t is a series-parallel graph if it is obtained from the following inductive definition:

1. The graph consisting of a single edge from s to t is series-parallel.

2. If G = (V, E, s, t) and G′ = (V′, E′, s′, t′) are series-parallel then

(a) [parallel] the new graph obtained by identifying s with s′ and t with t′ is series-parallel (with distinguished vertices s and t)

(b) [series] the new graph obtained by identifying t with s′ is series-parallel (with distinguished vertices s and t′)

We extend the notion of an f(n)-separator to directed graphs simply by ignoring the directions of the edges and applying the standard definition for undirected graphs.

Show that every series-parallel graph has a 2-separator. Also give an O(m + n) time algorithm to find this separator in a graph of n vertices and m edges. You may assume that the series-parallel graph is given to you with its underlying “parse tree”.

4 3-Coloring planar Graphs

Give an O(2^{c\sqrt{n}}) time algorithm to 3-color a planar graph, where c is some fixed constant.

Hint: Use the Planar Separator Theorem.