# Basic Algorithms -- Fall 2007

## Course Numbers

This is both V22.0310.001 Basic Algorithms Honors and
V22.0310.002 Basic Algorithms.

The assignments and exams
will be the same.

Those students registered for the Honors
section will have an additional project.

## When and Where

Lecture: Tuesday Thursday, 3:30-4:45, 102 ciww
Recitation: Wednesday, 9:30-10:45, 102 ciww

## Instructor

Prof. Joel Spencer
Office: 829ciww

Office Hours: Wednesday 1-2:30

Email: {lowercaselastname}@cims.nyu.edu

## Teaching Assistant

Marc Millstone
Office: 530ciww

Email: {lowercaselastname}@cims.nyu.edu

## Text

Algorithm Design by Jon Kleinberg and Eva Tardos (Addisson Wesley, publ.)
## Basic Information

There will be a final exam and a midterm.

There will be
assignments to be handed in pretty much every week.

Special Note: Collaboration on Weekly Assignments is
encouraged.

Each student must hand in a separate paper with
results written in their own words

and must note any students
with whom there has been collaboration.

Click here
postscript
LaTeX
pdf
for tentative syllabus and more info.

## Midterm

Click here
postscript
LaTeX
pdf

and for solutions
postscript
LaTeX
pdf
## Questions?

Send me an email: {lowercaselastname}@cs.nyu.edu
## Assignments

Due September 11
postscript
LaTeX
pdf

Due September 18
postscript
LaTeX
pdf

Due September 27
postscript
LaTeX
pdf

Due October 4 [Problem 3 REVISED!!]
postscript
LaTeX
pdf

Due October 18
postscript
LaTeX
pdf

Due October 25
postscript
LaTeX
pdf

Due Be Do Bee Due
postscript
LaTeX
pdf

Due November 8
postscript
LaTeX
pdf

Due November 15
postscript
LaTeX
pdf

Due November 20
postscript
LaTeX
pdf

## Solutions

Due September 11
postscript
LaTeX
pdf

Due September 18
postscript
LaTeX
pdf

Due September 27
postscript
LaTeX
pdf

Due Oct 4
postscript
LaTeX
pdf

Due Oct 18
postscript
LaTeX
pdf

Due Oct 25 (one problem missing)
postscript
LaTeX
pdf

Due Nov 8
postscript
LaTeX
pdf

Due Nov 15
postscript
LaTeX
pdf

Due Nov 20
postscript
LaTeX
pdf

## Assorted Stuff

Gale-Shapley Implementation
postscript
LaTeX
pdf

Heaps (REVISED Sept 26!!)
postscript
LaTeX
pdf

Topological Order and DAGs
postscript
LaTeX
pdf

Generating the Strong Components
postscript
LaTeX
pdf

NP-Complete Notes (revised slightly, Nov 14)
postscript
LaTeX
pdf
## Honors Project

Here are some ideas for this **optional** project.
postscript
LaTeX
pdf

Just in case:
Academic Integrity Policies