COURSEPACK

SCHEME
The scheme is an overview of work-integrated learning opportunities and gets students out into the
real world. This will give what a course entails.

Course Title Design & Analysis of Algorithm Course Type Integrated

Course Code R1PC302B Class MCA III Sem
Activity Credits Credit Hours Total Number of Classes per Assessment in
Lecture 3 3 Semester Weightage
Instruction
Tutorial 0 0 Tutorial Self-stu SEE
delivery dy
Pra CIE
Practical 1 2 ctic
al
Theory P
r a
Self-study 0 0 ct
ic
al

Total 4 5 45 0 15 0 50% 50%

Course
Course Lead Dr. Sonia Rani Dr. Anil Gankotia
Coordinator
Theory Practical
Dr. Sanjeev Kumar Prasad Dr. Sanjeev Kumar Prasad
Dr. Prashant Johri Dr. Prashant Johri
Names [Link] Krishnan [Link] Krishnan
Course Dr Anil Gankotia Dr Anil Gankotia
Instructors Dr. Sonia Rani Dr. Sonia Rani
Dr. Sanjiv Sharma Dr. Sanjiv Sharma
Dr. Bhoopendra Dewedi Dr. Bhoopendra Dewedi
Dr. Anuj Kumar Singh Dr. Anuj Kumar Singh
Dr. Farhan Sufiyan Dr. Farhan Sufiyan

COURSE OVERVIEW
To introduce students, the concepts of algorithm analysis for finding out the space and time complexity of
different algorithms. Different design techniques such as greedy method, divide and conquer, backtracking,
dynamic programming, branch and bound are to be studied for finding the solution to the different problems. It
also provides an insight into the basic concepts of NP and NP-hard problems and their relevance in research.
PREREQUISITE COURSE

Prerequisite Course Required Yes

Prerequisite
If, yes please fill in the Details Prerequisite course name
Course code
Data structure using C
 COURSE OBJECTIVE

1. To develop proficiency in designing efficient algorithms for solving diverse computational problems.
2. To analyze the time and space complexity of algorithms to evaluate their performance.
3. To apply algorithmic strategies and techniques to improve problem-solving capabilities.
4. To gain insights into various algorithmic paradigms and their applications in real-world scenarios.
5. To demonstrate the ability to critically assess and compare different algorithms for specific tasks.

COURSE OUTCOMES (COs)

After the completion of the course, the student will be able to:
CO No. Course Outcomes
R1PC302B.1 Understand the concept of algorithms.

R1PC302B.2 Analyze algorithmic complexity for efficient problem-solving.

R1PC302B.3 Apply algorithms to real-world scenarios.

R1PC302B.4 Develop problem-solving skills through algorithmic approaches.

BLOOM’S LEVEL OF THE COURSE OUTCOMES

Bloom's taxonomy is a set of hierarchical models used for the classification of educational
learning objectives into levels of complexity and specificity. The learning domains are cognitive,
affective, and psychomotor.

INTEGRATED
Remember Understand Apply Analyse KL Evaluate KL Create
CO No.
KL1 KL 2 KL 3 4 5 KL 6
 R1PC302B.1

R1PC302B.2

R1PC302B.3

R1PC302B.4

R1PC302B.5

PROGRAM EDUCATIONAL OBJECTIVES

The Post Graduates of Computer Application shall:

PEO1: be able to successfully pursue research in Computer Applications and allied disciplines at
institutions of transnational reputation.
PEO2: serve in technical or managerial roles at Government firms, Corporates and contributing to the
society as successful entrepreneurs through startup.
PEO3: be engaged with leading Global Software services companies, Consultancy organizations and
academic Institutions.

PROGRAM OUTCOMES (POs):

1. Computational Knowledge: Apply knowledge of computing fundamentals, computing

