Fundamental Algorithms:
G22.1170
 Lecturer:

Professor B. Mishra
Office Hours: Fri 45pm
Office Phone: 212.998.3464
Email Address: mishra@nyu.edu
 Day and Time:

Tuesday 5:006: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.
 Teaching Assistants:

Wei Shao, Room 410 WWH, weishao@cs.nyu.edu, Phone: 83105
Office Hour: Wed 3:304:30 pm

Evgeni Parilov, Room 417 WWH, parilov@cs.nyu.edu,Phone: 83106
Office Hour: Thu 7:008:00 pm
 Midterm Date:

November 7, 2000.
90 minutes, closed book.
 Final Date:

December 12, 2000.
TakeHome Open Book.
Problem 1 is trivial; Problems 2 and 3 are relatively harder and 
Problem 4 is probably harder than the rest.
[ FINAL EXAM (pdf) , Due
December 19 2000 67pm in class.]
 Homework(s):

Three assignments;
[ HW0 (pdf) , Due Oct 3;
HW1 (pdf) , Due Oct 24,
Soln to HW1 (pdf), prepared by E.Parilov;
HW2 (pdf) , Due Nov 21,
HW3 , Due Dec 5]
Bud Mishra
September 1 2000