Name of Department: Computer Science & Engineering

Course Handout

CourseCode UGCSE301
CourseTitle Design and Analysis of Algorithms
LTPC Structure 3L+0T+2P+4C
Course Type B.Tech.CSE
Name of Faculty Member Dr. Pawan Bhambu
Designation Professor
Contact Number 9468842949
Email pawan.bhambu @vgu.ac.in

This course introduces basic elements of the design and analysis

of computer algorithms. Topics include asymptotic notations
Course Description and analysis, divide and conquer strategy, greedy methods,
dynamic programming, basic graph algorithms, NP-
completeness, and approximation algorithms.
 Scope- DAA is used to develop algorithms for tasks such as
data mining, machine learning, and natural language
processing. Networking: DAA is used in the design and
analysis of network protocols and algorithms. This includes
developing algorithms for routing, flow control, congestion
control, and network security.

Objective-

 Analyze the asymptotic performance of algorithms.

 Write rigorous correctness proofs for algorithms.
Scope and Objective
 Demonstrate a familiarity with major algorithms and
data structures.
 Apply important algorithmic design paradigms and
methods of analysis.
 Synthesize efficient algorithms in common engineering
design situations

Program Name:

Program Outcomes (PO):

After successful completion of the program, the graduate will be able to:

PO1. Engineering knowledge: Apply the knowledge of mathematics, science, engineering

fundamentals, and an engineering specialization to the solution of complex engineering
problems.
PO2. Problem analysis: Identify, formulate, review research literature, and analyze
complex engineering problems reaching substantiated conclusions using first principles of
mathematics, natural sciences, and engineering sciences.

PO3. 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.

PO4. 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.

PO5. Modern tool usage: Create, select, and apply appropriate techniques, resources, and
modern engineering and IT tools including prediction and modeling to complex engineering
activities with an understanding of the limitations.

PO6. 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.

PO7. Environment and sustainability: Understand the impact of the professional

engineering solutions in societal and environmental contexts, and demonstrate the
knowledge of, and need for sustainable development.

PO8. Ethics: Apply ethical principles and commit to professional ethics and responsibilities
and norms of the engineering practice.

PO9. Individual and team work: Function effectively as an individual, and as a member or
leader in diverse teams, and in multidisciplinary settings.

PO10. 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.

PO11. 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.

PO12. 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.

Program Specific Outcomes:

PSO 1: The ability to understand, analyse and develop computer programs in the areas
related to algorithms, system software, multimedia, web design, big data analytics, and
networking for efficient design of computer-based systems of varying complexity.

PSO 2: The ability to understand the evolutionary changes in computing, apply standard
practices and strategies in software project development using open-ended programming
environments to deliver a quality product for business success, real world problems and
meet the challenges of the future.

PSO 3: The ability to employ modern computer languages, environments, and platforms in
creating innovative career paths to be an entrepreneur, lifelong learning and a zest for higher
studies and also to act as a good citizen by inculcating in them moral values & ethics.
 B.Tech. V Semester CSE
Design & Analysis of Algorithms
Course Code: UGCSE301

3L+0T+2P+4CMM: 100

Course Objectives

1. Understand the fundamental concepts of algorithm design, analysis, and

complexity, including growth of functions and performance measurements.

2. Apply divide-and-conquer, greedy, and dynamic programming techniques to solve

problems like sorting, knapsack, and shortest path algorithms.

3. Analyze the efficiency and correctness of advanced data structures (e.g., Red-Black
Trees, B-Trees, Binomial Heaps, Fibonacci Heaps) and algorithms using tools like
the Master’s Theorem.

4. Evaluate the applicability and trade-offs of backtracking, branch-and-bound, and

approximation algorithms for complex problems like the Traveling Salesman
Problem, Graph Coloring, and N-Queens.

5. Create solutions for string matching, NP-completeness, and randomized algorithms,

justifying their design and performance.

Course Outcomes

At the end of the course, the student will be able to:

CO 1 Understand and explain the principles of algorithm design, including complexity analysis,
growth of functions, and performance metrics.

CO 2 Apply sorting algorithms (Quick Sort, Merge Sort, Heap Sort) and advanced data structures
(Red-Black Trees, B-Trees) to solve computational problems efficiently.

CO 3 Analyze the time and space complexity of algorithms, including greedy methods (e.g., Prim’s,
Kruskal’s, Dijkstra’s) and dynamic programming (e.g., Matrix Multiplication, Longest Common
Subsequence).

CO 4 Evaluate the effectiveness of backtracking, branch-and-bound, and approximation algorithms

for solving problems like Graph Coloring, N-Queens, and Traveling Salesman Problem.

