### Homework 9, Randomized Algorithms

Due date: May 10.

All references are to the course text.

1. Consider applying Valiant's randomized routing scheme on the butterfly network with wraparound. Suppose there are at most C >= log N packets to be routed from each input node, with at most C >= log N packets going to each output node. So in Phase 1, each packet is routed to a random output; in phase 2, each packet is routed to its actual destination. Show that with probability at least 1-1/N^c there are at most dcC packets going through any given vertex, where d is a constant, and c>=1 is arbitrary.

2. This problem continues Problem 1. Show how to assign random ranks so that packets in Phase 2 do not interfere with packets in Phase 1. Hence conclude that the greedy routing with random ranks in conjunction with Valiant's randomized routing of <=C packets per input and output node takes O(C) time with high probability, for C>= log N, on a butterfly network with wraparound assuming unbounded queues. Show the same result holds for Ranade's algorithm used in conjunction with Valiant's randomized routing.

cole@cs.nyu.edu (Richard Cole)