JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Pre-Requisites

UG level course in Algorithm Design and Analysis

Course Objectives:

• 1. Introduce students to the advanced methods of designing and analyzing algorithms.
• 2. The student should be able to choose appropriate algorithms and use it for a specific problem.
• 3. To familiarize students with basic paradigms and data structures used to solve advanced algorithmic problems.
• 4. Students should be able to understand different classes of problems concerning their computation difficulties.
• 5. To introduce the students to recent developments in the area of algorithmic design.

Course Outcomes

After completion of course, students would be able to:

• 1. Analyze the complexity/performance of different algorithms.
• 2. Determine the appropriate data structure for solving a particular set of problems.
• 3. Categorize the different problems in various classes according to their complexity.

UNIT - I

Sorting: Review of various sorting algorithms, topological sorting Graph: Definitions and Elementary Algorithms: Shortest path by BFS, shortest path in edge-weighted case (Dijkstra's), depth-first search and computation of strongly connected components, emphasis on correctness proof of the algorithm and time/space analysis, example of amortized analysis.

UNIT - II

Matroids: Introduction to greedy paradigm, algorithm to compute a maximum weight maximal independent set. Application to MST. Graph Matching: Algorithm to compute maximum matching. Characterization of maximum matching by augmenting paths, Edmond's Blossom algorithm to compute augmenting path.

UNIT - III

Flow-Networks: Maxflow-mincut theorem, Ford-Fulkerson Method to compute maximum flow, Edmond-Karp maximum-flow algorithm. Matrix Computations: Strassen's algorithm and introduction to divide and conquer paradigm, inverse of a triangular matrix, relation between the time complexities of basic matrix operations, LUP- decomposition.

UNIT - IV

Shortest Path in Graphs: Floyd-Warshall algorithm and introduction to dynamic programming paradigm. More examples of dynamic programming. Modulo Representation of integers/polynomials: Chinese Remainder Theorem, Conversion between base-representation and modulo-representation. Extension to polynomials. Application: Interpolation problem. Discrete Fourier Transform (DFT): In complex field, DFT in modulo ring. Fast Fourier Transform algorithm. Schonhage-Strassen Integer Multiplication algorithm.

UNIT - V

Linear Programming: Geometry of the feasibility region and Simplex algorithm NP-completeness: Examples, proof of NP-hardness and NP-completeness.

Recent Trends in problem solving paradigms using recent searching and sorting techniques by applying recently proposed data structures.

REFERENCES:

• 1. Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms".
• 2. Aho, Hopcroft, Ullman "The Design and Analysis of Computer Algorithms".
• 3. Kleinberg and Tardos."Algorithm Design".