Difference between revisions of "Fall 2026: Design and Analysis of Algorithms"

From MKWiki
Jump to navigation Jump to search
 
(11 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
== Logistics ==
 
== Logistics ==
 
*Class Timings: '''Mondays''', '''Tuesdays''', and '''Thursdays''' 9:30 am - 10:30 am  
 
*Class Timings: '''Mondays''', '''Tuesdays''', and '''Thursdays''' 9:30 am - 10:30 am  
−
*Classroom: Mondays (''T-7'')  and Thursdays(''T-11'')
+
*Classroom: (''R-43'')
−
*Lab Timings: '''Mondays''' 1:30 pm - 3:30 pm
+
*Lab Timings: '''Fridays''' 8:30 am - 10:30 am
−
*Labs: Computer Lab 4 (''CL-4'')
+
*Labs: Computer Lab 4 (''CL-3'')
  
 
== Course Overview ==
 
== Course Overview ==
Line 17: Line 17:
 
|-
 
|-
 
| style="width: 12%; " |  Unit-1  
 
| style="width: 12%; " |  Unit-1  
−
| style="width: 60%" |  '''''Introduction to Data Mining:'''''  
+
| style="width: 60%" |  '''''Searching, Sorting, Selection, Divide and Conquer:'''''  
 
| style="width: 15%" | [unit1.pdf]   
 
| style="width: 15%" | [unit1.pdf]   
−
| Chapter 1
+
| Chapter 2,4,6,7,8,9 (R1)
 
|-
 
|-
 
| Unit 2  
 
| Unit 2  
−
|  '''''Data Pre-Processing:'''''
+
|  '''''Graphs and Greedy algorithms:'''''
 
|  [unit2.pdf]   
 
|  [unit2.pdf]   
−
| Chapter 2
+
| Chapter 3, 4 (R2) & 15(R1)
 
|-
 
|-
 
| Unit 3  
 
| Unit 3  
−
|  '''''Cluster Analysis:'''''
+
|  '''''Dynamic Programming:'''''
 
|  [unit3.pdf]   
 
|  [unit3.pdf]   
−
| Chapter 5
+
| Chapter 6 (R2)
 
|-
 
|-
 
| Unit 4
 
| Unit 4
−
|  '''''Association Rule Mining:'''''  
+
|  '''''Hash Functions, Collision resolution schemes:'''''  
 
|  [unit4.pdf]     
 
|  [unit4.pdf]     
−
| Chapter 4
+
| Chapter 11 (R1)
−
|-
 
−
| Unit 5
 
−
|  '''''Classification:'''''
 
−
| [unit5.pdf] 
 
−
| Chapter 3 & 6
 
 
|}
 
|}
  
Line 59: Line 54:
 
* Turn off'''(shut down) your assigned computer and arrange the chair''' before you leave the lab.
 
* Turn off'''(shut down) your assigned computer and arrange the chair''' before you leave the lab.
  
−
=== '''Lab 0: Getting Started''' ( week of 03<sup>rd</sup>, 10<sup>th</sup > & 17<sup>th</sup >  August 2026 ) ===
+
=== '''Practicals LIst '''===
−
{| class="wikitable" style="text-align: justify;  
+
# Write a program to sort the elements of an array using Insertion Sort (The program should report the number of comparisons).
−
|-
+
# Write a program to sort the elements of an array using Merge Sort (The program should report the number of comparisons).
−
! Task No.
+
# Write a program to sort the elements of an array using Heap Sort (The program should report the number of comparisons).
−
! Task  
+
# Write a program to sort the elements of an array using Quick Sort (The program should report the number of comparisons).
−
! Assessment Period.
+
# Write a program to multiply two matrices using the Strassen’s algorithm for matrix multiplication.
−
! Submission Deadline
+
# Write a program to sort the elements of an array using Count Sort.
−
|-
+
# Display the data stored in a given graph using the Breadth-First Search algorithm.
−
| style="width: 8%" | 1
+
# Display the data stored in a given graph using the Depth-First Search algorithm.
−
| style="width: 60%" | https://www.cse.msu.edu/~ptan/dmbook/tutorials/tutorial1/tutorial1.html
+
# Write a program to determine a minimum spanning tree of a graph using the Prim’s algorithm.
−
| style="width: 15%" | --
+
# Write a program to determine the shortest path from a given node s to the other nodes of a graph using the Dijkstra’s algorithm.
−
| --
+
# Write a program to solve the 0-1 knapsack problem using Dynamic Programming.
−
|-
 
−
| 2 || https://www.cse.msu.edu/~ptan/dmbook/tutorials/tutorial2/tutorial2.html  || -- || --
 
−
|-
 
−
| 3 || https://www.cse.msu.edu/~ptan/dmbook/tutorials/tutorial3/tutorial3.html || -- || --
 
−
|}
 
−
 
 
−
=== '''Lab 1: ''' ( week of 24<sup>th</sup> & 31<sup>st</sup> August 2026  ) ===
 
−
{| class="wikitable" style="text-align: justify;  
 
−
|-
 
−
! Task No.
 
−
! Task  
 
−
! Assessment Period.
 
−
! Submission Deadline
 
−
|-
 
−
| style="width: 8%" style="text-align: center;  | 1
 
−
| style="width: 60%" | Apply data cleaning techniques on any dataset (e.g., Paper Reviews dataset in UCI repository). Techniques may include handling missing values, outliers and inconsistent values. A set of validation rules can be prepared based on the dataset and validations can be performed.
 
−
| style="width: 15%" |  24/08/2026 - 31/08/2026
 
−
| 01/09/2026
 
−
|}
 
