DAA - IV Unit PDF

Design & Analysis of Algorithms – IV UNIT 2 marks: 1.What is Greedy problem? List requirements of the solution at each step in greedy approach. The greedy approach suggests to construct a solution through a sequence of steps, each expanding a partially constructed solution obtained so far, until a c...

Design & Analysis of Algorithms – IV UNIT 2 marks: 1.What is Greedy problem? List requirements of the solution at each step in greedy approach. The greedy approach suggests to construct a solution through a sequence of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached. On each step the choice made must be: feasible locally optimal irrevocable 2. Differentiate between Prim’s and Kruskal’s Algorithm. Prim’s Algorithm Kruskal’s Algorithm It starts to build the Minimum Spanning Tree It starts to build the Minimum Spanning Tree from from any vertex in the graph. the vertex carrying minimum weight in the graph. It traverses one node more than one time to get It traverses one node only once. the minimum distance. It generates the minimum spanning tree starting It generates the minimum spanning tree starting from the root vertex. from the least weighted edge. Prim’s algorithm prefer list data structures. Kruskal’s algorithm prefer heap data structures. 3. What is the Prim’s algorithm? How it works? Prim's algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a weighted, undirected graph. Here's how Prim's algorithm works: (i) The initial subtree consists of a single vertex selected arbitrarily from the set V of the graph's vertices. (ii) On each iteration, select the next nearest vertex with the smallest weight and attach it to the subtree in a greedy manner. (iii) Continue Step 2 until all vertices have been included in the tree but should not form a cycle. 4. What is the approach to solve a problem using Kruskal’s algorithm. Kruskal's algorithm looks at a minimum spanning tree for a weighted connected graph G = (V, E) as an acyclic subgraph with |V| - 1 edges for which the sum of the edge weights is the smallest. The algorithm begins by sorting the graph's edges in nondecreasing order of their weights. Then, starting with the empty subgraph, it scans this sorted list adding the next edge on the list to the current sub graph if such an inclusion does not create a cycle and simply skipping the edge otherwise. 5. What is the approach to solve a problem using Dijkstra’s algorithm. Dijkstra's algorithm is a greedy algorithm used to find the shortest path between two nodes in a weighted graph. Approach: 1. Initialize distances from the source to all vertices as infinity and distance to the source itself as 0. 2. Mark all vertices as unvisited. 3. While the destination vertex is not marked as visited: - Select the unvisited vertex with the smallest known distance. - For the selected vertex, update the distances to its neighbors. - Mark the selected vertex as visited. 6. Write the Complexity of Kruskal’s and Prism Algorithms. Complexity of Kruskal’s algorithm will be in O(|E| log |E|) Complexity of Prim’s algorithm is in (|V|-1 + |E|) O(log |V|) = O(|E| log |V|) |E| - number of edges |V| - number of vertices 7. Define spanning tree and minimum spanning tree. A spanning tree of a connected graph is its connected acyclic subgraph (i.e., a tree) that contains all the vertices of the graph. A minimum spanning tree of a weighted connected graph is its spanning tree of the smallest weight, where the weight of a tree is defined as the sum of the weights on all its edges. 8. What is dynamic Huffman encoding? Dynamic Huffman encoding (also known as adaptive Huffman coding) is a variant of Huffman coding in which the coding tree is updated each time a new character is read from the source text, rather than requiring a full symbol frequency table beforehand. This makes it ideal for compressing data streams where the symbol frequencies aren't known in advance or may change over time. 9. Differentiate fixed length encoding and variable length encoding in Huffman tree. Fixed Length : Each symbol is encoded using the same number of bits. In this each character is represented by a fixed length binary codes⁶. For example, if there are 6 characters, we need 3 bits to store each character uniquely. Variable Length : Different symbols may have different lengths of codes, allowing more frequent symbols to have shorter codes. The idea is to assign frequent characters short code words and infrequent characters long code words. 10. Define Huffman tree and Huffman code. Huffman Tree : A binary tree used for Huffman coding, where each leaf represents a symbol and the path to the leaf corresponds to its binary code. It’s is a full binary tree used for Huffman coding. Each leaf of the Huffman tree corresponds to a letter, and the weight of the leaf node is the weight (frequency) of its associated letter. Huffman Code : A variable-length code that assigns shorter codes to more frequent symbols and longer codes to less frequent symbols. It’s is a variable-length code assigned to input characters based on the frequencies of corresponding characters. 11. What is lower bound Arguments? Lower bound arguments are mathematical proofs that establish a minimum amount of time or space resources that any algorithm solving a particular problem must require, regardless of how clever or efficient it is. They serve as fundamental limitations on algorithmic performance, guiding algorithm design and helping to identify problems that are inherently hard or intractable. 12. What are P problems? Write example. P problem is the class of problem. Class P is a class of decision problems that can be solved in polynomial time by (deterministic) algorithms. It is the class of decision problems that are solvable in O(p(n)) time, where p(n) is a polynomial of problem’s input size. Example: Basic Math, String Operations, Shortest path algorithms etc. 13. What are NP problems? Write example. Class NP is the class of decision problems that can be solved by nondeterministic polynomial algorithms. It contains problems whose solutions can be verified in polynomial time, but not necessarily solved in polynomial time. P ⊆ NP Eg: Integer Factorisation, Graph Isomorphism, Scheduling Algorithm 14. What are NP Complete problems? Write example. NP-complete problems are a class of decision problems that are considered the most difficult within the NP class. A decision problem D is said to be NP-complete if (i) it belongs to class NP (ii) every problem in NP is polynomially reducible to D. Eg: Travelling salesman problem, Hamiltonian cycle problem 15. What are Decision Trees? Draw the Decision tree for Maximum of two numbers. Decision trees are a graphical representation of decision-making processes, where each node represents a decision or test, each branch represents an outcome of the test, and each leaf node represents a decision or a classification. Decision tree for Maximum of two numbers: yes no a>b a b Long Answer Questions: 1. Write and explain the Prim’s algorithm and find Minimum Spanning tree for the given graph. Prim's algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a weighted, undirected graph. Here's how Prim's algorithm works: (i) The initial subtree consists of a single vertex selected arbitrarily from the set V of the graph's vertices. (ii) On each iteration, select the next nearest vertex with the smallest weight and attach it to the subtree in a greedy manner. (iii) Continue Step 2 until all vertices have been included in the tree but should not form a cycle. 2. Apply Prim's algorithm to the following graph and find Minimum Spanning tree for the given graph. 1. We start with an arbitrary vertex, let’s say ‘a’. So, our tree now has one vertex ‘a’. 2. The edge with the smallest weight connected to ‘a’ is a-b with weight 2. So, we add ‘b’ to our tree. 3. Now, our tree has vertices ‘a’ and ‘b’. The edge with the smallest weight connected to ‘a’ or ‘b’ but not in the tree is b-c with weight 3. So, we add ‘c’ to our tree. 4. Our tree now has vertices ‘a’, ‘b’, and ‘c’. The edge with the smallest weight connected to ‘a’, ‘b’, or ‘c’ but not in the tree is c-d with weight 4. So, we add ‘d’ to our tree. 5. Our tree now has vertices ‘a’, ‘b’, ‘c’, and ‘d’. The edge with the smallest weight connected to ‘a’, ‘b’, ‘c’, or ‘d’ but not in the tree is d-e with weight 5. So, we add ‘e’ to our tree. 6. Now, all vertices are included in the tree. So, we stop here. So, the minimum spanning tree for the given graph is: Edge a-b with weight 2 Edge b-c with weight 3 Edge c-d with weight 4 Edge d-e with weight 5 3. Apply Prim's algorithm to the following graph and find Minimum Spanning tree for the given graph. Step 1: Choose vertex A as the starting vertex. Step 2:Add the edges AB (weight 2) and AC (weight 4) to the MST. Step 3: Mark vertex A as visited. Step 4: Find the edge with the smallest weight that connects a visited vertex to an unvisited vertex. In this case, the edge BC (weight 5) has the smallest weight. Add this edge to the MST. Step 5: Mark vertex B as visited. Step 6: Find the edge with the smallest weight that connects a visited vertex to an unvisited vertex. In this case, the edge AD (weight 6) has the smallest weight. Add this edge to the MST. Step 7: Mark vertex D as visited. Step 8: All the vertices have now been visited, so the MST is complete. The Minimum Spanning Tree for the given graph is shown below: A |\ B C | \ D ``` The total weight of the Minimum Spanning Tree is 11. 4. Apply Prim's algorithm to the following graph and find Minimum Spanning tree for the given graph. 1. 2. 3. 4. 5. 6. 7. 8. 9. 5. Apply Prim's algorithm to the following graph and find Minimum Spanning tree for the given graph. 6. Write Kruskal’s algorithms and Apply Kruskal's algorithm to find a minimum spanning tree of the following graphs. 7. Apply Kruskal's algorithm to find a minimum spanning tree of the following graphs. 8. Apply Kruskal's algorithm to find a minimum spanning tree of the following graphs. 9. Apply Kruskal's algorithm to find a minimum spanning tree of the following graph. 10. Write Dijkstra's Algorithm and solve the following instances of the single-source shortest- paths problem with vertex “a” as the source. The shortest paths and their lengths are as follows: 11. Using Dijkstra's Algorithm to solve the following instances of the single-source shortest- paths problem with vertex “a” as the source: 12. Write and explain the Huffman algorithm and construct Huffman coding tree. Consider the five character alphabet [A, B, C, D, _ ] with the following occurrence probabilities. Huffman's Algorithm: Step 1 Initialize n one-node trees and label them with the characters of the alphabet. Record the frequency of each character in its tree's root to indicate the tree's weight. Step 2 Repeat the following operation until a single tree is obtained. Find two trees with the smallest weight. Make them the left and right subtree of a new tree and record the sum of their weights in the root of the new tree as its weight. Huffman coding tree: The resulting codewords are as follows: With the occurrence probabilities given and the codeword lengths obtained, the expected number of bits per character in this code is 2. 0.35 + 3. 0.1 + 2. 0.2 + 2. 0.2 + 3. 0.15 = 2.25. 13.Construct a Huffman code for following data. 14. Construct a Huffman code for following data. 15.Write a note on following a. Trivial lower Bounds b. Information-Theoretic Arguments c. Adversary Arguments d. Problem Reduction a. Trivial lower Bounds : It is the easiest method to find the lower bound. The Lower bounds which can be easily observed based on the number of input taken and the number of output produced are called Trivial Lower Bound. Example: Multiplication of n x n matrix, where, Input: For 2 matrices, we will have 2n2 inputs Output: 1 matrix of order n x n, i.e., n2 outputs b. Information-Theoretic Arguments : the information-theoretical approach seeks to establish a lower bound based on the amount of information it has to produce. They rely on the fact that collecting information from many different processes takes a long time. They usually give bounds of the form Ω (log n), where n is the number of processes in the system. c. Adversary Arguments : A method of proving a lower bound by playing role of adversary that makes algorithm work the hardest by adjusting input. The adversary cannot lie, however. Eg: “Guessing” a number between 1 and n with yes/no questions. (e.g., are 4 questions enough to guess a number between 1 and 17) Adversary: Puts the number in a larger of the two subsets generated by last question. d. Problem Reduction : If problem P is at least as hard as problem Q, then a lower bound for Q is also a lower bound for is also a lower bound for P. Hence, find problem Q with a known lower bound that can be reduced to problem P in question. Eg : P: finding convex hull for n points in Cartesian plane Q: comparison-based sorting problem (known to be in Ω (nlogn)) Show that convex hull problem is Show that convex hull problem is in Ω (nlogn) 16. Explain Decision Tree and draw the Decision tree for minimum of three numbers. A decision tree is a full binary tree that shows the comparisons between elements that are executed by an appropriate sorting algorithm operating on an input of a given size. - Many important algorithms, especially those for sorting and searching, work by comparing items of their inputs. So, it is possible to study the performance of such algorithms with a device called decision tree. - The Control, data movement and all other conditions of the algorithm are ignored. - In a decision tree, there will be an array of length ‘n’. So, the total leaves will be n! (i.e, total number of comparisons). Decision tree for minimum of three numbers: 17. Draw the Decision tree for binary search in a four-element array. 18. Draw the Decision tree for the three-element selection sort. 19. Draw the Decision tree for the three-element insertion sort. 20. Explain P, NP, and NP-complete Problems. P problem : Problems that can be solved in polynomial time as the set, called as P. Definition : Class P is a class of decision problems that can be solved in polynomial time by (deterministic) algorithms. This class of problems is called polynomial. Example: Searching & sorting algorithms, Finding shortest paths etc. NP problem: A nondeterministic algorithm is said to be nondeterministic polynomial if the time efficiency of its verification stage is polynomial. Most decision problems are in NP. Definition : Class NP is the class of decision problems that can be solved by nondeterministic polynomial algorithms. It contains problems whose solutions can be verified in polynomial time, but not necessarily solved in polynomial time. P ⊆ NP Eg: Hamiltonian circuit problem, the knapsack, graph coloring etc. NP-complete problems : These are a class of decision problems that are considered the most difficult within the NP class. Definition : A decision problem D is said to be NP-complete if (i) it belongs to class NP (ii) every problem in NP is polynomially reducible to D. 21. Write a note on Challenges of Numerical Algorithm. Numerical algorithms are used to solve mathematical problems that cannot be solved analytically. While they are powerful tools, they face several challenges: (i) Approximation: Most numerical algorithms involve approximations, which can introduce errors. These errors can accumulate and affect the accuracy of the final solution. (ii) Stability: Some algorithms are unstable, meaning small changes in the input can lead to large changes in the output. This can make them difficult to use in practice. (iii) Computational complexity: Some algorithms require a lot of computation time or memory, especially for large problems. This can make them impractical for real-world applications. (v) Rounding errors: Computers can only store numbers with a limited precision, which can lead to rounding errors. These errors can also accumulate and affect the accuracy of the solution. (vi) Ill-conditioning: Some problems are ill-conditioned, meaning that small changes in the input can lead to large changes in the solution. This can make them difficult to solve accurately with numerical algorithms.