HW 6

Phipps Garden Subway Problem

Written submission is due in lecture on Wednesday, April 11 2012.

I’m updating this post according to the restatement given in lecture on Friday.

You’re given a map of a subway rail system (planar graph). Each face (except the outer one) of the planar graph is a country with a train that travels around it continuously in the clockwise direction.

All vertices are intersections of track of degree 3. Furthermore, the graph is 2-edge-connected, meaning you can’t delete a single edge and disconnect the graph.

Prove that there is a scheduling algorithm that guarantees no gridlocks and no starvation.

No gridlocks means that trains may only travel in one direction on a rail at one time. No starvation means that every train must make infinitely many trips around its face.

If the planar graph is embedded on a sphere, there’s now an outside country that has a train traveling clockwise. Prove that there is no scheduling algorithm.


HW 5

Due: Wednesday March 7th, 2012 Friday March 9th, 2012

You’re given a splay tree formed by the following sequence of inserts: insert(1, S), insert(2, S), …, insert(n, S). S looks like a linked list n -> n-1 -> … -> 2 -> 1.

Give a sequence of m splay operations that keep the height of S at least \floor{n/2}.

You should end up with a tree that looks like a linked list but is actually 1 -> 2 -> … -> n-1 -> n.

Now, give an explanation as to why this data structure is as good as an ordinary binary search tree given that the tree is always highly unbalanced.


Due: Wednesday, February 15th, 2012

Write a good exam problem. It should be insightful, interesting, and have a short description. It should come with a complete solution.


Due: Wednesday, February 8th, 2012

1) Define a bag-heap to be an unsorted array of positive integers with a pointer to the minimum element. Compare the bag-heap to the Fibonacci heap on all operations supported by the Fibonacci heap.

2) Get tight bounds for the special case of a_i + b_j = c_k problem (3SUM) where:
for i = 0, 1, …, n-1:
a_i = i + e_i: 0 < e_i < 1/4
b_i = i + d_i: 0 < d_i < 1/4
c_i = n + g_i: 0 < g_i < 1/2

Good luck!


HW2 is due in class on Wednesday February 1st, 2012.

1) Show how to create a Binary Heap in O(n) steps.
2) Show how to create a Binomial Heap in O(n) steps.

Good luck. Remember to use the TAs’ office hours. You can also use the comments sections to clarify or discuss the questions.


HW1: Upper and lower bounds on the running time of the 3SUM problem will be due on WED 25 JAN 2012.

3SUM Problem
INPUT: a positive integer n. Three arrays A,B,C, each containing n positive integers. A = [a1,…,an], and similarly for B and C. Integers in an array not necessarily sorted.
OUTPUT: any triple such that a_i + b_j = c_k if such a triple exists; “NONE SUCH” otherwise. Note that if there is more than one triple, only one has to be output.

As mentioned in class, you are to make your bounds as tight as you can make them but no tighter. Remember to say where your ideas came from, including (if it’s the case) from your own head. You will NEVER lose points for good scholarship.

See Lecture 1 for problem description.