17CS554 Advanced Algorithms syllabus for CS



A d v e r t i s e m e n t

Module-1 Analysis Techniques 8 hours

Analysis Techniques: Growth functions, Recurrences and solution of recurrence equations; Amortized analysis: Aggregate, Accounting, and Potential methods, String Matching Algorithms: Naive Algorithm; Robin-Karp Algorithm, String matching with Finite Automata, Knuth-Morris-Pratt and Boyer-Moore Algorithms

Module-2 Number Theoretic Algorithms 8 hours

Number Theoretic Algorithms: Elementary notions, GCD, Modular arithmetic, Solving modular linear equations, The Chinese remainder theorem, Powers of an element RSA Cryptosystem, Primality testing, Integer factorization, - Huffman Codes, Polynomials. FFT-Huffman codes: Concepts, construction, Proof correctness of Huffman's algorithm; Representation of polynomials

Module-3 DFT and FFT efficient implementation of FFT 8 hours

DFT and FFT efficient implementation of FFT, Graph Algorithms, Bellman-Ford Algorithm Shortest paths in a DAG, Johnson's Algorithm for sparse graphs, Flow networks and the Ford-Fulkerson Algorithm, Maximum bipartite matching.

Module-4 Computational Geometry-I 8 hours

Computational Geometry-I: Geometric data structures using, C, Vectors, Points, Polygons, Edges Geometric objects in space; Finding the intersection of a line and a triangle, Finding star-shaped polygons using incremental insertion.

Module-5 Computational Geometry-II 8 hours

Computational Geometry-II: Clipping: Cyrus-Beck and Sutherland-Hodman Algorithms; Triangulating, monotonic polygons; Convex hulls, Gift wrapping and Graham Scan; Removing hidden surfaces

Last Updated: Tuesday, January 24, 2023