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