Credits corrected

01.02.2023

Design and Analysis of Algorithms

Course Code 22MCA15 CIE Marks 50
Teaching Hours/Week (L:P:SDA) 4:0:0 SEE Marks 50
Total Hours of Pedagogy 40 Total Marks 100
Credits 04 Exam Hours 03
Course Learning objectives:
 Explain various computational problem solving techniques.
 Apply appropriate method to solve a given problem.
 Describe various methods of algorithm analysis.
Module-1
Introduction: What is an Algorithm? (T2:1.1), Algorithm Specification (T2:1.2), Analysis Framework (T1:2.1),
Performance Analysis: Space complexity, Time complexity (T2:1.3). and notation (o), Mathematical analysis of Non-
Recursive and recursive Algorithms), Asymptotic Notations: Big-Oh notation (O), Omega notation (Ω), Theta notation
( Littleoh with Examples (T1:2.2, 2.3, 2.4). Important Problem Types: Sorting, Searching, String processing, Graph
Problems, Combinatorial Problems. Fundamental Data Structures: Stacks, Queues, Graphs, Trees, Sets and Dictionaries.
(T1:1.3,1.4). RBT: L1, L2, L3
Teaching- 1. Problem based Learning.
Learning 2. Chalk & board, Active Learning.
Process 3. Laboratory Demonstration.
Module-2
Divide and Conquer: General method, Binary search, Recurrence equation for divide and conquer, Finding the maximum
and minimum (T2:3.1, 3.3, 3.4), Merge sort, Quick sort (T1:4.1, 4.2), Strassen‟s matrix multiplication (T2:3.8),
Advantages and Disadvantages of divide and conquer. Decrease and Conquer Approach: Topological Sort. (T1:5.3).
Transform and Conquer Approach: Heaps and Heap Sort (T1:6.4). RBT: L1, L2, L3
Teaching- 1. Chalk & board, Active Learning, MOOC, Problem based Learning.
Learning 2. Laboratory Demonstration.
Process
Module-3
Greedy Method: General method, Coin Change Problem, Knapsack Problem, Job sequencing with deadlines (T2:4.1,
4.3, 4.5). Minimum cost spanning trees: Prim‟s Algorithm, Kruskal‟s Algorithm (T1:9.1, 9.2). Single source shortest
paths: Dijkstra's Algorithm (T1:9.3). Optimal Tree problem: Huffman Trees and Codes (T1:9.4). RBT: L1, L2, L3
Teaching- 1. Chalk & board, Active Learning, MOOC, Problem based Learning.
Learning 2. Laboratory Demonstration.
Process
Module-4
Dynamic Programming: General method with Examples, Multistage Graphs (T2:5.1, 5.2). Transitive Closure:
Warshall‟s Algorithm, All Pairs Shortest Paths: Floyd's Algorithm, Optimal Binary Search Trees, Knapsack problem
((T1:8.2, 8.3, 8.4), Bellman-Ford Algorithm (T2:5.4), Travelling Sales Person problem (T2:5.9), Reliability design
(T2:5.8). RBT: L1, L2, L3
Teaching- 1. Chalk & board, Active Learning, MOOC, Problem based Learning.
Learning 2. Laboratory Demonstration.
Process
Module-5
Backtracking: General method (T2:7.1), N-Queens problem (T1:12.1), Sum of subsets problem (T1:12.1), Graph
coloring (T2:7.4), Hamiltonian cycles (T2:7.5). Programme and Bound: Assignment Problem, Travelling Sales Person
problem (T1:12.2), 0/1 Knapsack problem (T2:8.2, T1:12.2): LC Programme and Bound solution (T2:8.2), FIFO
Programme and Bound solution (T2:8.2). Probabilistic and Randomized Algorithms: Probabilistic Algorithms
Randomizing deterministic Algorithms: Randomizing Probelinsrch quicksort, MonteCarlo Algorithm, Biased Monte
Carlo Algorithms: A Montecarlo algorithm for testing polynomial quality, Introduction to Las vegas Algorithms
(T3:24.1, 24.2,24.3) NP-Complete and NP-Hard problems: Basic concepts, non deterministic algorithms, P,NP, NP-
Complete, and NP-Hard classes (T2:11.1). RBT: L1, L2, L3

1
 Credits corrected
01.02.2023
Teaching- 1. Chalk & board, Active Learning, MOOC, Problem based learning.
Learning 2. Laboratory Demonstration.
Process
Assessment Details (both CIE and SEE)
The weightage of Continuous Internal Evaluation (CIE) is 50% and for Semester End Exam (SEE) is 50%. The
minimum passing mark for the CIE is 50% of the maximum marks. Minimum passing marks in SEE is 40% of the
maximum marks of SEE. A student shall be deemed to have satisfied the academic requirements and earned the
credits allotted to each subject/ course if the student secures not less than 50% (50 marks out of 100) in the sum
total of the CIE (Continuous Internal Evaluation) and SEE (Semester End Examination) taken together.
Continuous Internal Evaluation:
1. Three Unit Tests each of 20 Marks
2. Two assignments each of 20 Marks or one Skill Development Activity of 40 marks
to attain the COs and POs
The sum of three tests, two assignments/skill Development Activities, will be scaled down to 50 marks
CIE methods /question paper is designed to attain the different levels of Bloom’s taxonomy as per the
outcome defined for the course.

Semester End Examination:

1. The SEE question paper will be set for 100 marks and the marks scored will be proportionately reduced to 50.
2. The question paper will have ten full questions carrying equal marks.
3. Each full question is for 20 marks. There will be two full questions (with a maximum of four sub-questions)
from each module.
4. Each full question will have a sub-question covering all the topics under a module.
5. The students will have to answer five full questions, selecting one full question from each module
Suggested Learning Resources:
Text Books:

1. Introduction to the Design and Analysis of Algorithms, Anany Levitin: 2nd Edition, 2009. Pearson.
2. Computer Algorithms/C++, Ellis Horowitz, SatrajSahni and Rajasekaran, 2nd Edition, 2014, Universities Press.
3. Algorithms, Kenneth A Berman and Jerome L Paul, Cengage Learning India Pvt Ltd, 2002 edition.
Reference books:

1. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronal L. Rivest, Clifford Stein, 3rd Edition, PHI.
2. Design and Analysis of Algorithms, S. Sridhar, Oxford (Higher Education)
Web links and Video Lectures (e-Resources):
 http://elearning.vtu.ac.in/econtent/courses/video/CSE/06CS43.html
 https://nptel.ac.in/courses/106/101/106101060/
 http://elearning.vtu.ac.in/econtent/courses/video/FEP/ADA.html
 http://cse01-iiith.vlabs.ac.in/
 http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=IntroToAlgorit
hms
Skill Development Activities Suggested
 The students with the help of the course teacher can take up technical –activities which will enhance their skill or
the students should interact with industry (small, medium and large), understand their problems or foresee what
can be undertaken for study in the form of research/testing/projects, and for creative and innovative methods to
solve the identified problem. The prepared report shall be evaluated for CIE marks.

2
 Credits corrected
01.02.2023
Course outcome (Course Skill Set)
At the end of the course the student will be able to :
Sl. No. Description Blooms Level
CO1 Describe the basic algorithm design strategies and use them for devising new L2
solutions to various
problems
CO2 Analyse algorithms for time/space complexity L2
CO3 Differentiate between deterministic and probabilistic algorithms and use the L1
probabilistic algorithms in appropriate scenarios

Program Outcome of this course

Sl. No. Description POs

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

fundamentals, and computer science and business systems to the solution of complex
engineering and societal problems.

2 Problem analysis: Identify, formulate, review research literature, and analyze complex PO2
engineering and business problems reaching substantiated conclusions using first
principles of mathematics, natural sciences, and engineering sciences.

3 Design/development of solutions: Design solutions for complex engineering problems and PO3
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.

4 Conduct investigations of complex problems: Use research-based knowledge and research PO4
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, and apply appropriate techniques, resources, and PO5
modern engineering and IT tools including prediction and modeling to complex
engineering activities with an understanding of the limitations
6 The engineer and society: Apply reasoning informed by the contextual knowledge to PO6
assess societal, health, safety, legal and cultural issues and the consequent responsibilities
relevant to the professional engineering and business practices.
7 Environment and sustainability: Understand the impact of the professional engineering PO7
solutions in business societal and environmental contexts, and demonstrate the knowledge
of, and need for sustainable development.

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

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

10 Communication: Communicate effectively on complex engineering activities with the PO10

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.

11 Project management and finance: Demonstrate knowledge and understanding of the PO11
engineering, business 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.

12 Life-long learning: Recognize the need for, and have the preparation and ability to engage PO12
in independent and life-long learning in the broadest context of technological change.

3
 Credits corrected
01.02.2023
Mapping of COS and POs
PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
CO1 x x
CO2 x x
CO3 x x