This course investigates methods for designing efficient and reliable algorithms. By carefully analyzing the structure of a problem within a mathematical framework, it is often possible to dramatically decrease the computational resources needed to find a solution. In addition, analysis provides a method for verifying the correctness of an algorithm and accurately estimating its running time and space requirements. We will study several algorithm design strategies that build on data structures and programming techniques introduced in Computer Science 136. These include induction, divide-and-conquer, dynamic programming, and greedy algorithms. Additional topics of study include algorithms on graphs and strategies for handling potentially intractable problems.
Format: lecture; Lectures will be simultaneously recorded in classroom and broadcast over Zoom. Office hours will be done over Zoom. Some additional course materials (examples, solutions, definitions and core concepts, etc.) may be provided as prerecorded videos.
Grading: yes pass/fail option,
no fifth course option
Problem sets, midterm and final examinations
CSCI 136 and fulfillment of the Discrete Mathematics Proficiency requirement
Preference will be given to students who need the class in order to complete the major. Ties will be broken by seniority (seniors first, then juniors, etc.).
This course will have weekly problem sets in which students will formally prove statements about the behavior and performance of algorithms. In short, the entirety of the course is about applying abstract and mathematical reasoning to the way computers work.