|
CSEP 521 - Applied Algorithms - Winter 2007
|
|
Instructor:
Teaching Assistant:
Meeting Times:
Wednesday, 6:30 - 9:20 pm, EE1 045
CSEP 521 E-mail Announcements
We will periodically send out important information via email to the course email group. To subscribe to the group, you should visit the list home page,
http://mailman.cs.washington.edu/mailman/listinfo/csep521 to add yourself, or you can use the email interface to subscribe. Email to csep521-request@cs with the word "help" in the subject will return a message listing all of the email command options.
You can also vist the list archives by clicking on the very first URL on the list "home page", or by clicking here.
Please note that we will use this group as an announcement list only; if you have a homework question or some other topic that you'd like to discuss with your fellow students, do so on the course message board (described below).
CSEP 521 Message Board
Use the discussion
board to ask questions and consult with each other about the
homework and anything else related to class.
Assignments
Please read the grading guidelines. Also
note that if you choose to submit your assignment as a soft copy, you
should send only a PDF/PS file as an attachment to Roee and make sure
that the
name of the file you attach clearly indicates your name and the
assignment number (this information should also appear in the
file submitted).
Assignment 1 due 7pm, January 13, 2007.
Solution
Assignment 2 due 7pm, January 27, 2007
Solution
Assignment 3 due 7pm, February 3, 2007
Solution
Assignment 4 due 7pm, February 10, 2007
Solution
Assignment 5 due 7pm, February 17, 2007
Solution, part a;
Solution, part b
Assignment 6 due 7pm, February 26, 2007
Solution
Project
Please read the project description.
This year's projects
Lectures (slides require password)
Lecture 1: Course Introduction,
Stable Marriage, Review of
basics (Chapters 1-2)
Lecture 2: Graphs, BFS, Connectivity,
Topological Sort, DFS (and Articulation
points), Greedy Algorithms, including
Shortest Paths (Chapter 3, 4.1-- 4.4)
Lecture 3: MST; Divide & Conquer
(counting inversions, closest pair of points, integer multiplication)
(Sections 4.5-4.7, 5.1--5.5)
Lecture 4: Fast Fourier Transform;
dynamic
programming(applications in scheduling and computational biology)
(Sections 5.6, 6.1-- 6.7)
Lecture 5: Bellman/Ford;
theory of network flow
network flow applications
(Sections 6.8- 6.10, 7.1-- 7.3, 7.5 -- 7.12)
Lecture 6: Finish up network flow,
linear programming (Chapter 7 of Dasgupta et al book).
Lecture 7: Finish up linear programming, NP-completeness
(part 1,
part 2 ,
part 3 )
(Chapter 8)
Lecture 8: Coping with NP-completeness --branch and bound, local search, approximation algorithms, etc.
(part 1,
part 2)
Lecture 9: Randomized algorithms
(part 1,
part 2)
Lecture 10: Student Project Presentations
Textbook
The textbook will be used as a resource for most of the course.
Algorithm Design
Jon Kleinberg and Eva Tardos
Addison Wesley, 2005
Algorithm Resources
These resources may be helpful
in your studies.
Grading
- Weekly assignments (70%)
- Take home midterm (15%)
- Project (15%)
- There is no final exam this year.
Collaboration
You are allowed to collaborate with your classmates on formulating ideas
for solving the homework problems. When it comes to writing up solutions,
if you wish, you may
pair up with one other student on the preparation and submission of
a single joint written homework. On the homework you submit, please include
a list of all the people that you discussed the problems with. You may not consult
written materials other than the course materials in coming up with
your solutions. Needless to say, you are expected to maintain the utmost
level of academic integrity in the course.
|
 |
Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to roee]
|
CSE Home