DarshanRokkad/daa_lab

Design and Analysis of Algorithms Lab [4th semester subject] (Nitte Meenakshi Institute Of Technology, Banglore)

Program List:

PART - A

1. Digital maps, unlike humans, see cities as a bunch of nodes. We (humans) consider this map as a single entity. a GPS navigation or any other digital map divides it into hundreds of segments, with some only 24 meters long. A map displays n cities and their distances. Design and develop a program in C to print all the cities reachable from a given starting city in a digraph by using BFS method. Repeat the experiment for different values of n and plot a graph of the time taken versus n(n=no of nodes)

2. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands using DFS algorithm. Design and develop a program in C to print all the lands reachable from a given starting land in a digraph by using DFS method. Repeat the experiment for different values of n and plot a graph of the time taken versus n(n=no of nodes)

3. “Digishop” a online shopping website needsto keep track of the product availabilitybased on the product ID. Design a program in C to read the product ID provided by the customer and search for it’s availability by using Binary search method and display the relevant message whether the product is in stock or not. Determine the time required to search for the product. Repeat the experiment for different values of n and plot a graph of the time taken versus n. (n=no of elements).

4. “Aircel” a mobile network company need to maintain the telephone numbers of itscustomer in order to call and inform them about the new year offer. They have to sort the contact numbers in ascending order to keep track of the customers whom they called. Design and develop a program in C to sort the phone numbers by using insertion sort algorithm, Input should be generated randomly. Determine the time required to sort the elements. Repeat the experiment for different values of n and plot a graph of the time taken versus n. (n=no of elements).

5. “Deloit”, a software company needs to maintain its employee details like employeeid, name, address in a record, design and develop a program in C to sort the employee records based on their employee ID by using merge sort algorithm, employee ID should be generated randomly. Determine the time required to sort theelements. Repeat the experiment for different values of n and plot a graph of the time taken versus n. (n=no of elements).

6. Assume that NMIT college needs to maintain the student details like USN, name, and contact details in a record. USN should be generated randomly. Design and develop a program in C to sort the records based on USN by using quick sort algorithm, Determine the time required to sort the roll numbers. Repeat the experiment for different values of n and plot a graph of the time taken versus n. (n=no of elements).

7. “Sunshine” a job search portal is looking for engineering graduates, they need to sort the candidate’s resume based on their ranking (Average Percentage). Ranking should be generated randomly. Design and develop a program in C to sort the resumes by using heap sort algorithm. Determine the time required to sort the elements. Repeat the experiment for different values of n and plot a graph of the time taken versus n.(n=no of elements).

PART - B

8. Consider the problem of searching for genes in DNA sequences using Horspool’s algorithm. A DNA sequence is represented by a text on the alphabet {A, C, G, T}, and the gene or gene segment is the pattern. A gene segment of your chromosome 10 has the pattern TCCTATTCTT . Design and develop a program in C to locate the above pattern in the following DNA sequence by applying Horspool’s algorithm. TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTT Also compute the number of comparisons using this method as compared to linear search method.

9. There have been a number of fire outbreak cases recorded in the Florida area that has brought about loss of lives to inhabitants and loss of properties. Some routes within the district can be reconstructed into shortcut routes, so that fire man can traverse through the district in order to prevent fire incidents. The objective is to find the minimum distance and shortest path from the fire station to all the residential layout in Florida area. Write an algorithm by applying Floyd’s method to find the solution for the given scenario.

10. DMART is providing special offer to its customer on New Year’s Eve. Customers can buy anything they want with flat80% discount, but the products they buy should fit into the basket provided by DMART. The objective is to collect the expensive products which fit into the given basket and overall weight of the basket cannot exceed 15kg.Write an algorithm by using knapsack algorithm using dynamic programming to find the best subset for the given scenario.

11. Bangalore Water supply Board responsibility is to distribute water evenly among all the areas in Bangalore city. A new layout has been developed by Maxworth real estate developers. BWSB should connect the water lines to the new layout with minimum cost. The objective is to connect the water pipes so that it reaches all the houses in new layout with minimum cost. Write an algorithm by applying Kruskal’s method to find the minimum spanning tree for the given scenario.

12. DigiMap services is a module in G-Maps which is used to find the distance from one place to another or from your location to the nearest desired location. This requires the Shortest Path Algorithm, as there are various routes/paths connecting them but it has to show the minimum distance. . Represent a city/place with a vertex and the route between two cities/places as an edge, then by using Dijkstra’s algorithm, find the shortest routes between any two cities/places or from one city/place to another city/place.

13. Consider the n-queens puzzle in which the goal is to place N queens on an N×N chessboard such that no two queens attack each other. A queen can attack horizontally, vertically, or diagonally. Given an integer N, return all distinct solutions to the N-queens puzzle. Note: Use Backtracking technique.

14. Consider the Subset sum problem in which the objective is to find subset of elements that are selected from a given set whose sum adds up to a given number K. Assume the set contains non-negative values and also the input set is unique (no duplicates are present.). Design and develop a program in C to find the subset of a given set whose sum is equal to a positive integer K and display an appropriate message if the given problem instance does not have the solution. Note : Use Backtracking method.