specialization, mathematics, and domain knowledge appropriate for the computing specialization to the
abstraction and conceptualization of computing models from defined problems and requirements.
2. Problem Analysis: Identify, formulate, research literature, and solve complex computing problems
reaching substantiated conclusions using fundamental principles of mathematics, computing sciences,
and relevant domain disciplines.
3. Design /Development of Solutions: Design and evaluate solutions for complex computing
problems, and design and evaluate systems, components, or processes that meet specified needs with
appropriate consideration for public health and safety, cultural, societal, and environmental
considerations.
4. Conduct investigations of complex Computing 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.
5. Modern Tool Usage: Create, select, adapt and apply appropriate techniques, resources, and modern
computing tools to complex computing activities, with an understanding of the limitations.
 6. Professional Ethics: Understand and commit to professional ethics and cyber regulations,
responsibilities, and norms of professional computing practices.
7. Life-long Learning: Recognize the need, and have the ability, to engage in independent learning for
continual development as a computing professional.
8. Project management and finance: Demonstrate knowledge and understanding of the computing
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.
9. Communication Efficacy: Communicate effectively with the computing community, and with
society at large, about complex computing activities by being able to comprehend and write effective
reports, design documentation, make effective presentations, and give and understand clear
instructions.
10. Societal and Environmental Concern: Understand and assess societal, environmental, health,
safety, legal, and cultural issues within local and global contexts, and the consequential responsibilities
relevant to professional computing practices.
11. Individual and Team Work: Function effectively as an individual and as a member or leader in
diverse teams and in multidisciplinary environments.
12. Innovation and Entrepreneurship: Identify a timely opportunity and using innovation to pursue
that opportunity to create value and wealth for the betterment of the individual and society at large.

PROGRAMME SPECIFIC OUTCOME (PSO):

The students of Computer Application shall:

PSO1: Have the ability to work with contemporary technologies in computing requisite to Industry 4.0
developing and implementing solutions to real life problems.

PSO2: Demonstrate application development skills learned through technical training and projects to solve real
world problems.
COURSE ARTICULATION MATRIX

The Course articulation matrix indicates the correlation between Course Outcomes and Program
Outcomes and their expected strength of mapping in three levels (low, medium, and high).

COs#/ PO PO PO PO PO PO PO PO PO PO1 PO11 PO1 PSO PSO

POs 1 2 3 4 5 6 7 8 9 0 2 1 2

302B.1 1 - - - - - 2 1 - - - - 2 2
302B.2 2 - - - - - - - 1 - - 2 2
302B.3 - 3 - 2 - 2 1 - - - 1 - 2 2
302B.4 - - 3 - - 2 - - - - - 2 2
302B.5 - 1 2 - - 2 - - 1 - 1 2 2

Note: 1-Low, 2-Medium, 3-High

COURSE ASSESSMENT

TOTAL
CIE
S. Assessment CIE
SEE
No. Tools LAB Marks
AI- 1 MTE AT-2 LAB
Exam
Theory 25 50 25 100 100
1
Lab 25 25 50 100
 COURSE CONTENT : THEORY+ PRACTICAL
Introduction to Algorithms 8 hours
Introduction: Algorithms, Analysis of algorithms, Asymptotic Notations, Growth of
function, Recurrences, and their solution methods.
Sorting in polynomial Time: Insertion sort, Merge sort, Heap sort, and Quick sort
Sorting in Linear Time: Counting sort, Radix Sort, Bucket Sort.
Advance Data Structure 8 hour
Advanced Data Structure: Red Black Trees, Binomial Heap, B-Tree, Fibonacci Heap,
and priority Queues.
Advance Design and Analysis Techniques 8 hours
THEORY Dynamic programming: Matrix Multiplication and Longest Common Sequence.
Greedy Algorithm: Huffman Coding, and Knapsack problem
Backtracking: N-Queen Problem, Sum of subset problem
Graph Algorithms 8 hours
Elementary Graph Algorithms, Breadth First Search, Depth First Search,
Minimum Spanning Tree: Kruskal’s Algorithms, Prim’s Algorithms, Single Source
Shortest Path, All pair Shortest Path, and Traveling Salesman Problem
Advanced Algorithms Design 8 hours
Randomized Algorithms, String Matching, NP-Hard and NP-Completeness
Approximation Algorithms, Matrix Operations.

