Fundamental Algorithms:
G22.1170
 Lecturer:

Prof. B. Mishra
Office Hours: By appt
Office Phone: 212.998.3464
Email Address: mishra@nyu.edu
Class mailing list:
http://www.cs.nyu.edu/mailman/listinfo/g22_1170_001_sp06
 Day and Time:

Tuesday 7:008:50pm EST
 Credits for Course:

3
 Prerequisites:

Mathematical Maturity
 Syllabus:
 Introduction

History of Algorithms, Models of Computation, Computational
Complexity, Cost Measure, Spectrum of Complexity
 Analysis of Algorithms

Big Omicron, Big Omega, Big Theta; Algebra on BigOh, Self
Recursive Algorithms and Recurrence Relations, Techniques for
Solving Recurrence Equations: Induction, Expansion, recursion
Tree, Telescopy, Summing factors, Range and Domain
Transformations; Examples: DivideandConquer Algorithms
and Master Equation, Randomized DivideandConquer
 Data Structures: Searching and Dictionaries

Arbitrary Universe & Linear Search, Universe with good
distribution properties: Hashing, Hash Functions, Collision
Resolution, Universal Hashing, Linearly Ordered Universe: Binary
Search Trees, Balanced Trees, 23 Trees
 Priority Queues, Sorting and Order Statistics

Heap and Heap Ordered Trees, Binomial Heap, Sorting: HeapSort,
QuickSort, Average Case Complexity of QuickSort; Lower Bound for
Sorting; Selection: QuickSelect, BFPRT Selection Algorithm
 String Matching

KarpRabin Algorithm, DFA (Deterministic Finite Automaton), and
Algorithms based on DFA.
 Graph Algorithms

Minimum Spanning Trees, Graph Traversal Techniques: BreadthFirst
and DepthFirst Search, Shortest Path Algorithm.
 Required Text(s):

Introduction to Algorithms,
Cormen, Leiserson & Rivest, MIT Press, MA.
Notes on Recurrence Equations: Notes
Reading Assignment 1: 1/24/2006: Ch.26;
Reading Assignment 2: 1/31/2006: Ch.7 & 8;
Reading Assignment 3: 2/07/2006: Ch. 9;
Reading Assignment 4: 2/14/2006: Ch. 4;
Reading Assignment 5: 2/21/2006: Ch. 10;
Reading Assignment 6: 2/28/2006: Ch. 23;
 Teaching Assistants:

Raghavan Dhandapani: raghavan@dept.cs.nyu.edu, Room 417 WWH, Phone: 83106
Office Hour: By appt.

Sherman Chow: schow@cs.nyu.edu, Room 715 715 Broadway, Phone: 83485
Office Hour: By appt.
 Homework(s):

Assignments;
[ HW1 due Wednesday, February, 22 2006];
[ HW2 due Wednesday, March, 8 2006];
[ HW3 due Wednesday, April, 5 2006];
[ HW4 due Wednesday, April, 26 2006].
Bud Mishra
January 1 2006