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.

Instructors.

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

Precepts.   Precepts meet on Tuesdays for 50 minutes. 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.

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.

Administrative Web Site.   The COS 226 administrative website is http://www.princeton.edu/~cos226. We will post announcements and administrative information on this site and use it to control assignment submission and other administrative tasks. It also includes links to course content, including lecture notes, programming assignments, and exercises. Course staff will be responding to discussion groups on that site before direct e-mail, so using them is your best bet for questions on content.

Course Web Site.   You may wish to bookmark the following link (to this page) for direct access to materials that will persist after the end of the course.

http://www.cs.princeton.edu/courses/archive/spr07/cos226/info.html

Textbooks.   The course textbooks are:

• Algorithms in Java, Third Edition, Parts 1-4 by Robert Sedgewick, Addison-Wesley, 2003. ISBN 0-201-36120-5.
• Algorithms in Java, Third Edition, Part 5 by Robert Sedgewick, Addison-Wesley, 2003. ISBN 0-201-36121-3.

• Introduction to Programming in Java: An Interdisciplinary Approach, Addison-Wesley, 2007. ISBN 0-536-35652-1.

You are expected to read the books, particularly the parts that cover the same ground as lectures and programming assignments. They contain a wealth of information beyond what we can cover in lecture that are certain to enhance your understanding of the course material. A safe strategy is to skim through the book before lecture to get a general idea of what is to be covered, then study it carefully afterwards. While you are not responsible for reading about topics that we do not cover in lecture or that are beyond the scope of the course, you are responsible for exercising good judgement about choosing what to read.

Booksites.   You can find an extensive amount of supplementary information at the booksites for Introduction to Programming in Java: An Interdisciplinary Approach and the forthcoming Introduction to Algorithms and Data Structures, both by Sedgewick and Wayne.

www.cs.princeton.edu/IntroCS

www.cs.princeton.edu/IntroAlgsDS

Programming assignments.   There will be regular programming assignments.

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

Exams.   There will be an in-class midterm exam on the Wednesday before break and a final exam as scheduled by the Registrar. The midterm will cover all material up to and including the lecture on the previous Wednesday and the final covers the whole course, with an emphasis on the second half. 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 (written on one side only) to the exam. Here is an archive of old exams.

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 Friend 016 and 017 labs. Lab TAs 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.

Important note.   Please do not publish solutions to programming assignments or exercises 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 lecture notes and assignments were rewritten by Robert Sedgewick and Kevin Wayne in 2003-2007.