MANIPAL UNIVERSITY JAIPUR

Faculty of Engineering | School of Computer Science and Engineering

Department of Computer Science and Engineering
Course Hand-out
Design & Analysis of Algorithm | CS3102 | 3 1 0 4
Session: Aug 2024 – Dec 2024 | Program: B.Tech. | Semester: V

Course Coordinator: Dr. Amit Garg/ Dr. Ajit Noonia

Faculty: Dr Amit Garg (Section A) | Mr. Sunil Kumar Patel (Section-E & J) | Mr. Lav Upadyay (Section-B & H) | Dr. Susheela
Vishnoi (Section-F & I) Dr. Ajit Noonia (Section-G) | | Dr. S. S. Shekhawat (Section-D) Mr. Tarun Jain (Section-C)

A. Introduction: This course aims to discuss various techniques for designing efficient algorithms and analyze their
complexity and performance. The course is intended to provide the students an experience in algorithm design and to
emphasize both the practical as well as the mathematical formulation including the mentioned points.
a. Analyse the asymptotic performance of the designed algorithms.
b. Write correctness proofs for algorithms.
c. Demonstrate familiarity with major algorithms and data structures.
d. Apply important algorithmic design paradigms and methods of analysis.
e. Demonstrate efficient algorithms in common engineering design situations.
Pre-requisite(s): Programming in C [CS 1101] and Data Structures [CS 1301].

B. Course Outcomes: At the end of the course, students will be able to

[CS3102.1] Analyze the running times of algorithms using asymptotic analysis. (Bloom’s Level: 4 Analyze)
[CS3102.2] Contrast and design algorithms using the divide-and-conquer and graph-searching algorithms to solve
business problems, hence enhancing analytical skills. (Bloom’s Level: 4 Analyze)
[CS3102.3] Apply the concept of greedy and dynamic programming approaches to solving real-life problems to
enhance entrepreneurship capabilities. (Bloom’s Level: 3 Apply)
[CS3102.4] Utilize the principles of backtracking and branch and bound algorithms to showcase their functioning and
problem-solving capabilities. (Bloom’s Level: 3 Apply)
[CS3102.5] Evaluate various advanced algorithm concepts such as string matching, approximation algorithms, and
complexity classes to enhance employability. (Bloom’s Level: 5 Evaluate)

C. Program Outcomes and Program-Specific Outcomes:

[PO.1]. Engineering Knowledge: Apply the knowledge of mathematics, science, engineering fundamentals, and an
engineering is to the solution of complex engineering problems.
[PO.2]. Problem Analysis: Identify, formulate, research literature, and analyze complex engineering problems
reaching substantiated conclusions using first principles of mathematics, natural sciences, and engineering
sciences.
[PO.3]. Design/development of solutions: Design solutions for complex engineering problems and design system
components or processes that meet the specified needs with appropriate consideration for the public health
and safety, and the cultural, societal, and environmental considerations.
[PO.4]. Conduct investigations of complex problems: Use research-based knowledge and research methods including
design of experiments, analysis and interpretation of data, and synthesis of the information to provide valid
conclusions.
[PO.5]. Modern tool usage: Create, select, and apply appropriate techniques, resources, and modern engineering and
IT tools including prediction and modelling to complex engineering activities with an understanding of the
limitations.
 [PO.6]. The engineer and society: Apply reasoning informed by the contextual knowledge to assess societal, health,
safety, legal, and cultural issues and the consequent responsibilities relevant to the professional engineering
practice.
[PO.7]. Environment and sustainability: Understand the impact of professional engineering solutions in societal and
environmental contexts, and demonstrate the knowledge of, and need for sustainable development.
[PO.8]. Ethics: Apply ethical principles and commit to professional ethics and responsibilities and norms of engineering
practices.
[PO.9]. Individual and Teamwork: Function effectively as an individual, and as a member or leader in diverse teams,
and in multidisciplinary settings.
[PO.10]. Communication: Communicate effectively on complex engineering activities with the engineering community
and with society at large, such as being able to comprehend and write effective reports and design
documentation, make effective presentations, and give and receive clear instructions.
[PO.11]. Project Management and Finance: Demonstrate knowledge and understanding of the engineering and
management principles and apply these to one’s own work, as a member and leader in a team, to manage
projects and in multidisciplinary environments.
[PO.12]. Life-long Learning: Recognize the need for and have the preparation and ability to engage in independent and
life-long learning in the broadest context of technological change.

