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.

Course Secretary:   Mitra Kelly, CS Bldg. 323, 258-4562, mkelly@cs.

Lectures:   MW 11-12:20, Friend 004. Attendance at lectures is expected.

Precepts:   Precepts meet on Monday for 50 minutes. The first precept is 2/10. At precepts, we return and discuss the program and written assignment that were handed in the previous week, and give details and answer questions about the new assignment. You should come prepared to participate in the discussion, not just ask questions.

Web Site:   The COS 226 course website is http://www.princeton.edu/~cs226. It contains copies of the lecture notes, programming assignments, and exercises.

Textbooks:   The course textbooks are:

Prerequisites:   Students in the course should have an understanding of the basic principles of computer science and computer architecture, significant programming experience with a working knowledge of C and Unix (or some similar programming environment) and familiarity with elementary data structures such as arrays, stacks, queues, and trees. Most students registered for the course have this background; those who do not may have to work harder at the beginning.

The course will cover algorithms from a variety of applications areas, and several mathematical topics will be discussed. The course is intended to be self-contained with respect to such topics, but students are likely to find any mathematical experience helpful.

Grades:   Your grade for the course will be based on the following components:

• programming assignments: 40%
• exercises: 20%
• midterm exam: 15%
• final exam: 25%
• staff discretion

There will also be weekly exercises. These will be due at precept on Mondays. These will consist of short questions on the material in the lectures, notes, and programs. Some of these questions will reappear on the exams, but with different input data.

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. You may bring a 8.5-by-11 sheet with handwritten notes to the exam. No calculators or other computational devices.

Computers:   You may develop your programs on any machine that you like: we encourage you to use your own equipment. However, your finished programs must run on any ANSI C89 compliant system. We provide instructions for setting up such a C programming environment on Windows, OS X, and arizona machines.

Lab TA coverage:   The Princeton CS 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, C), 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 C to use this supplemental material in conjunction with their course.

Short history of credits:   These course materials have been under development by R. 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 are being made in 2002 and 2003. Problems in exams and problem sets are adapted from many sources, but primarily the new (third) edition of Algorithms in C.