DAA - III UNIT PDF

Design and Analysis of Algorithm – III UNIT 2 marks: 1. Define decrease and conquer technique and list any two of its variations. Decrease and conquer is a problem-solving technique where a problem is solved by reducing it to a simpler or smaller instance of the same problem and then solving the sim...

Design and Analysis of Algorithm – III UNIT 2 marks: 1. Define decrease and conquer technique and list any two of its variations. Decrease and conquer is a problem-solving technique where a problem is solved by reducing it to a simpler or smaller instance of the same problem and then solving the simpler instance. Variations: Decrease by a constant : In each step, the problem size is reduced by a fixed amount. Decrease by a constant factor : In each step, the problem size is reduced by a fixed fraction. 2. What is a decrease by a constant technique and give an example. In the decrease-by-a-constant variation, the size of an instance is reduced by the same constant on each iteration of the algorithm. Typically, this constant is equal to one. Insertion sort is a classic example of a decrease-by-constant algorithm. For each subsequent element, create a subproblem consisting of the sorted portion of the array (to its left) and the element to be inserted. 3. What is a decrease by a constant factor technique and give an example. The decrease-by-a-constant-factor technique suggests reducing a problem's instance by the same constant factor on each iteration of the algorithm. In most applications, this constant factor is equal to two. Eg : Binary Search - In each step, the algorithm divides the search space in half, reducing the problem size by a factor of 2. 4. What is a variable size decrease technique and give an example. In variable size decrease technique, the size of the problem is reduced by a variable amount in each step. Example: Quick Sort - The pivot element is chosen dynamically, and the array is partitioned into sub-arrays of varying sizes based on the pivot. 5. Write the time complexity for worst, best and average case of Insertion sort. Cworst(n) = O(n2) (when the array is in reverse order) Cbest(n) = O(n) (when the array is already sorted) Cavg(n) = O(n2) (quadratic) 6. Give any four comparisons among Depth First Search and Breadth First Search. Depth First Search Breadth First Search Data structure stack Queue No. of vertex orderings 2 orderings 1 ordering Edge types tree and back edges tree and cross edges Applications connectivity, acyclicity, connectivity, acyclicity, articulation points minimum-edge paths 7. Define digraph and dag. A directed graph (digraph) is a graph in which edges have a direction, i.e., they are ordered pairs of vertices (u, v) indicating a directed edge from vertex u to vertex v. A directed acyclic graph (DAG) is a special type of directed graph that does not contain any cycles. In other words, there is no sequence of vertices such that the first vertex is also the last. 8. Write an algorithm to find height of Binary tree. 9. Write the recurrence relation for Binary tree. 10. Define Topological sorting. Give an example. Topological sorting is a way of arranging the vertices (nodes) of a directed acyclic graph (DAG) in a linear order such that for every directed edge (u, v) from vertex u to vertex v, u comes before v in the ordering. In simpler terms, it's a way of sequencing tasks or events where some tasks depend on others being completed first. Here is an example of a topological sort: A -> B B -> C C -> D A -> D In this example, task A must be completed before task B can be completed, task B must be completed before task C can be completed, and task C must be completed before task D can be completed. A topological sort of this set of tasks is A, B, C, D. 11. Define following. a. Tree Edge : A tree edge is an edge that connects two nodes in a tree. Tree edges are directed from a parent node to a child node. b. Cross Edge : A cross edge is an edge that connects two nodes in a tree that are not parent-child relationships. Cross edges are not directed. c. Back Edge : A back edge is an edge that connects a node to one of its ancestors in a tree. Back edges are directed. 12. List the Two algorithms for solving topological sorting problem. DFS Decrease (by one )-and-conquer technique 13. Define decrease-by-one technique in topological sorting. The decrease-by-one technique is a way to improve the time complexity of topological sorting. This technique is based on the observation that each time a node is topologically sorted, its in-degree decreases by one. By keeping track of the in-degree of each node, we can avoid revisiting nodes that have already been topologically sorted. 14. Define divide and conquer technique and list its steps. Divide and conquer is a powerful algorithmic technique that involves breaking down a problem into smaller, more manageable subproblems, solving them recursively, and then combining their solutions to solve the original problem. Steps: (i) Divide: Break the problem into smaller subproblems. (ii) Conquer: Solve the subproblems recursively. (iii) Combine: Combine the solutions of subproblems to solve the original problem. 15. Give the structure of Recurrence equation for Divide and Conquer. The recurrence equation for divide and conquer is: T(n) = aT(n/b) + c where: T(n) is the time complexity of solving the problem of size n a is the number of subproblems into which the problem is divided b is the size of each subproblem c is the time taken to combine the solutions to the subproblem 16. Write the time complexity for Merge and Quick sort. The time complexity for Mege Sort is O(n logn) The time complexity for Quick Sort is Worst case: O(n^2) Average case: O(n log n) Best case : O(n log n) 17. Write the time complexity for Strassen’s Matrix Multiplication and Multiplication of Larger integer. The time complexity for Strassen’s Matrix Multiplication : O(nlog27) The time complexity for Multiplication of Larger integer : O(nlog23) 18. State Master theorem of Divide and conquer. 19. Write the time complexity for worst, best and average case of Binary Search. Cworst(n) = O(log n) (Target element found in the last comparison, or not found at all) Cbest(n) = O(1) (Target element found in the middle of the first comparison) Cavg(n) = O(log n) (Target element found after a typical number of comparisons) 20. Write the steps followed in divide and Conquer approach. The steps followed in the divide and conquer approach are: (i) Divide the problem into smaller subproblems. (ii) Solve the subproblems recursively. (iii) Combine the solutions to the subproblems to solve the original problem. Long Answer Questions 1. Write an algorithm to sort N numbers using Insertion sort. Derive the time complexity for worst case and best case. Time Complexity: The basic operation of the algorithm is the key comparison A[j] > v. The number of key comparisons depends on the nature of the input. The worst case occurs when the array is in reverse order, each element requires a maximum number of comparisons and shifts. The best case is when the array is already sorted, only one comparison is made per element. The average case is when the there is half array comparison in decreasing array. 2. Define decrease and conquer technique and explain its variations. Refer 2 marks Q.No. 1,2,3,4 3. Write and explain Depth-First Search Algorithm with example. DFS is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the tree root (or some arbitrary node of a graph, sometimes called a 'search key'), and explores as far as possible along each branch before backtracking. Example: Refer Q.No. 5 b 4. Write and explain Breadth-First Search Algorithm with example. BFS is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes called a 'search key'), and explores the neighbor nodes first, before moving to the next level neighbors. Example : Refer Q.No. 5 a 5. Consider the following graph and perform following traversal and also draw the TREE. a. BFS b. DFS a. BFS ‘ BFS Forest: b. DFS DFS Forest: 6. Consider the following graph and perform following traversal also draw the TREE. a. BFS b. DFS Ans: a. BFS b. DFS 7. Give any five comparisons among Depth First Search and Breadth First Search. o Data Structure: BFS uses a queue to keep track of the next vertex to visit, whereas DFS uses a stack or can be implemented with recursion. o Traversal Order: BFS visits all the vertices of a level before going to the next level, while DFS visits a vertex and then iteratively explores its adjacent vertices before backtracking. o Memory Space: DFS uses less memory than BFS because it’s not necessary to store all the child pointers at each level. o Cycle Detection: DFS is more suitable for cycle detection in a graph because it explores vertices as far as possible before backtracking, while BFS is not suitable for cycle detection. o Path Finding: BFS is better for path finding problems where the shortest path is required, as it explores vertices in order of their distance from the source, DFS is not suitable for such problems. 8. Write a note on topological sorting with an example. Topological sorting is a way of arranging the vertices (nodes) of a directed acyclic graph (DAG) in a linear order such that for every directed edge (u, v) from vertex u to vertex v, u comes before v in the ordering. In simpler terms, it's a way of sequencing tasks or events where some tasks depend on others being completed first. Example : Refer Q.No. 9 9. Explain DFS-based algorithm to solve the topological sorting problem and also write topological order for below graph. The popping order : C5, C4, C3, C1, C2 The topologically sorted list : 10. Apply the DFS-based algorithm to solve the topological sorting problem for the following digraphs. 11. Apply the source-removal (Decrease by one) algorithm to solve the topological sorting problem for the following digraphs. (a) 12. Explain source-removal (Decrease by one) algorithm to solve the topological sorting problem and also write topological order for below graph. 13. Explain divide and conquer technique of solving problem with diagram. The divide and conquer technique is a problem-solving strategy that involves recursively breaking down a problem into smaller subproblems until they can be solved directly, and then combining the solutions to the subproblems to solve the original problem. This technique is often used to solve problems that are too difficult or time-consuming to solve directly. Steps: (i) Divide: Break the problem into smaller subproblems. (ii) Conquer: Solve the subproblems recursively. (iii) Combine: Combine the solutions of subproblems to solve the original problem. Examples : Merge Sort, Quick Sort, Binary Search 14. Solve the recursion relation using Master theorems. T(n) = 2T(n/2) + n T(1) = 2 15. Solve the recursion relation using Master theorems. A(n) = 2A(n/2) + 1 16. Write an algorithm to sort N numbers using Merge sort. Derive the time complexity. Time Complexity: 17. Write an algorithm to sort N numbers using Quick sort. Derive the time complexity. Best Case: If all the splits happen in the middle of corresponding subarrays. The number of key comparisons in the best case will satisfy-the recurrence According to the Master Theorem, Worst Case : If one of the two subarrays is empty or the size of the other will be less than the size of the subarray being partitioned or the given array is a strictly increasing array. Average Case : Let Cavg(n) be the average number of key comparisons made by quicksort on a randomly ordered array of size n. Assuming that the partition split can happen in each positions (0