[PSO.1]. Will be able to design, develop and implement efficient software for a given real-life problem.
[PSO.2]. Will be able to apply knowledge of AI, Machine Learning, and Data Mining in analyzing big data for extracting
useful information from it and for performing predictive analysis.
[PSO.3]. Will be able to design, manage and secure wired/ wireless computer networks for the transfer and sharing of
information.

D. PROGRAM SPECIFIC OUTCOMES:

[PSO.1]. Will be able to design, develop and implement efficient software for a given real-life problem.
[PSO.2]. Will be able to apply knowledge of AI, Machine Learning, and Data Mining in analyzing big data for extracting
useful information from it and for performing predictive analysis.
[PSO.3]. Will be able to design, manage and secure wired/ wireless computer networks for the transfer and sharing of
information.

E. Assessment Rubrics:

Criteria Description Maximum Marks

MTE (Closed Book) 30
NPTEL Course Certification *(25 Marks)
Internal Assessment Course Link: Design and Analysis of Algorithms
(Summative) by Prof. Madhavan Mukund 30
https://onlinecourses.nptel.ac.in/noc24_cs79
Attendance *(5 Marks)

End Term Exam ETE (Closed Book) 40

(Summative)
Total 100
Attendance A minimum of 75% Attendance is required to be maintained by a student to be eligible
(Formative) to appear for the ETE. The allowance of 25% includes all types of leaves including
medical leaves.
Homework/ Home Assignment/ There are situations where a student may have to work in home, especially before a
Activity Assignment flipped classroom. Some of these works are graded with marks. A student is expected
(Formative) to participate and perform these assignments with full zeal since the activity/ flipped
classroom participation by a student will be assessed and marks will be awarded.
F. Syllabus

Introduction: Algorithm Definition and Criteria of Algorithms, Iterative and Recursive Algorithms. Performance
Analysis: Priori and Posteriori Analysis, Asymptotic Notations, Space Complexity, Time Complexity, Performance
measurement of iterative and recursive algorithms. Solving Recurrence Relations: Substitution Method, Iterative
Method, Recursive Tree Method, Master Method. Divide and Conquer: Introduction, Binary Search, Finding Maximum
and Minimum, Merge Sort, Quick Sort, Randomized Quick Sort, Integer Multiplication. Graph Search Algorithm: Graph
representation, Breadth First Search, and Depth First Search. Greedy Strategy: Introduction, Knapsack Problem, Job
Sequencing with Deadlines, Huffman Coding, Union and Find Operation (Set and Disjoint Set), Minimum Cost Spanning
Tree Algorithms (Prim’s and Kruskal’s), Optimal Merge Patterns, Single Source Shortest Path (Dijkstra’s Algorithm).
Dynamic Programming: Introduction, Single Source Shortest Path (Bellman and Ford Algorithm), All Pair Shortest Path
(Floyd Wrashal’s Algorithm), Optimal Binary Search Trees, 0/1 Knapsack Problem, Travelling Salesperson Problem,
Longest Common Subsequence, Matrix Chain Multiplication, Edit distance. Backtracking: Introduction, N-Queens
Problem, Graph Colouring, and Hamiltonian Cycles. Branch and Bound: Introduction, FIFO and LC Branch and Bound,
0/1 Knapsack Problem, Travelling Salesman Problem. String Matching: Naïve String Matching, Rabin Karp Algorithm,
Knuth-Morris-Pratt Algorithm. Complexity Classes: NP, NP-Complete and NP-Hard Problems, Cook’s Theorem,
Polynomial-time reductions, Satisfiability, Reduction from Satisfiability to Vertex Cover.

G. References:
Textbooks:
1. E. Horowitz, S. Sahni, and S. Rajasekaran, “Computer Algorithms”, 2nd Edition, University Press, 2008.
2. T. H. Cormen, C. E. Leiserson, R.L. Rivest, and C. Stein, "Introduction to Algorithms", 3rd Edition, MIT Press, 2010.

