CSE 421 - Introduction to Algorithms - Autumn 2010
 CSE Home About Us Search Contact Info

### 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

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 2
Basics of Algorithm Analysis

Linear Programming
Introduction to Linear Programming

Contiguous Ordering and PQ-trees
Contiguous Ordering - PQ Trees

### Textbook

Algorithm Design by Jon Kleinberg and Eva Tardos

### Exams

Midterm: Friday, November 5, 2010
Midterm Study Guide

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