Problem 1 Fewer Routes with 3 hops

Your second homework asked you to construct a Θ(n log n)-segment NorthSouth route system (i.e., all of the routes in the system are only allowed to move from i to j > i) that allows any commuter to get from stop i to j using at most 2 segments.

In this problem, we design a new North-South system that allows any commuter to get from stop i to j > i in at most 3 “hops", but only requires Θ(n log log n) segments. Hint: the basic idea is to divide the n stops into groups of size d √ n e. Build a system for these groups recursively so that any travel entirely within these groups can be accomplished in 3 hops. In addition, each group has designated “hubs" which have both incoming and out-going segments to other stops. It is then possible to add Θ(n) segments to and from these hubs so that a person can get from any stop i to any stop j within another group using at most 3 route segments. Note: these extra routes cannot start at a node j and go backwards to a node i < j.

(a) Fully describe this scheme. Clearly specify how to add the Θ(n) segments to implement the 3-hop property in your route system.

(b) State a recurrence that counts the segments required by your route system.

(c) Prove a tight upper bound on your recurrence using induction.