CSE548/AMS542 Analysis of Algorithms
Locations and Hours:
Tuesday,
Thursday 2:20pm-3:40am @ Life Sciences L-3.
Lecturer:
Prof. Jie Gao, 1415
TA: Xiaomeng
Ban, Email: xban at cs dot sunysb dot edu. Office hour:
Monday 12:00-2pm at CS2110.
TA: Irina Kostitsyna,
Email: ikost at cs dot sunysb dot edu. Office hour:
Wednesday 1-2pm at the TA office.
News:
1.
Professor Himanshu
Gupta will be the replacement instructor starting Oct 14th. This
website will no longer be updated. Please refer to Professor Gupta’s course webpage
for the syllabus/schedule.
2.
Midterm in class on Oct 23rd.
3.
I
put 2 copies of the textbook “Algorithm Design” by Kleinberg and Tardos on reserve in the North Reading Room in the main
library. Please ask the librarian to access a copy.
Course Description:
This course targets at graduate
students with undergraduate algorithm background. If you plan to take this
course, I expect that you know what the following words mean: big-O notion,
running time, sorting, worst-case analysis.
For students who want to fulfill
MS proficiency, please take the undergraduate algorithm course CSE373.
This course will introduce
algorithms used in practice as well as their performance analysis. The list of
topics I plan to cover includes:
·
Graph
algorithms.
·
Greedy
algorithms.
·
Divide
and conquer.
·
Dynamic
programming.
·
NP
and intractability.
·
Approximation
algorithms.
·
Randomized
algorithms.
·
Geometric
algorithms.
Everyone is welcome to sit in
the lectures. Graduate students with interest in theory and algorithms are
highly encouraged to take this course.
Course materials:
The recommended textbooks, as
listed below are put on reserve in the CS library. I will follow the Kleinberg
& Tardos Book mainly. The [CLRS] book is a good
reference.
·
[KT]
Algorithm design, by Jon Kleinberg, Eva Tardos,
Addison-Wesley, 2005.
·
[CLRS]
Introduction to algorithms, by Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest,
Clifford Stein, The MIT Press, 2nd edition, 2001.
Later in the class I may
introduce more topics covered in the following books. I will give handouts for
materials not covered in these textbooks.
·
[Va] Approximation algorithms, Vijay V. Vazirani.
·
Lectures
on discrete geometry, by Jiri Matousek.
·
Randomized
algorithms, by Rajeev Motwani, Prabhakar
Raghavan.
There is a recent book written
by S. Dasgupta,
C.H. Papadimitriou, and U.V. Vazirani titled “Algorithms” you
can also use as a reference book. The full electronic version of the book is
available online.
Grading:
6-8 written homework (30%),
midterm (35%) and final (35%).
·
Homework
problems are not trivial. Start early with the homework problems. It is
unlikely you are able to finish last minute before the due date.
·
Late
homework gets 25% penalty per day.
·
Students
may choose to form a group of 2 students to discuss homework problems.
But it is a firm requirement that every student writes down the solution, and clearly
indicates the collaboration and the sources of materials used/consulted.
Schedules for Fall08:
|
|
|
Lecture Topics |
Required
readings |
Notes |
|
1 |
Sep 2 |
Algorithmic thinking,
Running time, big-O notation, basic combinatorics |
Topic 1 in
reading list. [KT] Chap 2.1, 2.2, 2.4 |
|
|
2 |
Sep 4 |
Priority
queue, graph, tree, BFS, test graph bipartiteness,
strong connectivity |
[KT] Chap 2.5,
3.2-3.5 |
|
|
3 |
Sep 9 |
DFS,
topological ordering, strongly connected components |
[KT] Chap
3.2-3.6, [CLRS] 22.3-22.5 |
Homework 1 out |
|
4 |
Sep 11 |
Greedy
algorithm (scheduling I) |
[KT] Chap 4.1 |
|
|
5 |
Sep 16 |
Greedy
algorithm (scheduling II) |
[KT] Chap 4.1,
4.2 |
|
|
6 |
Sep 18 |
Dijkstra’s algorithm, MST |
[KT] Chap 4.4,
4.5 |
Homework 1 due Homework 2 out |
|
7 |
Sep 23 |
MST implementation,
Union-Find data structure |
[KT] Chap 4,6.
Notes
on union-find data structures. Notes on Minimum
Steiner tree |
|
|
8 |
Sep 25 |
Divide and
conquer: merge-sort, counting inversions, solving recurrences, finding median
(deterministic), quick-sort |
[KT] Chap 5.3,
[CLRS] 4.1-4.3, Notes
on solving recurrences. |
|
|
9 |
Oct 2 |
Divide and
conquer: integer multiplication, matrix multiplication, closest pair of
points |
Lecture
notes on divide and conquer |
Homework 2 due Homework 3 out |
|
10 |
Oct 7 |
Dynamic
programming |
|
|
|
11 |
Oct 14 |
Dynamic
programming: |
Chap 5 problem
1, 2 Chap 6.1 |
|
|
12 |
Oct 16 |
All pairs
shortest paths |
Homework 3 due Homework 4 out |
|
|
13 |
Oct 21 |
Review session |
||
|
14 |
Oct 23 |
Midterm |
|
|
|
15 |
Oct 28 |
|
||
|
16 |
Oct 30 |
|
|
|
|
17 |
|
Flow, Ford
Fulkerson Algorithm |
Chap 7.1-7.3, Online
notes |
|
|
18 |
|
Max flow min
cut. Better flow algorithms |
|
|
|
19 |
|
Circulation,
edge disjoint paths |
Chap 7.5-7.7 |
|
|
20 |
|
NP hard and
polynomial reduction |
|
|
|
21 |
|
NP hard and
polynomial reduction |
|
|
|
22 |
|
NP hard and
polynomial reduction |
Notes on subset sum |
|
|
25 |
|
Approximation
algorithms |
|
|
|
26 |
|
Randomized
algorithms |
|
|
|
27 |
|
Randomized
algorithms |
|
|
|
28 |
|
Review session |
|
|
|
|
|
Final exam |
|
|
Reading List:
·
Beyond the algorithmization of the sciences, Thomas A. Easton, May
2006, Communications of the ACM.
·
Is the Thrill
Gone?, Sanjeev Arora
and Bernard Chazelle, August, 2005, Communications of
the ACM.
l
Wiki page.
l
A list of
NP-Complete problems.
l
Jeff
Erickson’s lecture
notes on NP-hard problems.
·
Lecture
notes from
Policies:
·
All
students are expected to follow CEAS's policies governing
academic dishonesty. Suspected academic dishonesty will be reported to
CEAS's Committee on Academic Standing and Appeals (CASA).
·
Showing
your own work to other students, giving it to them, or making it accessible to
them (e.g., by making the files world-readable, whether intentionally or
through carelessness) will be treated as academic dishonesty.
Internet resources:
·
Demos:
http://www.cs.princeton.edu/~wayne/cs423/demos.html