Syllabus Design and Analysis of Algorithms - (410241) Credit Examination Scheme : 03 End-Sem (Paper) : 70 Marks 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)
