CS 6363.004: Algorithms
Spring 2019
Assignment 2
Wed, Feb 13, 2019

You can write or type your answers.  Submit on elearning.

If you submit photos of your written assignment, make sure that they are readable
and all pages are included.  Use lower resolution so that each page is less
than 256 KB.  Submit a single pdf, docx or txt file with all the pages.

Due: 11:59 PM, Sun, Feb 24 (on elearning).


1. Problem 9-2, parts a,b,c (p. 225) [Weighted median].

2. Problem 7-2, part b (p. 186).  Partition into {<x}, {=x}, {>x}.
   Rewrite Quicksort to use this version of partition. No proofs required.

Optional problems (extra credit):

3. Given a stream of N integers (N >> memory), where the number of its distinct
   elements, n, is smaller than the available memory, design an algorithm to find
   the median of the stream.

4. Ex. 9.3-7 (p. 223) [k elements closest to median].