CSE548/AMS542 Analysis of Algorithms (Spring 2018)


Course Description

This is the CS PhD qualifier course on algorithms and covers advanced topics on algorithm design and analysis.


Instructor: Jing Chen

Office: 247 New Computer Science Building

Spring 2018 Office Hour: Monday 1pm-2pm (there will be pizza!) or by appointment


Prerequisite: CSE373, or CSE385, or equivalent ones

Lecture: Mo 10:00am-12:50pm, Computer Science 2120 (note this is the old CS building)

Required textbook: Algorithm Design. J. Kleinberg and …. Tardos. Addison Wesley, 2005.

Recommended reading: Introduction to Algorithms, 3rd Edition. T. Cormen, C. Leiserson, R. Rivest, and C. Stein. MIT Press, 2009.

Randomized Algorithms. R. Motwani and P. Raghavan. Cambridge University Press, 1995.


        We will use Blackboard (http://blackboard.stonybrook.edu/) for future announcements and course materials. Course Calendar can be found there in Course Tools.

        Syllabus will be updated on Blackboard as the course proceeds. Syllabus from Spring 2017 is available here.

        Please type your homework solutions using LaTeX and submit the pdf file on Blackboard. Here is the template.

        Problem Set 0: Academic Honesty Review. Due by Jan. 29, 5:00pm.

Grading Policy

The grade will be based on the following parts.

        Homework (30 points in total)

Homework assignments will be bi-weekly or tri-weekly. You can discuss the problems with other students taking this class, but you must write up your solution individually and acknowledge with whom you have discussed.

If more than one student submits substantially the same writeup for a particular problem, or if there is some other evidence that the writeup you submit is not your own work, I will regard this as evidence that you are trying to get a higher grade without actually doing the required work and may choose either to make a corresponding deduction from your homework score or (in egregious cases) to pursue the matter as a case of academic dishonesty.

Note! If you really donít know how to solve a problem after making serious effort, write ďI honestly donít know how to solve this problemĒ and youíll get 25% of it. While if you make up a solution by putting together some random sentences, you may get 0.

        In-class midterm exam (30 pts): Mar. 19

        Final exam (35 pts): in the Final period (May 8-16), to be scheduled

        Class participation (5 pts)

I encourage you to ask and to answer questions in class, as interaction is an efficient way of learning.

Students with Disabilities

"If you have a physical, psychological, medical or learning disability that may impact on your ability to carry out assigned course work, I would urge that you contact the staff in the Disability Support Services office (DSS), ECC Building (behind SAC), 632-6748/TDD. DSS will review your concerns and determine, with you, what accommodations are necessary and appropriate. All information and documentation of disability is confidential."

Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and Disability Support Services. For procedures and information go to this web site and search Fire Safety and Evacuation and Disabilities.

Critical Incident Management

Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of Judicial Affairs any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn.