LNMIIT, Jaipur

Department of Computer Science & Engineering

Programme: Course Title: Course Code:

B. Tech. (CSE, CCE) Design and Analysis of Algorithms CSE325
Type of Course: Pro- Prerequisites: Total Contact Hours:
gram Core Data Structures and Algorithms 40 +20
Year/Semester: Lecture Tutorial Hrs/Week: Practical Hrs/Week: Credits:
Hrs/Week:
2/Odd 0 2 4
3

Learning Objective:

The objective of this course is to introduce the notion of algorithm, how to describe an algorithm
and model of computation for which an algorithm for a problem is to be designed. Time and space
complexities will be introduced to express the resource needed by an algorithm and to compare
different algorithms for a problem and to classify an algorithm as efficient or non-efficient. Algo-
rithm design paradigms such as Divide and Conquer, Greedy and Dynamic programming will be
introduced that will enable a student to apply one of the paradigms to design algorithm for a given
problem. The last part of the course will introduce the notion of NP-completeness to capture the
hardness of a problem and will show several fundamental problems in Computer Science and en-
gineering to be NP-complete.

Course outcomes (COs):

On completion of this course, the students will have the ability to: Bloom’s Level
CO-1 Analyze the complexity of algorithms in terms of asymptotic notations 3
and implement the algorithms
CO-2 Perform Analysis of important algorithmic design paradigms and imple- 4
ment one algorithm designed using each paradigm
CO-3 Design efficient algorithmic solutions to graph related problems 6
and implement them
CO-4 Understand the concept of Computational Intractability 2

Course Topics Lecture CO Map-

Hours ping
UNIT – I (Introduction) 14

1.1 What is algorithm? How to describe an algorithm? Why analyze al- 1 CO1
gorithms? RAM Model of Computation.

CSE Department, LNMIIT Jaipur Page | 1-3

 LNMIIT, Jaipur
Department of Computer Science & Engineering

1.2 Asymptotic notation: Definitions of big-Oh, big-Omega, big-Theta, small- 2

oh and problem solving
1.3 Recurrence relations: iterative method, substitution method, recursion-tree
3
method, Master method with problem solving
1.4 Sorting Algorithms: Bubble sort, Insertion sort, and Selection sort with complexity 3
analysis and proof of correctness
1.5 Lower bound of sorting, Counting Sort, Radix Sort, Bucket Sort with complexity 3
analysis and proof of correctness
1.6 Concepts of Graph: Graph Representation, Applications of graphs, Hand-Shaking 2
Lemma, Different Graph types like connected, strongly connected, etc.

UNIT – II (Design Paradigm) 13

2.1 Divide and Conquer: Stassen’s Matrix Multiplication, Merge Sort, Quick
Sort; Complexity Analysis and proof of Correctness of all the algorithms.
3
2.2 Greedy Algorithms: Huffman Coding, Fractional Knapsack, Kruskal’s CO2
4
Algorithm, Prim’s Algorithm and its implementation using heap data structure.
Complexity Analysis and Correctness proof of all the algorithms.
2.3 Dynamic Programming: Introduction to Dynamic Programming; Top
4
down versus Bottom Up approach of Problem solving; Computing Fibonacci
Number; Matix Chain Multiplication Algorithms; Longest Common subse-
quence, Complexity Analysis and proof of Correctness of all the algorithms
2.4 Backtracking: 8 Queen problem with complexity analysis and Correct-
1
ness proof.
2.5 Branch and Bound: 0/1 Knapsack problem with complexity Analysis and
1
Correctness proof.

UNIT-III (Graph Algorithms) 7

3.1 Breadth First Search (BFS): BFS Algorithm, BFS edge classification
for directed and undirected graphs, Applications of BFS: Shortest Path on
un-weighted graph, testing bipartiteness 2
3.2 Depth First Search (DFS): DFS Algorithm, DFS edge classification for di-
rected and undirected graphs, Application of DFS like Topological Sort, Cycle 2 CO3
Detection.
3.3 Shortest Path Algorithms: Dijkstra’s Single source Algorithm; All pair 3
Shortest paths: Floyd-Warshall and Bellman Ford;

