CSE548/AMS542 Analysis of Algorithms

Locations and Hours:

Tuesday, Thursday 2:20-3:40pm @ Life Sciences L-3.

Instructor:

Prof. Himanshu Gupta (Taking over from Prof. Jie Gao). Email: hgupta at cs dot sunysb dot edu. Office hour: Tuesday/Thursday 1-2pm.

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.

Announcements

0.      Please do not ask about cut-off and/or final examination scores; I am not planning to disclose these details.

0.      Finals Information: 5-7:30pm in our classroom on 12/18 (Thursday). Full Syllabus (3 questions from pre-midterm material, 2 questions of network flows, 3 questions on NPC-related-material). More than half of the questions are from JE-UIUC-exericses. You are allowed 1-sheet of notes for examination.

0.      Office hours for this week and next: 12/17 (Wednesday) 2-5pm, 12/18 (Thursday) 2-5pm.

1.      Complete HW 6 Solutions (updated 4pm, 12/13). Also see the counter-example for the simple greedy algorithm (start with all edges in the cut, and then make the sets equal by greedily moving vertices from the larger set) for the max-cut in trees problem. In this example, the greedy will give 3, while the optimal is 4. .

2.      Vertex Cover Approximation: Find a maximal (not necessarily maximum) matching M. Let S = set of both end-points from each edge in M. Note that S is a vertex-cover of size 2|M|. Also, the optimal vertex cover must be at least of size |M| (think why?). Thus, we have a 2-approximation algorithm for vertex cover.

Past Announcements

Ø      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, Overall Syllabus

Required Readings

Homeworks, Additional 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 solution

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 solution

Homework 3 out

10

Oct 7

Dynamic programming: Introduction, weighted interval scheduling, edit distance, knapsack.

Online notes on DP

Notes1 Notes2 on lower bound

 

11

Oct 14

Dynamic programming: Independent set in a tree, increasing subsequence, shortest paths in a DAG (with negative weights), chain matrix-multiplication.

Online notes by David Mount (on chain matrix)

 

12

Oct 16

Dynamic Programming: All pairs shortest paths (Bellman-Fords, Floyds), other examples.

Online notes on APSP.

Homework 3 solution

Homework 4 out

13

Oct 21

Review session

 

Practice midterm 1, Solution;

Practice midterm 2, Solution.

14

Oct 23

Midterm

 

Midterm (with solutions); Grading.

Example 1 and Example 2 for Q3.

15

Oct 28

Midterm Solutions; Network Flows

 

 

16

Oct 30

Max-flow Min-cut Theorem, Ford Fulkerson Algorithm

Online notes

Homework 4 Solutions

Homework 5 out

17

Nov 4

Efficient flow algorithms.

Online notes

 

18

Nov 6

Edge disjoint paths, Bipartite Matching, Examples

Overall Flow-Notes

 

19

Nov 11

P, NP, NP-complete, NP-hard

Overall NP-Notes

 

 

Nov 13

NP-Complete, Karp-reductions

Online notes

Homework 5 Solutions; Grading

Homework 6 out

21

Nov 18

NP-Complete, Karp-reductions

-

Hints for HW 6 problems (updated 11/24, 11:30pm)

 

Nov 20

Karp-reductions

 

 

 

Nov 25

Approximation Algorithms

Set Coverage Notes

Steiner Tree Notes

 

 

Dec 2-4

Approximation Algorithms

 

 

 

Dec 9-11

Review

 

 

 

 

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.