Lesson Plan for Integrated Courses

FOR THEORY 15 weeks * 3 Hours = 45 Classes) (1credit = 1Lecture Hour)
FOR PRACTICAL 15 weeks * 2Hours = 30 Hours lab sessions (1 credit = 2 lab hours)
Lesson Plan for Theory

Level CO Assessment Learning

[Link]. Topic Lesson Outcome (LO)
(SOLO) Mapping Activity
Define an algorithm and Relational CO1, CO2 MCQ test Think-Pair-
Introduction to explain the properties and Share
1
Algorithms importance of algorithms
in problem-solving.
Analyze algorithms based Relational CO1,CO2 Wooclap Brain
Analysis of on input size and and stroming
2
Algorithms understand time and Interactive and Think
space complexities. Quiz Pair Share
Illustrate and compare Relational CO1, CO2 Brain Group
Asymptotic the Big-O, Omega, and stroming Discussion
3
Notations Theta notations with and Activity
examples. Presentation
Relational CO1 MCQ-based Wooclap
Demonstrate
quiz quiz on
understanding of function
Growth of segment
4 growth and use it to
Functions definitions
analyze algorithm
performance.
and
applications
 Formulate recurrence Multistructural CO1, CO2 Case study Wooclap
Recurrence
5 relations for recursive analysis interactive
Relations
algorithms. quiz
Solve recurrence relations Relational CO1, Think-Pair- Short
Substitution using the substitution CO2, CO3 Share reflection
6
Method method with paper
mathematical induction.
Solve recurrences using Relational CO2 Group Mentimeter
Recursion Tree the recursion tree presentation (Voting)
7 & peer
Method technique to estimate
algorithm complexity. evaluation
Relational CO2 Scenario- Think-Pair-
based MCQ Share
test (Compare
Apply Master’s Theorem
Row Major
8 Master’s Theorem to solve divide-and-
Order, and
conquer recurrences.
Column
Major
Order)
Implement insertion sort Relational CO1, CO2 Case study Think-Pair-
and analyze its best, review Share
9 Insertion Sort
worst, and average-case
time complexities.
Design and implement Relational CO1, CO2 Group Group risk
merge sort using the presentation assessment
10 Merge Sort & peer simulation
divide-and-conquer
paradigm. evaluation
Relational CO2 Report Gallery
Use heap data structures submission Walk
11 Heap Sort to perform sorting and (Exploring
analyze its efficiency. different
case studies)
Construct quick sort Relational CO2 Peer Case study
algorithm with assessment on Linked
12 Quick Sort randomized and lists
deterministic pivots and
analyze performance.
Implement counting sort Relational CO1, CO2 Wooclap Brain
and explain its linear time Quiz stroming
13 Counting Sort
complexity for specific ,Think Pair
input types. Share
Demonstrate the working Relational CO1, CO2 Brain Group
14 Radix Sort of radix sort and discuss stroming Discussion
its stability and efficiency. Activity
Relational CO1, CO2 Wooflash Jigsaw
Apply bucket sort for
quiz activity
uniformly distributed
15 Bucket Sort (Teams
input and analyze its
research
complexity.
different
 players and
present their
role)
Relational CO2 Report Gallery
Explain properties of red-
submission Walk
black trees and perform
16 Red-Black Trees (Exploring
insertions and deletions
different
maintaining balance.
case studies)
Describe the structure of Relational CO2 Peer Case study
a binomial heap and assessment on Linked
17 Binomial Heap
perform basic heap lists
operations.
Understand B-Trees and Relational CO1, CO2 Wooclap Brain
implement insertion, Quiz stroming
18 B-Trees
deletion, and search ,Think Pair
operations. Share
Illustrate Fibonacci heap Relational CO1, CO2 Brain Group
structure and stroming Discussion
19 Fibonacci Heap
demonstrate amortized Activity
cost of its operations.
Relational CO1, CO2 Wooflash Jigsaw
quiz activity
Implement priority (Teams
queues using heaps and research
20 Priority Queues
analyze performance in different
different scenarios. players and
present their
role)
Solve matrix chain Relational CO1, CO2 MCQ test Think-Pair-
multiplication problems Share
Matrix Chain
21 using dynamic
Multiplication (DP)
programming to minimize
computations.
Apply dynamic Relational CO1, CO2 Group Wooclap
programming to debate quiz
Longest Common
22 determine the longest
Subsequence (DP)
common subsequence
between two sequences.
Understand the greedy Relational CO2 Group Think-Pair-
Greedy Algorithms strategy and identify debate Share
23
Introduction problems suitable for
greedy solutions.
Construct optimal prefix Relational CO1, CO2 Reflective Wooflash
codes using Huffman’s paper quiz
24 Huffman Coding
algorithm and explain its
compression benefits.
Apply greedy approach to Extended CO1, CO2 Reflective Group
0/1 Knapsack solve fractional knapsack abstract paper discussion
25
Problem (Greedy) and explain its limitations
on 0/1 knapsack.
 Explain the concept of Relational CO1, CO2 Group Think-Pair-
