Computer Science 226
Algorithms and Data Structures
Spring 2011


Course Information | Assignments | Exercises | Lectures | Exams | Booksite

COURSE INFORMATION

Description.   This course surveys the most important algorithms and data structures in use on computers today. Particular emphasis is given to algorithms for sorting, searching, and string processing. Fundamental algorithms in a number of other areas are covered as well, including geometric and graph algorithms. The course will concentrate on developing implementations, understanding their performance characteristics, and estimating their potential effectiveness in applications.

Prerequisites.   COS 126 or COS 217 or permission of instructor.

Lectures.   Attendance is required. You are responsible for all material presented in lecture; some of that material is not covered in the textbook.

Precepts.   We cover details pertinent to programming assignments and exams. You should come to precept prepared to participate in the discussion, not just ask questions.

Basic information.   If you have not taken COS 126, or just not taken COS 126 recently, please read the early part of the checklist carefully and thoroughly to learn about our conventions for preparing and submitting assignments.

Staff.   You are welcome to attend the office hours of any staff member. Office hours begin Thursday, Feb 3. For administrative questions contact Maia Ginsburg, the lead preceptor.

The last day of regular office hours is Friday, Apr 29. There will be additional office hours on Sunday, May 15 and Monday, May 16:


May 15
Q&A 3-5pm in Friend 006

May 16
Rob 10-11am; Dave 11-12pm; Josh 12:00-1:30pm; Maia 1:45-2:45pm; Aman 3-4pm

        TIME      ROOM    PERSON    OFFICE      HOURS           EMAIL       
L01 M W
11–12:20pm
Friend
101
Bob
Sedgewick
CS
319
Tue and Thu
12-1:30
rs@cs
P01 Th
12:30–1:20pm
Friend
112
Maia
Ginsburg
CS
205
Th 1:30-2:00;
4:30-5:00pm
M 4:00-5:00pm
maia@cs
P01A Th
12:30–1:20pm
Friend
108
Josh
Kroll
Sherrerd Hall
320
M 1:45-2:45pm
T 10am-11am
kroll@cs
P01B Th
12:30–1:20pm
Friend
109
Dave
Walker
CS
211
W 2:00-3:00pm
M 1:45-2:45pm
dpw@cs
P03 Th
3:30–4:20pm
Friend
109
Maia
Ginsburg
CS
205
Th 1:30-2:00;
4:30-5:00pm
M 4:00-5:00pm
maia@cs
P02 F
11:00–11:50am
CS
102
Rob
Schapire
CS
407
see wass.princeton.edu (netid=schapire) schapire@cs
P02A F
11:00–11:50am
Friend
109
Aman
Dhesi
CS
103B
F 2:00-4:00pm adhesi@cs


Grading.   Your grade for the course will be based on the following components: programming assignments: (40%), midterm exam: (15%), final exam: (30%), and exercises (15%), and staff discretion.

Regrading policy. 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 your preceptor within two weeks of when the graded work was returned.

Course website.   The course website

http://www.princeton.edu/~cos226
includes links to course content, including programming assignments, exercises, lecture slides, and old exams. You will also use it to submit programming assignments.

Readings.   Kevin Wayne and Professor Sedgewick just finished the new 4th edition and have rebuilt the course content around it. Unfortunately, it will not be printed until the week of 3/9. For the first time in years, you will have a single resource to study for the final exam. When it is available, it will be required. It contains a wealth of information beyond what we can cover in lecture; it is certain to enhance your understanding of algorithms and data structures.

For February, we will post some readings, but will primarily work from the lecture slides and the booksite. The preliminary edition that was used last fall is no longer in print. Several copies of the preliminary edition are on reserve in the Engineering library, or you may also want to borrow one from a friend. Beware: while reading this material may be useful for an overview, be careful, because there are many, many small differences between this preliminary material and the book that will be published in March.

For the midterm and the exercises in February, you can use the lecture slides and the booksite. For the final, which is 30 percent of the grade, you will want to review everything in the textbook that you will get in March.

The COS 126 textbook is a recommended basic Java programming reference.

Booksites.   The booksites contain an extensive amount of supplementary information, including the code from lecture.

http://introcs.cs.princeton.edu

http://algs4.cs.princeton.edu

Programming assignments.   The programming assignments involve applying the material from lecture to solve problems in science, engineering, and commerce.

Exercises.   The exercises consist of short questions on the material in the lectures and readings.

Exams.   The in-class midterm exam is March 7. The final exam is scheduled by the Registrar on May 16, 7:30pm.

Computers.   You may develop your programs on any machine that you like: we encourage you to use your own equipment. We provide instructions for setting up a Java programming environment under Windows, OS X, and Linux.

Laboratories.   We hire undergraduate Lab TAs who are available starting Wednesday, Feb 2, to answer general computing questions in the Friend 017 lab. They can assist you in debugging, provided you have first made a reasonable effort to identify the bug and isolate the problem. If you have questions regarding the course material or programming assignments, see your preceptor or instructor.

Copyright.   All rights reserved. None of this material may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise without prior written permission. Permission is granted to instructors who adopt Algorithms, 4th edition to use this material in conjunction with their course.

Short history of credits.   These course materials have been under development by Robert Sedgewick since at least 1978. The lecture notes and assignments were rewritten by Robert Sedgewick and Kevin Wayne in 2003–2010.