CO 5 Create and validate algorithms for string matching, NP-complete problems, and randomized
algorithms, demonstrating their correctness and efficiency.
 OUTLINEOFTHE COURSE
Module No Title of Module Time Required for Module (Hours)

1 Introduction to Algorithm 10
2 Advanced Data Structures 6

3 Greedy Method and Trees 9

4 Dynamic Programming 10
5 NP- Complete 10

COURSE CONTENT

Module -1
Introduction: Algorithms, Analyzing Algorithms, Complexity of Algorithms, Growth
of Functions, Performance Measurements, Master’s Theorem, Sorting and Order
Statistics – Divide and conquer - Quick Sort, Merge Sort, Heap Sort, Comparison of
Sorting Algorithms, Sorting in Linear Time.

Module -2
Advanced Data Structures: Red-Black Trees, B – Trees, Binomial Heaps, Fibonacci
Heaps.

Module -3
Greedy Methods with Examples Such as Optimal Reliability Allocation, Knapsack,

Minimum Spanning Trees – Prim’s and Kruskal’s Algorithms,

Single Source Shortest Paths - Dijkstra’s and Bellman Ford Algorithms.

Module -4
Dynamic Programming with Examples Such as Knapsack. Matrix Multiplication,
Longest Common Subsequence

All Pair Shortest Paths – Warshal’s and Floyd’s Algorithms.

Backtracking, Branch and Bound with Examples Such as Travelling Salesman

Problem, Graph Coloring, n-Queen Problem.

Module -5
 Selected Topics: String Matching, Theory of NP Completeness,
Approximation Algorithms and Randomized Algorithms

TEXTBOOK(S)

1. Thomas H. Core man, Charles E. Leiserson and Ronald L. Rivest,

“Introduction to Algorithms”, Printice Hall of India.
2. E. Horowitz & S Sahni, "Fundamentals of Computer Algorithms"

REFERENCEBOOKS
1. Aho, Hopcraft, Ullman, “The Design and Analysis of Computer Algorithms”
Pearson Education, 2008.
2. LEE "Design & Analysis of Algorithms (POD)",McGraw Hill
3. Richard E.Neapolitan "Foundations of Algorithms" Jones & Bartlett
Learning
4. Jon Kleinberg and ÉvaTardos, Algorithm Design, Pearson, 2005.
5. Michael T Goodrich and Roberto Tamassia, Algorithm Design: Foundations,
Analysis, and Internet Examples, Second Edition, Wiley, 2006.

CO-POMapping

CO PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
andP
O

CO1 2 3 - 2 1 - 1 - - 1 - 2
CO2 1 - 2 - - - - - - - - -
CO3 - 2 2 - 1 - 1 - - - 1 -
CO4 1 - - - - - - - - - - -
CO5 2 2 - 1 - - - - - - - -

CO-PSO Mapping

CO and PSO PSO1 PSO2 PSO3

CO1 2 1 1
 CO2 2 2 -
CO3 2 2 1
CO4 1 1 -
CO5 2 2 1

LIST OF EXPERIMENTS:
1. Program for Insertion Sort.
2. Program for Merge Sort.
3. Program for Selection Sort.
4. Program for Heap Sort.
5. Program for Quick Sort.
6. Knapsack Problem using Greedy Solution
7. Perform Travelling Salesman Problem
8. Perform Matrix Chain Multiplication.
9. Find Minimum Spanning Tree using Kruskal’s Algorithm
Implement N Queen Problem using Backtracking
 Lecture Plan

Additiona
l topics to
be
discussed
(topics
beyond
Date of Date of the
Lectur Title of the Pedagog Referenc
Plannin Implementati syllabus
e No. Lecture y e
g on and may
be four to
five topics
against
every 10
lecture
topics)

Module 0: Introduction

Importanc
Introduction of
e and need
course, vision, PPT/C&
1 of NA
mission, COs, T
Algorithm
POs
s in CSE

Module 1: Introduction: Algorithms, Analyzing Algorithms, Complexity of Algorithms

Basics of
Introduction PPT/C& algorithm
2 of Algorithm 1
T writing
Complexities and need
 PPT/C&
3 Growth of NA 3
Functions T

Need of
Sorting
PPT/C&
4 Performance with basic 3
Measurements T
sorting
algorithms

Need and
Master’s importanc
Theorem, PPT/C& e of
5 Sorting and 3
T Divide and
Order
Conquer
Statistics
Method

Divide and
PPT/C&
6 Conquer NA 3
Method-II T
(Merge Sort)
Divide and
PPT/C&
7 Conquer NA 3
Method-III T
(Quick Sort)
Divide and
PPT/C&
8 Conquer NA 1
Method-IV T
Heap Sort
Introductio
Comparison of PPT/C& n of
9 Sorting 1
T Greedy
Algorithms,
Methods

