Scribd
Upload
137 views2 pages

Design and Analysis of Algorithms Course

This document outlines the course objectives and outcomes for the Design and Analysis of Algorithms course. The course introduces techniques for analyzing algorithm performance, including asymptotic analysis. It covers major algorithm design strategies like divide-and-conquer, dynamic programming, greedy algorithms, and branch and bound. Students will learn to evaluate algorithms using best, average, and worst-case analysis, and understand the differences between tractable and intractable problems. The course is divided into five units covering topics like algorithm analysis, disjoint sets, backtracking, dynamic programming, greedy methods, and NP-hard and NP-complete problems.

Uploaded by

sushankreddy0712
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
137 views2 pages

Design and Analysis of Algorithms Course

This document outlines the course objectives and outcomes for the Design and Analysis of Algorithms course. The course introduces techniques for analyzing algorithm performance, including asymptotic analysis. It covers major algorithm design strategies like divide-and-conquer, dynamic programming, greedy algorithms, and branch and bound. Students will learn to evaluate algorithms using best, average, and worst-case analysis, and understand the differences between tractable and intractable problems. The course is divided into five units covering topics like algorithm analysis, disjoint sets, backtracking, dynamic programming, greedy methods, and NP-hard and NP-complete problems.

Uploaded by

sushankreddy0712
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
You are on page 1/ 2

R18 B.Tech.

CSE (AIML) III Year JNTU Hyderabad


DESIGN AND ANALYSIS OF ALGORITHMS

B.Tech. III Year I Sem. L T P C


3 0 0 3
Prerequisites:
1. A course on “Computer Programming and Data Structures”.
2. A course on “Advanced Data Structures”.
Course Objectives:
1. Introduces the notations for analysis of the performance of algorithms.
2. Introduces the data structure of disjoint sets.
3. Describes major algorithmic techniques (divide-and-conquer, backtracking, dynamic
Programming, greedy, branch and bound methods) and mention problems for which each
technique is appropriate
4. Describes how to evaluate and compare different algorithms using worst-, average-, and bestcase
analysis.
5. Explains the difference between tractable and intractable problems, and introduces the
Problems that are P, NP and NP complete.
Course Outcomes:
1. Ability to analyze the performance of algorithms
2. Ability to choose appropriate data structures and algorithm design methods for a specified
application
3. Ability to understand how the choice of data structures and the algorithm design methods
Impact the performance of programs

UNIT – I : Introduction: Algorithm, Performance Analysis-Space complexity, Time complexity, Asymptotic


Notations- Big oh notation, Omega notation, Theta notation and Little oh notation.
Divide and conquer: General method, applications-Binary search, Quick sort, Merge sort, Strassen’s matrix
multiplication.

UNIT – II: Disjoint Sets: Disjoint set operations, union and find algorithms
Backtracking: General method, applications, n-queen’s problem, sum of subsets problem, graphcoloring

UNIT – III: Dynamic Programming: General method, applications- Optimal binary search trees, 0/1
knapsackproblem, All pairs shortest path problem, Traveling sales person problem, Reliability design.

UNIT – IV: Greedy method: General method, applications-Job sequencing with deadlines, knapsack
problem,Minimum cost spanning trees, Single source shortest path problem.

UNIT – V: Branch and Bound: General method, applications - Travelling sales person problem, 0/1 knapsack
problem - LC Branch and Bound solution, FIFO Branch and Bound solution.
NP-Hard and NP-Complete problems: Basic concepts, non-deterministic algorithms, NP - Hard and
NP-Complete classes, Cook’s theorem.

TEXT BOOK: 1. Fundamentals of Computer Algorithms, Ellis Horowitz, Satraj Sahni and Rajasekharan,
University Press.
REFERENCE BOOKS:
1. Design and Analysis of algorithms, Aho, Ullman and Hopcroft, Pearson education.
2. Introduction to Algorithms, second edition, T. H. Cormen, C.E. Leiserson, R. L. Rivest, and C.
Stein, PHI Pvt. Ltd./ Pearson Education.
3. Algorithm Design: Foundations, Analysis and Internet Examples, M.T. Goodrich and R.
Tamassia, John Wiley and sons.

You might also like