Computer Science 284/484

Homework

Spring 2009

Homework 1
Due Thursday 1/29 in class
  • MU 3.1, 3.3, 3.14, 3.20
  • Show that running Randomized Median until it finds an answer has expected running time linear in n.
  • MU 4.10
Homework 2
Due Thursday 2/12 in class
  • CLRS: 26.2-4, 26.2-9, 26-1, 26-2
  • CLRS: 28.1-3, 28.1-6, 28.1-10
Homework 3
Due Thursday 2/26 in class
  • CLRS: 28.3-4, 28.3-5
  • CLRS: 29.1-4, 29.1-5, 29.1-6, 29.1-7, 29.1-8, 29.1-9, 29.3-6, 29.4-5
Homework 4
Due Tuesday 3/17 in class
  • CLRS: 30.2-6, 30.2-8, 30-6
Homework 5
Due Thursday 4/9 in class
  • CLRS: 31.1-5, 31.1-6, 31.6-3, 31.8-3
Homework 6
Due Tuesday 4/28 in class
  • CLRS: 33.3-1, 33.3-2, 35.1-4, 35.2-3, 35.4-2

gildea @ cs rochester edu
April 21, 2009