Reference Book:
3. V. Aho, J. E. Hopcroft and J. D. Ullman, "The Design and Analysis of Computer Algorithms", 1st Edition, Pearson
Education, 2002.
4. NPTEL Course: Design and Analysis Of Algorithms By Prof. Madhavan Mukund | Chennai Mathematical Institute.
H. Lecture Plan:

Lecture Topics Learning Objective Mode of Corresponding Mode of Assessing

No Delivery CO the Outcome
1 Introduction to the course To acquaint and clear teachers’ expectations and Interactive NA
NA
understand students’ expectations.
2 Introduction: Algorithm Definition and Understand the scope and objectives of the course. Interactive 3102.1
Criteria of Algorithms, Iterative and Define what an algorithm is and its essential criteria.
Recursive Algorithms. Differentiate between iterative and recursive algorithms.

3 Performance Analysis: Priori and Posteriori Understand different methods of performance analysis, Interactive 3102.1
Analysis, Asymptotic Notations including a priori and posterior analysis. Learn about
asymptotic notations (Big O, Omega, and Theta) to analyze
algorithm efficiency.
4 Time & Space Complexity – Hands-on Calculate the time and space complexity of algorithms Interactive 3102.1
through practical examples.
Assignments
5 Mathematical Analysis of Recursive Analyse recursive algorithms mathematically to determine Interactive 3102.1
Class Test
Techniques their time complexity.
MTE
6 Mathematical Analysis of non-recursive Analyze non-recursive algorithms mathematically to Interactive 3102.1
ETE
techniques determine their time complexity.
7-14 Solving Recurrence Relations: Substitution Learn various techniques to solve recurrence relations and Interactive 3102.1
Method, Iterative Method, Recursive Tree analyze recursive algorithms.
Method, Master Method
15 Divide and Conquer: Introduction, Binary Understand the divide and conquer paradigm and apply it Interactive 3102.2
Search, Finding Maximum and Minimum to solve problems like binary search and finding
maximum/minimum elements.
16 Selection sort, Insertion Sort, Bubble Sort, Analyze the time complexity of sorting algorithms such as Interactive 3102.2
and their Analysis, QA-Discussions selection sort, insertion sort, and bubble sort. Participate
(Flip Class) in question-and-answer discussions.
17 Merge Sort and Analysis, QA- Discussions Analyze the time complexity of the merge sort algorithm. Interactive 3102.2
Participate in question-and-answer discussions.
18 Quick Sort and Analysis Analyze the time complexity of the quick sort algorithm. Interactive 3102.2
19 Randomized Quick Sort Understand the concept of randomized algorithms and Interactive 3102.2
Assignments
(Flip Class) apply it to quick sorting.
Class Test
20 Integer Multiplication Learn algorithms for integer multiplication and their Interactive 3102.2
MTE
analysis.
ETE
21 Graph Search Algorithm: Graph Understand graph representations and data structures Interactive 3102.2 &
Representation used for graph algorithms. 3102.5
22 Graph Search Algorithm - BFS/ DFS Learn about breadth-first search (BFS) and depth-first Interactive 3102.2
(Flip Class) search (DFS) graph traversal algorithms.
23 Greedy Strategy: Introduction, Knapsack Understand the greedy algorithm paradigm and apply it to Interactive 3102.3
Problem solve the knapsack problem.
24 Job Sequencing with deadline Learn about job sequencing problems with deadlines and Interactive 3102.3
their optimal solutions.
25 Optimal Merge tape, Huffman Coding Study optimal merge tape algorithms and Huffman coding Interactive 3102.3
for data compression.
26 Spanning Trees - MST (Prim’s and Kruskal’s Learn about minimum spanning tree algorithms like Prim's Interactive 3102.3
Algorithm) and Kruskal's algorithms.
(Flip Class)
27 Union and Find Operation (Set and Disjoint Understand the union-find data structure and its Interactive 3102.3
Set) applications.
28 Optimal Merge Patterns Study algorithms for optimal merge patterns and their Interactive 3102.3
analysis.
29 Dijkstra’s Algorithm-SSSP Learn Dijkstra's algorithm for single-source shortest paths. Interactive 3102.3
30 Dynamic Programming: Introduction to DP Understand the concept of dynamic programming and Interactive 3102.3
(Top-Down Fibonacci, Binomial Coefficient, apply it to solve problems like Fibonacci and binomial
Bottom-up Binomial Coefficient) coefficients.
31 Bellman Ford Algorithm – SSSP Learn the Bellman-Ford algorithm for single-source Interactive 3102.3
shortest paths.
32 Optimal Binary Search Trees Study algorithms to construct optimal binary search trees. Interactive 3102.3
33 0/1 Knapsack Problem Apply dynamic programming to solve the 0/1 knapsack Interactive 3102.3
problem.
34 Longest Common Subsequence Use dynamic programming to find the longest common Interactive 3102.3
subsequence of two sequences.
35 Multi-Stage Graph Understand multi-stage graph problems and their Interactive 3102.3
solutions.
36 Floyd Warshal Algorithm – All pair of shortest Learn the Floyd-Warshall algorithm for finding all pair of Interactive 3102.4
paths shortest paths in a graph.
37 Matrix Chain Multiplication Apply dynamic programming to solve the matrix chain Interactive 3102.4
multiplication problem.
38 TSP- Dynamic Programming Solve the traveling salesman problem using dynamic Interactive 3102.4
programming. Assignments
39 Edit distance Apply dynamic programming to find the edit distance Interactive 3102.4 Class Test
between two strings. ETE
40 Backtracking: Introduction, N-Queens Understand the backtracking algorithm paradigm and Interactive 3102.4
Problem apply it to solve the N-Queens problem.
41 Graph Colouring Learn graph coloring algorithms and applications. Interactive 3102.4
42 Hamiltonian Cycles Problem Study algorithms for finding Hamiltonian cycles in a graph. Interactive 3102.4
(Flip Class)
43 Branch and Bound: Introduction, FIFO, and Understand the branch and bound technique and its Interactive 3102.4
LC Branch and Bound variations.
 44 Branch and bound – 0/1 Knapsack Problem Apply branch and bound to solve the 0/1 knapsack Interactive 3102.5
