|
Description. This course is designed to provide students with an understanding of the principles and techniques used in the design and analysis of efficient data structures and algorithms. We shall discuss and analyze a variety of data structures and algorithms chosen for their importance and their illustration of fundamental concepts. We shall emphasize analyzing the worst-case running time of an algorithm as a function of input size. We shall also spend some time exploring the boundary between feasible (polynomial-time) computations and infeasible computations. This will include discussion of the notorious P vs. NP question.
Prerequisites. COS 226 and COS 340, or permission of instructor. The course requires some knowledge of elementary data structures and the understanding of the notion of a mathematical proof. Any proof-based math course (such as MAT 215) is usually a sufficient substitute for COS 340.
Lectures. Monday and Wednesday 11–12:20pm in Friend 006. Attendance is required. You are responsible for all material presented in lecture; some of that material is not covered in the textbook.
Precepts. Thursday 4:30–5:20pm in Friend 008 or Friday 11–12pm in Friend 006. Attendance is recommended. A preceptor will work through problems that are similar in spirit to those on the problem sets.
Office hours. You are welcome to attend the office hours of any staff member.
| PERSON | OFFICE | HOURS |
|---|---|---|
| Kevin Wayne | CS 207 | M 3–4pm, W 2–3pm |
| Dan Larkin | CS 201 | M 6:30–8:30pm |
| Sachin Ravi | CS 001A | T 4–6pm |
Undergraduate course assistants.
Ilias Giechaskiel and Edward Zhang.
Online forum. If you have general questions about the problem sets, lectures, textbook, or other course materials, please post via Piazza. Posts marked private are viewable only by the course staff.
Course website. The course website
http://www.cs.princeton.edu/courses/archive/spring13/cos423includes links to the lecture slides, problem sets, and precept material. You will also use it to submit problem sets electronically.
Readings. The following textbook is required:
Problem sets. There will be 8 problem sets.
Grading. We will determine your course grade based primarily on weekly problem sets, using class participation and staff discretion to resolve borderline situations. We will grade your problem sets for correctness, clarity, and conciseness.
Regrading. Occasionally, we make mistakes. To request a regrade, write a brief note indicating the perceived mistake by the grader; attach it to your graded work; and give it to the instructor within two weeks of when the graded work was returned.
