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