CSE548/AMS542 Analysis of Algorithms

Locations and Hours:

Tuesday, Thursday 9:50am-11:10am @ Melville Library E4320.

Lecturer:

Prof. Jie Gao, 1415 Computer Science Building. Email: jgao at cs dot sunysb dot edu. Office hour: Tuesday, Thursday 11:20-12:30pm.

TAs: Xiaomeng Ban, xban at cs dot sunysb dot edu. Office hour: Monday 12pm-2pm @ CS2110.

News:

1.      Final exam papers have been graded. The average is 11. Maximum is about 25. Solution can be found here. You can pick up your exam paper in the box outside my office. Friday I have office hour from 1:30-3pm. If you have any questions, come to my office hour.

2.      Partial solution to Homework 4, Homework 5 and Homework 6, and practice final.

3.      Homework 6 is out and due on May 13th. Submit to my mailbox.

4.      There will be no classes in the week April 22-24. Instead, we will have long sessions in the week of April 29-May 1st: 9:50-12:30pm at Room CS1211.

5.      Homework 5 is still due Tuesday April 22nd. Please put your homework in my mailbox anytime on Tuesday (my mailbox is located opposite to my office 1415), the 2nd one from top in the 2nd left column. The TA will pick up from there.

6.      Solution to midterm is posted.

7.      Midterm in class on March 27th.

8.      Solutions to homework 2 and 3 are posted below.

9.      Practice midterm is posted.

10. Students who have not picked up graded homework can find it in the box outside my office.

11.  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 (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 Spring08:

 

 

Lecture Topics

Required readings

Notes

1

1/29

Algorithmic thinking, Running time, big-O notation

Topic 1 in reading list.

[KT] Chap 2.1, 2.2, 2.4

 

2

1/31

Priority queue, graph, tree

[KT] Chap 2.5, 3.1-3.1

Homework 1 out

3

2/5

BFS, DFS, strong connectivity

[KT] Chap 3.2-3.5, Chap 3 problem 7, 9

 

4

2/7

Topological ordering, Greedy algorithm

[KT] Chap 3.6, 4.1

 

5

2/12

Greedy algorithm

[KT] Chap 4.1, Chap 4 problem 13, 17

Homework 1 due before class

6

2/14

Dijkstra’s algorithm, MST

[KT] Chap 4.4, 4.5

Homework 2 out

Homework 1 solution

7

2/19

MST implementation, Union-Find data structure

[KT] Chap 4,6, Chap 4 problem  26

 

8

2/21

Minimum steiner tree, solving recurrences, counting inversions

[KT] Chap 5.3, [CLRS] 4.1-4.3, Notes on Minimum Steiner tree.

Notes on solving recurrences.

 

9

2/26

Divide and conquer

Closest pair of points

Binary Addition (using adders)

Quicksort

Median (deterministic)

Lecture notes on divide and conquer

Homework 2 due

Homework 3 out

10

2/28

Divide and conquer

Merge-sort.

Intuitive proof for lower bound for sorting (giving only the comparison operator)

Binary Adder (using adder/multiplexer)

Integer Multiplication (n^(log 3) algorithm)

Strassen's algorithm

 

11

3/4

Lower bound (adversarial argument)

Dynamic programming

Notes1 Notes2 on lower bound

Chap 5 problem 1, 2

Chap 6.1

 

12

3/6

Dynamic programming

Weighted interval scheduling, Longest common subsequences,

Matrix chain multiplication.

Online notes by David Mount.

 

13

3/11

Dynamic programming

Online notes

Homework 3 due

Practice midterm is out.

14

3/13

All pairs shortest paths

Online notes

Homework 4 out

 

3/18

Spring break, No class.

 

Solutions to homework 2 and 3.

 

3/20

Spring break, N0 class.

 

 

15

3/25

Review session

 

Solution to practice midterm out

16

3/27

Midterm

 

Homework 4 due

17

4/1

Flow, Ford Fulkerson Algorithm

Chap 7.1-7.3, Online notes

 

18

4/3

Max flow min cut. Better flow algorithms

Online notes

Solution and grading rule to midterm is out

19

4/8

Circulation, edge disjoint paths

Chap 7.5-7.7

Homework 5 out

20

4/10

NP hard and polynomial reduction

Chap 8

 

21

4/15

NP hard and polynomial reduction

 

 

22

4/17

NP hard and polynomial reduction

Notes on subset sum

 

23

4/22

NO class

 

Homework 5 due

24

4/24

NO class

 

 

25

4/29 @ CS1211 9:50-12:30

Approximation algorithms

Chap 11.1-11.4, 11.6, 11.8

Homework 6 out

Practice final out

26

5/1 @CS1211 9:50-12:30

Randomized algorithms

Chap 13.1-13.4, 13.6

 

27

5/6

Randomized algorithms

 

 

28

5/8

Review session

 

Homework 6 due on May 13th

 

5/15 8:00-10:30 am.

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.