Reviews a number of important algorithms with emphasis on correctness and efficiency: solving recurrence equations; sorting algorithms; selection; binary search; hashing; binary search trees and balanced-tree strategies; tree traversal; dynamic storage management; partitioning; graphs; spanning trees; shortest paths; connectivity; depth first search; breadth first search. Dynamic programming, divide and conquer. Programming practice.
Advanced Algorithms (Introduction to Algorithmic Analysis) G22.1171 Prerequisite: G22.1170. 3 points.
Amortized analysis of algorithms. Binomial and Fibonacci heaps, splay trees, string matching, network flow. NP-completeness and approximation algorithms. Programming practice.
Elements of Discrete Mathematics G22.2340 Identical to G63.2050. 3 points.
Sets, relations, and functions. Algebraic structures. Recursion and induction. Combinatorial mathematics. Graph theory. Probability.
Symbolic Mathematical Computation G22.2542 Prerequisite: G22.1170. 3 points.
Commutative rings, modules, syzygies, Groebner basis, solving a system of polynomial equations, Euclidean domain, resultant, polynomial remainder sequences, formally real fields, Sturm's theorem, algebraic numbers, semi-algebraic sets, Tarski-Collin's algorithm.
Analysis of Algorithms (Honors) G22.3520 Prerequisites: G22.1170 or one semester of undergraduate algorithms and permission of the instructor. 4 points.
Design of algorithms and data structures. Review of searching, sorting, and fundamental graph algorithms (covered in G22.1170 and G22.1171). In-depth analysis of algorithmic complexity including advanced topics on recurrence equations and NP-complete problems. Advanced topics on lower bounds, randomized algorithms, amortized algorithms, and data structure design as applied to union-find, pattern matching, polynomial arithmetic, network flow, and matching.
GSAS /
NYU
-- last modified 24 September 1996