PPT/C&
10 Sorting in 1
Linear Time. T

Module 2: Advanced Data Structures

Introduction of
PPT/C&
11 Advanced Data 1
T
Structures

PPT/C&
12 Red-Black Trees 1
T

Properties of PPT/C&
13 1
Red-Black Trees T
 Implementatio
PPT/C&
14 n of Red-Black 1
T
Trees

B – Trees, PPT/C&
15 1
Binomial Heaps T

Fibonacci PPT/C&
16 1
Heaps. T

Module 3: Greedy Methods with Examples Such as Optimal Reliability

Allocation, Knapsack,

Introduction PPT/C&
17 of Greedy 1
T
Methods
Optimal PPT/C&
18 Reliability 1
T
Allocation
PPT/C&
19 Knapsack, 1
T

Introduction PPT/C&
20 of Minimum 1
T
Spanning Trees
PPT/C&
21 Prim’s 1
Algorithm T

PPT/C&
22 Kruskal’s 3
Algorithms, T

Introduction
PPT/C&
23 to Single 1
Source T
Shortest Paths
PPT/C&
24 Dijkstra’s 3
Algorithm T

PPT/C&
25 Bellman Ford 3
Algorithms. T

Module 4: Dynamic Programming

Introduction PPT/C&
26 to Dynamic 1
T
Programming
27 Examples PPT/C& 1
Such as T
Knapsack.
Matrix
 Multiplication
Longest PPT/C&
28 Common 1
T
Subsequence
Introduction PPT/C&
29 to All Pair 1
T
Shortest Paths
Warshal’s and PPT/C&
30 Floyd’s 1
T
Algorithms.
Randomized PPT/C&
31 algorithm for 1
T
2-SAT
Backtracking, PPT/C&
32 Branch and 3
T
Bound
Travelling PPT/C&
33 Salesman 3
T
Problem
PPT/C&
34 Graph 3
Coloring T

PPT/C&
35 n-Queen 1
Problem T

Module 5: String Matching

Introduction PPT/C&
36 to String 3
T
Matching
Examples of PPT/C&
37 String 3
T
Matching
Proving NP-
Complete PPT/C&
38 Problems 3
T
(Satisfiability
problem)
Proving NP-
Complete PPT/C&
39 Problems 3
T
(Vertex Cover
Problem)
40 Approximatio PPT/C& 1
n Algorithm T
for Vertex
Cover
 Problem
Approximatio
PPT/C&
41 n Algorithms 1
for Set Cover T
Problem
Example of
PPT/C&
42 Vertex Cover 1
and Set Cover T
Problem
Introduction
PPT/C&
43 to 1
Randomized T
Algorithms
Examples of PPT/C&
44 Randomized 1
T
Algorithms
Implementati
PPT/C&
45 on to 1
Randomized T
Algorithms

Course Assessment Plan: CAP

Assignment Mid Term End Term

COs Description of COs BTL
Weightage Weightage Weightage
Understand and explain the
principles of algorithm design,
CO1 including complexity analysis, L2 & L3 05 10 05
growth of functions, and
performance metrics
Apply sorting algorithms (Quick
Sort, Merge Sort, Heap Sort) and
CO2 advanced data structures (Red- L2 & L3 05 05 10
Black Trees, B-Trees) to solve
computational problems efficiently
Analyze the time and space
complexity of algorithms, including
greedy methods (e.g., Prim’s,
Kruskal’s, Dijkstra’s) and dynamic
CO3 L2 & L3 05 05 10
programming (e.g., Matrix
Multiplication, Longest Common
Subsequence).
 Evaluate the effectiveness of
backtracking, branch-and-bound,
and approximation algorithms for
CO4 L2 & L3 05 10 10
solving problems like Graph
Coloring, N-Queens, and Traveling
Salesman Problem.

Create and validate algorithms for

string matching, NP-complete
CO5 problems, and randomized L2 & L3 05 10 10
algorithms, demonstrating their
correctness and efficiency.

Evaluation Scheme:

Maximum
Component Duration Date &Time Mode
Marks
Mid Term I-Examination 1:30Hr 20
Assignment-I - 5 Through ERP Lx
Assignment-II - 5 Through ERP Lx
Assignment-III - 5 Through ERP Lx
Assignment-IV - 5 Through ERP Lx
Assignment-V - 5 Through ERP Lx
20 Through ERP
Quiz-I Minutes.
5
MCQ
Through ERP
Quiz-II 20 Minutes 5
MCQ

Mid-term II -Examination 1:30 Hr 20 Open Book

End Term Examinations 3:00 Hrs 60

Signature

Dr. Pawan Bhambu