DAA - II UNIT PDF

Design and Analysis of Algorithm – II UNIT 2 marks: 1. What is Brute force approach of problem solving? Give an example. The brute force approach is a problem-solving strategy that involves trying every possible solution until the correct one is found. It is a straightforward and intuitive method, b...

Design and Analysis of Algorithm – II UNIT 2 marks: 1. What is Brute force approach of problem solving? Give an example. The brute force approach is a problem-solving strategy that involves trying every possible solution until the correct one is found. It is a straightforward and intuitive method, but it can be inefficient for large problems due to its exponential time complexity. Example: Finding the shortest path between two cities in a road network. To find the largest number in a list of numbers. 2. List any four importance of Brute force. Simplicity: The brute force approach is easy to understand and implement. Guaranteed solution: The brute force approach always finds a solution if one exists. Benchmarking: The brute force algorithm can be used as a benchmark to compare the performance of other algorithms. Educational value: The brute force approach can help students understand the concept of algorithm efficiency. 3. Write the number of operations and time complexity of selection sort. Number of operations : Time Complexity : O(n2) 4. Write the number of operations and time complexity of bubble sort. Number of operations : Time Complexity : O(n2) 5. What do you mean by Sequential Search? Write its time complexity. Sequential search, also known as linear search, is a simple search algorithm that searches for a target element in a list by examining each element in the list sequentially until the target element is found or the end of the list is reached. The time complexity of sequential search is O(n), where n is the number of elements in the list. 6. Write the worst case and average case complexity of Brute force String Matching. Worst case complexity: O(mn) Average case complexity: O(n+m) = O(n) 7. Write the number of operations and time complexity of Closest-Pair Problem. Number of operations : (n - 1)n Time Complexity : O(n2) 8. Define Convex and Convex hull. Convex : A set of points in space is convex if for any two points in the set, the line segment connecting them lies entirely within the set. Convex hull : The convex hull of a set of points is the smallest convex set that contains all the points in the set. 9. List any two example algorithms of the brute force approach. Sequential search Brute force string matching 10. What do you mean by convex hull problem? Write its time complexity. The convex-hull problem is the problem of constructing the convex hull for a given set S of n points. To solve it, we need to find the points that will serve as the vertices of the polygon in question. Time Complexity : O(n3) 11. Define Exhaustive search mechanism. Give example. Exhaustive search is simply a brute-force approach to combinatorial problems. It suggests generating each and every element of the problem's domain, selecting those of them that satisfy all the constraints, and then finding a desired element. Example : Traveling Salesman Problem (TSP), Knapsack problem 12. What do you mean by Knapsack Problem? Write its time complexity. The problem is to find the subset of a set of items that maximizes the total value of the items subject to a weight constraint. Time Complexity : O (N*W) where 'N' - number of weight elements, 'W' - capacity of the knapsack 13. What do you mean by Travelling Salesman Problem? Write its time complexity. The problem asks to find the shortest tour through a given set of n cities that visits each city exactly once before returning to the city where it started. The problem can be conveniently modeled by a weighted graph, with the graph's vertices representing the cities and the edge weights specifying the distances. Time Complexity : O(n!) where n is the number of cities. 14. What do you mean by Job assignment problem? Write its time complexity. The job assignment problem is a classic optimization problem in computer science. The problem is to assign a set of n jobs to n machines in such a way that the total completion time is minimized. Time Complexity : O(n!) Long Answer Questions 1. Write an algorithm to sort N numbers using Selection sort. Derive the number of operations and time complexity. The input's size is given by the number of elements n. The algorithm's basic operation is the key comparison A[j] < A[min]. The number of times it is executed depends only on the array's size and is given by the following sum: Thus, selection sort is a O(n2) algorithm on all inputs. The number of key swaps is O(n). 2. Write an algorithm to sort N numbers by applying Bubble sort. Derive the number operations and time complexity. The input's size is given by the number of elements n. The algorithm's basic operation is the key comparison. The number of times it is executed depends only on the array's size and is given by the following sum: 3. Write and describe the Sequential search algorithm. Sequential search, also known as linear search, is a simple method to find a specific value in a list. It works by starting at the beginning of the list and comparing each element with the value we’re searching for, until the desired element is found or the end of the list is reached. The time complexity of sequential search is O(n), where n is the number of elements in the list. This is because in the worst-case scenario, we have to check every element in the list. Therefore, while sequential search is easy to implement, it can be inefficient for large lists. 4. Write and describe Brute force String Matching Algorithm. Brute force string matching is a simple string matching algorithm that searches for a pattern string in a text string by comparing the pattern string to each substring of the text string of the same length. The brute force string matching algorithm is a simple and intuitive algorithm, but it is also inefficient for large problems. This is because the time complexity of the algorithm is O(mn), which means that the algorithm can take a long time to run for long text strings and pattern strings. 5. Write and explain the algorithm for Closest-Pair Problem. Derive its complexity. The closest-pair problem is to find the pair of points in a set of points that are closest to each other. The basic operation of the algorithm is computing the Euclidean distance between two points. The number of times it will be executed can be computed as follows: 6. Write and explain the algorithm for Convex Hull problem. The Convex Hull is the smallest convex polygon that contains all the points of a given set in the plane. The problem is to compute the Convex Hull of a set of points. BruteForceConvexHull(points): n = number of points convex_hull = empty list for each subset of 3 points (p1, p2, p3): if points form a left turn: Add p1, p2, and p3 to convex_hull return convex_hull The time complexity of this brute force algorithm is O(n3), where N is the number of points. This is because the algorithm iterates through all possible subsets of three points. 7..Explain Travelling Salesman Problem by exhaustive search with an example. The problem asks to find the shortest tour through a given set of n cities that visits each city exactly once before returning to the city where it started. The problem can be conveniently modeled by a weighted graph, with the graph's vertices representing the cities and the edge weights specifying the distances. Example: Refer Q.No. 9 8. Write a note on Knapsack Problem with an example. Given n items of known weights w1,... , wn and values v1,... , vn and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack. Example: Refer Q.No. 12 9. Find the optimal solution for the Traveling Salesman problem using exhaustive search method by considering ‘A’ as the starting city. Tour Length a -> b -> c -> d -> a l=20+30+12+35=97 optimal a -> b -> d -> c -> a l=20+34+12+42=98 a -> c -> b -> d -> a l=42+30+34+35=141 a -> c -> d -> b -> a l=42+12+34+20=108 a -> d -> b -> c -> a l=35+34+30+42=141 a -> d -> c -> b -> a l=35+12+30+20=97 optimal So its optimal solution is : a -> b -> c -> d -> a 97 a -> d -> c -> b -> a 10. Find the optimal solution for the Traveling Salesman problem using exhaustive search method by considering ‘C’ as the starting city. Possible routes: C -> A -> B -> D -> C (total distance = 125) C -> A -> D -> B -> C (total distance = 145) C -> B -> A -> D -> C (total distance = 120) C -> B -> D -> A -> C (total distance = 145) C -> D -> A -> B -> C (total distance = 120) C -> D -> B -> A -> C (total distance = 125) So its optimal solution is : C -> B -> A -> D -> C (total distance = 120) C -> D -> A -> B -> C (total distance = 120) 11. Find the optimal solution for the Traveling Salesman problem using exhaustive search method by considering ‘City D’ as the starting city. Possible routes: D -> A -> B -> C -> D (total distance = 95) D -> A -> C -> B -> D (total distance = 95) D -> B -> A -> C -> D (total distance = 80) D -> B -> C -> A -> D (total distance = 95) D -> C -> A -> B -> D (total distance = 80) D -> C -> B -> A -> D (total distance = 95) So its optimal solution is : D -> B -> A -> C -> D (total distance = 80) D -> C -> A -> B -> D (total distance = 80) 12.Consider the Knapsack problem with the following inputs. Solve the problem using exhaustive search. Enumerate all possibilities and indicate unfeasible solutions and Optimal solution. Knapsack total capacity W=15kg Items A B C D Weight(kg) 3 5 4 6 Value 36 25 41 34 Ans: The optimal solution is the subset with the highest total value that does not exceed the knapsack capacity. In this case, the optimal solution is A + C + D, with a total weight of 13kg and a total value of 111. 13.Consider the Knapsack problem with the following inputs. Solve the problem using exhaustive search. Enumerate all possibilities and indicate unfeasible solutions and optimal solution. Knapsack total capacity W=20kg Items Item1 Item2 Item3 Item4 Weight(kg) 8 10 7 4 Value 40 45 65 30 From the above combinations, the combination with the highest total value that doesn't exceed the total capacity of the knapsack is {Item1, Item3, Item4} with a total weight of 19 kg and a total value of 135. Therefore, the optimal solution to this problem is to take items Item1, Item3, and Item4. 14. Consider the Job Assignment problem with the following inputs. Solve the problem using exhaustive search. Calculate Minimal total cost to complete to all jobs one job by each person. JOB1 JOB2 JOB3 JOB4 Person-1 9 2 7 8 Person-2 6 4 3 7 Person-3 5 8 1 8 Person-4 7 6 9 4 From the combinations given above, the combination with the lowest total cost is {Person-1: JOB2, Person-2: JOB1, Person-3: JOB3, Person-4: JOB4} with a total cost of 13. Therefore, the optimal solution to this problem is to assign JOB2 to Person-1, JOB1 to Person-2, JOB3 to Person-3, and JOB4 to Person-4. 15.Consider the Job Assignment problem with the following inputs. Solve the problem using exhaustive search. Calculate Minimal total cost to complete to all jobs one job by each person. JOB1 JOB2 JOB3 Person-1 9 2 7 Person-2 6 4 3 Person-3 5 8 1 From the above combinations, the combination with the lowest total cost is {Person-1: JOB2, Person-2: JOB1, Person-3: JOB3} with a total cost of 9. Therefore, the optimal solution to this problem is to assign JOB2 to Person-1, JOB1 to Person-2, and JOB3 to Person-3.