README

DSC-10 Design and Analysis of Algorithms

Welcome to the collection of practical assignments for the Design and Analysis of Algorithms course.

📅 List of Practical

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.

📊 Sorting Algorithm Comparison (1-4)

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.

View Experiment Results:

C++ Data Collector
Python Plotting Script
Experiment Results (Plot)

<i>Developed with ❤️ by <a href="https://github.com/16ratneshkumar">16ratneshkumar</a></i>

</p>

← Previous Next →