Backtracking backtracking and identify debate Share
26
Introduction problem domains suitable
for it.
Formulate and solve the Relational CO1, CO2 Reflective Case study
27 N-Queens Problem N-Queens problem using paper gallery walk
backtracking strategies.
Implement backtracking Relational CO1, CO2 Group Jigsaw
Subset Sum to determine if a subset presentation activity
28
Problem exists that adds up to a
given sum.
Represent graphs using Relational CO1, CO2 Case study Think-Pair-
Graph
adjacency matrix and review Share
29 Representation
adjacency list with
Techniques
applications.
Apply BFS to traverse Relational CO2 Group case Wooclap
Breadth First graphs and analyze its study quiz
30
Search (BFS) complexity and
applications.
Implement DFS traversal Multistructural CO2 Data Wooflash
Depth First Search and explain its use in cycle analysis Q&A
31
(DFS) detection and component project
discovery.
Minimum Multistructural CO1, CO2 Position Debate
Construct minimum
Spanning Trees paper
spanning trees using
32 Overview,
Kruskal’s algorithm and
Kruskal’s
analyze its complexity.
Algorithm
Implement Prim’s Relational CO1, CO2 Group Wooclap
algorithm to find debate quiz
33 Prim’s Algorithm minimum spanning trees
and compare with
Kruskal’s.
Single Source Relational CO1, Group case Wooclap
Apply Dijkstra’s algorithm
Shortest Path CO2, CO4 study quiz
to determine shortest
34 Overview,
paths from a single source
Dijkstra’s
in weighted graphs.
Algorithm
Use Bellman-Ford Relational CO1, Group Think-Pair-
Bellman-Ford algorithm to find shortest CO2, CO4 discussion Share
35
Algorithm paths and detect negative
weight cycles.
Formulate solutions for Relational CO1, Timeline Wooflash
All-Pairs Shortest all-pairs shortest paths CO2, CO4 project quiz
36
Path using matrix-based or
graph algorithms.
Implement Floyd-Warshall Relational CO1, Group Think-Pair-
Floyd-Warshall algorithm and analyze its CO2, CO4 discussion Share
37
Algorithm time and space
complexities.
 Formulate the Traveling Relational CO1, Group Wooclap
