CSE logo University of Washington Computer Science & Engineering
 CSE 421 - Introduction to Algorithms - Autumn 2010
  CSE Home   About Us    Search    Contact Info 

Instructor:

Teaching Assistants:

Meeting Times:

MWF, 1:30-2:20 pm, Johnson 111

CSE 421 Discussion Board

Use the discussion board to ask questions and consult with instructors and each other about the homework and anything else related to class.

CSE 421 E-mail Announcements

We will periodically send out important information via email to the course email group. All registered students are on the e-mail list with their UWNet ID e-mail box. If you want your messages forwared to your private e-mail address then go to MyUW to forward your e-mail. You may look at the mailing list archive to find past e-mails. If you have a homework question or some other topic that you'd like to discuss with your fellow students, the instructor, or TA, do so on the course discussion board (described below).

Assignments

Assignments are due each Friday at the beginning of class (late assignments not accepted without prior approval). Start each homework solution on a new page.

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 271-2. 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

Reading

9/27/10 - 10/03/10 Chapter 1
10/4/10 - 10/10/10 Chapter 2, 3
10/11/10 - 10/17/10 Chapter 4
10/18/10 - 10/24/10 Chapter 5
10/25/10 - 10/31/10 Chapter 6
11/1/10 - 11/7/10 Continue Reading Chapter 6
11/8/10 - 11/14/10 Chapter 7
11/15/10 - 11/21/10 Chapter 8
11/22/10 - 11/28/10 Continue Reading Chapter 8
11/29/10 - 12/05/10 Continue Reading Chapter 8
12/6/10 - 12/12/10 Chapter 11, Section 6 and Chapter 7 from Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

Lectures

Lecture notes are provided by the publisher.

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
Bellman-Ford Algorithm
Optimal Stream Merging for Media on Demand

Chapter 7
Network Flow
Ford-Fulkerson Demo
Applications of Network Flow

Chapter 8
Polynomial Time Reducibility
NP-Completeness
More Polynomial Time Reductions

Linear Programming
Introduction to Linear Programming

Contiguous Ordering and PQ-trees
Contiguous Ordering - PQ Trees

Textbook

Algorithm Design by Jon Kleinberg and Eva Tardos
Pearson / Addison Wesley, 2006

Exams

Midterm: Friday, November 5, 2010
Midterm Study Guide

Final: Monday, Dec. 13, 2010, 2:30-4:20 p.m.
Final Exam Study Guide

Algorithms Resources

These resources may be helpful in your studies.

Grading


CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to ladner]