CSE 521: Algorithms, Spring 2003

University of Washington Department of Computer Science & Engineering

CSE Home

About Us

Contact Info

Instructor:

Richard E. Ladner (ladner@cs.washington.edu)
Office: Sieg 311, 543-9347

Teaching Assistant:

Gidon Shavit (gidon@cs.washington.edu)
Office: Chateau 109B

Meeting Times:

Tuesday and Thursday, 9:00 - 10:20, MGH 074

CSE 521 E-mail Group

Go to CSE 521 e-mail. The main purpose of the e-mail group is to post announcements from the instructors.

Assignments are due on Tuesday (late assignments not accepted without prior approval).

Assignment 1, due Tuesday, April 8 (solution outline)
Assignment 2, due Tuesday, April 15 (solution outline)
Assignment 3, due Tuesday, April 22 (solution)
Assignment 4, due Tuesday, April 29 (solution)
Assignment 5, due Tuesday, May 6 (solution)
Assignment 6, due Tuesday, May 13 (solution)
Assignment 7, due Tuesday, May 20 (solution)
Assignment 8, due Tuesday, May 27 (solution)
Assignment 9, due Tuesday, June 3 (solution)

Projects

Project Description

Thursday, June 5, 3:30 - 5:00, MGH 271
3:30 - Luna Dong and Peter Young - Topological Optimization in a Peer Data Management System
4:00 - Tal Shaked and Parag - Theoretical and Practical Aspects of Boosting in Machine Learning
4:30 - Xu Miao and Lin liao - VC Dimension and its Application in Machine Learning
Thursday, June 12, 10:30 - 12:30, Sieg 134
10:30 - Alex Lindblad and Ian Simon - Computing the Voronoi Diagram of a Set of Line Segments
11:00 - Paul Gauthier and Michael Ringenburg - Applications of Min-Cut/Max-Flow Algorithms to Problems in Computer Vision
11:30 - Stevan Parikh and Krzysztof Gajos - Boosting in Machine Learning
12:00 - Keith Grochow and Neva Cherniavski - Floodlight Illumination Algorithms and Open Problems
Friday, June 13, 10:30 - 11:30, Sieg 134
10:30 - Adam Fuchs and Ioannis Giotis - The Search for Better Exponential Bounds for k-SAT, How They're Achieved and Why it Matters
11:00 Mirco Stern and Evan Welbourne - Feasibility Analysis of Optimal Static Distributed Scheduling Algorithms

Reading

3/31 - 4/6 : Chapter 26 of CLRS
4/7 - 4/13 : Chapter 29 of CLRS
4/14 - 4/20 : Chapter 29 of CLRS
4/21 - 4/27 : Chapter 30 of CLRS
4/28 - 5/4 : Chapter 30 of CLRS
5/5 - 5/11: Chapter 33 of CLRS
5/12 - 5/18: Chapter 35 of CLRS
5/26 - 6/1: Chapter 15, section 5 of CLRS

Notes

Convex Hull, Line Segment Intersection, Voronoi Diagram
Randomized Incremental Algorithms, k-d trees
On-line Algorithms 1
On-line Algorithms 2
Arithmetic Coding
Contiguous Ordering and PQ-trees

Text Book

Introduction to Algorithms, Second Edition , by Cormen, Leiserson, Rivest, Stein. MIT Press, Cambridge, MA, USA.

General Theory Resources

These resources may be helpful in your studies.

Final Exam

10:30-12:20 p.m. Wednesday, Jun. 11, 2003
Final Exam study guide

Grading

Weekly assignments (30%)
Project (30%)
Final exam (40%)

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