Traveling Salesman Salesman Problem and CO2, CO4 Discussion Q&A
38
Problem explore brute-force and &
heuristic solutions. Comparison
Understand the concept Unistructural CO1,CO4 Case study Jigsaw
Randomized
and advantages of report activity
39 Algorithms
randomized algorithms
Overview
through basic examples.
Compare various string Relational CO1,CO4 Case study Think-Pair-
String Matching matching approaches and review Share
40
Algorithms analyze their
performance.
Implement the naive Extended CO1,CO4 MCQ Wooclap
Naive String pattern matching Abstract quiz
41
Matching algorithm and evaluate its
limitations.
Extended CO1,CO4 MCQ Group
Apply the KMP algorithm
Abstract Discussion
Knuth-Morris-Pratt for efficient string
42 &
(KMP) Algorithm matching using prefix
Comparison
function.
with DFS
Explain the concept of Relational CO1, CO2 Group case Wooclap
computational study quiz
NP-Hard and NP-
43 complexity, P vs NP, and
Completeness
classify problems
accordingly.
Describe the need for Relational CO1,CO2, Research Think-Pair-
Approximation approximation algorithms CO3 paper on Share
44 binary
Algorithms and apply them to NP-
Hard problems. search
Perform and analyze basic Relational CO1, MCQ Group
matrix operations CO3, CO4 discussion
45 Matrix Operations
relevant to algorithm
design.
 Lesson Plan for Practical’s
Write a program to sort given set of numbers in ascending/descending order using
PRACTICA Bubble sort and
L
also search a number using binary search.
Write a program to sort a given set of numbers in ascending/descending order
1 using Insertion sort and also search a number using linear search.
Write a program to sort a given set of numbers in ascending/descending order using
2 Quick sort and any other sorting algorithm. Also record the time taken by these two
programs and compare them.
3 Write a program to sort a given set of numbers using Heap sort.
4 Write a program to sort a given set of numbers using Heap sort.
5 Write a program to sort a given set of numbers Counting Sort.
6 Write a program to sort a given set of numbers Radix Sort.
7 Write a program to implement Matrix Chain Multiplication.
8 Implement Matrix Chain Multiplication (MCM) using Dynamic Programming.
9 Implement Longest Common Subsequence (LCS) using Dynamic Programming.
10 Implement BFS for a given Graph G.
11 Implement DFS for a given Graph G.
12 Implement the Minimum Spanning tree using Prims’s Approach.
13 Implement the Minimum Spanning tree using Kruskal Approach.
14 Write a program to implement Greedy algorithm using Acitivity Selection Problem.

T= Theory, L= Lab

BIBLIOGRAPHY

● Text Book
1. Thomas H. Coreman, Charles E. Leiserson and Ronald L. Rivest, “Introduction to Algorithms”, The MIT Press,
3rd edition, 2009.

● Reference Books

1. Ellis Horowitz, SartajSahni, SanguthevarRajasekaran. Fundamentals of Computer Algorithms, MIT

Press, Second Edition (Indian reprint: Prentice-Hall), 2008.
2. Aho, Hopcraft, Ullman, “The Design and Analysis of Computer Algorithms” Pearson
Education.
● Journals/Magazines/Govt. Reports/Gazatte/Industry Trends
1. [Link]

● Webliography
1. [Link]
2. [Link]

● SWAYAM/NPTEL/MOOCs Certification
1. Code Tantra
2. Coding Ninjas
3. Code Chef
4. [Link] (Swayam)

PROBLEM-BASED LEARNING

Exercises in Problem-based Learning (Assignments) (Min 45 Problems*)

[Link] Proble BTL

. m
1 Write a program to implement Minimum Cost spanning tree. BTL5
2 Write a program to implement Sum of subset problem. BTL5
Write a program to implement Greedy algorithm using Task Scheduling
3 BTL5
Problem.
Write a program to implement Greedy algorithm using Activity Selection
4 BTL5
Problem.
Compute the transitive closure of a given directed graph using Warshall's
5 BTL6
algorithm. Write a program to implement shortest path algorithm.
Write a program to find all Hamiltonian Cycles in a connected undirected
6 BTL5
Graph G of n vertices using backtracking principle.
7 Develop a program to implement solve LCS problem. BTL6
8 Develop a program to implement Huffman-code. BTL6
Find Minimum Cost Spanning Tree of a given connected undirected graph
9 BTL6
using Kruskal's algorithm. Use Union-Find algorithms in your program.
Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s
10 BTL6
algorithm.
Design a programs to
11 (a) Implement All-Pairs Shortest Paths problem using Floyd's algorithm. BTL6
(b) Implement Travelling Sales Person problem using Dynamic programming.
 Design and implement to find a subset of a given set S = {Sl, S2, ,Sn} of n
