Scribd
Upload
2 views4 pages

DAA theory syllabus

The course BCSE503, titled Design & Analysis of Algorithm, provides students with the skills to design and analyze efficient algorithms using various paradigms such as divide and conquer, greedy algorithms, and dynamic programming. It covers algorithm performance evaluation through time and space complexity analysis, advanced data structures, and real-world applications of graph algorithms. The course includes assessments like class attendance, teaching assignments, and examinations to evaluate students' understanding of the material.

Uploaded by

farawey903
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views4 pages

DAA theory syllabus

The course BCSE503, titled Design & Analysis of Algorithm, provides students with the skills to design and analyze efficient algorithms using various paradigms such as divide and conquer, greedy algorithms, and dynamic programming. It covers algorithm performance evaluation through time and space complexity analysis, advanced data structures, and real-world applications of graph algorithms. The course includes assessments like class attendance, teaching assignments, and examinations to evaluate students' understanding of the material.

Uploaded by

farawey903
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

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

You might also like