Anna University DESIGN AND ANALYSIS OF ALGORITHMS Two Marks unit 3
Brute force is a straightforward approach to solving a problem, usually directly based on the problem’s statement and definitions of the concepts involved. The brute force approach is one that is easiest to apply.
2. What are the advantages of brute force technique?
The various advantages of brute force technique are
v Brute force applicable to a very wide variety of problems. It is used for many elementary but important algorithmic tasks
For some important problems this approach yields reasonablev algorithms of at least some practical value with no limitation on instance size
The expense to design a more efficient algorithm may bev unjustifiable if only a few instances of problems need to be solved and a brute force algorithm can solve those instances with acceptable speed
v Even if inefficient in general it can still be used for solving small-size instances of a problem
v It can serve as a yardstick with which to judge more efficient alternatives for solving a problem
3. What is selection sort?
Selection sort is started by scanning the entire list to find the smallest element and exchange it with the first element, putting the first element in the final position in the sorted list. Then the scan starts from the second element to find the smallest among n-1 elements and exchange it with the second element.
A0 A1 ………… Ai-1 | Ai……..…,Amin,………,An-1
In their final position The last n-I elements
4. Mention the pseudocode for selection sort.
ALGORITHM SelectionSort(A[0..n-1])
//The algorithm sorts a given array by selection sort
//Input: An array A[0..n-1] of orderable elements
//Output: Array A[0..n-1] sorted in ascending order
0 to n-2 doßfor I
Ißmin
I+1 to n-1 doßfor j
if A[j] < jßA[min] min
swap A[I] and A[min]
5. What is bubble sort?
Another brute force approach to sort a problem is to compare adjacent elements of the list and exchange them if they are out of order, so we end up “bubbling up” the largest element to the last position in the list. The next pass bubbles up the second largest element, and so on until n-1 passes , the list is sorted. Pass I can be represented as follows
?
A0,……, Aj Aj+1,……, An-I-1 | An-I …… An-1
In their final positions
6. Give an algorithm for bubble sort?
ALGORITHM BubbleSort(A[0..n-1])
//The algorithm sorts array A[0..n-1] by bubble sort
//Input: An array A[0..n-1] of orderable elements
//Output: Arrar A[0..n-1] sorted in ascending order
0 to n-2 doßfor I
0 to n-2-I doßfor j
if A[j+1]<A[j] swap A[j] and A[j+1]
7. Give the benefit of application of brute force technique to solve a problem.
With the application of brute force strategy, the first version of an algorithm obtained can often be improved with a modest amount of effort. So a first application of the brute force approach often results in an algorithm that can be improved with a modest amount of effort.
8. Explain about the enhanced version of sequential search.
Sequential search simply compares successive elements of a list with a given search key until either a match is encountered or the list is exhausted without finding a match. The enhancement in this version is to append the search key to the end of the list , then the search for the key will have to be successful & so we can eliminate a check for the list’s end on each iteration.
9. Give the algorithm for the enhanced version of sequential search.
ALGORITHM SequentialSearch2(A[0..n-1],K)
//The algorithm implements sequential search with the search key as sentinael
//Input: An array A of n elements and a search key K
//Output: The position of the first element in a[0..n-1] whose value is equal to K or //–1 if no such element is found
KßA[n]
0ßI
K do¹while A[I]
I+1ßI
If I < n return I
else return -1
10. What is the improvement that can be applied to sequential search if the list is sorted?
The straightforward improvement that can be incorporated in sequential search if a given list is known to be sorted is that searching in the list can be stopped as soon as an element greater than or equal to the search key is encountered.
11. Define brute force string matching.
The brute force string matching has a given string of n characters called the text and a string of m characters called the pattern, find a substring of the text that matches the pattern. And find the index I of the leftmost character of the first matching substring in the text.
12. Mention the algorithm for brute force string matching
ALGORITHM BruteForceStringMatching(T[0..n-1],P[0..m-1])
//The algorithm implements brute force string matching
//Input: an array T[0..n-1] of n characters representing text
//An array P[0..m-1] of m characters representing pattern
//Output : The position of the first characters in the text that starts the first //matching substring if search is successful and –1 otherwise
0 to n-m doßfor I
0ßj
while j < m and P[j] = T[I+j] do
j+1ßj
if j =m return I
return –1
13. Give the general plan for divide-and-conquer algorithms.
The general plan is as follows
v A problems instance is divided into several smaller instances of the same problem, ideally about the same size
v The smaller instances are solved, typically recursively
v If necessary the solutions obtained are combined to get the solution of the original problem
14. State the Master theorem and its use.
0 in recurrence equation T(n) = aT(n/b)+f(n), then³(nd) where d q ÎIf f(n)
(nd)q if a<bd
ÎT(n) (ndlog n)q if a=bd
(nlogba)q if a>bd
The efficiency analysis of many divide-and-conquer algorithms are greatly simplified by the use of Master theorem.
15. What is the general divide-and-conquer recurrence relation?
An instance of size ‘n’ can be divided into several instances of size n/b, with ‘a’ of them needing to be solved. Assuming that size ‘n’ is a power of ‘b’, to simplify the analysis, the following recurrence for the running time is obtained:
T(n) = aT(n/b)+f(n)
Where f(n) is a function that accounts for the time spent on dividing the problem into smaller ones and on combining their solutions.
16. Define mergesort.
Mergesort sorts a given array A[0..n-1] by dividing it into two halves a[0..(n/2)-1] and A[n/2..n-1] sorting each of them recursively and then merging the two smaller sorted arrays into a single sorted one.
17. Give the algorithm for mergesort.
ALGORITHM Mergesort(A[0..n-1])
//Sorts an array A[0..n-1] by recursive mergesort
//Input: An array A[0..n-1] of orderable elements
//Output: Array A[0..n-1] sorted in nondecreasing order
if n > 1
copy A[0..(n/2)-1] to B[0..(n/2)-1]
copy A[(n/2)..n-1] to C[0..(n/2)-1]
Mergesort(B[0..(n/2)-1])
Mergesort(C[0..(n/2)-1])
Merge(B,C,A)
18. Give the algorithm to merge two sorted arrays into one.
ALGORITHM Merge(B[0..p-1], C[0..q-1], A[0..p+q-1])
//Merges two sorted arrays into one sorted array
//Input: arrays B[0..p-1] and C[0..q-1] both sorted
//Output: sorted array A[0..p+q-1] of the elements of B & C
0ß 0; k ß 0; j ßI
while I < p and j < q do
C[j]£if B[I]
I+1ß B[I]; I ßA[k]
else
j+1ß C[j]; j ßA[k]
k+1ßk
if I = p
copy C[j..q-1] to A[k..p+q-1]
else
copy B[i..p-1] to A[k..p+q-1]
19. What is the difference between quicksort and mergesort?
Both quicksort and mergesort use the divide-and-conquer technique in which the given array is partitioned into subarrays and solved. The difference lies in the technique that the arrays are partitioned. For mergesort the arrays are partitioned according to their position and in quicksort they are partitioned according to the element values.
20. Give the algorithm for Quicksort.
ALGORITHM Quicksort(A[l..r])
//Sorts a array by quicksort
//Input: A subarray A[l..r] of A[0..n-1], defined by the left and right indices l & r
//Output: the subarray A[l..r] sorted in nondecreasing order
if l < r
Partition(A[l..r])ßs
Quicksort(A[l..s-1])
Quicksort(A[s+1..r])
21. Mention the algorithm used to partition an array for quicksort.
ALGORITHM Partition(A[l..r])
//Partitions a subarray using the first element as pivot
//Input: A subarray A[l..r] of A[o..n-1]
//Output: A partition of A[l..r] with split position returned as function’s value
A[l]ßp
r+1ß l; j ßI
repeat
I+1 until A[I] pßrepeat I
j-1 until A[j]ßrepeat j p
swap(A[I],A[j])
until i j
swap(A[I],A[j])
swap(A[l],A[j])
return j
22. What is binary search?
Binary search is a remarkably efficient algorithm for searching in a sorted array. It works by comparing a search key K with the arrays middle element A[m]. if they match the algorithm stops; otherwise the same operation is repeated recursively for the first half of the array if K < A[m] and the second half if K > A[m].
K
A[0]………A[m-1] A[m] A[m+1]………A[n-1]
search here if K<A[m] search here if K>A[m]
23. What is a binary tree extension and what is its use?
The binary tree extension can be drawn by replacing the empty subtrees by special nodes in a binary tree. The extra nodes shown as little squares are called external & the original nodes shown as little circles called internal. The extension of a empty binary tree is a single external node. The binary tree extension helps in analysis of tree algorithms.
24. What are the classic traversals of a binary tree?
The classic traversals are as follows
v Preorder traversal: the root is visited before left & right subtrees
v Inorder traversal: the root is visited after visiting left subtree and before visiting right subtree
v Postorder traversal: the root is visited after visiting the left and right subtrees
25. Mention an algorithm to find out the height of a binary tree.
ALGORITHM Height(T)
//Compares recursively the height of a binary tree
//Input: A binary tree T
//Output: The height of T
if T = return –1
else return max{Height(TL), Height(TR)}+1
26. Draw the extension tree of the given binary tree.
27. What is decrease and conquer approach and mention its variations?
The decrease and conquer technique based on exploiting the relationship between a solution to a given instance of a problem and a solution to a smaller instance of the same problem. The three major variations are
v Decrease by a constant
v Decrease by a constant-factor
v Variable size decrease
28. What is insertion sort?
Insertion sort in an application of decrease-by-one technique to sort an array A[0..n-1]. We assume that the smaller problem of sorting an array A[0..n-2] has already been solved to give us a sorted array of size n-1. Then an appropriate position for A[n-1] is found among the sorted element and then the element is inserted.
29. Give the algorithm for insertion sort.
//Sorts a given array by insertion sort
//Input: An array A[0..n-1] of n orderable elements
//Output: Array A[0..n-1] sorted in non-decreasing order
1 to n-1 doßfor I
A[I]ßv
I-1ßj
while j 0 and A[j] > v do
A[j]ßA[j+1]
j – 1ßj
vßA[j+1]
30. What is a tree edge and back edge?
In the depth first search forest, whenever a new unvisited vertex is reached for the first time, it is attached as a child to the vertex from which it is being reached. Such an edge is called tree edge because the set of all such edges forms a forest. The algorithm encounters an edge leading to a previously visited vertex other than its immediate predecessor. Such an edge is called a back edge because it connects a vertex to its ancestor, other than the parent, in the depth first search forest.
31. What is a tree edge and cross edge?
In the breadth first search forest, whenever a new unvisited vertex is reached for the first time, it is attached as a child to the vertex from which it is being reached. Such an edge is called tree edge. If an edge is leading to a previously visited vertex other than its immediate predecessor, that edge is noted as cross edge.
Explain
§ Selection sort
§ Bubble sort
§ Sequential Search
§ Brute-force String Matching
2. Discuss in detail about divide – and-conquer approach
Explain
§ Merge sort
§ Quick sort
§ Binary search
3. Discuss in detail about decrease-and-conquer approach
Explain
• Insertion sort
• Binary Search
4. Explain about Depth First Search
Explain
§ DFS Algorithm
§ Example
5. Explain about Breadth First Search
Explain
§ BFS algorithm
§ Example
2 Marks
1. Define Brute force approach?Brute force is a straightforward approach to solving a problem, usually directly based on the problem’s statement and definitions of the concepts involved. The brute force approach is one that is easiest to apply.
2. What are the advantages of brute force technique?
The various advantages of brute force technique are
v Brute force applicable to a very wide variety of problems. It is used for many elementary but important algorithmic tasks
For some important problems this approach yields reasonablev algorithms of at least some practical value with no limitation on instance size
The expense to design a more efficient algorithm may bev unjustifiable if only a few instances of problems need to be solved and a brute force algorithm can solve those instances with acceptable speed
v Even if inefficient in general it can still be used for solving small-size instances of a problem
v It can serve as a yardstick with which to judge more efficient alternatives for solving a problem
3. What is selection sort?
Selection sort is started by scanning the entire list to find the smallest element and exchange it with the first element, putting the first element in the final position in the sorted list. Then the scan starts from the second element to find the smallest among n-1 elements and exchange it with the second element.
A0 A1 ………… Ai-1 | Ai……..…,Amin,………,An-1
In their final position The last n-I elements
4. Mention the pseudocode for selection sort.
ALGORITHM SelectionSort(A[0..n-1])
//The algorithm sorts a given array by selection sort
//Input: An array A[0..n-1] of orderable elements
//Output: Array A[0..n-1] sorted in ascending order
0 to n-2 doßfor I
Ißmin
I+1 to n-1 doßfor j
if A[j] < jßA[min] min
swap A[I] and A[min]
5. What is bubble sort?
Another brute force approach to sort a problem is to compare adjacent elements of the list and exchange them if they are out of order, so we end up “bubbling up” the largest element to the last position in the list. The next pass bubbles up the second largest element, and so on until n-1 passes , the list is sorted. Pass I can be represented as follows
?
A0,……, Aj Aj+1,……, An-I-1 | An-I …… An-1
In their final positions
6. Give an algorithm for bubble sort?
ALGORITHM BubbleSort(A[0..n-1])
//The algorithm sorts array A[0..n-1] by bubble sort
//Input: An array A[0..n-1] of orderable elements
//Output: Arrar A[0..n-1] sorted in ascending order
0 to n-2 doßfor I
0 to n-2-I doßfor j
if A[j+1]<A[j] swap A[j] and A[j+1]
7. Give the benefit of application of brute force technique to solve a problem.
With the application of brute force strategy, the first version of an algorithm obtained can often be improved with a modest amount of effort. So a first application of the brute force approach often results in an algorithm that can be improved with a modest amount of effort.
8. Explain about the enhanced version of sequential search.
Sequential search simply compares successive elements of a list with a given search key until either a match is encountered or the list is exhausted without finding a match. The enhancement in this version is to append the search key to the end of the list , then the search for the key will have to be successful & so we can eliminate a check for the list’s end on each iteration.
9. Give the algorithm for the enhanced version of sequential search.
ALGORITHM SequentialSearch2(A[0..n-1],K)
//The algorithm implements sequential search with the search key as sentinael
//Input: An array A of n elements and a search key K
//Output: The position of the first element in a[0..n-1] whose value is equal to K or //–1 if no such element is found
KßA[n]
0ßI
K do¹while A[I]
I+1ßI
If I < n return I
else return -1
10. What is the improvement that can be applied to sequential search if the list is sorted?
The straightforward improvement that can be incorporated in sequential search if a given list is known to be sorted is that searching in the list can be stopped as soon as an element greater than or equal to the search key is encountered.
11. Define brute force string matching.
The brute force string matching has a given string of n characters called the text and a string of m characters called the pattern, find a substring of the text that matches the pattern. And find the index I of the leftmost character of the first matching substring in the text.
12. Mention the algorithm for brute force string matching
ALGORITHM BruteForceStringMatching(T[0..n-1],P[0..m-1])
//The algorithm implements brute force string matching
//Input: an array T[0..n-1] of n characters representing text
//An array P[0..m-1] of m characters representing pattern
//Output : The position of the first characters in the text that starts the first //matching substring if search is successful and –1 otherwise
0 to n-m doßfor I
0ßj
while j < m and P[j] = T[I+j] do
j+1ßj
if j =m return I
return –1
13. Give the general plan for divide-and-conquer algorithms.
The general plan is as follows
v A problems instance is divided into several smaller instances of the same problem, ideally about the same size
v The smaller instances are solved, typically recursively
v If necessary the solutions obtained are combined to get the solution of the original problem
14. State the Master theorem and its use.
0 in recurrence equation T(n) = aT(n/b)+f(n), then³(nd) where d q ÎIf f(n)
(nd)q if a<bd
ÎT(n) (ndlog n)q if a=bd
(nlogba)q if a>bd
The efficiency analysis of many divide-and-conquer algorithms are greatly simplified by the use of Master theorem.
15. What is the general divide-and-conquer recurrence relation?
An instance of size ‘n’ can be divided into several instances of size n/b, with ‘a’ of them needing to be solved. Assuming that size ‘n’ is a power of ‘b’, to simplify the analysis, the following recurrence for the running time is obtained:
T(n) = aT(n/b)+f(n)
Where f(n) is a function that accounts for the time spent on dividing the problem into smaller ones and on combining their solutions.
16. Define mergesort.
Mergesort sorts a given array A[0..n-1] by dividing it into two halves a[0..(n/2)-1] and A[n/2..n-1] sorting each of them recursively and then merging the two smaller sorted arrays into a single sorted one.
17. Give the algorithm for mergesort.
ALGORITHM Mergesort(A[0..n-1])
//Sorts an array A[0..n-1] by recursive mergesort
//Input: An array A[0..n-1] of orderable elements
//Output: Array A[0..n-1] sorted in nondecreasing order
if n > 1
copy A[0..(n/2)-1] to B[0..(n/2)-1]
copy A[(n/2)..n-1] to C[0..(n/2)-1]
Mergesort(B[0..(n/2)-1])
Mergesort(C[0..(n/2)-1])
Merge(B,C,A)
18. Give the algorithm to merge two sorted arrays into one.
ALGORITHM Merge(B[0..p-1], C[0..q-1], A[0..p+q-1])
//Merges two sorted arrays into one sorted array
//Input: arrays B[0..p-1] and C[0..q-1] both sorted
//Output: sorted array A[0..p+q-1] of the elements of B & C
0ß 0; k ß 0; j ßI
while I < p and j < q do
C[j]£if B[I]
I+1ß B[I]; I ßA[k]
else
j+1ß C[j]; j ßA[k]
k+1ßk
if I = p
copy C[j..q-1] to A[k..p+q-1]
else
copy B[i..p-1] to A[k..p+q-1]
19. What is the difference between quicksort and mergesort?
Both quicksort and mergesort use the divide-and-conquer technique in which the given array is partitioned into subarrays and solved. The difference lies in the technique that the arrays are partitioned. For mergesort the arrays are partitioned according to their position and in quicksort they are partitioned according to the element values.
20. Give the algorithm for Quicksort.
ALGORITHM Quicksort(A[l..r])
//Sorts a array by quicksort
//Input: A subarray A[l..r] of A[0..n-1], defined by the left and right indices l & r
//Output: the subarray A[l..r] sorted in nondecreasing order
if l < r
Partition(A[l..r])ßs
Quicksort(A[l..s-1])
Quicksort(A[s+1..r])
21. Mention the algorithm used to partition an array for quicksort.
ALGORITHM Partition(A[l..r])
//Partitions a subarray using the first element as pivot
//Input: A subarray A[l..r] of A[o..n-1]
//Output: A partition of A[l..r] with split position returned as function’s value
A[l]ßp
r+1ß l; j ßI
repeat
I+1 until A[I] pßrepeat I
j-1 until A[j]ßrepeat j p
swap(A[I],A[j])
until i j
swap(A[I],A[j])
swap(A[l],A[j])
return j
22. What is binary search?
Binary search is a remarkably efficient algorithm for searching in a sorted array. It works by comparing a search key K with the arrays middle element A[m]. if they match the algorithm stops; otherwise the same operation is repeated recursively for the first half of the array if K < A[m] and the second half if K > A[m].
K
A[0]………A[m-1] A[m] A[m+1]………A[n-1]
search here if K<A[m] search here if K>A[m]
23. What is a binary tree extension and what is its use?
The binary tree extension can be drawn by replacing the empty subtrees by special nodes in a binary tree. The extra nodes shown as little squares are called external & the original nodes shown as little circles called internal. The extension of a empty binary tree is a single external node. The binary tree extension helps in analysis of tree algorithms.
24. What are the classic traversals of a binary tree?
The classic traversals are as follows
v Preorder traversal: the root is visited before left & right subtrees
v Inorder traversal: the root is visited after visiting left subtree and before visiting right subtree
v Postorder traversal: the root is visited after visiting the left and right subtrees
25. Mention an algorithm to find out the height of a binary tree.
ALGORITHM Height(T)
//Compares recursively the height of a binary tree
//Input: A binary tree T
//Output: The height of T
if T = return –1
else return max{Height(TL), Height(TR)}+1
26. Draw the extension tree of the given binary tree.
27. What is decrease and conquer approach and mention its variations?
The decrease and conquer technique based on exploiting the relationship between a solution to a given instance of a problem and a solution to a smaller instance of the same problem. The three major variations are
v Decrease by a constant
v Decrease by a constant-factor
v Variable size decrease
28. What is insertion sort?
Insertion sort in an application of decrease-by-one technique to sort an array A[0..n-1]. We assume that the smaller problem of sorting an array A[0..n-2] has already been solved to give us a sorted array of size n-1. Then an appropriate position for A[n-1] is found among the sorted element and then the element is inserted.
29. Give the algorithm for insertion sort.
//Sorts a given array by insertion sort
//Input: An array A[0..n-1] of n orderable elements
//Output: Array A[0..n-1] sorted in non-decreasing order
1 to n-1 doßfor I
A[I]ßv
I-1ßj
while j 0 and A[j] > v do
A[j]ßA[j+1]
j – 1ßj
vßA[j+1]
30. What is a tree edge and back edge?
In the depth first search forest, whenever a new unvisited vertex is reached for the first time, it is attached as a child to the vertex from which it is being reached. Such an edge is called tree edge because the set of all such edges forms a forest. The algorithm encounters an edge leading to a previously visited vertex other than its immediate predecessor. Such an edge is called a back edge because it connects a vertex to its ancestor, other than the parent, in the depth first search forest.
31. What is a tree edge and cross edge?
In the breadth first search forest, whenever a new unvisited vertex is reached for the first time, it is attached as a child to the vertex from which it is being reached. Such an edge is called tree edge. If an edge is leading to a previously visited vertex other than its immediate predecessor, that edge is noted as cross edge.
16 Marks
1. Explain about Brute force ApproachExplain
§ Selection sort
§ Bubble sort
§ Sequential Search
§ Brute-force String Matching
2. Discuss in detail about divide – and-conquer approach
Explain
§ Merge sort
§ Quick sort
§ Binary search
3. Discuss in detail about decrease-and-conquer approach
Explain
• Insertion sort
• Binary Search
4. Explain about Depth First Search
Explain
§ DFS Algorithm
§ Example
5. Explain about Breadth First Search
Explain
§ BFS algorithm
§ Example
0 comments:
Post a Comment