[go: up one dir, main page]
Scribd
Upload
9 views2 pages

Syllabus CS215

The document outlines the course structure for 'Design and Analysis of Algorithms' at R.V.R. & J.C. College of Engineering, detailing objectives, outcomes, and units of study. Key topics include algorithm design strategies, performance analysis, greedy programming, dynamic programming, backtracking, and NP-Completeness. The course aims to equip students with the skills to analyze algorithms and apply various design strategies to solve real-world problems.

Uploaded by

pardhunalamala07
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
9 views2 pages

Syllabus CS215

The document outlines the course structure for 'Design and Analysis of Algorithms' at R.V.R. & J.C. College of Engineering, detailing objectives, outcomes, and units of study. Key topics include algorithm design strategies, performance analysis, greedy programming, dynamic programming, backtracking, and NP-Completeness. The course aims to equip students with the skills to analyze algorithms and apply various design strategies to solve real-world problems.

Uploaded by

pardhunalamala07
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

R.V.R. & J.C. College of Engineering (Autonomous), Guntur-522019, A.P.

R-24

CS215 DESIGN AND ANALYSIS OF ALGORITHMS L T P C Int Ext


(Common to branches CSE/CSB/CSM/CSO/IT) 3 - - 3.0 30 70
Semester III [Second Year]
COURSE OBJECTIVES:
The main objectives of this course are to:
1. Impart knowledge on algorithm design strategies and performance analysis of algorithms.
2. Introduce pattern matching algorithms and NP-Completeness

COURSE OUTCOMES:
After successful completion of the course, the students are able to
1. Analyze the performance of algorithms based on time and space complexities.
2. Apply algorithm design strategies to solve the real world problems.
3. Use string matching algorithms to solve given problems.
4. Differentiate P and NP class problems.

UNIT I Text Book - 1 [CO:1] (10)

Introduction: What is an Algorithm? Algorithm Specification, Performance Analysis, Randomized


Algorithms – Identifying the repeated element, primality testing.

Divide and Conquer: General Method, Binary search, finding the maximum and minimum,
Strassensmatrix multiplication ,Merge Sort, Quick sort, Divide and Conquer Run Time Recurrence
Relations.

UNIT II Text Book - 1 [CO:2] (15)

Greedy Programming: General Method, Knapsack problem, Job Sequencing with Dead Lines,
MinimumSpanning Tree - Prim's and Kruskal's algorithms, Single Source Shortest-Paths-Dijkstra's.

Dynamic Programming:: General Method, Multi Stage Graph, All Pairs Shortest Paths, Single
SourceShortest Paths-general Weights, Optimal Binary Search Trees, 0/1 Knapsack, Traveling
SalesmanProblem.

UNIT III Text Book - 1 [CO:3] (13)

Back tracking: General Method, 8-queen problem, Sum of Subsets, Graph Coloring, Hamiltonian
Cycles, Knapsack.

Branch and Bound: The Method Least Cost Search, The 15-puzzle, Control Abstraction for LC Search,
Bounding, FIFO branch and bound, LC branch and bound, 0/1 Knapsack problem, Traveling Salesman
Problem.

UNIT IV Text Book - 2 [CO:4] (12)

String Matching : The Naïve String Matching Algorithm, The Rabin-Karp Algorithm, String Matching
with Finite Automata, The KMP Algorithm.

NP-Completeness: Polynomial Time, Polynomial Time verification, NP Completeness and reducibility,


NP Complete Problems.

LEARNING RESOURCES:

TEXT BOOK(s):
1. E. Horowitz, S. Sahni and S.Rajasekaran, "Fundamentals of Computer Algorithms", Galgotia
Publication.

B.Tech.(CS)/R-24/2024-2025 Printed through web on 07-08-2025 16:41:13 Page 1/ 2


R.V.R. & J.C. College of Engineering (Autonomous), Guntur-522019, A.P. R-24

2. T. H. Cormen, Leiserson, Rivest and Stein, "Introduction of Computer Algorithm", PHI.

REFERENCE BOOK(s):
1. Sara Basse, A.V. Gelder, "Computer Algorithms", Addison Wesley.
2. Richard E. Neapolitan, “Foundations of Algorithms―, Jones & Bartlett Learning.

B.Tech.(CS)/R-24/2024-2025 Printed through web on 07-08-2025 16:41:13 Page 2/ 2

You might also like