Syllabus
|
Course Code: Program Elective -II MTCE-111 Course Name: Algorithm Analysis and Design |
||
| MODULE NO / UNIT | COURSE SYLLABUS CONTENTS OF MODULE | NOTES |
|---|---|---|
| 1 | Introduction: Algorithm concepts, Analyzing and design, Pseudocode conventions, asymptotic efficiency of algorithms, asymptotic notations and their properties. Analysis Techniques: Growth Functions, Recurrences and Solution of Recurrence equation-, Amortized Analysis, Aggregate, Accounting and Potential Methods, Probabilistic analysis concepts, hiring problem and its probabilistic analysis, String Matching: naive string Matching, Rabin Karp, and String matching with finite Automata, KW and Boyer – Moore algorithm. |
|
| 2 | Number Theoretic Algorithms: Elementary notions, GCD, Modular Arithmetic, Solving modular linear equations, The chines remainder theorem, Powers of an element, RSA cryptosystem, Primality testing, Integer factorization, Polynomials. Huffman Codes: Concepts, construction, correctness of Huffman’s algorithms; Representation of polynomials, DFT, FFT, Efficient implementation of FFT, Graph Algorithm, Bellman Ford Algorithm, Single source shortest paths in a DAG Johnson’s Algorithm for sparse graph, Flow networks & Ford fulkerson Algorithm, Maximum bipartite matching. |
|
| 3 | Computational Geometry: Geometric structures using C++: Vectors, points, Polygons, Edges: Geometric Objects in space: Finding the intersection of a line & triangle, Finding star shaped polygons and convex hull using incremental insertion. |
|
| 4 | NP-completeness Concepts: Polynomial time verification, NP-completeness and reducibility, showing problems to be NP-complete like Clique problem, vertex cover problem etc. Approximation algorithms of these problems. |
|