CSE Department, LNMIIT Jaipur Page | 2-3

 LNMIIT, Jaipur
Department of Computer Science & Engineering

UNIT-IV (NP-Completeness and Computational Intractability) 6

4.1 Optimization and Decision Problems, D e c i s i o n P r o b l e m s : Boolean
Satisfiability Problem, Hamiltonian Cycle, Independent Set, Clique, Vertex 3
Cover, and Vertex Cover; Definitions of P and NP; Karp and Cook reduction; CO4
4.2 NP-complete and NP-hard; Cook-Levin Theorem; Tractability and In- 3
tractability problems; Proving NP-completeness of Clique Decision Problem.
Independent Set Decision Problem, Vertex Cover Decision Problem;
Design and Analysis of Algorithm Lab (20 Hrs.)
Lab Description of problem Co map- Hours
No ping
1 Compute the nth Fibonacci Number using recursive and non-recursive CO 1 2
program and compute the time taken by each program using time ()
function and estimate the time complexity
2 Implementations of Sorting Algorithms: Bubble sort, Insertion sort, and CO 1 2
Selection sort and compare the running time
3 Implementations of Counting Sort, Radix Sort, and Bucket Sort, Merge CO 1, 2
Sort, and Quick Sort CO 2
4-5 Implementation of Kruskal’s Algorithm using Union Find Data struc- CO 2 4
tures
6-7 Implementation of Prim’s Algorithm and its implementation using CO 2 4
heap data structure
8 Implementation of Dynamic programming-based algorithm for Long- CO 2 2
est Common subsequence
9 Implementation of backtracking algorithm to find all possible solu- CO 2 2
tions of 8 Queen problem
10 Implementation of (i) DFS based algorithm to test connectedness of a CO 3 2
graph and testing acyclicity of a graph
(ii) BFS based algorithm to test whether a graph is bipartite or not

Textbook References:
Text Book:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L. and Stein, Clifford. Introduction to Al-
gorithms. 4th Edition: The MIT Press, 2001.

Reference books:
1. Ellis Horowitz, Sartaj Sahani, Sanguthevar Rajasekaran. Fundamental of Computer Algo-
CSE Department, LNMIIT Jaipur Page | 3-3
 LNMIIT, Jaipur
Department of Computer Science & Engineering

rithm. 1st Edition: University Press, 2008.

2. Skiena Steven, S. The algorithm design manual, 2008
3. Kleinberg, J., & Tardos, É. Algorithm design. 1st Edition: Pearson Education India, 2006

Additional Resources:
1. [Link]
analysis-of-algorithms-spring-2015/
2. [Link]
to-algorithms-fall-2011/
3. [Link]
4. [Link]/courses/106/101/106101060/

Evaluation Method
Item Weightage (%)
Assignments (Theory) 3x3=9
Midterm (Theory) 26
Practical Lab 5 (attendance) + 8 (mid-term) + 12 (end-term) = 25
End Term (Theory) 40

*Please note, as per the existing institute’s attendance policy the student should have a minimum of 75%
attendance. Students who fail to attend a minimum of 75% lectures will be debarred from the End Term/Fi-
nal/Comprehensive examination.

CSE Department, LNMIIT Jaipur Page | 4-3

 LNMIIT, Jaipur
Department of Computer Science & Engineering

CO and PO Correlation Matrix (For CSE)

CO PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3
CO1 1 1 1 3 3 3 2
CO2 1 1 3 1 3 3 3 3 2 2
CO3 3 3 3 1 3 3 3 3 2 2
CO4 3 3 3 3 3 3 3 3 3

CO and PO Correlation Matrix (For Others)

CO PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
CO1 1 1 1 3 3 3
CO2 1 1 3 1 3 3 3
CO3 1 1 3 1 3 3 3
CO4 3 3 3 3 3 3

Last Updated On:

Updated By:

Approved By:

CSE Department, LNMIIT Jaipur Page | 5-3