Design and Analysis of Algorithms

Course Basics

Section 01 [Joshua]: Tuesday, Thursday 9:55AM - 11:10AM, Science Center 264
Lab C: Monday 8:50AM - 10:20AM, Clothier Hall 016
Section 02 [Lila]: Tuesday, Thursday 11:20AM - 12:35PM, Science Center 183
Lab A: Monday 1:15pm - 2:45pm, Clothier Hall 016
Lab B: Monday 3pm - 4:30pm, Clothier Hall 016
Instructors: Joshua Brody
Lila Fontes
Emails: brody at cs.swarthmore.edu
fontes at cs.swarthmore.edu
Office: Science Center 260 and 258
Office Hours: Wednesday 10AM-12PM, Thursday 2-4PM, Friday 2-4PM
Textbook: Algorithm Design, by Kleinberg and Tardos. (K\& T)
See also Introduction to Algorithms, by Cormen, Leiserson, Rivest, Stein.
This course uses clickers; you will need to have a clicker to participate.
Course Discussion: Piazza (mandatory enrollment)
Only the Kleinberg and Tardos book is required, but CLRS is a useful reference. (If you have financial need regarding the required textbook, please come talk to your professor.)

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.