### **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.

Course Home Page

cole@cs.nyu.edu (Richard Cole)

Last modified: Apr 3, 1997