UCS501 Algorithm Analysis and Design
Basics Of Algorithm Analysis & Design: stacks,
queues, trees, heaps, sets and graphs. Algorithm Definition, Analyzing
algorithms, order arithmetic, time and space complexity.
Algorithm Design Techniques: Divide and Conquer: general method, merge sort, selection problem, Recurrences, Solving Recurrences by Substitution method, Changing variables and Recursive Tree Method, Other applications of divide & conquer.
Greedy method: Job Sequencing with Deadlines, Knapsack problem, Optimal merge patterns, Optimal Storage on tapes, Minimum spanning trees & other applications of Greedy method
Dynamic Programming: Use of table instead of recursion, all pair shortest Path, 0/1 knapsack, Matrix Chain Multiplication, optimal binary search tree, Longest Common Subsequence, Traveling salesperson problem & other applications of Dynamic programming
Search and Traversal: Search techniques: breadth first search, depth first search, code optimization, Internal and External sorting, searching and merging techniques
Backtracking: 8 queens problem, sum of subsets, graph coloring, knapsack problem & other
Applications of Backtracking
Branch and Bound: 0/1 knapsack problem, traveling salesperson problem. Lower Bound Theory: Comparison trees for sorting and searching, Oracles and adversary arguments, techniques for algebraic problems.
Problem clauses: P, NP, NP- Hard and NP-complete, deterministic and non-deterministic polynomial time algorithm approximation and algorithm for some NP complete problems.
Introduction to parallel algorithms, Genetic algorithms, intelligent algorithms
Laboratory work: Implementation of all the algorithmic techniques studied.
1. E.Horowitz & S.Sahani, Fundamentals of Computer Algorithms. Galgotia Publications.
1. Corman, Leiserson & Rivest, Introduction to Algorithms, MIT Press.
2. Sara Basse, A.V. Geider, Computer Algorithms, Introduction to Design and Analysis.
3. Robert Lafore,, Data Structures & Algorithms in Java, Pearson Education Asia.