
CSE Home  About Us  Search  Contact Info 
Assignment 1 due Friday, October 8
1. Chapter 1, Number 3, page 22
2. Chapter 1, Number 5, page 24
3. Chapter 1, Number 7, page 26
Assignment 2 due Friday, October 15
1.Chapter 2, Number 4, page 67
2. Chapter 2, Number 6, page 68
3. Chapter 3, Number 4, page 107
4. Chapter 3, Number 9, page 110 (It helps to understand the structure of BFS)
Assignment 3 due Friday, October 22
1. Chapter 4, Number 2
2. Chapter 4, Number 4
3. Chapter 4, Number 5
4. Chapter 4, Number 10
Assignment 4 due Friday, October 29
1. Consider the recurrence T(n) = aT(n/b) + n, T(1) = 0. Solve this recurrence in terms of order of magnitude (big Theta notaton) for the three cases, a < b, a = b, and a > b. For simplicity, you can assume that n is a power of b.
2. Solve the recurrence T(n) = sqrt(n)T(n/sqrt(n)) + n, T(2) = 1 in terms of order of magnitude. For simplicity you can assume all numbers have a square root.
3. Chapter 5, Number 2
4. Chapter 5, Number 5 (Hint: I may be helpful to have your algorithm return the sequence of intersection points of the visible lines in increasing order of x coordinate.)
Assignment 5 due Friday, November 5
1. Consider the algorithm for the knapsack problem described on pages 2712. Design an algorithm that uses the result of that algorithm to find the actual subset that maximizes the value of any subset with total weight less than or equal to W.
2. Chapter 6, Number 6
Assignment 6 due Friday, November 19
1. Chapter 6, Number 27 (Hint: Think that any gas added to the tank is done at the beginning of the day and the storage cost for fuel is also calculated at the beginning of the day before any gas is added. If G gallons are added to the tank that already has F gallons in it then the storage cost for that day is cF. The total cost for that day would be cF + P + the cost of G gallons of fuel. At the beginning of the last day there should be g_n gallons left in the tank and at the end of that day there should be zero gallons left.)
2. Chapter 7, Number 7
3. Chapter 7, Number 8
Assignment 7 due Wednesday, November 24
1. Chapter 7, Number 20(a)
2. Chapter 8, Number 2 (part of the solution is reducing a problem like Independent Set to Diverse Subset)
Assignment 8 due Friday, December 3
1. Chapter 8, Number 4
2. Chapter 8, Number 26
Assignment 9 from Chapter 7 from Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
for discussion only on Friday, December 10th
1. 7.1
2. 7.3
3. 7.7
4. 7.12
Chapter 1
Introduction
Stable Matching
Demo of Propose and Reject Algorithm
Practice Propose and Reject Algorithm
Chapter 2
Basics of Algorithm Analysis
Chapter 3
Graph Algorithms
Topological Sort Example
Practice Topological Sort
Chapter 4
Greedy Algorithms
Interval Scheduling Example
Dijkstra's Algorithm Example
Extra Slides (coin changing and selecting breakpoints)
Minimum Spanning Tree Algorithms
Chapter 5
Divide and Conquer
Merge and Invert Example
Fast Fourier Transform
Chapter 6
Dynamic Programming
BellmanFord Algorithm
Optimal Stream Merging for Media on Demand
Chapter 7
Network Flow
FordFulkerson Demo
Applications of Network Flow
Chapter 8
Polynomial Time Reducibility
NPCompleteness
More Polynomial Time Reductions
Linear Programming
Introduction to Linear Programming
Contiguous Ordering and PQtrees
Contiguous Ordering  PQ Trees
Final: Monday, Dec. 13, 2010, 2:304:20 p.m.
Final Exam Study Guide
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 981952350 (206) 5431695 voice, (206) 5432969 FAX [comments to ladner] 