Dept.
of ISE, NIE, Mysuru-08
Course Code: 21IS4L01 Course: ANALYSIS AND DESIGN OF ALGORITHMS LAB
SET: 25 Marks SET Hours: 3 Hours
Scheme for Semester End Test (SET)
Procedure 10 marks
Analysis and Implementation 10 marks
with result
Viva Voce 5 marks
Total 25 marks
Note: Design an algorithm for the following problems and implement them in any one of the
programming languages: C, C++, Java, or Python. Also analyze its time complexity.
List of experiments
1. Implement linear search and binary search to find a key element in list of n elements.
Compare their time complexity for worst case for large values of n (100, 200, …,1000). The
elements can be read from a file or can be generated using the random number generator.
2. Implement Selection sort and Merge Sort algorithms to sort a given set of n elements and
determine the time required to sort the elements. Repeat the experiments for different values
of n (100, 200, …,1000) and plot a graph of the time taken versus n to compare the two
algorithms. The elements can be read from a file or can be generated using the random
number generator.
3. Implement Insertion sort and Quick Sort algorithms to sort a given set of n elements and
determine the time required to sort the elements. Repeat the experiments for different values
of n (100, 200, …,1000) and 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.
4. Print all the nodes reachable from a given starting node in a digraph using the BFS
method.
5. Check whether a given graph is connected or not using the DFS method.
6. Implement Topological sorting using DFS.
7. Find the Minimum Cost Spanning Tree of a given undirected graph using Prim’s
algorithm.
8. Implement the 0/1 knapsack problem using Dynamic programming.
9. Implement All-Pairs Shortest Paths Problem using Floyd’s algorithm.
10. Implement a single source shortest path using Dijkstra’s Algorithm.
[Link] a subset of a given set S = {Sl, S2, Sn} of n positive integers whose SUM is equal to a
given positive integer d. For example, if S = {1, 2, 5, 6, 8} and d= 9, there are two solutions
{1, 2, 6} and {1, 8}. Display a suitable message if the given problem instance doesn't have
a solution. Page | 1
