README.md

Course : Design Analysis of Algorithm Theory (NCMPC41)

Lab Instructor	Email-id	Syllabus	Theory Attendance
Lifna C S	[email protected]	Theory & Lab Syllabus	Attendance

Design and Analysis of Algorithms Lab Instructions

Evaluation Scheme

No	Rubrics	Marks	Document / Schedule
1	End Semester Exam	60 Marks	[Old University Papers] , [Practice Problems]
2	Internal Assessment	20 Marks	[DAA-MT-QP-2025], [DAA-MT-QP-Sol-2025]
3	Continuous Assessment	20 Marks	Subjected to Revision after Internal Meeting
	a. Virtual Lab	10 Marks
	b. MCQ	10 Marks
	c. Programming Test on HackerRank	10 Marks
	Total Marks	100 Marks

Note :

Continuous Assessment best out 2 of 3 will be considered

Module - 1 : Introduction to Design and Analysis of Algorithms (10 Hours)

• Performance analysis - space, and time complexity

• Growth of function - Big-Oh, Omega & Theta notations

• Mathematical background for algorithm analysis;

• Analysis of selection sort, insertion sort.

• Recurrences: The substitution method, Recursion tree method, Master method

• Complexity Classes: Definition of P, NP, NP-Hard, NP-Complete

• Theory-PPT

• Online Materials:

  • Selection Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort

• Useful Links:

  • Comparison on Sorting Techniques - 1
  • Comparison on Sorting Techniques - 2
  • Visualization of Sorting Techniques : ComparisonSort - Prof. Galles
  • Bucket Sort
  • Heap Sort
  • quick sort

• Quiz : Module - 1 Quiz

Module - 2: Divide and Conquer Strategy (06 Hours)

• General method,

• Min-Max Algorithm,

• Merge sort,

• Quick sort,

• Analysis of Binary search,

• Strassen's Matrix Multiplication.

• Theory-PPT

• Online Resources :

• Quiz : Module - 2 Quiz

Module - 3 : Greedy Method Approach (06 Hours)

• General Method,Single source shortest path: Dijkstra Algorithm, Fractional Knapsack problem, Job sequencing with deadlines, Minimum cost spanning trees: Kruskal and Prim’s algorithms

• [Theory-PPT]

• Online Resources :

  -- Dijkstra's Algorithm Visualization -- Dijkstra Algo. Visualization - Prof. Galles

• Quiz : Module - 3 Quiz

Module - 4 : Dynamic Programming Approach (09 Hours)

• General Method,

• Multistage graphs,

• Single source shortest path: Bellman Ford Algorithm,

• All pair shortest path: Floyd Warshall Algorithm,

• Matrix Chain Multiplication,

• Longest common subsequence,

• Optimal Binary Search Trees,

• 0/1 knapsack Problem.

• [Theory-PPT]

• Online Resources :

• Quiz : Module - 4 Quiz

Module - 5 : Backtracking and Branch and bound (05 Hours)

• Backtracking:

  • N-queen problem,
  • Sum of subsets,
  • Graph coloring

• Branch and Bound:

  • 15 Puzzle problem,
  • Traveling Salesperson problem.

• [Theory-PPT]

• Online Resources :

• Quiz : Module - 5 Quiz

Module - 6 : String Matching Algorithms (03 Hours)

• Naïve string-matching algorithm,

• Rabin Karp algorithm,

• Knuth-Morris-Pratt algorithm

• [Theory-PPT]

• Online Resources :

• Quiz : Module - 6 Quiz

Text Books & References :

1. T. H. Cormen, C.E. Leiserson, R. L. Rivest, and C. Stein, “Introduction to algorithms”, 2nd Edition, PHI Publication 2005.
2. Ellis Horowitz, Sartaj Sahni, S. Rajsekaran. “Fundamentals of computer algorithms',' University Press.
3. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, “Algorithms”, Tata McGraw Hill Edition.
4. S. K. Basu, “Design Methods and Analysis of Algorithm”, PHI.
5. J. Kleinberg and E. Tardos, Algorithm Design, Pearson International Edition, 2005.

Online Resources

1. https://nptel.ac.in/courses/106/106/106106131/
2. https://swayam.gov.in/nd1_noc19_cs47/preview
3. https://www.coursera.org/specializations/algorithms
4. https://www.mooc-list.com/tags/algorithms
5. Stanford University

AI Tools

5. Algorithmia:
6. TensorFlow:
7. VisuAlgo:
8. Algorithm Visualizer:
9. Pathfinding Visualizer:

Industry articles

10. Artificial intelligence (AI) algorithms: a complete overview
11. What Is an Algorithm?
12. Algorithmic bias detection and mitigation: Best practices and policies to reduce consumer harms
13. Code-Dependent: Pros and Cons of the Algorithm Age :

Case Studies

14. A Case Study in Algorithm Analysis
15. An Introduction to the Analysis of Algorithms
16. Parallel MCMC Algorithms: Theoretical Foundations, Algorithm Design, Case Studies

Acknowledgemnts

• This material was prepared as a part of Course - Design and Analysis of Algorithms offered by the Department of Computer Engineering, VESIT (Autonomous Institute), Affiliated to the University of Mumbai to the Second Year Students of Computer Engineering Branch during the Academic Year 2024-25