Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Syllabus for Computer Science 365b, Design and Analysis of Algorithms. Instructor: James Aspnes.

1. Meeting times

Lectures are Tuesdays and Thursdays from 1:00pm to 2:15pm in ML 211.

2. On-line course information

On-line information about the course, including copies of all handouts, can be found using the URL http://pine.cs.yale.edu/pinewiki/CS365. This will also be the main location for announcements about the course, lecture schedules, and so forth. Please check it frequently.

3. Synopsis of course

The course provides an introduction to the design and analysis of algorithms. The goal is to understand measures of efficiency of algorithms, to learn methods of analyzing efficiency, to learn algorithms for fundamental problems in computer science, and to learn techniques for designing efficient algorithms or for determining that efficient algorithms are unlikely to be found. In discussing algorithms we avoid the minor details and focus upon the important ideas.

4. Prerequisites

The prerequisites are CS 202 and CS 223. You are strongly encouraged to take these courses before you take CS 365. I will, however, accept students that have not taken these courses as long as they have comparable knowledge of discrete math and computer science. See me if you aren't sure.

5. Readings

The textbook is Introduction to the Design and Analysis of Algorithms by Anany Levitin, henceforth referred to as LevitinBook.

6. Course requirements

Eleven weekly homework assignments (approximately 55 percent of the grade), a midterm (15 percent), and a final (30 percent).

7. Use of outside help

Students are free to discuss homework problems and course material with each other, and to consult with the instructor or a TA. Solutions handed in, however, should be the student's own work. If a student benefits substantially from hints or solutions received from fellow students or from outside sources, then the student should hand in their solution but acknowledge the outside sources, and we will apportion credit accordingly. Using outside resources in solving a problem is acceptable but plagiarism is not.

8. Clarifications for homework assignments

From time to time, ambiguities and errors may creep into homework assignments. Questions about the interpretation of homework assignments should be sent to the instructor at <aspnes@cs.yale.edu>. Clarifications will appear in the on-line version of the assignment.

9. Late assignments

Late assignments will not be accepted without a Dean's Excuse.

10. Topics

Machines and Mathematics: Introduction to the analysis of algorithms. Models, measures, notation, growth of functions. Proving correctness and running time.
Sorting and Selection: Sorting. Mergesort, Quicksort; the technique of divide and conquer. Order statistics. Lower bounds: how to prove them and how to beat them.
Data Structures and Searching: Hash tables and hash functions, binary search trees, red/black trees, union/find. Augmented data structures.
Combinatorial Optimization: The greedy method. Dynamic programming. Branch-and-Bound.
Graph Algorithms: Minimum spanning trees, shortest paths, max flows, bipartite matching.
Intractability and NP-completeness: The class NP. Satisfiability. NP-hard and NP-complete problems. Proving a problem is NP-complete. Approximation algorithms for NP-hard problems.
Cryptography: Public-key cryptosystems and digital signatures.