DESIGN AND ANALYSIS OF ALGORITHMS

OBJECTIVES:
Upon completion of this course, college students will have the ability to do the next:
• Analyze the asymptotic efficiency of algorithms.
• Write rigorous correctness proofs for algorithms.
• Exhibit a familiarity with main algorithms and information constructions.
• Apply necessary algorithmic design paradigms and strategies of research.
• Synthesize environment friendly algorithms in frequent engineering design conditions
UNIT-I:
Introduction: What’s an Algorithm, Algorithm Specification, Pseudocode Conventions
Recursive Algorithm, Efficiency Evaluation, Area Complexity, Time Complexity, Amortized
Complexity, Amortized Complexity, Asymptotic Notation, Sensible Complexities, Efficiency
Measurement.
UNIT-II:
Dived and Conquer: Common Technique, Faulty Chessboard, Binary Search, Discovering the
Most and Minimal, Merge Kind, Fast Kind, Efficiency Measurement, Randomized
Sorting Algorithms.
UNIT-III:
The Grasping Technique: The Common Technique, Knapsack Downside, Job Sequencing with Deadlines,
Minimal-cost Spanning Timber, Prim’s Algorithm, Kruskal’s Algorithms, An Optimum
Randomized Algorithm, Optimum Merge Patterns, Single Supply Shortest Paths.
UNIT-IV:
Dynamic Programming: All – Pairs Shortest Paths, Single – Supply Shortest paths Common
Weights, String Version, 0/1 Knapsack, Reliability Design,
UNIT-V:
Backtracking: The Common Technique, The 8-Queens Downside, Sum of Subsets, Graph Coloring ,
Hamiltonian Cycles.
UNIT-VI:
Department and Certain: The Technique, Least value (LC) Search, The 15-Puzzle: an Instance, Management
Abstraction for LC-Search, Bounding, FIFO Department-and-Certain, LC Department and Certain, 0/1
Knapsack Downside, LC Department-and Certain Answer, FIFO Department-and-Certain Answer,
Touring Salesperson.
OUTCOMES:
College students who full the course could have demonstrated the power to do the next:
III 12 months – II Semester
L T P C
four Zero Zero 3
• Argue the correctness of algorithms utilizing inductive proofs and invariants.
• Analyze worst-case operating instances of algorithms utilizing asymptotic evaluation.
• Describe the divide-and-conquer paradigm and clarify when an algorithmic design
state of affairs requires it. Recite algorithms that make use of this paradigm. Synthesize divide-andconquer algorithms. Derive and resolve recurrences describing the efficiency of divideand-conquer algorithms.
• Describe the dynamic-programming paradigm and clarify when an algorithmic design
state of affairs requires it. Recite algorithms that make use of this paradigm. Synthesize dynamicprogramming algorithms, and analyze them.
• Describe the grasping paradigm and clarify when an algorithmic design state of affairs requires
it. Recite algorithms that make use of this paradigm. Synthesize grasping algorithms, and
analyze them.
TEXT BOOKS:
1. Fundamentals of pc algorithms E. Horowitz S. Sahni, College Press
2. Introduction to AlgorithmsThomas H. Cormen, PHI Studying
REFERENCE BOOKS
1. The Design and Evaluation of Pc Algorithms, Alfred V. Aho, John E. Hopcroft, Jeffrey D.
Ullman
2. Algorithm Design, Jon Kleinberg, Pearson.