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.


Text Books:

1.      E.Horowitz & S.Sahani, Fundamentals of Computer Algorithms. Galgotia Publications.

2.      Goodrich, Tamassia, Algorithm Analysis & Design, Wiley.


Reference Books:

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.