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:00-8: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 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.
Notes on Recurrence Equations: Notes
Reading Assignment 1: 1/24/2006: Ch.2-6;
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: 8-3106
Office Hour: By appt.

Sherman Chow: schow@cs.nyu.edu, Room 715 715 Broadway, Phone: 8-3485
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].

Day and Time:: Tuesday 7:00-8: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 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.: 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.; 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.; 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.; 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.; 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.; 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.
Notes on Recurrence Equations: Notes
Reading Assignment 1: 1/24/2006: Ch.2-6;
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: 8-3106
Office Hour: By appt.; Sherman Chow: schow@cs.nyu.edu, Room 715 715 Broadway, Phone: 8-3485
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