Analysis & Design of Algorithms Lab (BCSL404)

Analysis & Design of Algorithms Lab

Course Code BCSL404 
CIE Marks 50
Teaching Hours/Week (L:T:P: S) 0:0:2:0 
SEE Marks 50
Credits 01 
Exam Hours 2
Examination type (SEE) Practical

Experiments

1 Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected

undirected graph using Kruskal's algorithm.

2 Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected

undirected graph using Prim's algorithm.

3 a. Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem using Floyd's

algorithm.

b. Design and implement C/C++ Program to find the transitive closure using Warshal's

algorithm.

4 Design and implement C/C++ Program to find shortest paths from a given vertex in a weighted

connected graph to other vertices using Dijkstra's algorithm.

5 Design and implement C/C++ Program to obtain the Topological ordering of vertices in a given

digraph.

6 Design and implement C/C++ Program to solve 0/1 Knapsack problem using Dynamic

Programming method.

7 Design and implement C/C++ Program to solve discrete Knapsack and continuous Knapsack

problems using greedy approximation method.

8 Design and implement C/C++ Program to find a subset of a given set S = {sl , s2,.....,sn} of n

positive integers whose sum is equal to a given positive integer d.

9 Design and implement C/C++ Program to sort a given set of n integer elements using Selection

Sort method and compute its time complexity. Run the program for varied values of n> 5000 and

record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read

from a file or can be generated using the random number generator.

10 Design and implement C/C++ Program to sort a given set of n integer elements using Quick Sort

method and compute its time complexity. Run the program for varied values of n> 5000 and

record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read

from a file or can be generated using the random number generator.

11 Design and implement C/C++ Program to sort a given set of n integer elements using Merge Sort

method and compute its time complexity. Run the program for varied values of n> 5000, and

record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read

from a file or can be generated using the random number generator.

12 Design and implement C/C++ Program for N Queen's problem using Backtracking.

Suggested Learning Resources:

● Virtual Labs (CSE): http://cse01-iiith.vlabs.ac.in/