Syllabus for Semester III, B. Tech.
(Computer Science & Engineering)
Course Code: 24CS01TH0302 Course: Design and Analysis of Algorithms
L: 3 Hrs, T: 0 Hr, P: 0 Hr, Per Week Total Credits: 03
Course Objectives
The objective of this course is
• to introduce students to techniques for effective problem solving in computing.
• developing skills to solve real life applications which involving algorithm development.
• making students capable of analyzing different paradigms and their complexities to solve
a given problem in efficient way.
Syllabus
Unit I
Mathematical foundations- Recurrence relations and their solutions, Complexity Calculation-
Substitution Method, Recurrence tree method, Master Method, Asymptotic notations for analysis
of algorithms, Amortized Analysis.
Unit II
Greedy method – Basic strategy, Minimum cost spanning trees- Prim’s Algorithm, Kruskal’s
Algorithm, Fractional Knapsack Problem, Huffman Coding, Activity Selection Problem
Unit III
Dynamic Programming - Basic strategy, Bellmen ford algorithm, All pairs shortest path,
Multistage Graphs, Optimal Binary Search Trees, Traveling Salesman Problem, String Editing,
Longest Common Subsequence problem and its variations.
Unit IV
Divide and Conquer- Basic strategy, Binary Search, Quick Sort, Merge sort, Maximum sub-array
problem, Closest pair of points problem, Convex hull problem.
Backtracking- Basic strategy, N-Queen's problem, Graph Coloring, Hamiltonian Cycles, Sum of
Subset Problem.
Unit V
NP Theory: Non-Deterministic Algorithms, NP, NP-hard and NP-complete problems, Decision
and Optimization problems, Graph based problems on NP Principle-vertex cover problem, clique
cover problem, Independent Set Problem, Proving NP-completeness of various problems.
Course Outcomes
On successful completion of the course, students will be able to:
1. Comprehend the foundational principles involved in the design and analysis of algorithms.
2. Identify the algorithmic solution to solve a given problem.
3. Apply algorithmic techniques to solve real-life and complex computational problems.
4. Evaluate efficiency and complexity of various algorithms using mathematical analysis.
Text Books
1. Thomas H. Cormen et.al; “Introduction to Algorithms”; 3 Edition; Prentice Hall, 2009.
2. Horowitz, Sahani and Rajasekaram; “Computer Algorithms”, Silicon Press, 2008.
3. Sridhar S.; “Design and Analysis of Algorithms”, Oxford University Press.
4. Brassard and Bratley; “Fundamentals of Algorithms”, 1 Edition; Prentice Hall, 1995.
Reference Books
1. Parag Himanshu Dave, Balchandra Dave, “Design and Analysis of Algorithms” Pearson
Education, O'relly publication.
2. Jon Kleinberg, Éva Tardos, “Algorithm design”, Pearson, 2005.
3. Richard Johnsonbaugh, “Algorithms”, Pearson Publication, 2003.
