CS 340: Analysis of Algorithms

Fall 2020, Prof. Sorelle Friedler

Qualitative and quantitative analysis of algorithms and their corresponding data structures from a precise mathematical point of view. Performance bounds, asymptotic and probabilistic analysis, worst case and average case behavior. Correctness and complexity.

Prerequisites: (CS 106 or BMC CS 206) and CS 231, both with a grade of 2.0 or better.
Additionally, it is recommended that students wait until their junior or senior year to take this course.

Syllabus (pdf)

Resources

In addition to the syllabus above, the course will use the below linked resources. Moodle will be used to post grades, hand in problem sets, and post lecture recordings. Slack will be used for announcements and to alert the professor and TAs to questions. All students have been automatically enrolled in Moodle and Slack. Zoom links can be found in the Google Calendar entries at the bottom of this page, and Zoom passwords will be distributed via Slack.

Collaboration Policy   Moodle   QuaCS Slack

Problem Sets

Problem sets make up a major and important portion of the work for this course. For due dates, please also see the calendar below. Problem sets should be handed in via Moodle at 10am each Friday (unless otherwise noted). Problems noted as x.y are problem number y in chapter x of the Algorithm Design textbook.

Hint: You will likely find helpful information in the corresponding chapter in the textbook. This sometimes includes the answer - if so, you should go ahead and use that information.

Be sure to read the Algorithm Write-up Guidelines (see below) before writing up any algorithms for the exercises listed below (though you are excused from following them strictly for the first two homework assignments). (Questions that are not asking for you to design an algorithm do not need to follow these guidelines.)

• HW 1: stable matching

• HW 2: complexity

• HW 3: BFS, DFS, and interval scheduling

• HW 4: Dijkstra's algorithm

• HW 5: greedy algorithms

• HW 6: divide & conquer

• HW 7: dynamic programming

• HW 8: network flow

• HW 9: NP-Completeness

Write-up Requirements

Here are some write-up guidelines that you should be sure to follow as well as examples and templates:

• Algorithm write-up guidelines - explanation of what every problem set write-up should include

• Example write-up

• LaTeX example template

Project

An important part of the class is the large group project for which 2-3 students work together to create and implement an algorithm of real-world importance. The final product is a research paper and presentation. In Fall 2020 students will have a choice between two projects:

The Registrar's Problem:
Project Description
Starter Files (zip)
Haverford Extension Files (zip)

COVID Scheduling Problem:
Project Description
Demo Input/Output Files (zip)
Haverford Extension Files (zip) - files still being collected

Course Calendar

All course times, due dates, and office hours are listed on the calendar below as well as on the syllabus above. Office hours are also available via appointment, and short questions can be asked via slack. Zoom links to the course are given in the below calendar entries and the password will be posted on the class slack channel.