−
 
 
−
=== '''Lab 2: ''' ( week of 07<sup>th</sup> & 14<sup>th</sup> September 2026  ) ===
 
−
{| class="wikitable" style="text-align: justify; 
 
−
|-
 
−
! Task No.
 
−
! Task  
 
−
! Assessment Period. 
 
−
! Submission Deadline
 
−
|-
 
−
| style="width: 8%" style="text-align: center;  | 2
 
−
| style="width: 60%" | Apply data pre-processing techniques such as standardization/normalization, transformation, aggregation, discretization/binarization, sampling etc. on any dataset
 
−
| style="width: 15%" | 07/09/2026 - 14/09/2026
 
−
| 22/09/2025
 
−
|}
 
−
 
 
−
=== '''Lab 3: ''' ( week of 21<sup>st</sup> & 28<sup>th</sup>  September 2026  ) ===
 
−
{| class="wikitable" style="text-align: justify; 
 
−
|-
 
−
! Task No.
 
−
! Task  
 
−
! Assessment Period. 
 
−
! Submission Deadline
 
−
|-
 
−
| style="width: 8%" style="text-align: center;  | 5
 
−
| style="width: 60%" | Apply simple K-means algorithm for clustering any dataset. Compare the performance of clusters by varying the algorithm parameters. For a given set of parameters, plot a line graph depicting MSE obtained after each iteration.
 
−
| style="width: 15%" | 21/09/2026 - 28/09/2026
 
−
| 29/09/2026
 
−
|}
 
  
 
== Resources ==
 
== Resources ==
 
'''References:'''
 
'''References:'''
−
* '''Text Book''': Tan P.N., Steinbach M, Karpatne A. and Kumar V. Introduction to Data Mining, Second edition, Sixth Impression, Pearson, 2023.
+
* '''R1''': Cormen, T.H., Leiserson, C.E., Rivest, R. L., Stein C. Introduction to Algorithms, 4th edition, Prentice Hall of India, 2022.
−
 
+
* '''R2''': Kleinberg, J., Tardos, E. Algorithm Design, 1st edition, Pearson, 2013.
−
'''Additional References:'''
 
−
#  Han J., Kamber M. and Pei J. Data Mining: Concepts and Techniques, 3rd edition, 2011, Morgan Kaufmann Publishers.
 
−
#  Zaki M. J. and Meira J. Jr. Data Mining and Machine Learning: Fundamental Concepts and Algorithms, 2nd edition, Cambridge University Press, 2020.
 
−
#  Aggarwal C. C. Data Mining: The Textbook, Springer, 2015
 
−
#  Insight into Data mining: Theory and Practice, Soman K. P., Diwakar Shyam, Ajay V., PHI 2006
 

Latest revision as of 22:55, 7 September 2026

Logistics

  • Class Timings: Mondays, Tuesdays, and Thursdays 9:30 am - 10:30 am
  • Classroom: (R-43)
  • Lab Timings: Fridays 8:30 am - 10:30 am
  • Labs: Computer Lab 4 (CL-3)

Course Overview

Lectures

Lecture Topic Lecture Slides Readings
Unit-1 Searching, Sorting, Selection, Divide and Conquer: [unit1.pdf] Chapter 2,4,6,7,8,9 (R1)
Unit 2 Graphs and Greedy algorithms: [unit2.pdf] Chapter 3, 4 (R2) & 15(R1)
Unit 3 Dynamic Programming: [unit3.pdf] Chapter 6 (R2)
Unit 4 Hash Functions, Collision resolution schemes: [unit4.pdf] Chapter 11 (R1)

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.

Practicals LIst

  1. Write a program to sort the elements of an array using Insertion Sort (The program should report the number of comparisons).
  2. Write a program to sort the elements of an array using Merge Sort (The program should report the number of comparisons).
  3. Write a program to sort the elements of an array using Heap Sort (The program should report the number of comparisons).
  4. Write a program to sort the elements of an array using Quick Sort (The program should report the number of comparisons).
  5. Write a program to multiply two matrices using the Strassen’s algorithm for matrix multiplication.
  6. Write a program to sort the elements of an array using Count Sort.
  7. Display the data stored in a given graph using the Breadth-First Search algorithm.
  8. Display the data stored in a given graph using the Depth-First Search algorithm.
  9. Write a program to determine a minimum spanning tree of a graph using the Prim’s algorithm.
  10. Write a program to determine the shortest path from a given node s to the other nodes of a graph using the Dijkstra’s algorithm.
  11. Write a program to solve the 0-1 knapsack problem using Dynamic Programming.

Resources

References:

  • R1: Cormen, T.H., Leiserson, C.E., Rivest, R. L., Stein C. Introduction to Algorithms, 4th edition, Prentice Hall of India, 2022.
  • R2: Kleinberg, J., Tardos, E. Algorithm Design, 1st edition, Pearson, 2013.
Retrieved from "http://www.mkbhandari.com/mkwiki/index.php?title=Fall_2026:_Design_and_Analysis_of_Algorithms&oldid=2710"