Design and Analysis of Algorithms - 410241 Credit Examination Scheme : 03 In-Sem (Paper) : 30 Marks End-Sem (Paper) : 70 Marks Unit I Algorithms and Problem Solving Algorithm : The Role of Algorithms in Computing - What are algorithms, Algorithms as technology, Evolution of Algorithms, Design of Algorithm, Need of Correctness of Algorithm, Confirming correctness of Algorithm - sample examples, Iterative algorithm design issues. Problem solving Principles : Classification of problem, problem solving strategies, classification of time complexities (linear, logarithmic etc.) (Chapter - 1) Unit II Analysis of Algorithms and Complexity Theory Analysis : Input size, best case, worst case, average case, Counting Dominant operators, Growth rate, upper bounds, asymptotic growth, O, Ω, , o and ω notations, polynomial and non-polynomial problems, deterministic and non-deterministic algorithms, P - class problems, NP-class of problems, Polynomial problem reduction NP complete problems - vertex cover and 3-SAT and NP hard problem - Hamiltonian cycle. (Chapter - 2) Unit III Greedy And Dynamic Programming algorithmic Strategy Greedy strategy : Principle, control abstraction, time analysis of control abstraction, knapsack problem, scheduling algorithms-Job scheduling and activity selection problem. Dynamic Programming : Principle, control abstraction, time analysis of control abstraction, binomial coefficients, OBST, 0/1 knapsack, Chain Matrix multiplication. (Chapter - 3) Unit IV Backtracking and Branch-n-Bound Backtracking : Principle, control abstraction, time analysis of control abstraction, 8-queen problem, graph coloring problem, sum of subsets problem. Branch-n-Bound : Principle, control abstraction, time analysis of control abstraction, strategies - FIFO, LIFO and LC approaches, TSP, knapsack problem. (Chapter - 4) Unit V Amortized Analysis Amortized Analysis : Aggregate Analysis, Accounting Method, Potential Function method, Amortized analysis-binary counter, stack Time-Space tradeoff, Introduction to Tractable and Non-tractable Problems, Introduction to Randomized and Approximate algorithms, Embedded Algorithms : Embedded system scheduling (power optimized scheduling algorithm), sorting algorithm for embedded systems. (Chapter - 5) Unit VI Multithreaded and Distributed Algorithms Multithreaded Algorithms - Introduction, Performance measures, Analyzing multithreaded algorithms, Parallel loops, Race conditions. Problem Solving using Multithreaded Algorithms - Multithreaded matrix multiplication, Multithreaded merge sort. Distributed Algorithms - Introduction, Distributed breadth first search, Distributed Minimum Spanning Tree. String Matching - Introduction, The Naive string matching algorithm, The Rabin-Karp algorithm. (Chapter - 6)
