3 Review(s)

Unit III Greedy And Dynamic Programming algorithmic StrategyGreedy 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-BoundBacktracking : 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 VAmortized AnalysisAmortized 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 VIMultithreaded and Distributed AlgorithmsMultithreaded 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)