positive integers whose SUM is equal to a given positive integer d. For example,
12 if S ={1, 2, 5, 6, 8} and d= 9, there are two solutions {1,2,6}and BTL6
{1,8}. Display a suitable message, if the given problem instance doesn't have a
solution.
13 Comparing Kruskal and Prim’s algorithm in MST. BTL5
14 Greedy and Backtracking Algorithm Comparison in Graph Coloring Problem. BTL5
15 Build the game of Capsa Susun using Greedy Algorithm BTL6
Solving Travelling Salesman Problem Using Greedy Algorithm and Brute
16 BTL3
Force Algorithm
17 Design and Analysis 0/1 Knapsack Problem. BTL6
18 Design Coin Change Problem using Brute Force and Greedy Algorithm BTL6
Comparing Exhaustive Search Algorithm and Greedy Algorithm in job
19 BTL5
Scheduling Problem
20 Build a Cash Flow Minimiser BTL6
21 Build a CB Mario game using Dynamic Programming Optimisation. BTL6
22 Build an application of Sudoku game using Backtracking method BTL6
Build a Snakes & Ladders game, challenge the player to win in minimum
23 BTL6
number of moves. You can use BFS to compute it.
24 Explain (0/1) knapsack problem and fractional knapsack problem. BTL5
Explain the Dynamic Programming (DP) Algorithmic Paradigm? List a few
25 BTL5
problems which can be solved using the same.
Explain the recursive algorithms? State the important rules which every
26 BTL3
recursive algorithm must follow.
27 How can we compare between two algorithms written for the same problem? BTL3
Design an algorithm that finds the number of ways in which you can traverse N
28 meters by doing jumps of 1, 2, 3, 4, or 5- meter lengths. Assume that N can be BTL6
a very large number. What is the resulting complexity?
Design an algorithm that finds all pairs of integer arrays whose sum is equal to
29 BTL3
a given number?
Suppose a given space S of N contiguous memory cells is allocated to 6 stacks.
30 BTL4
Describe ways that the stack may be maintained in S
Write an algorithm to find solution to the Towers of Hanoi problem. Explain
31 BTL4
the working of your algorithm with 4 disks using diagrams.
32 Give an algorithm for graph coloring problem and analyze its complexity BTL5
Construct a B-tree of minimum degree 3 by inserting the elementsin the
33 order given F, Q,P,K,A,L,R,M,N,X,Y,D,Z,E,H,T,V,W,C. from the BTL6
constructed tree delete A,P,Q,R,T.
Construct a Red Black tree by inserting 9,19,30,15,16 and 27 into an initially
34 BTL6
empty tree and also delete 15,16 and 30 from the tree
 Obtain the solution to knapsack problem by Dynamic Programming
35 method n=6, (p1, p2,...p6)=(w1,w2,...w6)=(100,50,20,10,7,3) and BTL5
m=165.
Apply Merge Sort to sort the list
36 a[1:10]=(31,28,17,65, 35, 42.,86,25,45,52). Draw the tree of recursive calls of BTL6
merge sort, merge functions
37 Solve the Travelling Salesman problem Dynamic programming with example. BTL6
Write an algorithm String Matching using Rabin-Karp algorithm and also
38 BTL6
analyze its complexity.
39 Write an algorithm for randomized quick sort algorithm. BTL6
Write the Prim’s Algorithm to find out Minimum Spanning Tree. Apply the
40 BTL6
same and find MST for the graph given below.