Course Details

Subject {L-T-P / C} : CS2076 : Design and Analysis of Algorithms Laboratory { 0-0-3 / 2}

Subject Nature : Practical

Coordinator : Prof. Ramesh Kumar Mohapatra

Syllabus

1. Find second largest and second smallest number simultaneously in an array using Divide & Conquer Principle.
2. Given a sorted array and a number X, search two elements of array such that their sum is X. Expected time complexity is O(n).
3. Apply Binary Search on 2 D N by M array (A) having numbers stored in non-deceasing order under row-major scanning.
4. Given a sorted array and a number x, write a function that counts the occurrences of x in the array. Expected time complexity is O(log n).
5. Median of two sorted arrays: There are 2 sorted arrays A and B each of size n. Write an algorithm to find the median of the array obtained after merging the above 2 arrays (i.e.
array of length 2n). The complexity should be O(log(n))
6. A sorted array is rotated clockwise arbitrarily. Find the minimum element in it.
7. Apply Merge Sort to count inversion pairs in an array. Two elements a[i] and a[j] form an inversion pair if a[i] > a[j] and i < j. Example: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).
8. Implement Strassen’s Matrix Multiplication strategy for square matrices and apply for odd dimensional square matrix.
9. Given a value V and infinite supply of coins of m-denominations {C1=1 < C2 < C3<…..10. Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum. Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True // There is a subset (4, 5) with sum 9.
11 Given a cost 2D-matrix and a position (m, n), write a function that returns cost of minimum cost-path to reach (m, n) from (0, 0).
12. There are N stations on route of a train. The train goes from station 0 to N-1. The cost of ticket for pair of stations (i, j) is given where j is greater than i. Find the minimum cost to reach the destination.
13. Implement all pairs of Shortest path algorithm for a graph using Floyd-Warshall’s strategy.
14. Given an array of n numbers, design an algorithm for finding a contiguous subsequence A[i], A[i+1],…,A[i+k] having largest sum.
15. Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. You cannot break an item, either pick the item, or don’t pick it.
16. Find the smallest number with given digit sum s and number of digits d? Example Input : s = 9, d = 2 Output : 18
17. Every positive fraction can be represented as sum of unique unit fractions. A fraction is unit fraction if numerator is 1 and denominator is a positive integer (for example 1/3 is aunit fraction). Design and implement an algorithm to find all the unique unit fractions so that their sum equals a given positive fraction. Example for 2/3 output is 1/2 + 1/6 and for input 6/14 output is 1/3 + 1/11 + 1/231.
18. We need to connect n ropes of different lengths into one rope. The cost to connect two ropes is equal to sum of their lengths. Design and implement an algorithm to find the connection sequence resulting in minimum cost.
19. Suppose you are given a set S = {a1, a2, ..., an} of tasks, where task ai requires pi units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. Let ci be the completion time of task ai, that is, the time at which task ai completes processing. Your goal is to design an algorithm to find a schedule of the tasks so that the average completion time becomes minimum.
20. Implement a greedy algorithm to solve fractional knapsack problem.
21. Implement Kruskal’s and Prim’s algorithm for finding MST.
22. Implement greedy algorithm to solve the problem of Job Sequencing with deadlines.
23. Implement greedy algorithm of Huffman’s binary encoding of alphabets for a given list of words.
24. Implement KMP string matching algorithm.
25. A Maze is given as NxN binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N1]. A rat starts from source and has to reach destination. The rat can move only in two directions: forward and down. Write an algorithm to find its path from source to destination.
26. Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with same color. Here coloring of a graph means assignment of colors to all vertices.
27. Write a program to print all permutations of a given string (use Backtracking Principle).
28. The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.
29. Job Assignment Problem: Let there be N workers and N jobs. Any worker can be assigned to perform any job, incurring some cost that may vary depending on the work-job assignment. It is required to perform all jobs by assigning exactly one worker to each job and exactly one job to each agent in such a way that the total cost of the assignment is minimized.
30. You are given a 3×3 board with 8 tiles (every tile has one number from 1 to 8 and one space is empty). The objective is to place the numbers on tiles to match final configuration using the empty space. We can slide four adjacent (left, right, above and below) tiles into the empty space.

Course Objectives

Course Outcomes

Identify the problem given and design the algorithm using various algorithm design techniques. Apply important algorithmic design paradigms and methods of analysis. Synthesize efficient algorithms in common engineering design situations.

Essential Reading

Supplementary Reading