Design and Analysis of Algorithms

Course Basics

Lecture: Monday, Wednesday, Friday 9:20am - 10:10am, hosted on Zoom.
Lab A: Monday 1:15pm - 2:45pm, hosted on Slack (in the #lab-a channel)
Lab B: Monday 3pm - 4:30pm, hosted on Slack (in the #lab-b channel)
Instructor: Joshua Brody
Email: brody at cs.swarthmore.edu
Office Hours: Thursday 2-4pm, Friday 10:30am-12:30pm, and by appointment. Hosted on Slack in the #office-hours channel.
Extra Office Hours: Monday 9-10pm for approved lab attendance exemptions; email Joshua
Textbook: Algorithm Design, by Kleinberg and Tardos. (K & T)
See also Introduction to Algorithms, by Cormen, Leiserson, Rivest, Stein.
Course Discussion: Piazza (mandatory enrollment)
Github: CS41 Swarthmore Github Org
There will be no required readings this semester. However, each week there will be suggested readings from the Kleinberg and Tardos book. If you have financial need regarding the required textbook, please send me an email to discuss options. CLRS is not required but is a useful reference.

Welcome to CS41. This class explores algorithmic design and analysis in a more formal approach than CS21 or CS35. Algorithmic problems arise in many diverse areas of computer science. Often, one must take open ended, abstract, real-world problems and extract a clean mathematical problem that can be approached algorithmically. Designing a solution requires knowing the rules and common techniques of the model of computation used. Multiple models represent various abstractions of real computer systems and may result in very different solutions. Regardless of the model however, good algorithmic design requires careful analysis of complexity and proofs of correctness. Topics covered include asymptotic notation, graph algorithms, greedy algorithms, divide and conquer, dynamic programming, NP-completeness, approximation algorithms, and randomized algorithms.