CIE352 Design and Analysis of Algorithms Syllabus:
CIE352 Design and Analysis of Algorithms Syllabus – Anna University Regulation 2021
COURSE OBJECTIVES:
• To understand and apply the algorithm analysis techniques.
• To critically analyze the efficiency of alternative algorithmic solutions for the same problem.
• To understand different algorithm design techniques.
• To understand the limitations of Algorithmic power.
UNIT I ANALYSING ALGORITHMS
The Role of Algorithms in Computing – Growth of Functions – Recurrences – The Substitution Method – The Recurrence Tree Method – The Master Method – Probabilistic Analysis and Randomized Algorithms – Amortized Analysis – Aggregate Analysis – Accounting Method
UNIT II DIVIDE AND CONQUER & GREEDY DESIGN STRATEGIES
Analysis of Quick Sort, Merge Sort – Quick Sort Randomized Version – Sorting in Linear Time – Lower Bounds for Sorting – Selection in Expected Linear Time – Selection in Worst case Linear Time – Greedy Algorithms – Elements of Greedy Strategy – Huffman Code, Dijkstra’s Shortest Path Algorithm.
UNIT III DYNAMIC PROGRAMMING AND OTHER DESIGN STRATEGIES
Dynamic Programming – Matrix Chain Multiplication – Elements of Dynamic programming – Longest Common Sequences – Warshall’s and Floyds Algorithm – Transitive Closure – All Pairs Shortest Path Algorithm – Analysis – Backtracking – Graph Coloring Problem – Branch and Bound Strategy – Knapsack Problem.
UNIT IV FLOW NETWORKS AND STRING MATCHING
Flow Networks – Ford Fulkerson Method – String Matching – Naive String Matching Algorithm – Knuth Morris Pratt Algorithm – Analysis.
UNIT V NP PROBLEMS
NP-Completeness – Polynomial Time Verification – Theory of Reducibility – Circuit Satisfiability – NP – Completeness Proofs – NP Complete Problems: Vertex Cover, Hamiltonian Cycle and Traveling Salesman Problems – Approximation Algorithms – Approximation Algorithms to Vertex – Cover and Traveling Salesman Problems.
TOTAL: 45 PERIODS
COURSE OUTCOMES:
• Design algorithms for various computing problems.
• Analyze the time and space complexity of algorithms.
• Critically analyze the different algorithm design techniques for a given problem.
• Modify existing algorithms to improve efficiency.
• Analyze the concepts of NP problems
REFERENCES:
1. C.M. Krishna, Kang G. Shin, ―Real-Time Systems‖, McGraw-Hill International Editions,1st edition 2017.
2. Philip.A.Laplante, ―Real Time System Design and Analysis‖, Prentice Hall of India, 3rd Edition, 2004.
3. Rajib Mall, ―Real-time systems: theory and practice‖, Pearson Education, 2009.
3. Allen Burns, Andy Wellings, ―Real Time Systems and Programming Languages‖, Pearson Education, 2003.