CSE548/AMS542 Analysis of Algorithms

Locations and Hours:

Time/room change: Wednesday, Friday 9:35am-10:55am @ CS2311.

Lecturer:

Prof. Jie Gao, 1415 Computer Science Building. Email: jgao at cs dot sunysb dot edu. Office hour: Wednesday 3:30-5:30pm.

TAs: Shang Yang, Email: syang at cs.sunysb.edu. Office hour: Monday 11:00am-1:00pm at 2110 CS building.

Shupikov Yevgeniy, Email: yshupiko at cs.sunysb.edu. Office hour: Wednesday 12pm-2pm 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 4-6pm – 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 14th 4-6pm 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 Monday-Wednesday. 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 26th, in class from 9:35am-10: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 2nd 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: 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.

Grading:

6-8 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, big-O 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.1-3.1

 

3

9/12

Graph traversal

[KT] Chap 3.2-3.6

Homework 1 out

 

9/14

No class

 

 

4

9/19

Greedy algorithms I

[KT] Chap 4.1-4.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.4-4.5

 

7

9/28

MST, union-find algorithm, NP-Complete, 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.1-5.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

Online notes by David Mount.

 

13

10/19

Bellman-Ford algorithm

[KT] Chap 6.9-6.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

Edmonds-Karp 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.5-7.7

 

28

11/14

NP and polynomial reduction (3SAT, vertex cover, independent set)

[KT] Chap 8.1-8.4

 

19

11/16

Hamiltonian cycle, TSP, 3-coloring

[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, k-center

[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.1-13.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 4-6pm

Final exam

 

 

 

Reading List:

 

  1. What is algorithmic thinking?

·        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.

  1. NP-Complete:

l           Wiki page.

l           A list of NP-Complete problems.

l           Jeff Erickson’s lecture notes on NP-hard problems.

  1. Metric TSP

·        Lecture notes from Toronto.

 

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

·        Theoretical CS cheat sheet.