CSE548/AMS542 Analysis of Algorithms
Locations and Hours:
Time/room change: Wednesday, Friday
9:35am10:55am @ CS2311.
Lecturer:
Prof. Jie Gao, 1415
TAs: Shang Yang, Email: syang at cs.sunysb.edu. Office hour: Monday 11:00am1:00pm
at 2110 CS building.
Shupikov Yevgeniy, Email: yshupiko at cs.sunysb.edu. Office hour: Wednesday 12pm2pm
at 2110 CS building.
News:
1.
Final
exam is graded. The graded exam papers are left in the box outside my office. The
solution to the exam and our grading rule can be found here. The highest score is 28.5 out of 30 and the average is 16.5.
2.
I
will hold office hour Wednesday at 46pm – only come to my office hour if you
are absolutely sure that you have a grading problem. The rule for partial
grades was given in the solution sheet. I will not consider any other requests
for partial grades for incorrect answers.
3.
A few exercise
problems for approximation & randomized algorithms: Chap 11: 2, 6, 10. Chap
13: 1, 3.
4.
Final exam:
December 14^{th} 46pm at 2311 & 2129. The exam is open book/open
notes, but no computer/Internet is allowed. The focus will be on the second
half of the course materials.
5.
Graded
homework 5 was left in the box outside my office.
6.
The updated
solution to the midterm is posted here, with more clarifications on the
solutions, grading rules, and common mistakes.
7.
Someone has
left a textbook “algorithm design” in 2311 Friday. I put the book in the box
outside my office. Please pick up. Extra midterm solutions can also be picked
up there.
8.
I will be out
of town for a conference MondayWednesday. If you have any questions, feel free
to send me emails. My office hour on Wednesday will be moved to Thursday
afternoon. In the 10/24 lecture, our TAs will go over homework problems.
9.
To prepare for
dynamic programming, please find the list of exercise problems (not homework, not counted in final grades)
below. You don’t need to turn in the solutions. However, you can welcome to
email me or the TA for questions/answers to these problems.
10. Change of the midterm date: The midterm will be on
Friday Oct 26^{th}, in class from 9:35am10:55am at Room 2311 and 2129.
It is a closed book exam. You can only bring in the TCS cheat sheet.
11. I put a short syllabus covering the list of topics we
have covered so far.
12. Homework 2 has been graded.
13. Homework 1 has been graded. Students who have not
yet picked up homework 1 can find the graded homework outside my office 1415.
14. Update on enrollment: We will open a 2^{nd}
section for CSE548. Those who have submitted enrollment forms will be allowed
to register for section 02. Then you will be able to register yourself on
SOLAR. However, both sections will be taught at the same time & location
above.
15. 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: bigO notion, running time,
sorting, worstcase 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, AddisonWesley,
2005.
·
[CLRS]
Introduction to algorithms, by Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest,
Clifford Stein, The MIT Press, 2^{nd} 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.
Grading:
68 written homework (40%), midterm (30%)
and final (30%).
·
Each homework
has about 10 problems. 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 at most 3 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 Fall07:


Lecture Topics 
Required readings 
Notes 
1 
9/5 
Algorithmic thinking,
Running time, bigO notation 
Topic 1 in reading list. [KT] Chap 2.1, 2.2, 2.4 

2 
9/7 
Priority queue, graph,
tree 
[KT] Chap 2.5, 3.13.1 

3 
9/12 
Graph traversal 
[KT] Chap 3.23.6 
Homework
1 out 

9/14 
No class 


4 
9/19 
Greedy algorithms I 
[KT] Chap 4.14.2 

5 
9/21 
Greedy algorithms II 
[KT] Chap 4.3 
Homework 1 due, Homework
2 out 
6 
9/26 
Dijkstra’s algorithm, Minimum Spanning Trees 
[KT] Chap 4.44.5 

7 
9/28 
MST, unionfind
algorithm, NPComplete, Minimum Steiner Tree 
[KT] Chap 4.6, 8.1, [Va] Chap 3.1 (notes handed out in class) 
Homework 2 due Homework
3 out 
8 
10/3 
Divide and Conquer I 
[KT] Chap 5.15.3, solving
recurrences. 

9 
10/5 
Median and Quicksort, randomized and deterministic algorithms 
[KT] Chap 5.4, 13.5,
[CLRS] 9.3, online
notes. 

10 
10/10 
Matrix multiplication,
Lower bound, decision trees, adversarial strategies 
[CLRS] 8.1, 28.2, [KT]
5.5, online
notes 1, online
notes 2. 
Homework 3 due Homework
4 out 
11 
10/12 
Dynamic Programming I 
[KT] Chap 6.1, 6.2, 6.4,
online
notes. 

12 
10/17 
Dynamic Programming II 


13 
10/19 
BellmanFord algorithm 
[KT] Chap 6.96.10.
Exercise problems 6.1, 6.5 in [KT]. 
Homework 4 due Exercise problems:
Problem 3, 7, 11, 12, 14, 17, 20, 23. A few more difficult ones: 24, 29. 

10/24 
Midterm review 



10/26 
Midterm, in
class @ 2311 and 2129 


14 
10/31 
Flow algorithms 
[KT] Chap 7.1 

15 
11/2 
Max flow min cut, 
[KT] Chap 7.2, 7.3 

16 
11/7 
EdmondsKarp Algorithm,
Bipartite matching 
[KT] Chap 7.5, online
notes. 
Homework
5 out 
17 
11/9 
Applications of flow
algorithm (bipartite matching, edge disjoint paths, feasible circulation) 
[KT] Chap 7.57.7 

28 
11/14 
NP and polynomial
reduction (3SAT, vertex cover, independent set) 
[KT] Chap 8.18.4 

19 
11/16 
Hamiltonian cycle, TSP,
3coloring 
[KT] Chap 8.5, 8.7 

20 
11/21 
Subset Sum, Knapsack,
PTAS 
[KT] Chap 8.8, 11.8 
Homework 5 due Homework
6 out 

11/23 
No class 


21 
11/28 
Load balancing, kcenter 
[KT] Chap 11.1, 11.2 

22 
11/30 
Set cover, LP 
[KT] Chap 11.3 

23 
12/5 
LP rounding (vertex
cover and set cover) 
[KT] Chap 11.6, online
notes. 

24 
12/7 
Randomized algorithm 
[KT] Chap 13.113.3 


12/12 
In class homework
session 

Homework 6 due Exercise problems: Chap
11: 2, 6, 10. Chap 13: 1, 3. 

12/14 
Last class, Q & A
session 



12/14 46pm 
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
NPComplete problems.
l
Jeff
Erickson’s lecture
notes on NPhard 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 worldreadable, whether intentionally or through
carelessness) will be treated as academic dishonesty.
Internet resources:
·
Demos: http://www.cs.princeton.edu/~wayne/cs423/demos.html