Fundamental Algorithms

G22.1170 - Summer 2006

Mondays 6:00-7:00pm, Wednesdays 6:00-8:20pm

Room 102 WWH

Instructor Information

Shabsi Walfish
walfish AT cs DOT nyu DOT edu
Room 605, WWH
Office Hours: Monday 7:00-8:00pm

General Announcements and Course Information

The first class will be held on Monday, May 15th (the recitation session). During the first class, I will cover some administrative issues such as homework and grading policies, as well as doing a brief review of some of the mathematical tools you are expected to know coming into the course. A tentative syllabus for the remainder of the course is provided below. Check this page frequently for additional updates in the coming days.

Textbooks

The primary textbook for this course is Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (commonly referred to as the "CLRS" book). This is a required textbook, and some of the problems from the textbook will be assigned as homework in addition to the reading assignments.

Additionally, I  recommend obtaining a copy of An Inside Guide to Algorithms: their Application, Adaptation, Design, and Analysis by Alan Siegel and Richard Cole. The book is presently unfinished (and thus unpublished), but I find many of the explanations and intuitions it provides to be more helpful than the analogous content in CLRS. Photocopies of the current version can be purchased at Unique Copy, at 252 Greene Street.

Grading

Grading will be based on homeworks (to be graded by the TA), a midterm exam, and a cumulative final exam. Homeworks will be assigned approximately once every two weeks, so there will be between 4 and 6 assignments, each weighted equally. Homeworks will account for 50% of the course grade.

Academic Integrity

Students may not share homework solutions, and are not allowed to use the internet or other outside sources to find solutions to the homework problems. The work you hand in must be your own. Students are encouraged to read the departmental policy on Academic Integrity (which requires that a grade of F be given for the entire course if any instance of cheating occurs).

Class Mailing List

All registered students are required to subscribe to the class mailing list. To subscribe, follow the instructions at:
http://www.cs.nyu.edu/mailman/listinfo/g22_1170_001_su06

Syllabus

A tentative syllabus for the course is given below. There are likely to be some minor changes to the syllabus below, but all major topics included on the syllabus for the algorithms section of the Core Exam will certainly be covered.
Week
Date
Topics
Chapters
Notes
Assignments
1 5/17 Introduction: Basic sorting techniques (insertion sort, and merge sort), analyzing correctness and efficiency of algorithms 1,2,3, Appendix A Introduction
(Slides) (Handout)		 Homework #1
2 5/24 Mathematical Tools: Recurrence equations (recursion trees and the master method), probability, worst case vs. average case analysis 4,5, Appendix C Mathematical Tools
(Slides) (Handout)		  
3 5/31 Sorting: Bucket Sort, Heapsort, Quicksort. Lower bounds for sorting. 6,7,8 Sorting
(Slides) (Handout)		 Homework #2
4 6/7 Selection and Hashing: Selection in linear time, linked lists and hash tables, hash functions 9, 10, 11 Selection and Hashing
(Slides) (Handout)		  
5 6/14 Trees: Binary Trees, searching, tree traversal, 2-3 Trees, graph traversal (BFS / DFS), topological sort, strongly connected components (10?), 12, 22,  (14?) Trees and Graphs
(Slides) (Handout)

Additional notes on 2-3 Trees by Victor Shoup
  Homework #3
6 6/21 Midterm Exam
   
7 6/28 Minimum Spanning Trees and Shortest Paths:
Prim's, Kruskal's, and Dijkstra's algorithms. Proof techniques.		 23,24 More on Graphs
(Slides) (Handout)		  
8 7/5 Dynamic Programming: Matrix multiplication, longest common subsequence,  all pairs shortest paths 15,25 Dynamic Programming
(Slides) (Handout)		 Homework #4
9 7/12 Amortization: Binary counters and dynamic tables 17    
10 7/19 Greedy Algorithms: Activity selection, Huffman codes 16 Greedy Algorithms
(Slides) (Handout)		 Homework #5
11 7/26 Introduction to NP and NP-Completeness
 34    
12 8/2 Final Exam (strict 2 hr 20 min time limit)