Fall 2025: Design and Analysis of Algorithms

From MKWiki
Jump to navigation Jump to search

Logistics

  • Class Timings: Tuesdays 1:30 pm - 2:30 pm, Thursdays 1:30 pm - 2:30 pm & 4:30 pm - 5:50 pm
  • Classroom: R-27
  • Lab Timings: Fridays 8:30 am- 10:30 am
  • Labs: CS Lab-3

Course Overview

Lectures

Lecture Topic Lecture Slides Readings
Unit-1 Searching, Sorting, Selection: [unit1.pdf] Chapter 1 (CB1)
Unit 2 Graphs: [unit2.pdf] Chapter 2 (CB1)
Unit 3 Divide and Conquer: [unit3.pdf] Chapter 6 (CB1)
Unit 4 Greedy algorithms': [unit4.pdf] Chapter 4 (CB1)
Unit 5 Dynamic Programming: [unit5.pdf] Chapter 5 (CB1)
Unit 6 Intractability: [unit6.pdf] Chapter 6 (CB1)
Unit 7 Advanced Analysis of Algorithms: [unit7.pdf] Chapter 7 (CB1)

Assignments and Tests

Class Assignments

  • Assignment No. 1,
  • Assignment No. 2,

Tests and Quizzes

  • Test 1 :
  • Test 2 :

Labs

Instructions

  • Please be on time to avoid the Attendance Penalty.
  • Please put your mobile phone on Silent Mode.
  • Each lab assignment needs to be submitted in the Google Classroom for evaluation(will be notified in the GC lab-wise, submit before the deadline).
  • Turn off(shut down) your assigned computer and arrange the chair before you leave the lab.


Practical List

  1. Write a program to sort the elements of an array using Insertion Sort (The program should report the number of comparisons).
(Assessment on: 12/09/2025 , GC submission deadline: 15/09/2025)
  1. Write a program to sort the elements of an array using Merge Sort (The program should report the number of comparisons).
  2. Write a program to sort the elements of an array using Heap Sort (The program should report the number of comparisons).
  3. Write a program to sort the elements of an array using Quick Sort (The program should report the number of comparisons).
  4. Write a program to multiply two matrices using the Strassen’s algorithm for matrix multiplication.
  5. Write a program to sort the elements of an array using Count Sort.
  6. Display the data stored in a given graph using the Breadth-First Search algorithm.
  7. Display the data stored in a given graph using the Depth-First Search algorithm.
  8. Write a program to determine a minimum spanning tree of a graph using the Prim’s algorithm.
  9. Write a program to solve the 0-1 knapsack problem.

For the algorithms at S. no 1 to 4, test run the algorithm on 100 different input sizes varying from 30 to 1000. For each size find the number of comparisons averaged on 10 different input instances; plot a graph for the average number of comparisons against each input size. Compare it with a graph of n logn.

Resources

References

  1. Cormen, T.H., Leiserson, C.E., Rivest, R. L., Stein C. Introduction to Algorithms, 4th edition, Prentice Hall of India, 2022.
  2. Kleinberg, J., Tardos, E. Algorithm Design, 1st edition, Pearson, 2013.

Additional References

  1. Basse, S., Gelder, A. V., Computer Algorithms: Introduction to Design and Analysis, 3rd edition, Pearson, 1999.
Retrieved from "http://www.mkbhandari.com/mkwiki/index.php?title=Fall_2025:_Design_and_Analysis_of_Algorithms&oldid=2654"