Course Code BCSE503
Category Engineering Science Course
Course title Design & Analysis of Algorithm
Scheme & Credits L T P Credits Semester
V
3 1 0 4
Pre-requisite (if any) None
Design & Analysis of Algorithm
Course Description:
Design & Analysis of Algorithms provides students with the theoretical foundation and practical
skills necessary to design, analyze, and implement efficient algorithms for solving computational
problems. Topics include algorithmic paradigms such as divide and conquer, greedy algorithms,
dynamic programming, and graph algorithms. Through rigorous analysis and mathematical
reasoning, students learn to evaluate algorithm performance in terms of time and space
complexity. Practical exercises and assignments reinforce theoretical concepts and equip
students with problem-solving techniques applicable to a wide range of domains, including
computer science, engineering, and data science.
Course Objectives:
1. Learn key algorithmic approaches like divide and conquer, greedy algorithms, dynamic
programming, and graph algorithms.
2. Master techniques to evaluate algorithm efficiency and scalability through time and space
complexity analysis.
3. Develop the ability to break down complex problems, identify appropriate algorithmic
strategies, and optimize solutions.
4. Explore advanced data structures such as heaps, trees, hash tables, and disjoint-set
structures to enhance algorithm performance.
5. Apply graph algorithms for traversal, shortest paths, minimum spanning trees, and
network flow problems to real-world scenarios.
Course Outcome:
CO1: Describe asymptotic analysis concepts and use them to evaluate the time-complexity of
different algorithms.
CO2: Explain, apply and analyze the divide and conquer, greedy method and dynamic
programming techniques to solve various engineering problems.
CO3: Discuss and use Branch and Bound, and pattern-matching algorithms.
CO4: Discuss randomized algorithms for min-cut and 2-SAT problem.
CO5: Understand the concepts of NP-Hard and NP-Complete problems.
Mapping COs with POs:
PO PO PO PO PO5 PO5 PO7 PO8 PO PO10 PO11 PO12 PSO PSO PSO
1 2 3 4 9 1 2 3
CO 1 M M S S M S M
CO 2 M M
CO 3 S S M S M M
CO 4 S S M S
CO 5 S S S S S S
Unit – 1: Introduction (7 Hrs.)
Asymptotic notations for time and space complexity,
Big-Oh notation, Θ notation, Ω notation, the little-oh notation, the little-omega notation,
Recurrence relations: iteration method,
recursion tree method, substitution method,
master method (with proof),
subtract and conquer master method(with proof),
Data Structures for Disjoint Sets, Medians and Order statistics.
Complexity analysis, Insertion sort, Merge Sort, Quick sort.
Strassen’s algorithm for Matrix Multiplications.
Unit – 2: Dynamic Programming (8 Hrs.)
Ingredientsof Dynamic Programming, emphasis on optimal substructure ,
overlapping substructures, memorization.
Matrix Chain Multiplication, Longest common subsequence
optimal binary search trees problems, 0-1 knapsack problem,
Binomial coefficient computation through dynamic programming.
Floyd Warshall algorithm.
Unit – 3:Greedy Algorithm (7 Hrs.)
Elements of Greedy strategy, overview of local and global optima, matroid,
Activity selection problem, Fractional Knapsack problem,
Huffman Codes,
A task scheduling problem.
Minimum Spanning Trees: Kruskal’s and Prim’s Algorithm,
Single source shortest path: Dijkstra’s and Bellman Ford Algorithm (with proof of
correctness of algorithms).
Unit – 4: String Matching (7 Hrs.)
The naïve String Matching algorithm, The Rabin-Karp Algorithm,
String Matching with finite automata, The Knuth-Morris Pratt algorithm.
Unit – 5:NP-Problem (7 Hrs.)
NP-Complete Problem: Polynomial-time verification, NP-Completeness and
Reducibility,
NP-Completeness Proof, NP –hard ,Case study of NP-Complete problems (vertex cover
problem, clique problem).
Text Book (s):
1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Clifford Stein, “Introduction to
Algorithms”, 3rd Ed., PHI, 2013.
2. Jon Klenberg,EvaTardos,”Algorithm Design”, Pearson Publications,2014
References:
1. Sara Basse, “introduction to Design &analysis”,Pearson
2. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, “Computer Algorithms/C++
“Second Edition, Universities Press.
3. A. V. Aho, J. E. Hopcroft, J. D. Ullman, “The Design and Analysis of Computer
Algorithms”, Pearson Publication, 2013.
4. Richard Neapolitan, “Foundations of Algorithms” , Fifth Edition, Jones & Bartlett
Learning
Assessment Scheme:
Continuous Internal Evaluation (CIA) consisting of:
Class Attendance (AT): 5%
Teaching Assignment (TA): 5%
Sessional Examination (CT): 20%
End Semester Examination (ESE): 70%
Mapping Assessment Components to COs:
CO 1 CO 2 CO 3 CO 4 CO5
AT S S M
TA M S S
CT M S M S
ESE S S
Note:
•CIA can have more components depending on the nature of the course.
•The guidelines for all assessment components are as per MUIT Guidelines& Rules (2.3-
curriculum development).
