DAA- - JAN 2025
Module-1- Introduction to time and space complexity,
Algorithm definition, insertion sort running time calculation, Notations Theta, big O, big
Omega, little o notations with examples. Space complexity definition and examples like matrix
multiplication, bubble sort, factorial computation recursive and iterative version. Recurrence
relations and finding time complexity using substitution method, recursion tree and master theorem.
Proof of correctness of algorithms.
Module 2- Divide and conquer
General strategy of divide and conquer examples binary search, quick sort-best case, worst case and
average case time complexities, merge sort and analysis, finding majority element and analysis,
Order statistics- finding simultaneous maximum and minimum, selection problem.
Module 3:- Dynamic programming
General strategy, Fibonacci sequence example dynamic and recursive with comparison. Travelling
salesman problem by dynamic programming. And 0-1 knapsack problem using dynamic
programming.
Module 4:- Greedy strategy
General approach, fractional knapsack problem using greedy method, Job scheduling/sequencing
using greedy approach examples, Huffman coding, minimum spanning tree-Kruskal’s and Prim’s
algorithm
Module 5:- Backtracking strategy
General approach, N-queens problem using backtracking, graph coloring problem with examples
Module 6:- Complexity classes and Randomized algorithms
Introduction to P, NP, NPC and NP-Hard problems and their interrelations, Randomized algorithms-
Las Vegas and Monte Carlo simple examples
List of Lab assignments DAA
1. Implementation and timing analysis of matrix multiplication for square matrices
2. Implementation and analysis of quick sort
3. Finding out majority element from an array
4. : Compare dynamic programming and divide and conquer using
Fibonacci sequence
5. Huffman coding using Greedy strategy
6. Knapsack using dynamic programming
Text Books:
1. Cormen, Leiserson, Rivest and Stein “Introduction to Algorithms”, 3rd edition, 2009. ISBN
81-203-2141-3, PHI
2. Horowitz and Sahani, Fundamentals of computer Algorithms, Galgotia, ISBN 81-7371-612-9
3. Jon Kleinberg, Eva Tardos “Algorithm Design”, 1st edition, 2005. ISBN 978-81-317-0310-6,
Pearson
1. 4.Dasgupta, Papadimitriu, Vazirani “Algorithms”, 1st edition (September 13, 2006), ISBN-
10:9780073523408, ISBN-13: 978-0073523408, McGraw-Hill Education
Reference Books:
1. Anany Levitin, “Introduction to the Design & Analysis of Algorithm”, Pearson, ISBN 81- 7758-
835-4.
2. Gilles Brassard, Paul Bratle, Fundamentals of Algorithms, Pearson, ISBN 978-81-317-1244-3.
3. Motwani, Raghavan “Randomized Algorithms”, 1st edition (August 25, 1995), ISBN-
10:0521474655, ISBN-13: 978-0521474658, Cambridge University Press
4.Vazirani, “Approximation Algorithms”, ISBN-10: 3642084699, ISBN-13: 978-
3642084690,Springer (December 8, 2010)
CO Statements:
The student will be able –
1) To formulate computational problems in abstract and mathematically precise manner (1)
2) To design efficient algorithms for computational problems using appropriate algorithmic paradigm (3)
3) To analyze asymptotic complexity of the algorithm for a complex computational problem using suitable
mathematical techniques. (2)
4) To differentiate among Complexity classes, and understand their interrelation (3)
5) To establish NP--completeness of some decision problems, grasp the significance of the notion of NP--
completeness
6) To incorporate appropriate data structures, algorithmic paradigms to craft innovative scientific solutions for
complex computing problems
