MTH524A - Algorithms

Preliminaries: Introduction to algorithms; Analyzing algorithms: space and time complexity; growth of functions; summations; recurrences; sets, etc. Greedy Algorithms: General characteristics; Graphs: minimum spanning tree; The knapsack problem; scheduling. Divide and Conquer: Binary search; Sorting: sorting by merging, quick sort. Dynamic Programming: Elements of dynamic programming; The principle of optimality; The knapsack problem; Shortest paths; Chained matrix multiplication. Graph Algorithms: Depth first search; Breadth first search; Backtracking; Branch and bound. Polynomials and FFT: Representation of polynomials; The DFT and FFT; Efficient FFT implementation. Number Theoretic Algorithms: Greatest common divisor; Modular arithmetic; Solving modular linear equations. Introduction to cryptography. Computational Geometry: Line segment properties; Intersection of any pair of segments; Finding the convex hull; Finding the closest pair of points. Heuristic and Approximate Algorithms: Heuristic algorithms; Approximate algorithms; NP hard approximation problems.