CSE548/AMS542 Analysis of Algorithms

Basics

Time & Location: Tuesday Thursday 2:30pm-3:50pm @ Frey Hall 104

Instructor: Professor Jie Gao, jgao@cs.stonybrook, skype: jiegao79. Office hour Tuesday Thursday 4-5:20pm at NCS 243.

TA/Graders:

Shahira Abousamra (Wednesday 1:30 - 2:30 and Friday 11:45 - 12:45 @ NCS room 108. Email: shahira.abousamra@stonybrook.edu)
Zhi Chai (Monday 2-4 pm at NCS room 108. Email: Zhi.Chai@stonybrook.edu),
Rohit Chatterjee (Hours: Wednesdays 2-4 pm at NCS 340. Email: rochatterjee@cs.stonybrook.edu)
Grader: Siddesh Shinde <sbshinde@cs.stonybrook.edu>

We will also use blackboard to send out announcement and share materials. Lectures are videotaped by Echo360 and you may review the lectures on blackboard.

For discussions/questions, please signup at piazza.com: https://piazza.com/stonybrook/fall2018/cse548ams542section01ms . I will check piazza daily and answer questions there. It is highly encouraged that you ask questions on piazza (rather than sending me/TA separate emails) so my answer will be seen by others too (who may have the same question).

This course is meant for MS students of Computer Science major. Students from other departments/majors are encouraged to enroll after the first week of class.

This course expects students with undergraduate algorithm knowledge. 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.

Schedule

Thanks to Ritika Nevatia, the lecture notes of each class can be found from the following folder.

8/28: 1) Logistics; 2) Review of elementary functions, running time in practice, log, big-O notation. 3) Examples of algorithms with common running times (finding max, merge two sorted list, mergesort).
8/30: 1) Examples of algorithms with common running times continued: (closest pair, independent set, traveling salesman problem, binary search). 2) Priority queue/heap, heapsort. 3) Graph traversal (Jeff Erickson's notes).
9/4: 1) BFS, 2) Test bipartiteness; 3) Strong connectivity, First homework will be posted on blackboard.
9/6: DFS and properties, Topological sort.
9/11 Shortest path tree (Dijkstra's algorithm), Spanning tree: cut property, Prim's algorithm and implementation.
9/13 Kruskal's algorithm, Union-Find data structure. Greedy algorithm: interval scheduling.
9/18 Greedy algorithm: scheduling algorithms (minimize # classrooms, minimize max lateness). Second homework will be posted on blackboard.
9/20 Huffman Codes.
9/25 Solving recurrences.
9/27 Divide and conquer: count # inversions, Quicksort, randomized median, deterministic median, deterministic quicksort.
10/2 Lower bound on max/min/median, lower bound on sorting. Divide and conquer: integer multiplication, matrix multiplication, exponentiation, closest pair. Third homework posted on blackboard. Sample midterm shared on blackboard.
10/4 Quick review of homework 1 and 2. Dynamic programming.
10/9: Fall break, no class
10/11: Midterm exam during class (Open book, Open notes, covering everything till (including) divide and conquer).
10/16 Dynamic programming (Fibbonicci number, weighted interval selection, longest increasing subsequence)
10/18 Dynamic programming (Longest common subsequence, edit distance, matrix chain multiplication).
10/23 Dynamic programming (Min weight triangulation, optimal binary search tree, MIS on a tree)
10/25 All pairs shortest paths algorithms using dynamic programming. Fourth homework posted on blackboard.
10/30 Flow algorithm
11/1 Flow algorithm
11/6 Flow algorithm and applications (matching, disjoint paths)
11/8 Problem session on dynamic programming
11/13 NP-hard problems (NP-hard, 3SAT, max clique, max independent set, min vertex cover)
11/15 NP-hard problems (min dominating set, approximation algorithm, vertex cover, set cover). Last homework.
11/20 Approximation algorithm (set cover, hitting set, geometric set cover)
11/22: Thanksgiving break, no class
11/27 Dominating set and independent set on unit disk graphs, Hamiltonian cycle.
11/29 TSP, Load balancing.
12/4 Subset Sum, Knapsack packing and PTAS
12/6: Problem session
Final exam: Tuesday December 18th, 11:15-1:45pm @ Frey Hall 104 and Javits 111. Students with last name R-Z shall take the exam at Javits 111 and the rest of students take exam at Frey Hall 104. Only handwritten notes are allowed. No textbook, no electronic devices.

Course Materials

The recommended textbooks are listed below. I will follow the Kleinberg & Tardos book mainly. This book is put on 2-hours reserve at the main library. 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 post notes for materials not covered in these textbooks on blackboard.

[Va] Approximation algorithms, Vijay V. Vazirani.
[MR] Randomized algorithms, by Rajeev Motwani, Prabhakar Raghavan.

Good lecture notes:

Jeff Erickson: http://jeffe.cs.illinois.edu/teaching/algorithms/
David Mount: http://www.cs.umd.edu/~mount/451/Lects/451lects.pdf

Additional lecture notes or useful materials will be shared through blackboard.

Grading

6-8 written homework (20%), midterm (35%) and final (45%).

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.
No late homework accepted.
Homework submission must be in the format of pdf, formatted by Latex, submitted through blackboard. Handwritten homework will be returned. See below on how to use Latex.

Latex Resources

Install Latex on Windows: Miktex, WinEdt (a nice latex editor), how-to: https://guides.nyu.edu/c.php?g=601858&p=4168436.

Online Latex compilers: overleaf.com.

Draw figures:

xfig in X-window (cygwin on a windows machine).
Ipe (on both windows and Mac).

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).
Copying from other students or from the Internet is treated as academic dishonesty. If you consult outside sources, you must write down the references and you must write down the solution in your own words.
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.
Students are allowed to discuss with each other. But each student must write down the solution using own words and must write down the name of other students with whom you have discussed. Solutions that are the same in writing are treated as academic dishonesty.

Report abuse