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

From MKWiki
Jump to navigation Jump to search
 
(11 intermediate revisions by the same user not shown)
Line 17: Line 17:
 
|-
 
|-
 
| style="width: 12%; " |  Unit-1  
 
| style="width: 12%; " |  Unit-1  
−
| style="width: 60%" |  '''''Digital Forensics:''''':  
+
| style="width: 60%" |  '''''Searching, Sorting, Selection''''':  
 
| style="width: 15%" | [unit1.pdf]   
 
| style="width: 15%" | [unit1.pdf]   
 
| Chapter 1 (CB1)
 
| Chapter 1 (CB1)
 
|-
 
|-
 
| Unit 2  
 
| Unit 2  
−
|  '''''Windows OS Forensics:'''''
+
|  '''''Graphs''''':
 
|  [unit2.pdf]   
 
|  [unit2.pdf]   
 
| Chapter 2 (CB1)
 
| Chapter 2 (CB1)
 
|-
 
|-
 
| Unit 3  
 
| Unit 3  
−
|  '''''Evidence Recovery:'''''
+
|  '''''Divide and Conquer''''':
 
|  [unit3.pdf]   
 
|  [unit3.pdf]   
 
| Chapter 6 (CB1)
 
| Chapter 6 (CB1)
 
|-
 
|-
 
| Unit 4
 
| Unit 4
−
|  '''''Investigation:'''''  
+
|  '''''Greedy algorithms'''':
 
|  [unit4.pdf]     
 
|  [unit4.pdf]     
 
| Chapter 4 (CB1)
 
| Chapter 4 (CB1)
 
|-
 
|-
 
| Unit 5
 
| Unit 5
−
|  '''''Cyber Crimes and Cyber Laws:'''''  
+
|  '''''Dynamic Programming''''':
 
| [unit5.pdf]   
 
| [unit5.pdf]   
 
| Chapter 5 (CB1)
 
| Chapter 5 (CB1)
 +
|-
 +
| Unit 6
 +
|  '''''Intractability''''':
 +
| [unit6.pdf] 
 +
| Chapter 6 (CB1)
 +
|-
 +
| Unit 7
 +
|  '''''Advanced Analysis of Algorithms''''':
 +
| [unit7.pdf] 
 +
| Chapter 7 (CB1)
 
|}
 
|}
  
Line 59: Line 69:
 
* 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 1: ( week of 18<sup>th</sup> August 2025 ) ==
+
 
−
{| class="wikitable" style="text-align: justify;
+
'''Practical List'''
−
|-
+
 
−
! Task. No.   
+
# Write a program to sort the elements of an array using Insertion Sort (The program should report the number of comparisons).  <br>
−
! Task
+
::('''Assessment on''': 12/09/2025 , '''GC submission deadline:''' 15/09/2025)
−
! Assessment Period
+
# Write a program to sort the elements of an array using Merge Sort (The program should report the number of comparisons).
−
! Submission Deadline
+
# Write a program to sort the elements of an array using Heap Sort (The program should report the number of comparisons).
−
|-
+
# Write a program to sort the elements of an array using Quick Sort (The program should report the number of comparisons).
−
| style="width: 8%"  | 1
+
# Write a program to multiply two matrices using the Strassen’s algorithm for matrix multiplication.
−
| style="width: 60%" | Study of Network related Commands (Linux)
+
# Write a program to sort the elements of an array using Count Sort.
−
* Network Discovery: - '''''Ping, Traceroute/Tracepath, Nmap, MTR'''''
+
# Display the data stored in a given graph using the Breadth-First Search algorithm.
−
* Traffic Analysis: - '''''Tcpdump, Iftop/Bmon, Iperf'''''
+
# Display the data stored in a given graph using the Depth-First Search algorithm.
−
* DNS/Domain Forensics: - '''''Dig, Nslookup, Whois, Host'''''
+
# Write a program to determine a minimum spanning tree of a graph using the Prim’s algorithm.
−
* Host configuration:- '''''Ifconfig/Ip, SS/Netstat, Ethtool, Hostname'''''
+
# Write a program to solve the 0-1 knapsack problem.
−
* Address/Routing Analysis: - '''''ARP, Route, Iproute2'''''
+
 
−
* Data Transfer/File Retrieval: - '''''wget, curl'''''
+
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.
−
| style="width: 15%" |  18/08/2025 - 25/08/2025
 
−
|  26/08/2025
 
−
|}
 
  
 
== Resources ==
 
== Resources ==
−
'''References:'''
+
'''References''' <br>
−
* '''R1''':  Marjee T. Britz, Computer Forensics and Cyber Crime: An Introduction, Pearson Education, 2013. <br>
+
# Cormen, T.H., Leiserson, C.E., Rivest, R. L., Stein C. Introduction to Algorithms, 4th edition, Prentice Hall of India, 2022.
−
* '''R2''':  C. Altheide & H. Carvey Digital Forensics with Open Source Tools, Syngress, 2011. <br>
+
# Kleinberg, J., Tardos, E. Algorithm Design, 1st edition, Pearson, 2013.
  
−
'''Additional References:'''
+
'''Additional References'''
−
# Computer Forensics: Investigating Network Intrusions and Cybercrime" by Cameron H. Malin, Eoghan Casey, and James M. Aquilina
+
# Basse, S., Gelder, A. V., Computer Algorithms: Introduction to Design and Analysis, 3rd edition, Pearson, 1999.
−
# Online Course management System: https://esu.desire2learn.com/
 
−
# Computer Forensics, Computer Crime Investigation by John R,Vacca, Firewall Media, New Delhi.
 
−
# Computer Forensics and Investigations by Nelson, Phillips Enfinger, Steuart,CENGAGE Learning
 
−
# Real Digital Forensics by Keith j.Jones, Richard Bejitlich,Curtis W.Rose, AddisonWesley Pearson Education
 

Latest revision as of 09:58, 12 September 2025

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"