Page 102 - Microsoft Word - B.Tech. Course Structure (R20) WITH 163 CREDITS

JNTUA College of Engineering (Autonomous), Ananthapuramu
Department of Computer Science & Engineering
Design and Analysis of Algorithms
Corse Code: Semester V(20) L T P C : 3 0 0 3
Course Objectives:
● To analyze the asymptotic performance of algorithms.
● To understand the write rigorous correctness proofs for algorithms.
● To familiarity with major algorithms and data structures.
● Apply important algorithmic design paradigms and methods of analysis.
● Synthesize efficient algorithms in common engineering design situations.

Course Outcomes (CO):
CO1: Explain the basic concepts of time and space complexity
CO2: Explain the basic concepts of divide-and-conquer Strategy, dynamics programmings.
CO3:Greedy and Algorithm
CO4:Describe the methodologies of how to analyze the following applications by Dynamics
CO5:Programming Algorithm.
CO6:Discuss the concept of graph coloring and back tracking
CO7:Analyze the performance of algorithms

UNIT-I: Introduction
Introduction: Algorithm, Pseudo code for expressing algorithms, performance Analysis-Space
complexity, Time complexity, Asymptotic Notation- Big oh notation, Omega notation, Theta notation
and Little oh notation, probabilistic analysis, Amortized analysis. Disjoint Sets- disjoint set operations,
union and find algorithms, spanning trees, connected components and bi- connected components.

UNIT-II:Divide and Conquer
General method, applications-Binary search, Quick sort, Merge sort, Stassen’s matrix multiplication.
Greedy method: General method, applications-Job sequencing with deadlines, 0/1 knapsack problem,
Minimum cost spanning trees, Single source shortest path problem.

UNIT-III:Dynamic Programming
General method, applications-Matrix chain multiplication, Optimal binary search trees, 0/1 knapsack
problem, All pairs shortest path problem, Travelling sales person problem, Reliability design.

UNIT-IV:Backtracking
General method, applications-n-queen problem, sum of subsets problem, graph coloring, Hamiltonian
cycles.

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.

Mdv
Mdv