Scribd
Upload
45 views2 pages

AAD Syllabus for Algorithm Analysis

This document outlines the course objectives, units, outcomes, and experiments for an Analysis of Algorithms and Design course. The course aims to teach algorithm analysis techniques, design strategies including brute force, divide and conquer, greedy, dynamic programming, backtracking, and branch and bound. Students will analyze time and space complexity, apply design strategies to solve problems, and identify tractable and intractable algorithms. The course contains 5 units covering topics like algorithm analysis, design strategies, graph/tree algorithms, and complexity classes. Students will complete experiments involving implementing various algorithms and techniques.

Uploaded by

bhuvangates
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
45 views2 pages

AAD Syllabus for Algorithm Analysis

This document outlines the course objectives, units, outcomes, and experiments for an Analysis of Algorithms and Design course. The course aims to teach algorithm analysis techniques, design strategies including brute force, divide and conquer, greedy, dynamic programming, backtracking, and branch and bound. Students will analyze time and space complexity, apply design strategies to solve problems, and identify tractable and intractable algorithms. The course contains 5 units covering topics like algorithm analysis, design strategies, graph/tree algorithms, and complexity classes. Students will complete experiments involving implementing various algorithms and techniques.

Uploaded by

bhuvangates
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Subject Code Subject Name Category L T P C

CB19541 Analysis of Algorithms and Design + Lab PC 2 1 2 4


Course Objectives:
 Learn and understand the algorithm analysis techniques and complexity notations.
 Become familiar with the different algorithm design techniques for effective problem solving in
computing.
 Learn to apply the design techniques in solving various kinds of problems in an efficient way.
 Understand the limitations of Algorithm power.
 Solve variety of problems using different design techniques.
Unit-I Analysis of Algorithms 9
Introduction: Characteristics of Algorithm. Analysis of Algorithm: Performance Measurements of
Algorithm, Time and Space Trade-Offs, Asymptotic analysis of Complexity Bounds - Best, Average and
Worst-Case behaviour; Analysis of Recursive Algorithms through Recurrence Relations: Substitution
Method, Recursion Tree Method and Masters’ Theorem.
Unit-II Fundamentals of Algorithmic Strategies 9
Brute-Force, Heuristics, Greedy, Divide and Conquer, Dynamic Programming Methodologies;
Illustrations of these techniques for Problem-Solving, Bin Packing, Knapsack, Travelling Salesman
Problem.
Unit-III Algorithmic Strategies 9
Branch and Bound and Backtracking methodologies; Illustrations of these techniques for Problem-
Solving , n-Queens Problem , Graph Coloring, Knapsack, Travelling Salesman Problem.
Unit-IV Graph and Tree Algorithms 9
Traversal algorithms: Depth First Search (DFS) and Breadth First Search (BFS); Shortest path
algorithms, Transitive closure, Minimum Spanning Tree, Topological sorting, Network Flow Algorithm.
Unit-V Tractable, Intractable Problems and Advanced Topics 9
Tractable and Intractable Problems: Computability of Algorithms, Computability classes - P, NP, NP-
complete and NP-hard. Cook’s theorem, Standard NP-complete problems and Reduction techniques.
Advanced Topics: Approximation algorithms, Randomized algorithms, Class of problems beyond NP -
P SPACE, Introduction to Quantum Algorithms.
Contact Hours : 45
Course Outcomes:
On completion of the course, students will be able to:
 Analyse the time and space complexity of various algorithms and compare algorithms with respect
to complexities.
 Ability to decide and Apply Brute Force and Divide and Conquer design strategies to Synthesize
algorithms for appropriate computing problems.
 Ability to decide and Apply Greedy and Dynamic Programming techniques to Synthesize algorithms
for appropriate computing problems.
 Ability to decide and Apply Backtracking and Branch and Bound techniques to Synthesize
algorithms for appropriate computing problems.
 Ability to identify an algorithm is tractable or intractable
Text Books:
1. Fundamental of Computer Algorithms, E. Horowitz and S. Sahni.
2. The Design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft and J. Ullman.
Reference Books:
1. Introduction to Algorithms, T. H. Cormen, C. E. Leiserson and R. L. Rivest.
2. Computer Algorithms: Introduction to Design and Analysis, S. Baase.
3. The Art of Computer Programming, Vol. 1, Vol. 2 and Vol. 3, .D. E. Knuth.
List of Experiments

1. Finding Time Complexity of Algorithms


2. Design and implement algorithms using Brute Force Technique
3. Design and implement algorithms using Divide and Conquer Technique
4. Design and implement algorithms using Greedy Technique
5. Design and implement algorithms using Dynamic Programming
6. Design and implement algorithms using Backtracking
7. Design and implement algorithms using Branch and Bound

2 [Link] | AP (SG) | CSE | Rajalakshmi Engineering College

You might also like