Course : Design Analysis of Algorithm Theory (NCMPC41)

Lab Instructor	Email-id	Syllabus	Theory Attendance
Lifna C S	lifna.cs@ves.ac.in	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
• Insertion Sort Visualization : algorithm-visualize.org
• Selection Sort Visualization : algorithm-visualize.org

Useful Links:

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

Quiz:

• Algorithms

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 :

• Binary Search Visualization : algorithm-visualizer.org
• Quick Sort - Visualization : algorithm-visaulizer.org
• Merge Sort - Visualization : algorithm-visualizer.org
• Merge Sort - HackerRank
• Quick Sort - HackerRank
• Merge Sort - IIIT Hyderabad Virtual Labs
• Quick Sort - IIIT Hyderabad Virtual Labs
• Starssens Matrix Multiplication

Quiz :

• Sorting
• Merge Sort
• Quick Sort
• Binary Search - Quiz 1
• Binary Search - Quiz 2
• Starssens Matrix Multiplication

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 :

• Fractional Knapsack
• Dijkstra's Algorithm Visualization - 1
• Dijkstra's Algorithm Visualization - 2 : algorithm-visualizer.org
• Job Sequencing with Deadlines Visaulization : algorithm-visaulizer.org
• Kruskals Algorithm Visualiztion : algorithm-visualizer.org
• Prims Algorithm Visualization : algorithm-visualizer.org
• Dijkstra Algo. Visualization - Prof. Galles
• Minimum Spanning Trees - Virtual Labs

Quiz :

• Greey algorithm
• Fractional Knapsack Problem
• Job Sequencing with Deadlines
• Dijakstra Single Source Shortest Path
• Minimum Spanning Tree - Quiz
• Kruskals Algorithm
• Prims Algorithm

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 :

• 0/1 Knapsack Problem Visuailzation

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:

• Rabin Karp String Matching Algorithm Visualiztion : algorithm-visualizer.org
• Knuth Morris Pratt String Matching Algorithm Visualiztion : algorithm-visualizer.org

Quiz

• Rabin Karp Algorithm

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