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.

Instructor:   Kevin Wayne, CS 207, 258-4455, wayne@cs. Office hours T 4-5, Th 3-4.

Lectures:   MW 11-12:20, CS 105. Attendance at lectures is expected.

Precepts:   Precepts meet on Tuesday for 50 minutes. The first precept is 2/10. At precepts, we will return and discuss the exercises and programming assignment from the previous week. We will also give details and answer questions about the new assignment. You should come prepared to participate in the discussion, not just ask questions. Here is a list of students sorted by precept and by name.

Web Site:   The COS 226 course website is http://www.princeton.edu/~cos226. This is where we will post copies of the lecture notes, programming assignments, and exercises.

Textbooks:   The course textbooks are:

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

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

Programming assignments:   There will be weekly programming assignments. Generally, they will be due on Fridays at 11:59 PM. In calculating your course grade, we will drop your lowest programming assignment score. Thus, you may choose to "punt" one programming assignment, or you may choose to do them all in an attempt to learn more or to maximize your grade.

Exercises:   There will also be weekly exercises. These will consist of short questions on the material in the lectures. Some of these questions will reappear on the exams, but with different input data. Exercises are due at the beginning of lecture on Mondays and will be returned in precepts on Tuesdays. In calculating your course grade, we will drop your lowest three exercise scores.

Exams:   There will be an in-class midterm exam on the Wednesday before break, which will cover all material up to and including the lecture on the previous Wednesday. The final exam is comprehensive, although it will stress material covered since the midterm. Unless prior arrangements are made, a grade of zero will be recorded for missed exams. Exams are closed book, and no calculators or other computational devices are permitted. You may bring a 8.5-by-11 sheet with handwritten notes to the exam.

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

Lab TA coverage:   The Princeton COS department hires undergraduate lab assistants who are available to answer general computing questions in the labs. Here is the current schedule. These people should only be asked computer-related questions (e.g. Unix, Java), not questions regarding course material or programming assignments. They can also assist you in debugging your code, assuming 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.

Important note:   Please do not publish solutions to programming assignments, exercises, and exams in a way that could compromise their utility as pedagogical tools. At Princeton, this is a violation of the basic rights, rules and responsibilities of members of the university community.

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 in Java to use this supplemental 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 index, course information and other .html files on this website were created by Ed Felten in 1993-95, adapting the course materials written by Sedgewick in 1991. The lecture notes and most assignments were rewritten by Sedgewick in 1996-1997. Some material was added by Michael Goldwasser in 1999. Further updates by Bob Sedgewick and Kevin Wayne in 2003 and 2004. Problems in exams and problem sets are adapted from many sources, but primarily the new (third) edition of Algorithms in Java.