problem.
45 Branch & Bound – TSP Apply branch and bound to solve the traveling salesman Interactive 3102.5
problem.
46 String Matching: Naïve String Matching, Learn string matching algorithms like naive string Interactive 3102.5
Rabin Karp Algorithm matching and the Rabin-Karp algorithm.
47 Knuth-Morris-Pratt (KMP) Algorithm Study the Knuth-Morris-Pratt algorithm for string Interactive 3102.5
matching. Assignments
48 Complexity Classes: NP, NP-Complete, and NP, NP-Complete, and NP-Hard Problems: Understand Interactive 3102.5 Class Test
NP-Hard Problems complexity classes like NP, NP-Complete, and NP-Hard and ETE
their relationships.
49 Cook’s Theorem Learn Cook's theorem and its significance in complexity Interactive 3102.5
theory.
50 Polynomial-time reductions, Satisfiability Understand polynomial-time reductions and their Interactive 3102.5
applications to the satisfiability problem.
51 Reduction from Satisfiability to Vertex Cover Learn how to reduce the satisfiability problem to the Interactive 3102.5
vertex cover problem.

I. Course Articulation Matrix: (Mapping of COs with POs)

CORRELATION WITH PROGRAM OUTCOMES CORRELATION WITH
CO STATEMENT PROGRAM SPECIFIC
OUTCOMES
PO PO PO PO PO PO PO PO PO PO PO PO PSO PSO PSO
1 2 3 4 5 6 7 8 9 10 11 12 1 2 3
[CS3102.1] Analyze the running times of algorithms using asymptotic
3 3 1 1 3 2
analysis.
[CS3102.2] Contrast and design algorithms using the divide-and-conquer
and graph-searching algorithms to solve business problems, 3 3 3 1 1 1 3 1
hence enhancing analytical skills.
[CS3102.3] Apply the concept of greedy and dynamic programming
approaches to solving real-life problems to enhance 3 3 3 2 1 1 1 3 1 2
entrepreneurship capabilities.
[CS3102.4] Utilize the principles of backtracking and branch and bound
algorithms to showcase their functioning and problem-solving 3 3 3 2 1 1 1 3 3 2
capabilities.
[CS3102.5] Evaluate various advanced algorithm concepts such as string
matching, approximation algorithms, and complexity classes to 3 3 2 2 1 1 1 1 3 3 2
enhance employability.

Course Coordinator Student Representative Head of the Department