Anna University DESIGN AND ANALYSIS OF ALGORITHMS Two Marks unit 4
1. What is transform and conquer technique?
The group of design techniques that are based on the idea of transformation is called transform and conquer technique because the methods work as two stage procedures. First in the transformation stage, the problem’s instance is modified to be more amenable (agreeable) to the solution. Then in the second or conquering stage, it is solved.
2. What are the three variations by which a given instance of a problem is transformed into?
The three major variations are
v Transformation to a simpler or more convenient instance of the same problem called instance simplification
v Transformation to a different representation of the same instance called representation change
v Transformation to an instance of a different problem for which the algorithm is already available called problem reduction.
3. What is presorting?
Presorting is the idea of sorting a list so that problems can be solved more easier than in an unsorted list. The time efficiency of the algorithm that involve sorting before solving the problem depends on the sorting algorithm being used.
4. Give the algorithm for element uniqueness using presorting?
ALGORITHM PresortElementUniqueness(A[0..n-1]0
//Solves the element uniqueness problem by sorting the array first
//Input An array A[0..n-1] of orderable elements
//Output Returns “true” if A has no equal elements, “false” otherwise
Sort the array A
0 to n-2 doßfor I
If A[I] = A[I+1] return false
return true
5. Compare the efficiency of solving the problem of element uniqueness using presorting and without sorting the elements of the array?
The brute force algorithm compares pairs of the array’s elements until either two equal elements were found or no more pairs were left. (n2).qIt’s worst case efficiency was in
The running time of the presorted algorithm depends on the time spent on sorting and the time spent on checking consecutive elements. The worst case efficiency of the entire presorting based algorithm will be as follows
(n log n)q(n) = q(n log n) + q ÎT(n) = Tsort(n)+Tscan(n)
6. Give the algorithm for computing the mode using presorting.
ALGORITHM PresortMode(A[0..n-1])
//Computes the mode of an array by sorting it first
//Input an array A[0..n-1] of orderable elements
//Output The array’s mode
Sort the array
0ßi
0ßmodefrequency
n-1 do£while i
A[I]ß 1; runvalue ßrunlength
n-1 and A[i + runlength] = runvalue£while i + runlength
runlength + 1ßrunlength
if runlength > modefrequency
runvalueß runlength; modevalue ßmodefrequency
i + runlengthßi
return modevalue
7. Compare the efficiencies of the algorithms used to compute the mode before and after sorting the array of elements.
The efficiency of computing the mode before sorting the array for the worst case is a list with no equal elements. For such a list the Ith element is compared with I-1 elements of the auxiliary list of distinct values seen so far before being added to the list with a frequency of 1. The worst case number of comparisons made by the (n2).qalgorithm in creating the frequency list is
The analysis of the presorted algorithm will be dominated by the time spent on sorting the list, since the remainder time to search the frequency list takes only linear time. So the efficiency class for the (n log n).qalgorithm is
8. Define AVL trees and who was it invented by?
An AVL tree is a binary search tree in which the balance factor of every node, which is defined as the difference between the heights of the node’s left and right subtrees, is either 0 or +1 or –1. the height of an empty subtree is defined as –1. AVL trees were invented in 1962 by two Russian scientists, G.M.Adelson-Velsky and E.M.Landis, after whom the data struture is named.
9. What are binary search trees and what is it mainly used for?
Binary search trees is one of the principal data structures for implementing dictionaries. It is a binary tree whose nodes contain elements of a set of orderable items, one element per node, so that all elements in the left subtree are smaller than the element in the subtree’s root and all elements in the right subtree are greater than it.
10. What is a rotation in AVL tree used for?
If an insertion of a new node makes an AVL tree unbalanced, the tree is transformed by a rotation. A rotation in an AVL tree is a local transformation of its subtree rooted at a node whose balance has become either +2 or –2; if there are several such nodes, then the tree rooted at the unbalanced node that is closest to the newly inserted leaf is rotated.
11. What are the types of rotation?
There are four types of rotations, in which two of them are the mirror images of the other two rotations. The four rotations are
v Single right rotation or R-rotation
v Single left rotation or L-rotation
v Double left-right rotation or LR-rotation
v Double right-left rotation or RL-rotation
12. Write about the efficiency of AVL trees?
As with any search tree , the critical characteristic is the tree’s height. The tree’s height is bounded above and below by logarithmic functions. The height ‘h’ of any AVL tree with ‘n’ nodes satisfies the inequalities
h£log2 n < 1.4405 log2(n+2) – 1.3277
The inequalities imply that the operations of searching and (log n) in the worst case. The operation of key deletionqinsertion are in an AVL tree is more difficult than insertion, but it turns out to have the same efficiency class as insertion i.e., logarithmic.
13. What are the drawbacks of AVL trees?
The drawbacks of AVL trees are
v Frequent rotations
v The need to maintain balances for the tree’s nodes
v Overall complexity, especially of the deletion operation.
14. What are 2-3 trees and who invented them?
A 2-3 tree is a tree that can have nodes of two kinds:2-nodes and 3-nodes. A 2-node contains a single key K and has two children, the left child serves as the root of a subtree whose keys are less than K and the right child serves as the root of a subtree with keys greater than K.
A 3-node contains two ordered keys K1 & K2 (K1<K2). The leftmost child serves as the root of a subtree with keys less than K1, the middle child serves as the root of a subtree with keys between K1 & K2 and the rightmost child serves as the root of a subtree with keys greater than K2. The last requirement of 2-3 trees is that all its leaves must be on the same level, a 2-3 tree is always height balanced. 2-3 trees were introduced by John Hopcroft in 1970.
15. What is a heap?
A heap is a partially ordered data structure, and can be defined as a binary tree assigned to its nodes, one key per node, provided the following two conditions are met
The tree’s shape requirement-The binary tree is essentiallyv complete, that is all the leaves are full except possibly the last level, where only some rightmost leaves will be missing.
v The parental dominance requirement-The key at each node is greater that or equal to the keys of its children
16. What is the main use of heap?
Heaps are especially suitable for implementing priority queues. Priority queue is a set of items with orderable characteristic called an item’s priority, with the following operations
v Finding an item with the highest priority
v Deleting an item with highest priority
v Adding a new item to the set
17. Give three properties of heaps?
The properties of heap are
v There exists exactly one essentially complete binary tree with ‘n’ nodes. Its height is equal to log2n
v The root of the heap is always the largest element
v A node of a heap considered with all its descendants is also a heap
18. Give the main property of a heap that is implemented as an array.
A heap can be implemented as an array by recording its elements in the top-down, left-to-right fashion. It is convenient to store the heap’s elements in positions 1 through n of such an array. In such a representation
v The parental node keys will be in the first n/2 positions of the array, while the leaf keys will occupy the last n/2 positions
The children of a key in the array’s parental position ‘i’ (1 iv n/2) will be in positions 2i and 2i+1and correspondingly, the parent of the key in position ‘i’ (2 i n) will be in position i/2.
19. What are the two alternatives that are used to construct a heap?
The two alternatives to construct a heap are
v Bottom-up heap construction
v Top-down heap construction
20. Give the pseudocode for Bottom-up heap construction.
ALGORITHM HeapBottomUp(H[1..n])
//Constructs a heap from the elements of the given array
//Input An array H[1..n] of orderable elements
//Output A heap H[1..n]
n/2 downto 1 doßfor I
H[k]ß I ; v ßk
falseßheap
while not heap and 2*k n do
2*kßj
if j < n
if H[j] < j+1ßH[j+1] j
if v H[j]
trueßheap
jß H[j]; k ßelse H[k]
vßH[k]
21. What is the algorithm to delete the root’s key from the heap?
ALGORITHM
v Exchange the root’s key with the last key K of the heap
v Decrease the heap’s size by one
“Heapify” the smaller tree by sifting K down the tree exactly inv the same way as bottom-up heap construction. Verify the parental dominance for K: if it holds stop the process, if not swap K with the larger of its children and repeat this operation until the parental dominance holds for K in its new position.
22. Who discovered heapsort and how does it work?
Heapsort was discovered by J.W.J. Williams. This is a two stage process that works as follows
v Stage 1 Heap construction: construct a heap for a given array.
v Stage 2 Maximum deletions: Apply the root deletion operation n-1 times to the remaining heap
23. What is dynamic programming and who discovered it?
Dynamic programming is a technique for solving problems with overlapping subproblems. These subproblems arise from a recurrence relating a solution to a given problem with solutions to its smaller subproblems only once and recording the results in a table from which the solution to the original problem is obtained. It was invented by a prominent U.S Mathematician, Richard Bellman in the 1950s.
24. Define transitive closure.
The transitive closure of a directed graph with ‘n’ vertices is defined as the n-by-n Boolean matrix T={tij}, in which the elements in the ith row (1 i n) and the jth column (1 j n) is 1 if there exists a non trivial directed path from the ith vertex to the jth vertex otherwise, tij is 0
25. What is the formula used by Warshall’s algorithm?
The formula for generating the elements of matrix R(k) from the matrix R(k-1) is
rij(k) = rij(k-1) or rik(k-1) and rkj(k-1)
This formula implies the following rule for generating elements of matrix R(k) from the elements of matrix R(k-1)
v If an element r¬ij is 1 in R(k-1), it remains 1 in R(k)
If an element rij is 0 in R(k-1), it has to be changed to 1 inv R(k) if and only if the element in its row ‘i’ and column ‘k’ and the element in its row ‘k’ and column ‘j’ are both 1’s in R(k-1)
26. Give the Warshall’s algorithm.
ALGORITHM Warshall(A[1..n,1..n])
//Implements Warshall’s algorithm for computing the transitive closure
//Input The adjacency matrix A of a digraph with ‘n’ vertices
//Output The transitive closure of the digraph
AßR(0)
1 to n doßfor k
1 to n doßfor i
1 to n doßfor j
R(k-1)[I,j] or R(k-1)[I,k] and R(k-1)[k,j]ßR(k)[I,j]
return R(n)
27. Give the Floyd’s algorithm
ALGORITHM Floyd(W[1..n,1..n])
//Implements Floyd’s algorithm for the all-pair shortest–path problem
//Input The weight matrix W of a graph
//Output The distance matrix of the shortest paths’ lengths
WßD
1 to n doßfor k
1 to n doßfor i
1 to n doßfor j
min{D[I,j], D[I,k] + D[k,j]}ßD[I,j]
return D
28. How many binary search trees can be formed with ‘n’ keys?
The total number of binary search trees with ‘n’ keys is equal to the nth Catalan number
c(n) = for n >0, c(0) = 1,
which grows to infinity as fast as 4n/n1.5.
29. Give the algorithm used to find the optimal binary search tree.
ALGORITHM OptimalBST(P[1..n])
//Finds an optimal binary search tree by dynamic programming
//Input An array P[1..n] of search probabilities for a sorted list of ‘n’ keys
//Output Average number of comparisons in successful searches in the optimal //BST and table R of subtrees’ roots in the optimal BST
1 to n doßfor I
0ßC[I,I-1]
P[I]ßC[I,I]
IßR[I,I]
0ßC[n+1,n]
1 to n-1 doßfor d
1 to n-d doßfor i
i +dßj
ßminval
I to j doßfor k
if C[I,k-1]+C[k+1,j] < minval
kß C[I,k-1]+C[k+1,j]; kmin ßminval
kßR[I,j]
sum + P[s]ß I+1 to j do sum ßP[I]; for s ßSum
minval+sumßC[I,j]
Return C[1,n], R
30. What is greedy technique?
Greedy technique suggests a greedy grab of the best alternative available in the hope that a sequence of locally optimal choices will yield a globally optimal solution to the entire problem. The choice must be made as follows
v Feasible : It has to satisfy the problem’s constraints
v Locally optimal : It has to be the best local choice among all feasible choices available on that step.
v Irrevocable : Once made, it cannot be changed on a subsequent step of the algorithm
31. Mention the algorithm for Prim’s algorithm.
ALGORITHM Prim(G)
//Prim’s algorithm for constructing a minimum spanning tree
//Input A weighted connected graph G=
//Output ET, the set of edges composing a minimum spanning tree of G
VT ß {v0}
ET ß
for i ß 1 to |V|-1 do
Find the minimum-weight edge e*=(v*,u*) among all the edges (v,u) such that v is in VT and u is in V-VT
VT ß VT {u*}
ET ß ET {e*}
return ET
32. What are the labels in Prim’s algorithm used for?
Prim’s algorithm makes it necessary to provide each vertex not in the current tree with the information about the shortest edge connecting the vertex to a tree vertex. The information is provided by attaching two labels to a vertex
v The name of the nearest tree vertex
v The length of the corresponding edge
33. How are the vertices not in the tree split into?
The vertices that are not in the tree are split into two sets
v Fringe : It contains the vertices that are not in the tree but are adjacent to atleast one tree vertex.
v Unseen : All other vertices of the graph are called unseen because they are yet to be affected by the algorithm.
34. What are the operations to be done after identifying a vertex u* to be added to the tree?
After identifying a vertex u* to be added to the tree, the following two operations need to be performed
v Move u* from the set V-VT to the set of tree vertices VT.
For each remaining vertex u in V-VT that is connected to u* by av shorter edge than the u’s current distance label, update its labels by u* and the weight of the edge between u* and u, respectively.
35. What is a min-heap?
A min-heap is a mirror image of the heap structure. It is a complete binary tree in which every element is less than or equal to its children. So the root of the min-heap contains the smallest element.
36. What is the use of Kruskal’s algorithm and who discovered it?
Kruskal’s algorithm is one of the greedy techniques to solve the minimum spanning tree problem. It was discovered by Joseph Kruskal when he was a second-year graduate student.
37. Give the Kruskal’s algorithm.
ALGORITHM Kruskal(G)
//Kruskal’s algorithm for constructing a minimum spanning tree
//Input A weighted connected graph G=
//Output ET, the set of edges composing a minimum spanning tree of G
sort E in non decreasing order of the edge weights w(ei1) ……… w(ei|E|)
ET ß
Ecounter ß 0
k ß 0
while ecounter < |V|-1
k ß k+1
if ET {eik} is acyclic
ET ß ET {eik}; ecounter ß ecounter + 1
return ET
38. What is a subset’s representative?
One element from each of the disjoint subsets in a collection is used as the subset’s representative. Some implementations do not impose any specific constraints on such a representative, others do so by requiring the smallest element of each subset to be used as the subset’s representative.
39. What is the use of Dijksra’s algorithm?
Dijkstra’s algorithm is used to solve the single-source shortest-paths problem: for a given vertex called the source in a weighted connected graph, find the shortest path to all its other vertices. The single-source shortest-paths problem asks for a family of paths, each leading from the source to a different vertex in the graph, though some paths may have edges in common.
40. What is encoding and mention its types?
Encoding is the process in which a text of ‘n’ characters from some alphabet is assigned with some sequence of bits called codewords. There are two types of encoding they are
v Fixed-length encoding
v Variable-length encoding
41. What is the problem faced by variable-length encoding and how can it be avoided?
Variable-length encoding which assigns codewords of different lengths to different characters introduces a problem of identifying how many bits of an encoded text represent the first character or generally the ith character. To avoid this prefix-free codes or prefix codes are used. In prefix codes, no codeword is a prefix of a codeword of another character.
42. Mention the Huffman’s algorithm.
ALGOITHM Huffman
Initialize n one-node trees and label them with the characters ofv the alphabet. Record the frequency of each character in its tree’s root to indicate the tree’s weight.
Repeat the following operation until a single tree is obtained.v 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.
A tree constructed by the above algorithm is called Huffman tree and it defines the Huffman code
Explain
Explain
Explain
Explain
Explain
1. What is transform and conquer technique?
The group of design techniques that are based on the idea of transformation is called transform and conquer technique because the methods work as two stage procedures. First in the transformation stage, the problem’s instance is modified to be more amenable (agreeable) to the solution. Then in the second or conquering stage, it is solved.
2. What are the three variations by which a given instance of a problem is transformed into?
The three major variations are
v Transformation to a simpler or more convenient instance of the same problem called instance simplification
v Transformation to a different representation of the same instance called representation change
v Transformation to an instance of a different problem for which the algorithm is already available called problem reduction.
3. What is presorting?
Presorting is the idea of sorting a list so that problems can be solved more easier than in an unsorted list. The time efficiency of the algorithm that involve sorting before solving the problem depends on the sorting algorithm being used.
4. Give the algorithm for element uniqueness using presorting?
ALGORITHM PresortElementUniqueness(A[0..n-1]0
//Solves the element uniqueness problem by sorting the array first
//Input An array A[0..n-1] of orderable elements
//Output Returns “true” if A has no equal elements, “false” otherwise
Sort the array A
0 to n-2 doßfor I
If A[I] = A[I+1] return false
return true
5. Compare the efficiency of solving the problem of element uniqueness using presorting and without sorting the elements of the array?
The brute force algorithm compares pairs of the array’s elements until either two equal elements were found or no more pairs were left. (n2).qIt’s worst case efficiency was in
The running time of the presorted algorithm depends on the time spent on sorting and the time spent on checking consecutive elements. The worst case efficiency of the entire presorting based algorithm will be as follows
(n log n)q(n) = q(n log n) + q ÎT(n) = Tsort(n)+Tscan(n)
6. Give the algorithm for computing the mode using presorting.
ALGORITHM PresortMode(A[0..n-1])
//Computes the mode of an array by sorting it first
//Input an array A[0..n-1] of orderable elements
//Output The array’s mode
Sort the array
0ßi
0ßmodefrequency
n-1 do£while i
A[I]ß 1; runvalue ßrunlength
n-1 and A[i + runlength] = runvalue£while i + runlength
runlength + 1ßrunlength
if runlength > modefrequency
runvalueß runlength; modevalue ßmodefrequency
i + runlengthßi
return modevalue
7. Compare the efficiencies of the algorithms used to compute the mode before and after sorting the array of elements.
The efficiency of computing the mode before sorting the array for the worst case is a list with no equal elements. For such a list the Ith element is compared with I-1 elements of the auxiliary list of distinct values seen so far before being added to the list with a frequency of 1. The worst case number of comparisons made by the (n2).qalgorithm in creating the frequency list is
The analysis of the presorted algorithm will be dominated by the time spent on sorting the list, since the remainder time to search the frequency list takes only linear time. So the efficiency class for the (n log n).qalgorithm is
8. Define AVL trees and who was it invented by?
An AVL tree is a binary search tree in which the balance factor of every node, which is defined as the difference between the heights of the node’s left and right subtrees, is either 0 or +1 or –1. the height of an empty subtree is defined as –1. AVL trees were invented in 1962 by two Russian scientists, G.M.Adelson-Velsky and E.M.Landis, after whom the data struture is named.
9. What are binary search trees and what is it mainly used for?
Binary search trees is one of the principal data structures for implementing dictionaries. It is a binary tree whose nodes contain elements of a set of orderable items, one element per node, so that all elements in the left subtree are smaller than the element in the subtree’s root and all elements in the right subtree are greater than it.
10. What is a rotation in AVL tree used for?
If an insertion of a new node makes an AVL tree unbalanced, the tree is transformed by a rotation. A rotation in an AVL tree is a local transformation of its subtree rooted at a node whose balance has become either +2 or –2; if there are several such nodes, then the tree rooted at the unbalanced node that is closest to the newly inserted leaf is rotated.
11. What are the types of rotation?
There are four types of rotations, in which two of them are the mirror images of the other two rotations. The four rotations are
v Single right rotation or R-rotation
v Single left rotation or L-rotation
v Double left-right rotation or LR-rotation
v Double right-left rotation or RL-rotation
12. Write about the efficiency of AVL trees?
As with any search tree , the critical characteristic is the tree’s height. The tree’s height is bounded above and below by logarithmic functions. The height ‘h’ of any AVL tree with ‘n’ nodes satisfies the inequalities
h£log2 n < 1.4405 log2(n+2) – 1.3277
The inequalities imply that the operations of searching and (log n) in the worst case. The operation of key deletionqinsertion are in an AVL tree is more difficult than insertion, but it turns out to have the same efficiency class as insertion i.e., logarithmic.
13. What are the drawbacks of AVL trees?
The drawbacks of AVL trees are
v Frequent rotations
v The need to maintain balances for the tree’s nodes
v Overall complexity, especially of the deletion operation.
14. What are 2-3 trees and who invented them?
A 2-3 tree is a tree that can have nodes of two kinds:2-nodes and 3-nodes. A 2-node contains a single key K and has two children, the left child serves as the root of a subtree whose keys are less than K and the right child serves as the root of a subtree with keys greater than K.
A 3-node contains two ordered keys K1 & K2 (K1<K2). The leftmost child serves as the root of a subtree with keys less than K1, the middle child serves as the root of a subtree with keys between K1 & K2 and the rightmost child serves as the root of a subtree with keys greater than K2. The last requirement of 2-3 trees is that all its leaves must be on the same level, a 2-3 tree is always height balanced. 2-3 trees were introduced by John Hopcroft in 1970.
15. What is a heap?
A heap is a partially ordered data structure, and can be defined as a binary tree assigned to its nodes, one key per node, provided the following two conditions are met
The tree’s shape requirement-The binary tree is essentiallyv complete, that is all the leaves are full except possibly the last level, where only some rightmost leaves will be missing.
v The parental dominance requirement-The key at each node is greater that or equal to the keys of its children
16. What is the main use of heap?
Heaps are especially suitable for implementing priority queues. Priority queue is a set of items with orderable characteristic called an item’s priority, with the following operations
v Finding an item with the highest priority
v Deleting an item with highest priority
v Adding a new item to the set
17. Give three properties of heaps?
The properties of heap are
v There exists exactly one essentially complete binary tree with ‘n’ nodes. Its height is equal to log2n
v The root of the heap is always the largest element
v A node of a heap considered with all its descendants is also a heap
18. Give the main property of a heap that is implemented as an array.
A heap can be implemented as an array by recording its elements in the top-down, left-to-right fashion. It is convenient to store the heap’s elements in positions 1 through n of such an array. In such a representation
v The parental node keys will be in the first n/2 positions of the array, while the leaf keys will occupy the last n/2 positions
The children of a key in the array’s parental position ‘i’ (1 iv n/2) will be in positions 2i and 2i+1and correspondingly, the parent of the key in position ‘i’ (2 i n) will be in position i/2.
19. What are the two alternatives that are used to construct a heap?
The two alternatives to construct a heap are
v Bottom-up heap construction
v Top-down heap construction
20. Give the pseudocode for Bottom-up heap construction.
ALGORITHM HeapBottomUp(H[1..n])
//Constructs a heap from the elements of the given array
//Input An array H[1..n] of orderable elements
//Output A heap H[1..n]
n/2 downto 1 doßfor I
H[k]ß I ; v ßk
falseßheap
while not heap and 2*k n do
2*kßj
if j < n
if H[j] < j+1ßH[j+1] j
if v H[j]
trueßheap
jß H[j]; k ßelse H[k]
vßH[k]
21. What is the algorithm to delete the root’s key from the heap?
ALGORITHM
v Exchange the root’s key with the last key K of the heap
v Decrease the heap’s size by one
“Heapify” the smaller tree by sifting K down the tree exactly inv the same way as bottom-up heap construction. Verify the parental dominance for K: if it holds stop the process, if not swap K with the larger of its children and repeat this operation until the parental dominance holds for K in its new position.
22. Who discovered heapsort and how does it work?
Heapsort was discovered by J.W.J. Williams. This is a two stage process that works as follows
v Stage 1 Heap construction: construct a heap for a given array.
v Stage 2 Maximum deletions: Apply the root deletion operation n-1 times to the remaining heap
23. What is dynamic programming and who discovered it?
Dynamic programming is a technique for solving problems with overlapping subproblems. These subproblems arise from a recurrence relating a solution to a given problem with solutions to its smaller subproblems only once and recording the results in a table from which the solution to the original problem is obtained. It was invented by a prominent U.S Mathematician, Richard Bellman in the 1950s.
24. Define transitive closure.
The transitive closure of a directed graph with ‘n’ vertices is defined as the n-by-n Boolean matrix T={tij}, in which the elements in the ith row (1 i n) and the jth column (1 j n) is 1 if there exists a non trivial directed path from the ith vertex to the jth vertex otherwise, tij is 0
25. What is the formula used by Warshall’s algorithm?
The formula for generating the elements of matrix R(k) from the matrix R(k-1) is
rij(k) = rij(k-1) or rik(k-1) and rkj(k-1)
This formula implies the following rule for generating elements of matrix R(k) from the elements of matrix R(k-1)
v If an element r¬ij is 1 in R(k-1), it remains 1 in R(k)
If an element rij is 0 in R(k-1), it has to be changed to 1 inv R(k) if and only if the element in its row ‘i’ and column ‘k’ and the element in its row ‘k’ and column ‘j’ are both 1’s in R(k-1)
26. Give the Warshall’s algorithm.
ALGORITHM Warshall(A[1..n,1..n])
//Implements Warshall’s algorithm for computing the transitive closure
//Input The adjacency matrix A of a digraph with ‘n’ vertices
//Output The transitive closure of the digraph
AßR(0)
1 to n doßfor k
1 to n doßfor i
1 to n doßfor j
R(k-1)[I,j] or R(k-1)[I,k] and R(k-1)[k,j]ßR(k)[I,j]
return R(n)
27. Give the Floyd’s algorithm
ALGORITHM Floyd(W[1..n,1..n])
//Implements Floyd’s algorithm for the all-pair shortest–path problem
//Input The weight matrix W of a graph
//Output The distance matrix of the shortest paths’ lengths
WßD
1 to n doßfor k
1 to n doßfor i
1 to n doßfor j
min{D[I,j], D[I,k] + D[k,j]}ßD[I,j]
return D
28. How many binary search trees can be formed with ‘n’ keys?
The total number of binary search trees with ‘n’ keys is equal to the nth Catalan number
c(n) = for n >0, c(0) = 1,
which grows to infinity as fast as 4n/n1.5.
29. Give the algorithm used to find the optimal binary search tree.
ALGORITHM OptimalBST(P[1..n])
//Finds an optimal binary search tree by dynamic programming
//Input An array P[1..n] of search probabilities for a sorted list of ‘n’ keys
//Output Average number of comparisons in successful searches in the optimal //BST and table R of subtrees’ roots in the optimal BST
1 to n doßfor I
0ßC[I,I-1]
P[I]ßC[I,I]
IßR[I,I]
0ßC[n+1,n]
1 to n-1 doßfor d
1 to n-d doßfor i
i +dßj
ßminval
I to j doßfor k
if C[I,k-1]+C[k+1,j] < minval
kß C[I,k-1]+C[k+1,j]; kmin ßminval
kßR[I,j]
sum + P[s]ß I+1 to j do sum ßP[I]; for s ßSum
minval+sumßC[I,j]
Return C[1,n], R
30. What is greedy technique?
Greedy technique suggests a greedy grab of the best alternative available in the hope that a sequence of locally optimal choices will yield a globally optimal solution to the entire problem. The choice must be made as follows
v Feasible : It has to satisfy the problem’s constraints
v Locally optimal : It has to be the best local choice among all feasible choices available on that step.
v Irrevocable : Once made, it cannot be changed on a subsequent step of the algorithm
31. Mention the algorithm for Prim’s algorithm.
ALGORITHM Prim(G)
//Prim’s algorithm for constructing a minimum spanning tree
//Input A weighted connected graph G=
//Output ET, the set of edges composing a minimum spanning tree of G
VT ß {v0}
ET ß
for i ß 1 to |V|-1 do
Find the minimum-weight edge e*=(v*,u*) among all the edges (v,u) such that v is in VT and u is in V-VT
VT ß VT {u*}
ET ß ET {e*}
return ET
32. What are the labels in Prim’s algorithm used for?
Prim’s algorithm makes it necessary to provide each vertex not in the current tree with the information about the shortest edge connecting the vertex to a tree vertex. The information is provided by attaching two labels to a vertex
v The name of the nearest tree vertex
v The length of the corresponding edge
33. How are the vertices not in the tree split into?
The vertices that are not in the tree are split into two sets
v Fringe : It contains the vertices that are not in the tree but are adjacent to atleast one tree vertex.
v Unseen : All other vertices of the graph are called unseen because they are yet to be affected by the algorithm.
34. What are the operations to be done after identifying a vertex u* to be added to the tree?
After identifying a vertex u* to be added to the tree, the following two operations need to be performed
v Move u* from the set V-VT to the set of tree vertices VT.
For each remaining vertex u in V-VT that is connected to u* by av shorter edge than the u’s current distance label, update its labels by u* and the weight of the edge between u* and u, respectively.
35. What is a min-heap?
A min-heap is a mirror image of the heap structure. It is a complete binary tree in which every element is less than or equal to its children. So the root of the min-heap contains the smallest element.
36. What is the use of Kruskal’s algorithm and who discovered it?
Kruskal’s algorithm is one of the greedy techniques to solve the minimum spanning tree problem. It was discovered by Joseph Kruskal when he was a second-year graduate student.
37. Give the Kruskal’s algorithm.
ALGORITHM Kruskal(G)
//Kruskal’s algorithm for constructing a minimum spanning tree
//Input A weighted connected graph G=
//Output ET, the set of edges composing a minimum spanning tree of G
sort E in non decreasing order of the edge weights w(ei1) ……… w(ei|E|)
ET ß
Ecounter ß 0
k ß 0
while ecounter < |V|-1
k ß k+1
if ET {eik} is acyclic
ET ß ET {eik}; ecounter ß ecounter + 1
return ET
38. What is a subset’s representative?
One element from each of the disjoint subsets in a collection is used as the subset’s representative. Some implementations do not impose any specific constraints on such a representative, others do so by requiring the smallest element of each subset to be used as the subset’s representative.
39. What is the use of Dijksra’s algorithm?
Dijkstra’s algorithm is used to solve the single-source shortest-paths problem: for a given vertex called the source in a weighted connected graph, find the shortest path to all its other vertices. The single-source shortest-paths problem asks for a family of paths, each leading from the source to a different vertex in the graph, though some paths may have edges in common.
40. What is encoding and mention its types?
Encoding is the process in which a text of ‘n’ characters from some alphabet is assigned with some sequence of bits called codewords. There are two types of encoding they are
v Fixed-length encoding
v Variable-length encoding
41. What is the problem faced by variable-length encoding and how can it be avoided?
Variable-length encoding which assigns codewords of different lengths to different characters introduces a problem of identifying how many bits of an encoded text represent the first character or generally the ith character. To avoid this prefix-free codes or prefix codes are used. In prefix codes, no codeword is a prefix of a codeword of another character.
42. Mention the Huffman’s algorithm.
ALGOITHM Huffman
Initialize n one-node trees and label them with the characters ofv the alphabet. Record the frequency of each character in its tree’s root to indicate the tree’s weight.
Repeat the following operation until a single tree is obtained.v 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.
A tree constructed by the above algorithm is called Huffman tree and it defines the Huffman code
16 Marks
- 1. Explain about Transform-and-Conquer Approach
Explain
- Presorting
- Balanced Search Tree
- Heaps and Heap sort
- 2. Explain about Dynamic Programming
Explain
- Warshall’s And Floyd’s Algorithm
- Graph
- Algorithm
- 3. Explain Greedy techniques with algorithms
Explain
- Prim’s Algorithm
- Kruskal’s Algorithm
- Dijkstra’s Algorithm
- 4. Discuss in detail about Optimal Binary Trees
- 5. Explain briefly about Dijkstra’s Algorithm
Explain
- Minimum spanning tree
- Algorithm
- Graph
- 6. Discuss in detail about Huffman Trees
Explain
- Algorithm
- Diagram
0 comments:
Post a Comment