Professor B. Mishra
Office Hours: Fri 4-5pm
Office Phone: 212.998.3464
Email Address: email@example.com
- Day and Time:
Tuesday 5:00-6:50pm EST
- Credits for Course:
History of Algorithms, Models of Computation, Computational
Complexity, Cost Measure, Spectrum of Complexity
- Analysis of Algorithms
Big Omicron, Big Omega, Big Theta; Algebra on Big-Oh, Self
Recursive Algorithms and Recurrence Relations, Techniques for
Solving Recurrence Equations: Induction, Expansion, recursion
Tree, Telescopy, Summing factors, Range and Domain
Transformations; Examples: Divide-and-Conquer Algorithms
and Master Equation, Randomized Divide-and-Conquer
- 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, 2-3 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
Karp-Rabin Algorithm, DFA (Deterministic Finite Automaton), and
Algorithms based on DFA.
- Graph Algorithms
Minimum Spanning Trees, Graph Traversal Techniques: Breadth-First
and Depth-First Search, Shortest Path Algorithm.
- Required Text(s):
Introduction to Algorithms,
Cormen, Leiserson & Rivest, MIT Press, MA.
- Teaching Assistants:
Wei Shao, Room 410 WWH, firstname.lastname@example.org, Phone: 8-3105
Office Hour: Wed 3:30-4:30 pm
Evgeni Parilov, Room 417 WWH, email@example.com,Phone: 8-3106
Office Hour: Thu 7:00-8:00 pm
- Midterm Date:
November 7, 2000.
90 minutes, closed book.
- Final Date:
December 12, 2000.
Take-Home 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 6-7pm in class.]
[ 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]
September 1 2000