20-CS-472-001 Design and Analysis of Algorithms II Winter 2011

## Analysis

Due: xxx, 2011

1. A glob is an entity that can be attached to at most one other glob. A glob that is not attached to any other glob is said to be a terminal glob. For any glob g, one may trace a globular path from g through attached globs to a terminal glob; the number of globs traversed in a globular path from glob g is defined to be the length of the globular path of g (for example, if g is a terminal glob then its globular path has length 1, if glob a is attached to glob b and b to c and c is terminal then the globular path of a has length 3). All the globs which have a globular path ending at the same terminal glob are said to be in the same globular cluster. Globular clusters may be combined ONLY as follows: attach the terminal glob of the smaller (fewer globs) cluster to the terminal glob of the larger.

Start with n terminal globs (each by itself is a globular cluster). Now, repeatedly pick two globular clusters and combine them. Show by induction that the longest globular path is always less than O(log(n)) in length.

2. Alice flips one fair coin. Bob flips two fair coins. What is the probability that Alice obtains more heads than Bob.

3. A packet switch is designed to send packets from LAN clients to the internet. The switch can send one packet at a time and the duration of transmission is t seconds. At the front end of the switch is a queue which holds packets for transmission. A packet is always placed at the end of the queue where it waits, first-come first-serve, until the switch is ready to process it. Anytime the switch is idle and the queue is not empty, it leaves the idle state, and removes from the queue and processes the first (head) packet. After processing, the switch returns to the idle state. The minimum time the switch can be idle is d second. Assume the switch receives packets at random (constant probability that a new packet appears from a client for transmission every instant) at a rate of w packets per second and that it responds as fast as possible to any packet waiting in the queue. What is the average delay seen by a packet before it gets to the internet? What is the probability that the delay is more than r seconds?

4. What is the maximum number of inversions that can be removed from a permutation of size n by the interchange of a single pair of elements. Show an example of such.

5. Given a list of integers L[1:n] where adjacent elements in the list differ by at most one and L[1] < L[n].
1. Design and analyze an algorithm that finds an index j such that L[j]=X for a given search element X where L[1] < = X < = L[n].
2. Determine the lower bound for the worst-case complexity of this problem. Is your algorithm optimal?