Anna University Data Analysis of Algorithm Two marks question and answers
2 Marks
1. What is the need of studying algorithms?
A standard set of algorithms from different areas of computing must be known, in addition to be able to design them and analyze their efficiencies. From a theoretical standpoint the study of algorithms in the cornerstone of computer science.
2. What is algorithmics?
The study of algorithms is called algorithmics. It is more than a branch of computer science. It is the core of computer science and is said to be relevant to most of science, business and technology.
3. What is an algorithm?
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in finite amount of time.
4. Give the diagram representation of Notion of algorithm.
5. What is the formula used in Euclid
Gcd(m,n)=gcd(n,m mod n) until m mod n is equal to 0, since gcd(m,0)=m.
6. What are the three different algorithms used to find the gcd of two numbers?
The three algorithms used to find the gcd of two numbers are
v Euclid
v Consecutive integer checking algorithm
v Middle school procedure
7. What are the fundamental steps involved in algorithmic problem solving?
The fundamental steps are
v Understanding the problem
v Ascertain the capabilities of computational device
v Choose between exact and approximate problem solving
v Decide on appropriate data structures
v Algorithm design techniques
v Methods for specifying the algorithm
v Proving an algorithms correctness
v Analyzing an algorithm
v Coding an algorithm
8. What is an algorithm design technique?
An algorithm design technique is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.
9. What is pseudocode?
A pseudocode is a mixture of a natural language and programming language constructs to specify an algorithm. A pseudocode is more precise than a natural language and its usage often yields more concise algorithm descriptions.
10. What are the types of algorithm efficiencies?
The two types of algorithm efficiencies are
v Time efficiency: indicates how fast the algorithm runs
v Space efficiency: indicates how much extra memory the algorithm needs
11. Mention some of the important problem types?
Some of the important problem types are as follows
v Sorting
v Searching
v String processing
v Graph problems
v Combinatorial problems
v Geometric problems
v Numerical problems
12. What are the classical geometric problems?
The two classic geometric problems are
v The closest pair problem: given n points in a plane find the closest pair among them
v The convex hull problem: find the smallest convex polygon that would include all the points of a given set.
13. What are the steps involved in the analysis framework?
The various steps are as follows
v Measuring the input’s size
v Units for measuring running time
v Orders of growth
v Worst case, best case and average case efficiencies
14. What is the basic operation of an algorithm and how is it identified?
The most important operation of the algorithm is called the basic operation of the algorithm, the operation that contributes the most to the total running time. It can be identified easily because it is usually the most time consuming operation in the algorithms innermost loop.
15. What is the running time of a program implementing the algorithm?
The running time T(n) is given by the following formula
T(n) ≈ copC(n)
cop is the time of execution of an algorithm’s basic operation on a particular computer and C(n) is the number of times this operation needs to be executed for the particular algorithm.
16. What are exponential growth functions?
The functions 2n and n! are exponential growth functions, because these two functions grow so fast that their values become astronomically large even for rather smaller values of n.
17. What is worst-case efficiency?
The worst-case efficiency of an algorithm is its efficiency for the worst-case input of size n, which is an input or inputs of size n for which the algorithm runs the longest among all possible inputs of that size.
18. What is best-case efficiency?
The best-case efficiency of an algorithm is its efficiency for the best-case input of size n, which is an input or inputs for which the algorithm runs the fastest among all possible inputs of that size.
19. What is average case efficiency?
The average case efficiency of an algorithm is its efficiency for an average case input of size n. It provides information about an algorithm behavior on a “typical” or “random” input.
20. What is amortized efficiency?
In some situations a single operation can be expensive, but the total time for the entire sequence of n such operations is always significantly better that the worst case efficiency of that single operation multiplied by n. this is called amortized efficiency.
21. Define O-notation?
A function t(n) is said to be in O(g(n)), denoted by t(n) ɛ O(g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exists some positive constant c and some nonnegative integer n0 such that
T(n) ≤ cg(n) for all n ≥ n0
22. Define Ω-notation?
A function t(n) is said to be in Ω(g(n)), denoted by t(n) ɛ Ω(g(n)), if t(n) is bounded below by some constant multiple of g(n) for all large n, i.e., if there exists some positive constant c and some nonnegative integer n0 such that
T(n) ≥ cg(n) for all n ≥ n0
23. Define Θ-notation?
A function t(n) is said to be in Θ(g(n)), denoted by t(n) ɛ Θ(g(n)), if t(n) is bounded both above & below by some constant multiple of g(n) for all large n, i.e., if there exists some positive constants c1 & c2 and some nonnegative integer n0 such that c2g(n) ≤ t(n) ≤ c1g(n) for all n ≥ n0
24. Mention the useful property, which can be applied to the asymptotic notations and its use?
If t1(n) ɛO(g1(n)) and t2(n) ɛ O(g2(n)) then t1(n)+t2(n) ɛ max {g1(n),g2(n)} this property is also true for Ω and Θ notations. This property will be useful in analyzing algorithms that comprise of two consecutive executable parts.
25. What are the basic asymptotic efficiency classes?
The various basic efficiency classes are
v Constant : 1
v Logarithmic : log n
v Linear : n
v N-log-n : nlog n
v Quadratic : n2
v Cubic : n3
v Exponential : 2n
v Factorial : n!
16 Marks
1. Explain about the fundamentals of Algorithmic Problem solving
Explain about
• Understanding
• Ascertaining
• Choosing
• Deciding
• Designing
• Specifying
• Proving
• Analyzing
• Coding of an algorithm
2. Discuss the important problem types
Explain about
• Sorting
• Searching
• String Processing
• Graph Problems
• Combinatorial Problems
• Geometric Problems
• Numerical Problems
3. Explain Analysis framework with example
Explain about
• Measuring an input size
• Units for measuring running time
• Orders of growth
• Worst,Best and Average case efficiencies
• Recapitulation of the framework
4. Discuss the Asymptotic notations with efficiency classes and examples
Explain about
• Big-Oh notation
• Big-Theta notation
• Big-Omega notation
• Properties of notations
• Orders of growth
• Efficiency classes
16 Marks
1. Explain about the fundamentals of Algorithmic Problem solving
Explain about
• Understanding
• Ascertaining
• Choosing
• Deciding
• Designing
• Specifying
• Proving
• Analyzing
• Coding of an algorithm
2. Discuss the important problem types
Explain about
• Sorting
• Searching
• String Processing
• Graph Problems
• Combinatorial Problems
• Geometric Problems
• Numerical Problems
3. Explain Analysis framework with example
Explain about
• Measuring an input size
• Units for measuring running time
• Orders of growth
• Worst,Best and Average case efficiencies
• Recapitulation of the framework
4. Discuss the Asymptotic notations with efficiency classes and examples
Explain about
• Big-Oh notation
• Big-Theta notation
• Big-Omega notation
• Properties of notations
• Orders of growth
• Efficiency classes
1. Give an non-recursive algorithm to find out the largest element in a list of n numbers.
ALGORITHM MaxElement(A[0..n-1])
//Determines the value of the largest element in a given array
//Input:An array A[0..n-1] of real numbers
//Output: The value of the largest element in A
a[0]ßmaxval
1 to n-1 doßfor I
if A[I] > maxval
A[I]ßmaxval
return maxval
2. What are the two basic rules for sum manipulation?
The two basic rules for sum manipulation are
cai = c ai
bi) =±(ai ai bi
3. Mention the two summation formulas?
The two summation formulas are
1 = u-l+1 where l u are some lower and upper integer limits
= = 1+2+3+…+n = n(n+1)/2 n2/2 (n2)
4. Write the general plan for analyzing the efficiency for non-recursive algorithms.
The various steps include
vDecide on a parameter indicating input’s size.
vIdentify the algorithms basic operation.
Check whether the number of times the basic operation is executedv depends on size of input. If it depends on some additional property the worst, average and best-case efficiencies have to be investigated separately.
vSet up a sum expressing the number of times the algorithm’s basic operation is executed.
Using standard formulas and rules of manipulation, find avclosed-form formula for the count or at least establish its order of growth.
5. Give a non-recursive algorithm for element uniqueness problem.
ALGORITHM UniqueElements(A[0..n-1])
//Checks whether all the elements in a given array are distinct
//Input :An array A[0..n-1]
//Output Returns ‘true’ if all elements in A are distinct and ‘false’ //otherwise
to n-2 doßfor I
I+1 to n-1 doßfor j
if A[I] = A[j] return false
return true
6. Mention the non-recursive algorithm for matrix multiplication?
ALGORITHM MatrixMultiplication(A[0..n-1,0..n-1], B[0..n-1,0..n-1])
//Multiplies two square matrices of order n by the definition based //algorithm
//Input : Two n-by-n matrices A and B
//Output : Matrix C = AB
0 to n-1 doßfor I
0 to n-1 doßfor j
0.0ßC[I,j]
0 to n-1 doßfor k
C[I,j] + A[I,k]*B[k,j]ßC[I,j]
return C
7. Write a non-recursive algorithm for finding the number of binary digits for a positive decimal integer.
ALGORITHM Binary(n)
// Input A positive decimal integer n
// Output The number of binary digits in n’s binary representation
1ßcount
while n>1 do
count + 1ßcount
n/2ßn
return count
8. Write a recursive algorithm to find the n-th factorial number.
ALGORITHM F(n)
// Computes n! recursively
// Input A non-negative integer n
// Output The value of n!
if n=0 return 1
else return F(n-1) * n
9. What is the recurrence relation to find out the number of multiplications and the initial condition for finding the n-th factorial number?
The recurrence relation and initial condition for the number of multiplications is
M(n)=M(n-1)+1 for n>0
M(0)=0
10. Write the general plan for analyzing the efficiency for recursive algorithms.
The various steps include
vDecide on a parameter indicating input’s size.
vIdentify the algorithms basic operation.
Check whether the number of times the basic operation is executedv depends on size of input. If it depends on some additional property the worst, average and best-case efficiencies have to be investigated separately.
vSet up a recurrence relation with the appropriate initial condition , for the number of times the basic operation is executed.
vSolve the recurrence or at least ascertain the orders of growth of its solution.
11. Write a recursive algorithm for solving Tower of Hanoi problem.
ALGORITHM
To move nv>1 disks from peg1 to peg3, with peg2 as auxiliary, first move recursively n-1 disks from peg1 to peg2 with peg3 as auxiliary.
vThen move the largest disk directly from peg1 to peg3
vFinally move recursively n-1 disks from peg2 to peg3 with peg1 as auxiliary
vIf n=1 simply move the single disk from source peg to destination peg.
12. What is the basic operation in the Tower of Hanoi problem and give the recurrence relation for the number of moves?
The moving of disks is considered the basic operation in the Tower of Hanoi problem and the recurrence relation for the number of moves is given as
M(n)=2M(n)+1 for n>1
M(1)=1
13. Write a recursive algorithm to find the number of binary digits in the binary representation of an integer.
ALGORITHM BinRec(n)
// Input A positive decimal integer n
// Output The number of binary digits in n’s binary representation
if n=1 return 1
else return BinRec(n/2)+1
14. Who introduced the Fibonacci numbers and how can it be defined by a simple recurrence?
Leonardo Fibonacci introduced the fibonacci numbers in 1202 as a solution to a problem about the size of rabbit population. It can be defined by the simple recurrence
F(n)=F(n-1)+F(n-2) for n>1
And two initial conditions
F(0)=0 and F(1)=1
15. What is the explicit formula for the nth Fibonacci number?
The formula for the nth Fibonacci number is given by
F(n)= 1/ ( n - n)
Where
=(1+ )/2
=(1- )/2
16. Write a recursive algorithm for computing the nth fibonacci number?
ALGORITHM F(n)
// Computes the nth Fibonacci number recursively by using the definition
// Input A non-negative integer n
// Output The nth Fibonacci number
if n 1 return n
else return F(n-1)+F(n-2)
17. Write a non-recursive algorithm for computing the nth fibonacci number.
ALGORITHM Fib(n)
// Computes the nth Fibonacci number iteratively by using its definition
// Input A non-negative integer n
// Output The nth Fibonacci number
0;ßF[0]
1ßF[1]
2 to n doßFor I
F[I-1]+F[I-2]ßF[I]
return F[n]
18. (log n) algorithm for computing the nth fibonacci number based on?QWhat is the
(log n) algorithm for computing the nth fibonacciQThere exists a number that manipulates only integers. It is based on the equality
= for n 1 with an efficient way of computing matrix powers
19. What is the general plan for the Empirical Analysis of Algorithm Efficiency?
The general plan is as follows
vUnderstand the experiment’s purpose.
vDecide on the efficiency metric M to be measured & the measurement unit.
vDecide on characteristics of the input sample
vPrepare a program implementing the algorithm for the experimentation
vGenerate a sample of inputs
vRun the algorithm on the sample input and record the data observed
vAnalyze the data obtained
20. Give the various system commands used for timing the program implementing the algorithm.
The system commands are as follows
UNIX time command
C & C++ function clock
Java method currentTimeMillis() in the System class
21. Mention the linear congruential method for generating pseudorandom numbers.
ALGORITHM Random(n,m,seed,a,b)
//Generates a sequence of n pseudorandom numbers using linear congruential //method
//Input A positive integer n and positive integer parameters m, seed, a, b
//Output A sequence r1,…..,rn of n pseudorandom integers uniformly distributed //among integer values between 0 and m-1
seedßr0
1 to n doßfor I
(a*ri-1+b) mod mßri
22. What are the guidelines in choosing the values of m, seed, a, b for linear congruential method
The recommendations are as follows
seed May be chosen arbitrarily and is often set to current date and time
m Should be large and may be conveniently taken as 2w where w is the computer’s word size
a Should be selected as an integer between 0.01m and 099m with no particular pattern in its digits but such that a mod 8=5
b The value can be chosen as 1
23. What is algorithm visualization?
Algorithm visualization is a way to study algorithms. It is defined as the use of images to convey some useful information about algorithms. That information can be a visual illustration of algorithm’s operation, of its performance on different kinds of inputs, or of its execution speed versus that of other algorithms for the same problem.
24. What are the two variations of algorithm visualization?
The two principal variations of algorithm visualization”
vStatic algorithm visualization: It shows the algorithm’s progress through a series of still images
vDynamic algorithm visualization: Algorithm animation shows a continuous movie like presentation of algorithms operations
25. What are the features that are desired in algorithm animation?
Peter Gloor, who was the principal developer of Animated Algorithms suggested the following desirable features
vBe consistent
vBe interactive
vBe clear and concise
vBe forgiving to the user
vAdapt to the knowledge level of the user
vEmphasize the visual component
vKeep the user interested
vIncorporate both symbolic and iconic representations
vInclude algorithm’s analysis & comparisons with other algorithms for the same problem
vInclude execution history
26. What are the applications of algorithm visualization?
The two applications are
vResearch: Based on expectations that algorithm visualization may help uncover some unknown feature of the algorithm
vEducation: Seeks to help students learning algorithms
16 Marks
1. Explain Non-Recursive algorithms with suitable examples
Explain the algorithms
§Max element
§General Plan
§Unique Elements
§Matrix Multiplication
§Binary Representation
2. Explain Recursive algorithms with suitable examples
Explain the algorithms
• Factorial
• General Plan
• Towers of Hanoi
• Binary Representation
3. Discuss about the empirical analysis of algorithms
Explain
• General Plan
• Pseudo random numbers
4. Discuss briefly about Algorithmic visualization
Explain
• Static algorithm visualization
• Dynamic algorithm visualization
5. Discuss about the Fibonacci numbers
Explain about
§Explicit formula
§Computation
§Iterative algorithm
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
vBrute 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
vEven if inefficient in general it can still be used for solving small-size instances of a problem
vIt 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
vA problems instance is divided into several smaller instances of the same problem, ideally about the same size
vThe smaller instances are solved, typically recursively
vIf 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)qif a<bd
ÎT(n) (ndlog n)q if a=bd
(nlogba)qif 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
vPreorder traversal: the root is visited before left & right subtrees
vInorder traversal: the root is visited after visiting left subtree and before visiting right subtree
vPostorder 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
vDecrease by a constant
vDecrease by a constant-factor
vVariable 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 Approach
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
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
vTransformation to a simpler or more convenient instance of the same problem called instance simplification
vTransformation to a different representation of the same instance called representation change
vTransformation 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
vSingle right rotation or R-rotation
vSingle left rotation or L-rotation
vDouble left-right rotation or LR-rotation
vDouble 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
vFrequent rotations
vThe need to maintain balances for the tree’s nodes
vOverall 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.
vThe 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
vFinding an item with the highest priority
vDeleting an item with highest priority
vAdding a new item to the set
17. Give three properties of heaps?
The properties of heap are
vThere exists exactly one essentially complete binary tree with ‘n’ nodes. Its height is equal to log2n
vThe root of the heap is always the largest element
vA 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
vThe 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
vBottom-up heap construction
vTop-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
vExchange the root’s key with the last key K of the heap
vDecrease 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
vStage 1 Heap construction: construct a heap for a given array.
vStage 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)
vIf 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
vFeasible : It has to satisfy the problem’s constraints
vLocally optimal : It has to be the best local choice among all feasible choices available on that step.
vIrrevocable : 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
vThe name of the nearest tree vertex
vThe 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
vFringe : It contains the vertices that are not in the tree but are adjacent to atleast one tree vertex.
vUnseen : 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
vMove 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
vFixed-length encoding
vVariable-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
- Presorting
- Balanced Search Tree
- Heaps and Heap sort
- 2. Explain about Dynamic Programming
- Warshall’s And Floyd’s Algorithm
- Graph
- Algorithm
- 3. Explain Greedy techniques with algorithms
- Prim’s Algorithm
- Kruskal’s Algorithm
- Dijkstra’s Algorithm
- 4. Discuss in detail about Optimal Binary Trees
- 5. Explain briefly about Dijkstra’s Algorithm
- Minimum spanning tree
- Algorithm
- Graph
- 6. Discuss in detail about Huffman Trees
- Algorithm
- Diagram
UNIT III 9
CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS
UNIT –I
A Pseudo code is a mixture of a natural language and programming language like constructs. A pseudo code is usually more precise than a natural language, and its usage often yields more succinct algorithm descriptions.
UNIT I 9UNIT III 9
CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS
UNIT –I
A Pseudo code is a mixture of a natural language and programming language like constructs. A pseudo code is usually more precise than a natural language, and its usage often yields more succinct algorithm descriptions.
UNIT I 9UNIT III 9
CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS
UNIT –I
A Pseudo code is a mixture of a natural language and programming language like constructs. A pseudo code is usually more precise than a natural language, and its usage often yields more succinct algorithm descriptions.
UNIT I 9UNIT III 9
CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS
UNIT –I
A Pseudo code is a mixture of a natural language and programming language like constructs. A pseudo code is usually more precise than a natural language, and its usage often yields more succinct algorithm descriptions.
Explain
Explain
Explain
Explain
Explain
1. What is backtracking?
Backtracking constructs solutions one component at a time and such partially constructed solutions are evaluated as follows
If a partially constructed solution can be developed furtherv without violating the problem’s constraints, it is done by taking the first remaining legitimate option for the next component.
If there is no legitimate option for the next component, nov alternatives for the remaining component need to be considered. In this case, the algorithm backtracks to replace the last component of the partially constructed solution with its next option.
2. What is a state space tree?
The processing of backtracking is implemented by constructing a tree of choices being made. This is called the state-space tree. Its root represents a initial state before the search for a solution begins. The nodes of the first level in the tree represent the choices made for the first component of the solution, the nodes in the second level represent the choices for the second component and so on.
3. What is a promising node in the state-space tree?
A node in a state-space tree is said to be promising if it corresponds to a partially constructed solution that may still lead to a complete solution.
4. What is a non-promising node in the state-space tree?
A node in a state-space tree is said to be promising if it corresponds to a partially constructed solution that may still lead to a complete solution; otherwise it is called non-promising.
5. What do leaves in the state space tree represent?
Leaves in the state-space tree represent either non-promising dead ends or complete solutions found by the algorithm.
6. What is the manner in which the state-space tree for a backtracking algorithm is constructed?
In the majority of cases, a state-space tree for backtracking algorithm is constructed in the manner of depth-first search. If the current node is promising, its child is generated by adding the first remaining legitimate option for the next component of a solution, and the processing moves to this child. If the current node turns out to be non-promising, the algorithm backtracks to the node’s parent to consider the next possible solution to the problem, it either stops or backtracks to continue searching for other possible solutions.
7. What is n-queens problem?
The problem is to place ‘n’ queens on an n-by-n chessboard so that no two queens attack each other by being in the same row or in the column or in the same diagonal.
8. Draw the solution for the 4-queen problem.
Q
Q
Q
Q
Q
Q
Q
Q
9. Define the Hamiltonian circuit.
The Hamiltonian is defined as a cycle that passes through all the vertices of the graph exactly once. It is named after the Irish mathematician Sir William Rowan Hamilton (1805-1865).It is a sequence of n+1 adjacent vertices
vi0, vi1,……, vin-1, vi0
where the first vertex of the sequence is same as the last one while all the other n-1 vertices are distinct.
10. What is the subset-sum problem?
Find a subset of a given set S={s1,………,sn} of ‘n’ positive integers whose sum is equal to a given positive integer ‘d’.
11. When can a node be terminated in the subset-sum problem?
The sum of the numbers included are added and given as the value for the root as s’. The node can be terminated as a non-promising node if either of the two equalities holds:
s’+si+1>d (the sum s’ is too large)
s’+ sj<d (the sum s’ is too small)
12. How can the output of a backtracking algorithm be thought of?
The output of a backtracking algorithm can be thought of as an n-tuple (x1, …xn) where each coordinate xi is an element of some finite linearly ordered set Si. If such a tuple (x1, …xi) is not a solution, the algorithm finds the next element in Si+1 that is consistent with the values of (x1, …xi) and the problem’s constraints and adds it to the tuple as its (I+1)st coordinate. If such an element does not exist, the algorithm backtracks to consider the next value of xi, and so on.
13. Give a template for a generic backtracking algorithm.
ALGORITHM Backtrack(X[1..i])
//Gives a template of a generic backtracking algorithm
//Input X[1..i] specifies the first I promising components of a solution
//Output All the tuples representing the problem’s solution
if X[1..i] is a solution write X[1..i]
else
Si+1 consistent with X[1..i] and the constraints doÎfor each element x
xßX[i+1]
Backtrack(X[1..i+1])
14. What are the tricks used to reduce the size of the state-space tree?
The various tricks are
Exploit the symmetry often present in combinatorial problems. Sov some solutions can be obtained by the reflection of others. This cuts the size of the tree by about half.
vPreassign values to one or more components of a solution
vRearranging the data of a given instance.
15. What is the method used to find the solution in n-queen problem by symmetry?
The board of the n-queens problem has several symmetries so that some solutions can be obtained by other reflections. Placements in the last n/2 columns need not be considered, because any solution with the first queen in square (1,i), n/2 i n can be obtained by reflection from a solution with the first queen in square (1,n-i+1)
16. What are the additional features required in branch-and-bound when compared to backtracking?
Compared to backtracking, branch-and-bound requires:
A way to provide, for every node of a state space tree, a bound onv the best value of the objective function on any solution that can be obtained by adding further components to the partial solution represented by the node.
vThe value of the best solution seen so far
17. What is a feasible solution and what is an optimal solution?
In optimization problems, a feasible solution is a point in the problem’s search space that satisfies all the problem’s constraints, while an optimal solution is a feasible solution with the best value of the objective function.
18. When can a search path be terminated in a branch-and-bound algorithm?
A search path at the current node in a state-space tree of a branch-and-bound algorithm can be terminated if
vThe value of the node’s bound is not better than the value of the best solution seen so far
vThe node represents no feasible solution because the constraints of the problem are already violated.
The subset of feasible solutions represented by the node consistsv of a single point in this case compare the value of the objective function for this feasible solution with that of the best solution seen so far and update the latter with the former if the new solution is better.
19. Compare backtracking and branch-and-bound.
Backtracking Branch-and-bound
State-space tree is constructed using depth-first search State-space tree is constructed using best-first search
Finds solutions for combinatorial non-optimization problems Finds solutions for combinatorial optimization problems
No bounds are associated with the nodes in the state-space tree Bounds are associated with the each and every node in the state-space tree
20. What is the assignment problem?
Assigning ‘n’ people to ‘n’ jobs so that the total cost of the assignment is as small as possible. The instance of the problem is specified as a n-by-n cost matrix C so that the problem can be stated as: select one element in each row of the matrix so that no two selected items are in the same column and the sum is the smallest possible.
21. What is best-first branch-and-bound?
It is sensible to consider a node with the best bound as the most promising, although this does not preclude the possibility that an optimal solution will ultimately belong to a different branch of the state-space tree. This strategy is called best-first branch-and-bound.
22. What is knapsack problem?
Given n items of known weights wi and values vi, i=1,2,…,n, and a knapsack of capacity W, find the most valuable subset of the items that fit the knapsack. It is convenient to order the items of a given instance in descending order by their value-to-weight ratios. Then the first item gives the best payoff per weight unit and the last one gives the worst payoff per weight unit.
23. Give the formula used to find the upper bound for knapsack problem.
A simple way to find the upper bound ‘ub’ is to add ‘v’, the total value of the items already selected, the product of the remaining capacity of the knapsack W-w and the best per unit payoff among the remaining items, which is vi+1/wi+1
ub = v + (W-w)( vi+1/wi+1)
24. What is the traveling salesman problem?
The problem can be modeled as a weighted graph, with the graph’s vertices representing the cities and the edge weights specifying the distances. Then the problem can be stated as finding the shortest Hamiltonian circuit of the graph, where the Hamiltonian is defined as a cycle that passes through all the vertices of the graph exactly once.
25. What are the strengths of backtracking and branch-and-bound?
The strengths are as follows
It is typically applied to difficult combinatorial problems forv which no efficient algorithm for finding exact solution possibly exist
vIt holds hope for solving some instances of nontrivial sizes in an acceptable amount of time
Even if it does not eliminate any elements of a problem’s statev space and ends up generating all its elements, it provides a specific technique for doing so, which can be of some value.
16 Marks
1. Explain about Backtracking with suitable examples
Explain
• n-Queen’s Problem
• Hamiltonian Circuit problem
• Subset-Sum problem
2. Explain about Branch-and-Bound
Explain
§Assignment problem
§Knapsack problem
§Travelling salesman problem.
3. Explain Travelling Salesman Problem with suitable diagrams
Explain
• TSP Concepts
• Graph
• Computation
• Algorithm
4. Discuss in detail about Assignment Problem
Explain
• Assignment Problem Definition
• Example
• Graph representation
• Algorithm computation
5. Explain Knapsack Problem & n-Queen’s Problem
Explain
• Knapsack 0/1Example & n-Queen’s Problem Example
• Graph representation
• Algorithm computation
SYLLABUS
CS 2251 DESIGN AND ANALYSIS OF ALGORITHMS 3 1 0 4
Algorithm Analysis – Time Space Tradeoff – Asymptotic Notations – Conditional asymptotic notation – Removing condition from the conditional asymptotic notation - Properties of big-Oh notation – Recurrence equations – Solving recurrence equations – Analysis of linear search.
UNIT II 9
Divide and Conquer: General Method – Binary Search – Finding Maximum and Minimum – Merge Sort – Greedy Algorithms: General Method – Container Loading – Knapsack Problem.
Dynamic Programming: General Method – Multistage Graphs – All-Pair shortest paths – Optimal binary search trees – 0/1 Knapsack – Travelling salesperson problem .
UNIT IV 9
Backtracking: General Method – 8 Queens problem – sum of subsets – graph coloring – Hamiltonian problem – knapsack problem.
UNIT V 9
Graph Traversals – Connected Components – Spanning Trees – Biconnected components – Branch and Bound: General Methods (FIFO & LC) – 0/1 Knapsack problem – Introduction to NP-Hard and NP-Completeness.
TUTORIAL = 15 Total = 60
TEXT BOOK:
1. Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, Computer Algorithms/ C++, Second Edition, Universities Press, 2007. (For Units II to V)
2. K.S. Easwarakumar, Object Oriented Data Structures using C++, Vikas Publishing House pvt. Ltd., 2000 (For Unit I)
REFERENCES:
1. T. H. Cormen, C. E. Leiserson, R.L.Rivest, and C. Stein, "Introduction to Algorithms", Second Edition, Prentice Hall of India Pvt. Ltd, 2003.
2. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, "The Design and Analysis of Computer Algorithms", Pearson Education, 1999.
Welcome to i-education
1. What is an Algorithm? May/June 2006, Nov/Dec 2008
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time
2. State the Euclid
ALGORITHM Euclid
// Computes gcd(m,n) by Euclid
//Input : Two nonnegative, not-both-zero integers mand n
//Output: Greatest common divisor of m and n
while n ¹ 0 do
r ß m mod n
m ß n
n ß r
return m.
3. What are Sequential Algorithms?
The central assumption of the RAM model is that instructions are executed one after another, one operation at a time. Accordingly, algorithms designed to be executed on such machines are called Sequential algorithms.
4. What are Parallel Algorithms?
The central assumption of the RAM model does not hold for some newer computers that can execute operations concurrently, i.e., in parallel algorithms that take advantage of this capability are called Parallel algorithms.
5. What is Exact and Approximation algorithm?
The principal decision to choose solving the problem exactly is called exact algorithm.
The principal decision to choose solving the problem approximately is called Approximation algorithm.
6. What is Algorithm Design Technique? Nov/Dec 2005
An algorithm design technique is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.
7. Define Pseudo code.
8. Define Flowchart.
A method of expressing an algorithm by a collection of connected geometric shapes containing descriptions of the algorithm’s steps.
9. Explain Algorithm’s Correctness
To prove that the algorithm yields a required result for every legitimate input in a finite amount of time.
Example: Correctness of Euclid
10. What is Efficiency of algorithm?
Efficiency of an algorithm can be precisely defined and investigated with mathematical rigor. There are two kinds of algorithm efficiency
1) Time Efficiency – Indicates how fast the algorithm runs
2) Space Efficiency – Indicates how much extra memory the algorithm needs.
11. What is generality of an algorithm?
It is a desirable characteristic of an algorithm. Generality of the problem the algorithm solves is sometimes easier to design an algorithm for a problem posed in more general terms.
12. What is algorithm’s Optimality?
Optimality is about the complexity of the problem that algorithm solves. What is the minimum amount of effort any algorithm will need to exert to solve the problem in question is called algorithm’s Optimality.
13. What do you mean by ²Sorting” problem?
The sorting problem asks us to rearrange the items of a given list in ascending order (or descending order)
14. What do you mean by ²Searching” problem?
The searching problem deals with finding a given value, called a search key, in a given set.
15. What do you mean by ²Worst case-Efficiency” of an algorithm?
The ²Worst case-Efficiency” of an algorithm is its efficiency for the worst-case input of size n, which is an input (or inputs) of size n for which the algorithm runs the longest among all possible inputs of that size.
Ex: if you want to sort a list of numbers in ascending order when the numbers are given in descending order. In this running time will be the longest.
16. What do you mean by ²Best case-Efficiency” of an algorithm?
The ²Best case-Efficiency” of an algorithm is its efficiency for the Best-case input of size n, which is an input(or inputs) of size n for which the algorithm runs the fastest among all possible inputs of that size.
Ex: if you want to sort a list of numbers in ascending order when the numbers are given in ascending order. In this running time will be the smallest.
17. Define the ²Average-case efficiency” of an algorithm?
The ²Average-case efficiency” of an algorithm is its efficiency for the input of size n, for which the algorithm runs between the best case and the worst case among all possible inputs of that size.
18. What do you mean by “Amortized efficiency”?
The “Amortized efficiency” applies not only a single run of an algorithm but rather to a sequence of operations performed on the same data structure. It turns out that in some situations a single operation can be expensive ,but the total time for an entire sequence of n such operations is always significantly better than the worst case efficiency of that single operation multiplied by n. This is known as “Amortized efficiency”.
19. How to measure the algorithm’s efficiency?
It is logical to investigate the algorithm’s efficiency as a function of some parameter n indicating the algorithm’s input size.
Example: It will be the size of the list for problems of sorting, searching, finding the list’s smallest element, and most other problems dealing with lists.
20. What is called the basic operation of an algorithm?
The most important operation of the algorithm is the operation contributing the most to the total running time is called basic operation of an algorithm.
21. How to measure an algorithm’s running time?
Let Cop be the time of execution of an algorithm’s basic iteration on a particular computer and let C (n) be the number of times this operation needs to be executed for this algorithm. Then we can estimate the running time T(n) of a program implementing this algorithm on that computer by the formula
T(n) ≈ CopC(n)
22. Define order of growth.
The efficiency analysis framework concentrates on the order of growth of an algorithm’s basic operation count as the principal indicator of the algorithm’s efficiency. To compare and rank such orders of growth we use three notations
1) O (Big oh) notation
2) Ω (Big Omega) notation &
3) Θ (Big Theta) notation
23. Define Big oh notation May/June 2006, April/May 2008
A function t(n) is said to be in O(g(n)) denoted t(n) ε O (g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some non negative integer n0 such that
T (n) < c g (n) for n >n0
24. Prove that 100n+5 Î O (n2)?
Clearly 100n+5 £ 100n+n (for all n ³ 5) = 101n£101n2
By choosing n0=5 and c=101 we find that 100n+5ÎO (n2).
25. Define Ω notation
A function t(n) is said to be in Ω (g(n)), denoted t(n) ÎΩ (g(n)), if t(n) is bounded below by some positive constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some non negative integer n0 such that
T (n) < c g (n) for n >n0
26. Prove that n3ÎW(n2)?
Clearly n3 ³ n2 for all n ³ 0. i.e., we can select c=1 and n0=0.
27. Define Θ - notation
A function t(n) is said to be in Θ(g(n)), denoted t(n) ÎΘ (g(n)), if t(n) is bounded both above and below by some positive constant multiples of g(n) for all large n, i.e., if there exist some positive constant c1 and c2 and some non negative integer n0such that
c2g (n) < t (n) < c1 g(n) for n > n0
28. Prove that( ½)n(n-1) Î Q(n2)
1/2n(n-1)=(1/2)n2-1/2n £ 1/2 n2for all n³0.(we have proved upper inequality) now 1/2n(n-1)=(1/2)n2-1/2n³(1/2)n2-1/2n*1/2n(for all n³2)=1/4 n2 hence we can select c2=1/4,c1=1/2 and n0=2.
29. What is the use of Asymptotic Notations?
The notations O, W and Q and are used to indicate and compare the asymptotic orders of growth of functions expressing algorithm efficiencies.
UNIT II
1) Explain divide and conquer algorithms
Divide and conquer is probably the best known general algorithm design technique. It work according to the following general plan
i)A problem's instance is divided into several smaller instances of the same problem, ideally of about the same size.
ii) The smaller instances are solved
iii) If necessary, the solutions obtained for the smaller instances are combined to get a solution to the original problem
2) Define Merge Sort
Merge sort is a perfect example of a successful application of the divide and conquer technique. It sorts a given array A[0...n-l] by dividing it into two halves A[0...[n/2] - 1] and A[[n/2]....n-l], sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one.
3) Define Binary Search
Binary Search is remarkably efficient algorithm for searching in a sorted array. It works by comparing a search key K with the array's 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 for the second half if K > A[m]
A[0].............A[m-l] A[m] A[m+l]............. A[n-l]
4) What can we say about the average case efficiency of binary search?
A sophisticated analysis shows that the average number of key comparisons made by binary search is only slightly smaller than that in the worst case
Cavg(n) » log2n
5) Define Binary Tree
A binary tree T is defined as a finite set of nodes that is either empty or consists of s root and two disjoint binary trees tL, and tr called, respectively the left and right subtree of the root.
6) How divide and conquer technique can be applied to binary trees?
Since the binary tree definition itself divides a binary tree into two smaller structures of the same type, the left subtree and the right subtree, many problems about binary trees can be solved by applying the divide-conquer technique.
7) Explain Internal and External Nodes
To draw the tree's extension by replacing the empty subtrees by special nodes.The extra nodes shown by little squares are called external. The original nodes shown by littile circles are called internal.
8) Define Preorder, inorder and postorder Traversal
PREORDER -The root is visited before the left and right subtrees are visited (in that order)
INORDER -The root is visited after visiting its left subtree but before visiting the right Subtree
POSTORDER - The root is visited after visiting the left and right subtrees(in that order)
9) Define the Internal Path Length
The Internal Path Length I of an extended binary tree is defined as the sum of the lengths of the paths - taken over all internal nodes- from the root to each internal node.
10) Define the External Path Length
The External Path Length E of an extended binary tree is defined as the sum of the lengths of the paths - taken over all external nodes- from the root to each external node.
11) Explain about greedy technique
The greedy technique suggests constructing a solution to an optimization problem 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 and irrevocable.
12) Define 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.
13) Define Minimum Spanning Tree
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.
14) Define min-heap
A min-heap is a complete binary tree in which every element is less than or equal to its children. All the principal properties of heaps remain valid for min-heaps, with some obvious modifications.
15) Define 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.
16) Define Prim's Algorithm
Prim's algorithm is a greedy algorithm for constructing a minimum spanning tree of a weighted connected graph.It works by attaching to a previously constructed subtree a vertex to the vertices already in the tree.
17) Explain Dijkstra's Algorithm
Dijkstra's algorithm solves the single - source shortest - path problem of finding shortest paths from a given vertex (the source) to all the other vertices of a weighted graph or digraph. It works as prim's algorithm but compares path lengths rather than edge lengths. Dijkstra's algorithm always yields a correct solution for a graph with nonnegative weights.
UNIT III
1)Define Dynamic Programming
Dynamic programming is a technique for solving problems with overlapping problems. Typically, these subproblems arise from a recurrence relating a solution to a given problem with solutions to its smaller subproblems of the same type. Rather than solving overlapping subproblems again and again, dynamic programming suggests solving each of the smaller sub problems only once and recording the results in a table from which we can then obtain a solution to the original problem.
2) Define Binomial Coefficient
n
The Binomial Coefficient, denoted C(n,k) or k is the number of Combinations(subsets) of k elements from an n-element set(0<k<n). The name "binomial coefficients" comes from the participation of these numbers in the so called binomial formula
(a+b)n =(n,0)an+..........+C(n,i)an-ibi+.......+C(n,n)bn
3) Define Transitive closure
The transitive closure of a directed graph with n vertices can be defined as the n by n Boolean matrix T = {ti,}, in which the element in the ith row (1<i<n) and the jthcolumn (l<j<n) is 1 if there exists a non trivial directed path from the ith vertex to jth vertex ; otherwise , tijis 0.
4) Explain Warshalls algorithm
Warshall's algorithm constructs the transitive closure of a given digraph with n vertices through a series of n by n Boolean matrices R(0), ………, R(k-l)R(k),…….., R(n)
Each of these matrices provides certain information about directed paths in the digraph.
4) Explain All-pair shortest-paths problem
Given a weighted connected graph (undirected or directed), the all pairs shortest paths problem asks to find the distances(the lengths of the shortest path) from each vertex to all other vertices.
5) Explain Floyd's algorithm
It is convenient to record the lengths of shortest paths in an n by n matrix D called the distance matrix: the element dijin the ith row and the jth column of this matrix indicates the length of the shortest path from the ith vertex to the jthvertex . We can generate the distance matrix with an algorithm that is very similar to warshall's algorithm. It is called Floyd's algorithm.
6) What does Floyd’s algorithm do?
It is used to find the distances (the lengths of the shortest paths) from each vertex to all other vertices of a weighted connected graph.
7) Explain principle of Optimality
It says that an optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances.
8) Explain Optimal Binary Search Trees
One of the principal application of Binary Search Tree is to implement the operation of searching. If probabilities of searching for elements of a set are known, it is natural to pose a question about an optimal binary search tree for which the average number of comparisons in a search is the smallest possible.
9) Explain Knapsack problem
Given n items of known weights w1,w2...........wnand values v1,v2............vn and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack.(Assuming all the weights and the knapsack's capacity are positive integers the item values do not have to be integers.)
10) Explain the Memory Function technique
The Memory Function technique seeks to combine strengths of the top down and bottom-up approaches to solving problems with overlapping subproblems. It does this by solving, in the top-down fashion but only once, just necessary sub problems of a given problem and recording their solutions in a table.
11) Explain ²Traveling salesman problem”?
A salesman has to travel n cities starting from any one of the cities and visit the remaining cities exactly once and come back to the city where he started his journey in such a manner that either the distance is minimum or cost is minimum. This is known as traveling salesman problem.
UNIT IV
l) Explain Backtracking
The principal idea is to construct solutions one component at a time and evaluate such partially constructed candidates as follows.
> If a partially constructed solution can be developed further without violating the problem's constraints, it is done by taking the first remaininig legitimate option for the next component.
> If there is no legitimate option for the next component, no alternatives for any remaining component need to be considered.
In this case, the algorithm backtracks to replace the last component of the partially constructed solution with its next option
2) Explain State Space Tree
If it is convenient to implement backtracking by constructing a tree of choices being made, the tree is called a state space tree. Its root represents an initial state before the search for a solution begins.
3) Explain promising and nonpromising node
A node in a state space tree is said to be promising if it corresponds to a partially constructed solution that may still lead to a complete solution;otherwise it is called nonpromising
4) Explain n-Queens problem
The problem is to place n queens on an n by n chessboard so that no two queens attack each other by being in the same row or same column or on the same diagonal.
5) Explain Subset-Sum Problem
We consider the subset-sum problem: Find a subset of a given
set S={S1,S2,..........Sn} of n positive integers whose sum is equal to a given positive integer d.
6) Explain Branch and Bound Technique
Compared to backtracking, branch and bound requires
The idea to be strengthened further if we deal with an optimization problem, one that seeks to minimize or maximize an objective function, usually subject to some constraints.
7) Define Feasible Solution
A feasible solution is a point in the problem's search space that satisfies all the problem's constraints.
Ex: A Hamiltonian Circuit in the traveling salesman problem. A subset of items whose total weight does not exceed the knapsack's Capacity
8) Define Optimal solution
Is a feasible solution with the best value of the objective function
Eg: The shortest Hamiltonian Circuit
The most valuable subset of items that fit the knapsack
9)Mention two reasons to terminate a search path at the current node in a state-space tree of a branch and bound algorithm.
The value of the node's bound is not better than the value of the best solution seen so far. The node represents no feasible solutions because the constraints of the problem are already violated.
10) Explain ²Graph coloring” problem.
The graph coloring problem asks us to assign the smallest number of colors to vertices of a graph so that no two adjacent vertices are the same color.
11) Explain Knapsack Problem
Find the most valuable subset of n items of given positive integer weights and values that fit into a knapsack of a given positive integer capacity.
UNIT V
1) Define tractable and intractable problems
Problems that can be solved in polynomial time are called tractable problems, problems that cannot be solved in polynomial time are called intractable problems.
2) Explain the theory of computational complexity
A problem's intractability remains the same for all principal models of computations and all reasonable input encoding schemes for the problem under consideration
3)Explain class P problems
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.
4)Explain undecidable problems
If the decision problem cannot be solved in polynomial time, and if the decision problems cannot be solved at all by any algorithm. Such problems are called Undecidable.
5) Explain the halting problem
Given a computer program and an input to it,determine whether the program will halt on that input or continue working indefinitely on it.
6) Explain class NP problems
Class NP is the class of decision problems that can be solved by nondeterministic polynomial algorithms.Most decision problems are in NP. First of all, this class includes all the problems in P. This class of problems is called Nondeterministic polynomial.
7)Explain NP-complete problems
A decision problem d is said to be NP-complete if
1) it belongs to class NP
2) every problem in NP is polynomially reducible to D.
8)When a decision problem is said to be polynomially reducible
A decision problem Dl is said to be polynomially reducible to a decision problem D2 if there exists a function t that transforms instances of Dl to instances ofD2 such that
i) t maps all yes instances of d1 to yes instances odf d2 and all no instances of dl to no instances ofd2
ii) t is computable by a polynomial time algorithm
9) Define a Heuristic
A heuristic is a common-sense rule drawn from experience rather than from a mathematically proved assertion.
Ex: Going to the nearest unvisited city in the traveling salesman problem is a good illustration for Heuristic
10) Explain NP-Hard problems
The notion of an NP-hard problem can be defined more formally by extending the notion of polynomial reducability to problems that are not necessary in class NP including optimization problems.
11)Define Traversals.
When the search necessarilyinvolves the examination of every vertex in the object being searched it is called a traversal.
12)List out the techniques for traversals in graph.
Breadth first search
Depth first search
13)What is articulation point.
A vertex v in a connected graph G is an articulation point if and only if the deletion of vertex v together with all edged incident to v disconnects the graph in to two or more nonempty components.
PART-B
I-UNIT
1. (a) Describe the steps in analyzing & coding an algorithm. (10)
(b) Explain some of the problem types used in the design of
algorithm. (6)
2.(a) Discuss the fundamentals of analysis framework . (10)
(b) Explain the various asymptotic notations used in algorithm design. (6)
3. (a) Explain the general framework for analyzing the efficiency of algorithm. (8)
(b) Explain the various Asymptotic efficiencies of an algorithm. (8)
4. (a) Explain the basic efficiency classes. (10)
(b) Explain briefly the concept of algorithmic strategies. (6)
5. Describe briefly the notions of complexity of an algorithm. (16)
6. (a) What is Pseudo-code?Explain with an example. (8)
(b) Find the complexity C(n) of the algorithm for the worst
case,best case and average case.(Evaluate average case complexity for n=3,Where n is the
number of inputs) (8)
7. Set up & solve a recurrence relation for the number of key comparisons made by above
pseudo code. (4)
II-UNIT
1) Write a pseudo code for divide & conquer algorithm for merging two sorted arrays in to a single sorted one.Explain with example. (12)
2) Construct a minimum spanning tree using Kruskal’s algorithm with your own example. (10)
3)Explain about Knapsack Problem with example
4) Explain Dijikstra algorithm (8)
5) Define Spanning tree.Discuss design steps in Prim’s algorithm to construct minimum spanning
tree with an example. (16)
6)Explain Kruskal’s algorithm. (8)
7)Explain about binary search with example.
III-UNIT
1) Solve the all pair shortest path problem for the diagraph with the weighted matrix given below:-
a b c d
a 0 ∞ 3 ∞
b 2 0 ∞ ∞
c ∞ 7 0 1
d 6 ∞ ∞ 0(16)
2) Explain Warshall’s & Floyd’s Algorithm. (16)
3) Explain about Multistage graphs with example.
4) Define optimal binary search trees with example.
5) Explain 0/1 knapsack problem with example.
6) Discuss the solution for Travelling salesman problem using branch & bound technique. (16)
VI-UNIT
1. Explain the 8-Queen’s problem & discuss the possible solutions. (16)
2. Solve the following instance of the knapsack problem by the branch & bound algorithm. (16)
3. Apply backtracking technique to solve the following instance of subset sum problem :
S={1,3,4,5} and d=11 (16)
5. Explain subset sum problem & discuss the possible solution strategies using backtracking.(16)
6. Explain Graph coloring with example.
7. Explain about Knapsack Problem using back tracking with example.
V-UNIT
1. Give a suitable example & explain the Breadth first search & Depth first search. (16)
2. Explain about biconnected components with example.
3. Briefly explain NP-Hard and NP-Completeness with examples.
4. Explain about 0/1 Knapsack Problem using branch and bound with example.
CS 2251 DESIGN AND ANALYSIS OF ALGORITHMS 3 1 0 4
Algorithm Analysis – Time Space Tradeoff – Asymptotic Notations – Conditional asymptotic notation – Removing condition from the conditional asymptotic notation - Properties of big-Oh notation – Recurrence equations – Solving recurrence equations – Analysis of linear search.
UNIT II 9
Divide and Conquer: General Method – Binary Search – Finding Maximum and Minimum – Merge Sort – Greedy Algorithms: General Method – Container Loading – Knapsack Problem.
Dynamic Programming: General Method – Multistage Graphs – All-Pair shortest paths – Optimal binary search trees – 0/1 Knapsack – Travelling salesperson problem .
UNIT IV 9
Backtracking: General Method – 8 Queens problem – sum of subsets – graph coloring – Hamiltonian problem – knapsack problem.
UNIT V 9
Graph Traversals – Connected Components – Spanning Trees – Biconnected components – Branch and Bound: General Methods (FIFO & LC) – 0/1 Knapsack problem – Introduction to NP-Hard and NP-Completeness.
TUTORIAL = 15 Total = 60
TEXT BOOK:
1. Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, Computer Algorithms/ C++, Second Edition, Universities Press, 2007. (For Units II to V)
2. K.S. Easwarakumar, Object Oriented Data Structures using C++, Vikas Publishing House pvt. Ltd., 2000 (For Unit I)
REFERENCES:
1. T. H. Cormen, C. E. Leiserson, R.L.Rivest, and C. Stein, "Introduction to Algorithms", Second Edition, Prentice Hall of India Pvt. Ltd, 2003.
2. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, "The Design and Analysis of Computer Algorithms", Pearson Education, 1999.
Welcome to i-education
1. What is an Algorithm? May/June 2006, Nov/Dec 2008
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time
2. State the Euclid
ALGORITHM Euclid
// Computes gcd(m,n) by Euclid
//Input : Two nonnegative, not-both-zero integers mand n
//Output: Greatest common divisor of m and n
while n ¹ 0 do
r ß m mod n
m ß n
n ß r
return m.
3. What are Sequential Algorithms?
The central assumption of the RAM model is that instructions are executed one after another, one operation at a time. Accordingly, algorithms designed to be executed on such machines are called Sequential algorithms.
4. What are Parallel Algorithms?
The central assumption of the RAM model does not hold for some newer computers that can execute operations concurrently, i.e., in parallel algorithms that take advantage of this capability are called Parallel algorithms.
5. What is Exact and Approximation algorithm?
The principal decision to choose solving the problem exactly is called exact algorithm.
The principal decision to choose solving the problem approximately is called Approximation algorithm.
6. What is Algorithm Design Technique? Nov/Dec 2005
An algorithm design technique is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.
7. Define Pseudo code.
8. Define Flowchart.
A method of expressing an algorithm by a collection of connected geometric shapes containing descriptions of the algorithm’s steps.
9. Explain Algorithm’s Correctness
To prove that the algorithm yields a required result for every legitimate input in a finite amount of time.
Example: Correctness of Euclid
10. What is Efficiency of algorithm?
Efficiency of an algorithm can be precisely defined and investigated with mathematical rigor. There are two kinds of algorithm efficiency
1) Time Efficiency – Indicates how fast the algorithm runs
2) Space Efficiency – Indicates how much extra memory the algorithm needs.
11. What is generality of an algorithm?
It is a desirable characteristic of an algorithm. Generality of the problem the algorithm solves is sometimes easier to design an algorithm for a problem posed in more general terms.
12. What is algorithm’s Optimality?
Optimality is about the complexity of the problem that algorithm solves. What is the minimum amount of effort any algorithm will need to exert to solve the problem in question is called algorithm’s Optimality.
13. What do you mean by ²Sorting” problem?
The sorting problem asks us to rearrange the items of a given list in ascending order (or descending order)
14. What do you mean by ²Searching” problem?
The searching problem deals with finding a given value, called a search key, in a given set.
15. What do you mean by ²Worst case-Efficiency” of an algorithm?
The ²Worst case-Efficiency” of an algorithm is its efficiency for the worst-case input of size n, which is an input (or inputs) of size n for which the algorithm runs the longest among all possible inputs of that size.
Ex: if you want to sort a list of numbers in ascending order when the numbers are given in descending order. In this running time will be the longest.
16. What do you mean by ²Best case-Efficiency” of an algorithm?
The ²Best case-Efficiency” of an algorithm is its efficiency for the Best-case input of size n, which is an input(or inputs) of size n for which the algorithm runs the fastest among all possible inputs of that size.
Ex: if you want to sort a list of numbers in ascending order when the numbers are given in ascending order. In this running time will be the smallest.
17. Define the ²Average-case efficiency” of an algorithm?
The ²Average-case efficiency” of an algorithm is its efficiency for the input of size n, for which the algorithm runs between the best case and the worst case among all possible inputs of that size.
18. What do you mean by “Amortized efficiency”?
The “Amortized efficiency” applies not only a single run of an algorithm but rather to a sequence of operations performed on the same data structure. It turns out that in some situations a single operation can be expensive ,but the total time for an entire sequence of n such operations is always significantly better than the worst case efficiency of that single operation multiplied by n. This is known as “Amortized efficiency”.
19. How to measure the algorithm’s efficiency?
It is logical to investigate the algorithm’s efficiency as a function of some parameter n indicating the algorithm’s input size.
Example: It will be the size of the list for problems of sorting, searching, finding the list’s smallest element, and most other problems dealing with lists.
20. What is called the basic operation of an algorithm?
The most important operation of the algorithm is the operation contributing the most to the total running time is called basic operation of an algorithm.
21. How to measure an algorithm’s running time?
Let Cop be the time of execution of an algorithm’s basic iteration on a particular computer and let C (n) be the number of times this operation needs to be executed for this algorithm. Then we can estimate the running time T(n) of a program implementing this algorithm on that computer by the formula
T(n) ≈ CopC(n)
22. Define order of growth.
The efficiency analysis framework concentrates on the order of growth of an algorithm’s basic operation count as the principal indicator of the algorithm’s efficiency. To compare and rank such orders of growth we use three notations
1) O (Big oh) notation
2) Ω (Big Omega) notation &
3) Θ (Big Theta) notation
23. Define Big oh notation May/June 2006, April/May 2008
A function t(n) is said to be in O(g(n)) denoted t(n) ε O (g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some non negative integer n0 such that
T (n) < c g (n) for n >n0
24. Prove that 100n+5 Î O (n2)?
Clearly 100n+5 £ 100n+n (for all n ³ 5) = 101n£101n2
By choosing n0=5 and c=101 we find that 100n+5ÎO (n2).
25. Define Ω notation
A function t(n) is said to be in Ω (g(n)), denoted t(n) ÎΩ (g(n)), if t(n) is bounded below by some positive constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some non negative integer n0 such that
T (n) < c g (n) for n >n0
26. Prove that n3ÎW(n2)?
Clearly n3 ³ n2 for all n ³ 0. i.e., we can select c=1 and n0=0.
27. Define Θ - notation
A function t(n) is said to be in Θ(g(n)), denoted t(n) ÎΘ (g(n)), if t(n) is bounded both above and below by some positive constant multiples of g(n) for all large n, i.e., if there exist some positive constant c1 and c2 and some non negative integer n0such that
c2g (n) < t (n) < c1 g(n) for n > n0
28. Prove that( ½)n(n-1) Î Q(n2)
1/2n(n-1)=(1/2)n2-1/2n £ 1/2 n2for all n³0.(we have proved upper inequality) now 1/2n(n-1)=(1/2)n2-1/2n³(1/2)n2-1/2n*1/2n(for all n³2)=1/4 n2 hence we can select c2=1/4,c1=1/2 and n0=2.
29. What is the use of Asymptotic Notations?
The notations O, W and Q and are used to indicate and compare the asymptotic orders of growth of functions expressing algorithm efficiencies.
UNIT II
1) Explain divide and conquer algorithms
Divide and conquer is probably the best known general algorithm design technique. It work according to the following general plan
i)A problem's instance is divided into several smaller instances of the same problem, ideally of about the same size.
ii) The smaller instances are solved
iii) If necessary, the solutions obtained for the smaller instances are combined to get a solution to the original problem
2) Define Merge Sort
Merge sort is a perfect example of a successful application of the divide and conquer technique. It sorts a given array A[0...n-l] by dividing it into two halves A[0...[n/2] - 1] and A[[n/2]....n-l], sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one.
3) Define Binary Search
Binary Search is remarkably efficient algorithm for searching in a sorted array. It works by comparing a search key K with the array's 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 for the second half if K > A[m]
A[0].............A[m-l] A[m] A[m+l]............. A[n-l]
4) What can we say about the average case efficiency of binary search?
A sophisticated analysis shows that the average number of key comparisons made by binary search is only slightly smaller than that in the worst case
Cavg(n) » log2n
5) Define Binary Tree
A binary tree T is defined as a finite set of nodes that is either empty or consists of s root and two disjoint binary trees tL, and tr called, respectively the left and right subtree of the root.
6) How divide and conquer technique can be applied to binary trees?
Since the binary tree definition itself divides a binary tree into two smaller structures of the same type, the left subtree and the right subtree, many problems about binary trees can be solved by applying the divide-conquer technique.
7) Explain Internal and External Nodes
To draw the tree's extension by replacing the empty subtrees by special nodes.The extra nodes shown by little squares are called external. The original nodes shown by littile circles are called internal.
8) Define Preorder, inorder and postorder Traversal
PREORDER -The root is visited before the left and right subtrees are visited (in that order)
INORDER -The root is visited after visiting its left subtree but before visiting the right Subtree
POSTORDER - The root is visited after visiting the left and right subtrees(in that order)
9) Define the Internal Path Length
The Internal Path Length I of an extended binary tree is defined as the sum of the lengths of the paths - taken over all internal nodes- from the root to each internal node.
10) Define the External Path Length
The External Path Length E of an extended binary tree is defined as the sum of the lengths of the paths - taken over all external nodes- from the root to each external node.
11) Explain about greedy technique
The greedy technique suggests constructing a solution to an optimization problem 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 and irrevocable.
12) Define 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.
13) Define Minimum Spanning Tree
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.
14) Define min-heap
A min-heap is a complete binary tree in which every element is less than or equal to its children. All the principal properties of heaps remain valid for min-heaps, with some obvious modifications.
15) Define 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.
16) Define Prim's Algorithm
Prim's algorithm is a greedy algorithm for constructing a minimum spanning tree of a weighted connected graph.It works by attaching to a previously constructed subtree a vertex to the vertices already in the tree.
17) Explain Dijkstra's Algorithm
Dijkstra's algorithm solves the single - source shortest - path problem of finding shortest paths from a given vertex (the source) to all the other vertices of a weighted graph or digraph. It works as prim's algorithm but compares path lengths rather than edge lengths. Dijkstra's algorithm always yields a correct solution for a graph with nonnegative weights.
UNIT III
1)Define Dynamic Programming
Dynamic programming is a technique for solving problems with overlapping problems. Typically, these subproblems arise from a recurrence relating a solution to a given problem with solutions to its smaller subproblems of the same type. Rather than solving overlapping subproblems again and again, dynamic programming suggests solving each of the smaller sub problems only once and recording the results in a table from which we can then obtain a solution to the original problem.
2) Define Binomial Coefficient
n
The Binomial Coefficient, denoted C(n,k) or k is the number of Combinations(subsets) of k elements from an n-element set(0<k<n). The name "binomial coefficients" comes from the participation of these numbers in the so called binomial formula
(a+b)n =(n,0)an+..........+C(n,i)an-ibi+.......+C(n,n)bn
3) Define Transitive closure
The transitive closure of a directed graph with n vertices can be defined as the n by n Boolean matrix T = {ti,}, in which the element in the ith row (1<i<n) and the jthcolumn (l<j<n) is 1 if there exists a non trivial directed path from the ith vertex to jth vertex ; otherwise , tijis 0.
4) Explain Warshalls algorithm
Warshall's algorithm constructs the transitive closure of a given digraph with n vertices through a series of n by n Boolean matrices R(0), ………, R(k-l)R(k),…….., R(n)
Each of these matrices provides certain information about directed paths in the digraph.
4) Explain All-pair shortest-paths problem
Given a weighted connected graph (undirected or directed), the all pairs shortest paths problem asks to find the distances(the lengths of the shortest path) from each vertex to all other vertices.
5) Explain Floyd's algorithm
It is convenient to record the lengths of shortest paths in an n by n matrix D called the distance matrix: the element dijin the ith row and the jth column of this matrix indicates the length of the shortest path from the ith vertex to the jthvertex . We can generate the distance matrix with an algorithm that is very similar to warshall's algorithm. It is called Floyd's algorithm.
6) What does Floyd’s algorithm do?
It is used to find the distances (the lengths of the shortest paths) from each vertex to all other vertices of a weighted connected graph.
7) Explain principle of Optimality
It says that an optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances.
8) Explain Optimal Binary Search Trees
One of the principal application of Binary Search Tree is to implement the operation of searching. If probabilities of searching for elements of a set are known, it is natural to pose a question about an optimal binary search tree for which the average number of comparisons in a search is the smallest possible.
9) Explain Knapsack problem
Given n items of known weights w1,w2...........wnand values v1,v2............vn and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack.(Assuming all the weights and the knapsack's capacity are positive integers the item values do not have to be integers.)
10) Explain the Memory Function technique
The Memory Function technique seeks to combine strengths of the top down and bottom-up approaches to solving problems with overlapping subproblems. It does this by solving, in the top-down fashion but only once, just necessary sub problems of a given problem and recording their solutions in a table.
11) Explain ²Traveling salesman problem”?
A salesman has to travel n cities starting from any one of the cities and visit the remaining cities exactly once and come back to the city where he started his journey in such a manner that either the distance is minimum or cost is minimum. This is known as traveling salesman problem.
UNIT IV
l) Explain Backtracking
The principal idea is to construct solutions one component at a time and evaluate such partially constructed candidates as follows.
> If a partially constructed solution can be developed further without violating the problem's constraints, it is done by taking the first remaininig legitimate option for the next component.
> If there is no legitimate option for the next component, no alternatives for any remaining component need to be considered.
In this case, the algorithm backtracks to replace the last component of the partially constructed solution with its next option
2) Explain State Space Tree
If it is convenient to implement backtracking by constructing a tree of choices being made, the tree is called a state space tree. Its root represents an initial state before the search for a solution begins.
3) Explain promising and nonpromising node
A node in a state space tree is said to be promising if it corresponds to a partially constructed solution that may still lead to a complete solution;otherwise it is called nonpromising
4) Explain n-Queens problem
The problem is to place n queens on an n by n chessboard so that no two queens attack each other by being in the same row or same column or on the same diagonal.
5) Explain Subset-Sum Problem
We consider the subset-sum problem: Find a subset of a given
set S={S1,S2,..........Sn} of n positive integers whose sum is equal to a given positive integer d.
6) Explain Branch and Bound Technique
Compared to backtracking, branch and bound requires
The idea to be strengthened further if we deal with an optimization problem, one that seeks to minimize or maximize an objective function, usually subject to some constraints.
7) Define Feasible Solution
A feasible solution is a point in the problem's search space that satisfies all the problem's constraints.
Ex: A Hamiltonian Circuit in the traveling salesman problem. A subset of items whose total weight does not exceed the knapsack's Capacity
8) Define Optimal solution
Is a feasible solution with the best value of the objective function
Eg: The shortest Hamiltonian Circuit
The most valuable subset of items that fit the knapsack
9)Mention two reasons to terminate a search path at the current node in a state-space tree of a branch and bound algorithm.
The value of the node's bound is not better than the value of the best solution seen so far. The node represents no feasible solutions because the constraints of the problem are already violated.
10) Explain ²Graph coloring” problem.
The graph coloring problem asks us to assign the smallest number of colors to vertices of a graph so that no two adjacent vertices are the same color.
11) Explain Knapsack Problem
Find the most valuable subset of n items of given positive integer weights and values that fit into a knapsack of a given positive integer capacity.
UNIT V
1) Define tractable and intractable problems
Problems that can be solved in polynomial time are called tractable problems, problems that cannot be solved in polynomial time are called intractable problems.
2) Explain the theory of computational complexity
A problem's intractability remains the same for all principal models of computations and all reasonable input encoding schemes for the problem under consideration
3)Explain class P problems
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.
4)Explain undecidable problems
If the decision problem cannot be solved in polynomial time, and if the decision problems cannot be solved at all by any algorithm. Such problems are called Undecidable.
5) Explain the halting problem
Given a computer program and an input to it,determine whether the program will halt on that input or continue working indefinitely on it.
6) Explain class NP problems
Class NP is the class of decision problems that can be solved by nondeterministic polynomial algorithms.Most decision problems are in NP. First of all, this class includes all the problems in P. This class of problems is called Nondeterministic polynomial.
7)Explain NP-complete problems
A decision problem d is said to be NP-complete if
1) it belongs to class NP
2) every problem in NP is polynomially reducible to D.
8)When a decision problem is said to be polynomially reducible
A decision problem Dl is said to be polynomially reducible to a decision problem D2 if there exists a function t that transforms instances of Dl to instances ofD2 such that
i) t maps all yes instances of d1 to yes instances odf d2 and all no instances of dl to no instances ofd2
ii) t is computable by a polynomial time algorithm
9) Define a Heuristic
A heuristic is a common-sense rule drawn from experience rather than from a mathematically proved assertion.
Ex: Going to the nearest unvisited city in the traveling salesman problem is a good illustration for Heuristic
10) Explain NP-Hard problems
The notion of an NP-hard problem can be defined more formally by extending the notion of polynomial reducability to problems that are not necessary in class NP including optimization problems.
11)Define Traversals.
When the search necessarilyinvolves the examination of every vertex in the object being searched it is called a traversal.
12)List out the techniques for traversals in graph.
Breadth first search
Depth first search
13)What is articulation point.
A vertex v in a connected graph G is an articulation point if and only if the deletion of vertex v together with all edged incident to v disconnects the graph in to two or more nonempty components.
PART-B
I-UNIT
1. (a) Describe the steps in analyzing & coding an algorithm. (10)
(b) Explain some of the problem types used in the design of
algorithm. (6)
2.(a) Discuss the fundamentals of analysis framework . (10)
(b) Explain the various asymptotic notations used in algorithm design. (6)
3. (a) Explain the general framework for analyzing the efficiency of algorithm. (8)
(b) Explain the various Asymptotic efficiencies of an algorithm. (8)
4. (a) Explain the basic efficiency classes. (10)
(b) Explain briefly the concept of algorithmic strategies. (6)
5. Describe briefly the notions of complexity of an algorithm. (16)
6. (a) What is Pseudo-code?Explain with an example. (8)
(b) Find the complexity C(n) of the algorithm for the worst
case,best case and average case.(Evaluate average case complexity for n=3,Where n is the
number of inputs) (8)
7. Set up & solve a recurrence relation for the number of key comparisons made by above
pseudo code. (4)
II-UNIT
1) Write a pseudo code for divide & conquer algorithm for merging two sorted arrays in to a single sorted one.Explain with example. (12)
2) Construct a minimum spanning tree using Kruskal’s algorithm with your own example. (10)
3)Explain about Knapsack Problem with example
4) Explain Dijikstra algorithm (8)
5) Define Spanning tree.Discuss design steps in Prim’s algorithm to construct minimum spanning
tree with an example. (16)
6)Explain Kruskal’s algorithm. (8)
7)Explain about binary search with example.
III-UNIT
1) Solve the all pair shortest path problem for the diagraph with the weighted matrix given below:-
a b c d
a 0 ∞ 3 ∞
b 2 0 ∞ ∞
c ∞ 7 0 1
d 6 ∞ ∞ 0(16)
2) Explain Warshall’s & Floyd’s Algorithm. (16)
3) Explain about Multistage graphs with example.
4) Define optimal binary search trees with example.
5) Explain 0/1 knapsack problem with example.
6) Discuss the solution for Travelling salesman problem using branch & bound technique. (16)
VI-UNIT
1. Explain the 8-Queen’s problem & discuss the possible solutions. (16)
2. Solve the following instance of the knapsack problem by the branch & bound algorithm. (16)
3. Apply backtracking technique to solve the following instance of subset sum problem :
S={1,3,4,5} and d=11 (16)
5. Explain subset sum problem & discuss the possible solution strategies using backtracking.(16)
6. Explain Graph coloring with example.
7. Explain about Knapsack Problem using back tracking with example.
V-UNIT
1. Give a suitable example & explain the Breadth first search & Depth first search. (16)
2. Explain about biconnected components with example.
3. Briefly explain NP-Hard and NP-Completeness with examples.
4. Explain about 0/1 Knapsack Problem using branch and bound with example.
CS 2251 DESIGN AND ANALYSIS OF ALGORITHMS 3 1 0 4
Algorithm Analysis – Time Space Tradeoff – Asymptotic Notations – Conditional asymptotic notation – Removing condition from the conditional asymptotic notation - Properties of big-Oh notation – Recurrence equations – Solving recurrence equations – Analysis of linear search.
UNIT II 9
Divide and Conquer: General Method – Binary Search – Finding Maximum and Minimum – Merge Sort – Greedy Algorithms: General Method – Container Loading – Knapsack Problem.
Dynamic Programming: General Method – Multistage Graphs – All-Pair shortest paths – Optimal binary search trees – 0/1 Knapsack – Travelling salesperson problem .
UNIT IV 9
Backtracking: General Method – 8 Queens problem – sum of subsets – graph coloring – Hamiltonian problem – knapsack problem.
UNIT V 9
Graph Traversals – Connected Components – Spanning Trees – Biconnected components – Branch and Bound: General Methods (FIFO & LC) – 0/1 Knapsack problem – Introduction to NP-Hard and NP-Completeness.
TUTORIAL = 15 Total = 60
TEXT BOOK:
1. Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, Computer Algorithms/ C++, Second Edition, Universities Press, 2007. (For Units II to V)
2. K.S. Easwarakumar, Object Oriented Data Structures using C++, Vikas Publishing House pvt. Ltd., 2000 (For Unit I)
REFERENCES:
1. T. H. Cormen, C. E. Leiserson, R.L.Rivest, and C. Stein, "Introduction to Algorithms", Second Edition, Prentice Hall of India Pvt. Ltd, 2003.
2. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, "The Design and Analysis of Computer Algorithms", Pearson Education, 1999.
Welcome to i-education
1. What is an Algorithm? May/June 2006, Nov/Dec 2008
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time
2. State the Euclid
ALGORITHM Euclid
// Computes gcd(m,n) by Euclid
//Input : Two nonnegative, not-both-zero integers mand n
//Output: Greatest common divisor of m and n
while n ¹ 0 do
r ß m mod n
m ß n
n ß r
return m.
3. What are Sequential Algorithms?
The central assumption of the RAM model is that instructions are executed one after another, one operation at a time. Accordingly, algorithms designed to be executed on such machines are called Sequential algorithms.
4. What are Parallel Algorithms?
The central assumption of the RAM model does not hold for some newer computers that can execute operations concurrently, i.e., in parallel algorithms that take advantage of this capability are called Parallel algorithms.
5. What is Exact and Approximation algorithm?
The principal decision to choose solving the problem exactly is called exact algorithm.
The principal decision to choose solving the problem approximately is called Approximation algorithm.
6. What is Algorithm Design Technique? Nov/Dec 2005
An algorithm design technique is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.
7. Define Pseudo code.
8. Define Flowchart.
A method of expressing an algorithm by a collection of connected geometric shapes containing descriptions of the algorithm’s steps.
9. Explain Algorithm’s Correctness
To prove that the algorithm yields a required result for every legitimate input in a finite amount of time.
Example: Correctness of Euclid
10. What is Efficiency of algorithm?
Efficiency of an algorithm can be precisely defined and investigated with mathematical rigor. There are two kinds of algorithm efficiency
1) Time Efficiency – Indicates how fast the algorithm runs
2) Space Efficiency – Indicates how much extra memory the algorithm needs.
11. What is generality of an algorithm?
It is a desirable characteristic of an algorithm. Generality of the problem the algorithm solves is sometimes easier to design an algorithm for a problem posed in more general terms.
12. What is algorithm’s Optimality?
Optimality is about the complexity of the problem that algorithm solves. What is the minimum amount of effort any algorithm will need to exert to solve the problem in question is called algorithm’s Optimality.
13. What do you mean by ²Sorting” problem?
The sorting problem asks us to rearrange the items of a given list in ascending order (or descending order)
14. What do you mean by ²Searching” problem?
The searching problem deals with finding a given value, called a search key, in a given set.
15. What do you mean by ²Worst case-Efficiency” of an algorithm?
The ²Worst case-Efficiency” of an algorithm is its efficiency for the worst-case input of size n, which is an input (or inputs) of size n for which the algorithm runs the longest among all possible inputs of that size.
Ex: if you want to sort a list of numbers in ascending order when the numbers are given in descending order. In this running time will be the longest.
16. What do you mean by ²Best case-Efficiency” of an algorithm?
The ²Best case-Efficiency” of an algorithm is its efficiency for the Best-case input of size n, which is an input(or inputs) of size n for which the algorithm runs the fastest among all possible inputs of that size.
Ex: if you want to sort a list of numbers in ascending order when the numbers are given in ascending order. In this running time will be the smallest.
17. Define the ²Average-case efficiency” of an algorithm?
The ²Average-case efficiency” of an algorithm is its efficiency for the input of size n, for which the algorithm runs between the best case and the worst case among all possible inputs of that size.
18. What do you mean by “Amortized efficiency”?
The “Amortized efficiency” applies not only a single run of an algorithm but rather to a sequence of operations performed on the same data structure. It turns out that in some situations a single operation can be expensive ,but the total time for an entire sequence of n such operations is always significantly better than the worst case efficiency of that single operation multiplied by n. This is known as “Amortized efficiency”.
19. How to measure the algorithm’s efficiency?
It is logical to investigate the algorithm’s efficiency as a function of some parameter n indicating the algorithm’s input size.
Example: It will be the size of the list for problems of sorting, searching, finding the list’s smallest element, and most other problems dealing with lists.
20. What is called the basic operation of an algorithm?
The most important operation of the algorithm is the operation contributing the most to the total running time is called basic operation of an algorithm.
21. How to measure an algorithm’s running time?
Let Cop be the time of execution of an algorithm’s basic iteration on a particular computer and let C (n) be the number of times this operation needs to be executed for this algorithm. Then we can estimate the running time T(n) of a program implementing this algorithm on that computer by the formula
T(n) ≈ CopC(n)
22. Define order of growth.
The efficiency analysis framework concentrates on the order of growth of an algorithm’s basic operation count as the principal indicator of the algorithm’s efficiency. To compare and rank such orders of growth we use three notations
1) O (Big oh) notation
2) Ω (Big Omega) notation &
3) Θ (Big Theta) notation
23. Define Big oh notation May/June 2006, April/May 2008
A function t(n) is said to be in O(g(n)) denoted t(n) ε O (g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some non negative integer n0 such that
T (n) < c g (n) for n >n0
24. Prove that 100n+5 Î O (n2)?
Clearly 100n+5 £ 100n+n (for all n ³ 5) = 101n£101n2
By choosing n0=5 and c=101 we find that 100n+5ÎO (n2).
25. Define Ω notation
A function t(n) is said to be in Ω (g(n)), denoted t(n) ÎΩ (g(n)), if t(n) is bounded below by some positive constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some non negative integer n0 such that
T (n) < c g (n) for n >n0
26. Prove that n3ÎW(n2)?
Clearly n3 ³ n2 for all n ³ 0. i.e., we can select c=1 and n0=0.
27. Define Θ - notation
A function t(n) is said to be in Θ(g(n)), denoted t(n) ÎΘ (g(n)), if t(n) is bounded both above and below by some positive constant multiples of g(n) for all large n, i.e., if there exist some positive constant c1 and c2 and some non negative integer n0such that
c2g (n) < t (n) < c1 g(n) for n > n0
28. Prove that( ½)n(n-1) Î Q(n2)
1/2n(n-1)=(1/2)n2-1/2n £ 1/2 n2for all n³0.(we have proved upper inequality) now 1/2n(n-1)=(1/2)n2-1/2n³(1/2)n2-1/2n*1/2n(for all n³2)=1/4 n2 hence we can select c2=1/4,c1=1/2 and n0=2.
29. What is the use of Asymptotic Notations?
The notations O, W and Q and are used to indicate and compare the asymptotic orders of growth of functions expressing algorithm efficiencies.
UNIT II
1) Explain divide and conquer algorithms
Divide and conquer is probably the best known general algorithm design technique. It work according to the following general plan
i)A problem's instance is divided into several smaller instances of the same problem, ideally of about the same size.
ii) The smaller instances are solved
iii) If necessary, the solutions obtained for the smaller instances are combined to get a solution to the original problem
2) Define Merge Sort
Merge sort is a perfect example of a successful application of the divide and conquer technique. It sorts a given array A[0...n-l] by dividing it into two halves A[0...[n/2] - 1] and A[[n/2]....n-l], sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one.
3) Define Binary Search
Binary Search is remarkably efficient algorithm for searching in a sorted array. It works by comparing a search key K with the array's 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 for the second half if K > A[m]
A[0].............A[m-l] A[m] A[m+l]............. A[n-l]
4) What can we say about the average case efficiency of binary search?
A sophisticated analysis shows that the average number of key comparisons made by binary search is only slightly smaller than that in the worst case
Cavg(n) » log2n
5) Define Binary Tree
A binary tree T is defined as a finite set of nodes that is either empty or consists of s root and two disjoint binary trees tL, and tr called, respectively the left and right subtree of the root.
6) How divide and conquer technique can be applied to binary trees?
Since the binary tree definition itself divides a binary tree into two smaller structures of the same type, the left subtree and the right subtree, many problems about binary trees can be solved by applying the divide-conquer technique.
7) Explain Internal and External Nodes
To draw the tree's extension by replacing the empty subtrees by special nodes.The extra nodes shown by little squares are called external. The original nodes shown by littile circles are called internal.
8) Define Preorder, inorder and postorder Traversal
PREORDER -The root is visited before the left and right subtrees are visited (in that order)
INORDER -The root is visited after visiting its left subtree but before visiting the right Subtree
POSTORDER - The root is visited after visiting the left and right subtrees(in that order)
9) Define the Internal Path Length
The Internal Path Length I of an extended binary tree is defined as the sum of the lengths of the paths - taken over all internal nodes- from the root to each internal node.
10) Define the External Path Length
The External Path Length E of an extended binary tree is defined as the sum of the lengths of the paths - taken over all external nodes- from the root to each external node.
11) Explain about greedy technique
The greedy technique suggests constructing a solution to an optimization problem 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 and irrevocable.
12) Define 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.
13) Define Minimum Spanning Tree
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.
14) Define min-heap
A min-heap is a complete binary tree in which every element is less than or equal to its children. All the principal properties of heaps remain valid for min-heaps, with some obvious modifications.
15) Define 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.
16) Define Prim's Algorithm
Prim's algorithm is a greedy algorithm for constructing a minimum spanning tree of a weighted connected graph.It works by attaching to a previously constructed subtree a vertex to the vertices already in the tree.
17) Explain Dijkstra's Algorithm
Dijkstra's algorithm solves the single - source shortest - path problem of finding shortest paths from a given vertex (the source) to all the other vertices of a weighted graph or digraph. It works as prim's algorithm but compares path lengths rather than edge lengths. Dijkstra's algorithm always yields a correct solution for a graph with nonnegative weights.
UNIT III
1)Define Dynamic Programming
Dynamic programming is a technique for solving problems with overlapping problems. Typically, these subproblems arise from a recurrence relating a solution to a given problem with solutions to its smaller subproblems of the same type. Rather than solving overlapping subproblems again and again, dynamic programming suggests solving each of the smaller sub problems only once and recording the results in a table from which we can then obtain a solution to the original problem.
2) Define Binomial Coefficient
n
The Binomial Coefficient, denoted C(n,k) or k is the number of Combinations(subsets) of k elements from an n-element set(0<k<n). The name "binomial coefficients" comes from the participation of these numbers in the so called binomial formula
(a+b)n =(n,0)an+..........+C(n,i)an-ibi+.......+C(n,n)bn
3) Define Transitive closure
The transitive closure of a directed graph with n vertices can be defined as the n by n Boolean matrix T = {ti,}, in which the element in the ith row (1<i<n) and the jthcolumn (l<j<n) is 1 if there exists a non trivial directed path from the ith vertex to jth vertex ; otherwise , tijis 0.
4) Explain Warshalls algorithm
Warshall's algorithm constructs the transitive closure of a given digraph with n vertices through a series of n by n Boolean matrices R(0), ………, R(k-l)R(k),…….., R(n)
Each of these matrices provides certain information about directed paths in the digraph.
4) Explain All-pair shortest-paths problem
Given a weighted connected graph (undirected or directed), the all pairs shortest paths problem asks to find the distances(the lengths of the shortest path) from each vertex to all other vertices.
5) Explain Floyd's algorithm
It is convenient to record the lengths of shortest paths in an n by n matrix D called the distance matrix: the element dijin the ith row and the jth column of this matrix indicates the length of the shortest path from the ith vertex to the jthvertex . We can generate the distance matrix with an algorithm that is very similar to warshall's algorithm. It is called Floyd's algorithm.
6) What does Floyd’s algorithm do?
It is used to find the distances (the lengths of the shortest paths) from each vertex to all other vertices of a weighted connected graph.
7) Explain principle of Optimality
It says that an optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances.
8) Explain Optimal Binary Search Trees
One of the principal application of Binary Search Tree is to implement the operation of searching. If probabilities of searching for elements of a set are known, it is natural to pose a question about an optimal binary search tree for which the average number of comparisons in a search is the smallest possible.
9) Explain Knapsack problem
Given n items of known weights w1,w2...........wnand values v1,v2............vn and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack.(Assuming all the weights and the knapsack's capacity are positive integers the item values do not have to be integers.)
10) Explain the Memory Function technique
The Memory Function technique seeks to combine strengths of the top down and bottom-up approaches to solving problems with overlapping subproblems. It does this by solving, in the top-down fashion but only once, just necessary sub problems of a given problem and recording their solutions in a table.
11) Explain ²Traveling salesman problem”?
A salesman has to travel n cities starting from any one of the cities and visit the remaining cities exactly once and come back to the city where he started his journey in such a manner that either the distance is minimum or cost is minimum. This is known as traveling salesman problem.
UNIT IV
l) Explain Backtracking
The principal idea is to construct solutions one component at a time and evaluate such partially constructed candidates as follows.
> If a partially constructed solution can be developed further without violating the problem's constraints, it is done by taking the first remaininig legitimate option for the next component.
> If there is no legitimate option for the next component, no alternatives for any remaining component need to be considered.
In this case, the algorithm backtracks to replace the last component of the partially constructed solution with its next option
2) Explain State Space Tree
If it is convenient to implement backtracking by constructing a tree of choices being made, the tree is called a state space tree. Its root represents an initial state before the search for a solution begins.
3) Explain promising and nonpromising node
A node in a state space tree is said to be promising if it corresponds to a partially constructed solution that may still lead to a complete solution;otherwise it is called nonpromising
4) Explain n-Queens problem
The problem is to place n queens on an n by n chessboard so that no two queens attack each other by being in the same row or same column or on the same diagonal.
5) Explain Subset-Sum Problem
We consider the subset-sum problem: Find a subset of a given
set S={S1,S2,..........Sn} of n positive integers whose sum is equal to a given positive integer d.
6) Explain Branch and Bound Technique
Compared to backtracking, branch and bound requires
The idea to be strengthened further if we deal with an optimization problem, one that seeks to minimize or maximize an objective function, usually subject to some constraints.
7) Define Feasible Solution
A feasible solution is a point in the problem's search space that satisfies all the problem's constraints.
Ex: A Hamiltonian Circuit in the traveling salesman problem. A subset of items whose total weight does not exceed the knapsack's Capacity
8) Define Optimal solution
Is a feasible solution with the best value of the objective function
Eg: The shortest Hamiltonian Circuit
The most valuable subset of items that fit the knapsack
9)Mention two reasons to terminate a search path at the current node in a state-space tree of a branch and bound algorithm.
The value of the node's bound is not better than the value of the best solution seen so far. The node represents no feasible solutions because the constraints of the problem are already violated.
10) Explain ²Graph coloring” problem.
The graph coloring problem asks us to assign the smallest number of colors to vertices of a graph so that no two adjacent vertices are the same color.
11) Explain Knapsack Problem
Find the most valuable subset of n items of given positive integer weights and values that fit into a knapsack of a given positive integer capacity.
UNIT V
1) Define tractable and intractable problems
Problems that can be solved in polynomial time are called tractable problems, problems that cannot be solved in polynomial time are called intractable problems.
2) Explain the theory of computational complexity
A problem's intractability remains the same for all principal models of computations and all reasonable input encoding schemes for the problem under consideration
3)Explain class P problems
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.
4)Explain undecidable problems
If the decision problem cannot be solved in polynomial time, and if the decision problems cannot be solved at all by any algorithm. Such problems are called Undecidable.
5) Explain the halting problem
Given a computer program and an input to it,determine whether the program will halt on that input or continue working indefinitely on it.
6) Explain class NP problems
Class NP is the class of decision problems that can be solved by nondeterministic polynomial algorithms.Most decision problems are in NP. First of all, this class includes all the problems in P. This class of problems is called Nondeterministic polynomial.
7)Explain NP-complete problems
A decision problem d is said to be NP-complete if
1) it belongs to class NP
2) every problem in NP is polynomially reducible to D.
8)When a decision problem is said to be polynomially reducible
A decision problem Dl is said to be polynomially reducible to a decision problem D2 if there exists a function t that transforms instances of Dl to instances ofD2 such that
i) t maps all yes instances of d1 to yes instances odf d2 and all no instances of dl to no instances ofd2
ii) t is computable by a polynomial time algorithm
9) Define a Heuristic
A heuristic is a common-sense rule drawn from experience rather than from a mathematically proved assertion.
Ex: Going to the nearest unvisited city in the traveling salesman problem is a good illustration for Heuristic
10) Explain NP-Hard problems
The notion of an NP-hard problem can be defined more formally by extending the notion of polynomial reducability to problems that are not necessary in class NP including optimization problems.
11)Define Traversals.
When the search necessarilyinvolves the examination of every vertex in the object being searched it is called a traversal.
12)List out the techniques for traversals in graph.
Breadth first search
Depth first search
13)What is articulation point.
A vertex v in a connected graph G is an articulation point if and only if the deletion of vertex v together with all edged incident to v disconnects the graph in to two or more nonempty components.
PART-B
I-UNIT
1. (a) Describe the steps in analyzing & coding an algorithm. (10)
(b) Explain some of the problem types used in the design of
algorithm. (6)
2.(a) Discuss the fundamentals of analysis framework . (10)
(b) Explain the various asymptotic notations used in algorithm design. (6)
3. (a) Explain the general framework for analyzing the efficiency of algorithm. (8)
(b) Explain the various Asymptotic efficiencies of an algorithm. (8)
4. (a) Explain the basic efficiency classes. (10)
(b) Explain briefly the concept of algorithmic strategies. (6)
5. Describe briefly the notions of complexity of an algorithm. (16)
6. (a) What is Pseudo-code?Explain with an example. (8)
(b) Find the complexity C(n) of the algorithm for the worst
case,best case and average case.(Evaluate average case complexity for n=3,Where n is the
number of inputs) (8)
7. Set up & solve a recurrence relation for the number of key comparisons made by above
pseudo code. (4)
II-UNIT
1) Write a pseudo code for divide & conquer algorithm for merging two sorted arrays in to a single sorted one.Explain with example. (12)
2) Construct a minimum spanning tree using Kruskal’s algorithm with your own example. (10)
3)Explain about Knapsack Problem with example
4) Explain Dijikstra algorithm (8)
5) Define Spanning tree.Discuss design steps in Prim’s algorithm to construct minimum spanning
tree with an example. (16)
6)Explain Kruskal’s algorithm. (8)
7)Explain about binary search with example.
III-UNIT
1) Solve the all pair shortest path problem for the diagraph with the weighted matrix given below:-
a b c d
a 0 ∞ 3 ∞
b 2 0 ∞ ∞
c ∞ 7 0 1
d 6 ∞ ∞ 0(16)
2) Explain Warshall’s & Floyd’s Algorithm. (16)
3) Explain about Multistage graphs with example.
4) Define optimal binary search trees with example.
5) Explain 0/1 knapsack problem with example.
6) Discuss the solution for Travelling salesman problem using branch & bound technique. (16)
VI-UNIT
1. Explain the 8-Queen’s problem & discuss the possible solutions. (16)
2. Solve the following instance of the knapsack problem by the branch & bound algorithm. (16)
3. Apply backtracking technique to solve the following instance of subset sum problem :
S={1,3,4,5} and d=11 (16)
5. Explain subset sum problem & discuss the possible solution strategies using backtracking.(16)
6. Explain Graph coloring with example.
7. Explain about Knapsack Problem using back tracking with example.
V-UNIT
1. Give a suitable example & explain the Breadth first search & Depth first search. (16)
2. Explain about biconnected components with example.
3. Briefly explain NP-Hard and NP-Completeness with examples.
4. Explain about 0/1 Knapsack Problem using branch and bound with example.
CS 2251 DESIGN AND ANALYSIS OF ALGORITHMS 3 1 0 4
Algorithm Analysis – Time Space Tradeoff – Asymptotic Notations – Conditional asymptotic notation – Removing condition from the conditional asymptotic notation - Properties of big-Oh notation – Recurrence equations – Solving recurrence equations – Analysis of linear search.
UNIT II 9
Divide and Conquer: General Method – Binary Search – Finding Maximum and Minimum – Merge Sort – Greedy Algorithms: General Method – Container Loading – Knapsack Problem.
Dynamic Programming: General Method – Multistage Graphs – All-Pair shortest paths – Optimal binary search trees – 0/1 Knapsack – Travelling salesperson problem .
UNIT IV 9
Backtracking: General Method – 8 Queens problem – sum of subsets – graph coloring – Hamiltonian problem – knapsack problem.
UNIT V 9
Graph Traversals – Connected Components – Spanning Trees – Biconnected components – Branch and Bound: General Methods (FIFO & LC) – 0/1 Knapsack problem – Introduction to NP-Hard and NP-Completeness.
TUTORIAL = 15 Total = 60
TEXT BOOK:
1. Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, Computer Algorithms/ C++, Second Edition, Universities Press, 2007. (For Units II to V)
2. K.S. Easwarakumar, Object Oriented Data Structures using C++, Vikas Publishing House pvt. Ltd., 2000 (For Unit I)
REFERENCES:
1. T. H. Cormen, C. E. Leiserson, R.L.Rivest, and C. Stein, "Introduction to Algorithms", Second Edition, Prentice Hall of India Pvt. Ltd, 2003.
2. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, "The Design and Analysis of Computer Algorithms", Pearson Education, 1999.
Welcome to i-education
1. What is an Algorithm? May/June 2006, Nov/Dec 2008
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time
2. State the Euclid
ALGORITHM Euclid
// Computes gcd(m,n) by Euclid
//Input : Two nonnegative, not-both-zero integers mand n
//Output: Greatest common divisor of m and n
while n ¹ 0 do
r ß m mod n
m ß n
n ß r
return m.
3. What are Sequential Algorithms?
The central assumption of the RAM model is that instructions are executed one after another, one operation at a time. Accordingly, algorithms designed to be executed on such machines are called Sequential algorithms.
4. What are Parallel Algorithms?
The central assumption of the RAM model does not hold for some newer computers that can execute operations concurrently, i.e., in parallel algorithms that take advantage of this capability are called Parallel algorithms.
5. What is Exact and Approximation algorithm?
The principal decision to choose solving the problem exactly is called exact algorithm.
The principal decision to choose solving the problem approximately is called Approximation algorithm.
6. What is Algorithm Design Technique? Nov/Dec 2005
An algorithm design technique is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.
7. Define Pseudo code.
8. Define Flowchart.
A method of expressing an algorithm by a collection of connected geometric shapes containing descriptions of the algorithm’s steps.
9. Explain Algorithm’s Correctness
To prove that the algorithm yields a required result for every legitimate input in a finite amount of time.
Example: Correctness of Euclid
10. What is Efficiency of algorithm?
Efficiency of an algorithm can be precisely defined and investigated with mathematical rigor. There are two kinds of algorithm efficiency
1) Time Efficiency – Indicates how fast the algorithm runs
2) Space Efficiency – Indicates how much extra memory the algorithm needs.
11. What is generality of an algorithm?
It is a desirable characteristic of an algorithm. Generality of the problem the algorithm solves is sometimes easier to design an algorithm for a problem posed in more general terms.
12. What is algorithm’s Optimality?
Optimality is about the complexity of the problem that algorithm solves. What is the minimum amount of effort any algorithm will need to exert to solve the problem in question is called algorithm’s Optimality.
13. What do you mean by ²Sorting” problem?
The sorting problem asks us to rearrange the items of a given list in ascending order (or descending order)
14. What do you mean by ²Searching” problem?
The searching problem deals with finding a given value, called a search key, in a given set.
15. What do you mean by ²Worst case-Efficiency” of an algorithm?
The ²Worst case-Efficiency” of an algorithm is its efficiency for the worst-case input of size n, which is an input (or inputs) of size n for which the algorithm runs the longest among all possible inputs of that size.
Ex: if you want to sort a list of numbers in ascending order when the numbers are given in descending order. In this running time will be the longest.
16. What do you mean by ²Best case-Efficiency” of an algorithm?
The ²Best case-Efficiency” of an algorithm is its efficiency for the Best-case input of size n, which is an input(or inputs) of size n for which the algorithm runs the fastest among all possible inputs of that size.
Ex: if you want to sort a list of numbers in ascending order when the numbers are given in ascending order. In this running time will be the smallest.
17. Define the ²Average-case efficiency” of an algorithm?
The ²Average-case efficiency” of an algorithm is its efficiency for the input of size n, for which the algorithm runs between the best case and the worst case among all possible inputs of that size.
18. What do you mean by “Amortized efficiency”?
The “Amortized efficiency” applies not only a single run of an algorithm but rather to a sequence of operations performed on the same data structure. It turns out that in some situations a single operation can be expensive ,but the total time for an entire sequence of n such operations is always significantly better than the worst case efficiency of that single operation multiplied by n. This is known as “Amortized efficiency”.
19. How to measure the algorithm’s efficiency?
It is logical to investigate the algorithm’s efficiency as a function of some parameter n indicating the algorithm’s input size.
Example: It will be the size of the list for problems of sorting, searching, finding the list’s smallest element, and most other problems dealing with lists.
20. What is called the basic operation of an algorithm?
The most important operation of the algorithm is the operation contributing the most to the total running time is called basic operation of an algorithm.
21. How to measure an algorithm’s running time?
Let Cop be the time of execution of an algorithm’s basic iteration on a particular computer and let C (n) be the number of times this operation needs to be executed for this algorithm. Then we can estimate the running time T(n) of a program implementing this algorithm on that computer by the formula
T(n) ≈ CopC(n)
22. Define order of growth.
The efficiency analysis framework concentrates on the order of growth of an algorithm’s basic operation count as the principal indicator of the algorithm’s efficiency. To compare and rank such orders of growth we use three notations
1) O (Big oh) notation
2) Ω (Big Omega) notation &
3) Θ (Big Theta) notation
23. Define Big oh notation May/June 2006, April/May 2008
A function t(n) is said to be in O(g(n)) denoted t(n) ε O (g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some non negative integer n0 such that
T (n) < c g (n) for n >n0
24. Prove that 100n+5 Î O (n2)?
Clearly 100n+5 £ 100n+n (for all n ³ 5) = 101n£101n2
By choosing n0=5 and c=101 we find that 100n+5ÎO (n2).
25. Define Ω notation
A function t(n) is said to be in Ω (g(n)), denoted t(n) ÎΩ (g(n)), if t(n) is bounded below by some positive constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some non negative integer n0 such that
T (n) < c g (n) for n >n0
26. Prove that n3ÎW(n2)?
Clearly n3 ³ n2 for all n ³ 0. i.e., we can select c=1 and n0=0.
27. Define Θ - notation
A function t(n) is said to be in Θ(g(n)), denoted t(n) ÎΘ (g(n)), if t(n) is bounded both above and below by some positive constant multiples of g(n) for all large n, i.e., if there exist some positive constant c1 and c2 and some non negative integer n0such that
c2g (n) < t (n) < c1 g(n) for n > n0
28. Prove that( ½)n(n-1) Î Q(n2)
1/2n(n-1)=(1/2)n2-1/2n £ 1/2 n2for all n³0.(we have proved upper inequality) now 1/2n(n-1)=(1/2)n2-1/2n³(1/2)n2-1/2n*1/2n(for all n³2)=1/4 n2 hence we can select c2=1/4,c1=1/2 and n0=2.
29. What is the use of Asymptotic Notations?
The notations O, W and Q and are used to indicate and compare the asymptotic orders of growth of functions expressing algorithm efficiencies.
UNIT II
1) Explain divide and conquer algorithms
Divide and conquer is probably the best known general algorithm design technique. It work according to the following general plan
i)A problem's instance is divided into several smaller instances of the same problem, ideally of about the same size.
ii) The smaller instances are solved
iii) If necessary, the solutions obtained for the smaller instances are combined to get a solution to the original problem
2) Define Merge Sort
Merge sort is a perfect example of a successful application of the divide and conquer technique. It sorts a given array A[0...n-l] by dividing it into two halves A[0...[n/2] - 1] and A[[n/2]....n-l], sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one.
3) Define Binary Search
Binary Search is remarkably efficient algorithm for searching in a sorted array. It works by comparing a search key K with the array's 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 for the second half if K > A[m]
A[0].............A[m-l] A[m] A[m+l]............. A[n-l]
4) What can we say about the average case efficiency of binary search?
A sophisticated analysis shows that the average number of key comparisons made by binary search is only slightly smaller than that in the worst case
Cavg(n) » log2n
5) Define Binary Tree
A binary tree T is defined as a finite set of nodes that is either empty or consists of s root and two disjoint binary trees tL, and tr called, respectively the left and right subtree of the root.
6) How divide and conquer technique can be applied to binary trees?
Since the binary tree definition itself divides a binary tree into two smaller structures of the same type, the left subtree and the right subtree, many problems about binary trees can be solved by applying the divide-conquer technique.
7) Explain Internal and External Nodes
To draw the tree's extension by replacing the empty subtrees by special nodes.The extra nodes shown by little squares are called external. The original nodes shown by littile circles are called internal.
8) Define Preorder, inorder and postorder Traversal
PREORDER -The root is visited before the left and right subtrees are visited (in that order)
INORDER -The root is visited after visiting its left subtree but before visiting the right Subtree
POSTORDER - The root is visited after visiting the left and right subtrees(in that order)
9) Define the Internal Path Length
The Internal Path Length I of an extended binary tree is defined as the sum of the lengths of the paths - taken over all internal nodes- from the root to each internal node.
10) Define the External Path Length
The External Path Length E of an extended binary tree is defined as the sum of the lengths of the paths - taken over all external nodes- from the root to each external node.
11) Explain about greedy technique
The greedy technique suggests constructing a solution to an optimization problem 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 and irrevocable.
12) Define 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.
13) Define Minimum Spanning Tree
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.
14) Define min-heap
A min-heap is a complete binary tree in which every element is less than or equal to its children. All the principal properties of heaps remain valid for min-heaps, with some obvious modifications.
15) Define 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.
16) Define Prim's Algorithm
Prim's algorithm is a greedy algorithm for constructing a minimum spanning tree of a weighted connected graph.It works by attaching to a previously constructed subtree a vertex to the vertices already in the tree.
17) Explain Dijkstra's Algorithm
Dijkstra's algorithm solves the single - source shortest - path problem of finding shortest paths from a given vertex (the source) to all the other vertices of a weighted graph or digraph. It works as prim's algorithm but compares path lengths rather than edge lengths. Dijkstra's algorithm always yields a correct solution for a graph with nonnegative weights.
UNIT III
1)Define Dynamic Programming
Dynamic programming is a technique for solving problems with overlapping problems. Typically, these subproblems arise from a recurrence relating a solution to a given problem with solutions to its smaller subproblems of the same type. Rather than solving overlapping subproblems again and again, dynamic programming suggests solving each of the smaller sub problems only once and recording the results in a table from which we can then obtain a solution to the original problem.
2) Define Binomial Coefficient
n
The Binomial Coefficient, denoted C(n,k) or k is the number of Combinations(subsets) of k elements from an n-element set(0<k<n). The name "binomial coefficients" comes from the participation of these numbers in the so called binomial formula
(a+b)n =(n,0)an+..........+C(n,i)an-ibi+.......+C(n,n)bn
3) Define Transitive closure
The transitive closure of a directed graph with n vertices can be defined as the n by n Boolean matrix T = {ti,}, in which the element in the ith row (1<i<n) and the jthcolumn (l<j<n) is 1 if there exists a non trivial directed path from the ith vertex to jth vertex ; otherwise , tijis 0.
4) Explain Warshalls algorithm
Warshall's algorithm constructs the transitive closure of a given digraph with n vertices through a series of n by n Boolean matrices R(0), ………, R(k-l)R(k),…….., R(n)
Each of these matrices provides certain information about directed paths in the digraph.
4) Explain All-pair shortest-paths problem
Given a weighted connected graph (undirected or directed), the all pairs shortest paths problem asks to find the distances(the lengths of the shortest path) from each vertex to all other vertices.
5) Explain Floyd's algorithm
It is convenient to record the lengths of shortest paths in an n by n matrix D called the distance matrix: the element dijin the ith row and the jth column of this matrix indicates the length of the shortest path from the ith vertex to the jthvertex . We can generate the distance matrix with an algorithm that is very similar to warshall's algorithm. It is called Floyd's algorithm.
6) What does Floyd’s algorithm do?
It is used to find the distances (the lengths of the shortest paths) from each vertex to all other vertices of a weighted connected graph.
7) Explain principle of Optimality
It says that an optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances.
8) Explain Optimal Binary Search Trees
One of the principal application of Binary Search Tree is to implement the operation of searching. If probabilities of searching for elements of a set are known, it is natural to pose a question about an optimal binary search tree for which the average number of comparisons in a search is the smallest possible.
9) Explain Knapsack problem
Given n items of known weights w1,w2...........wnand values v1,v2............vn and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack.(Assuming all the weights and the knapsack's capacity are positive integers the item values do not have to be integers.)
10) Explain the Memory Function technique
The Memory Function technique seeks to combine strengths of the top down and bottom-up approaches to solving problems with overlapping subproblems. It does this by solving, in the top-down fashion but only once, just necessary sub problems of a given problem and recording their solutions in a table.
11) Explain ²Traveling salesman problem”?
A salesman has to travel n cities starting from any one of the cities and visit the remaining cities exactly once and come back to the city where he started his journey in such a manner that either the distance is minimum or cost is minimum. This is known as traveling salesman problem.
UNIT IV
l) Explain Backtracking
The principal idea is to construct solutions one component at a time and evaluate such partially constructed candidates as follows.
> If a partially constructed solution can be developed further without violating the problem's constraints, it is done by taking the first remaininig legitimate option for the next component.
> If there is no legitimate option for the next component, no alternatives for any remaining component need to be considered.
In this case, the algorithm backtracks to replace the last component of the partially constructed solution with its next option
2) Explain State Space Tree
If it is convenient to implement backtracking by constructing a tree of choices being made, the tree is called a state space tree. Its root represents an initial state before the search for a solution begins.
3) Explain promising and nonpromising node
A node in a state space tree is said to be promising if it corresponds to a partially constructed solution that may still lead to a complete solution;otherwise it is called nonpromising
4) Explain n-Queens problem
The problem is to place n queens on an n by n chessboard so that no two queens attack each other by being in the same row or same column or on the same diagonal.
5) Explain Subset-Sum Problem
We consider the subset-sum problem: Find a subset of a given
set S={S1,S2,..........Sn} of n positive integers whose sum is equal to a given positive integer d.
6) Explain Branch and Bound Technique
Compared to backtracking, branch and bound requires
The idea to be strengthened further if we deal with an optimization problem, one that seeks to minimize or maximize an objective function, usually subject to some constraints.
7) Define Feasible Solution
A feasible solution is a point in the problem's search space that satisfies all the problem's constraints.
Ex: A Hamiltonian Circuit in the traveling salesman problem. A subset of items whose total weight does not exceed the knapsack's Capacity
8) Define Optimal solution
Is a feasible solution with the best value of the objective function
Eg: The shortest Hamiltonian Circuit
The most valuable subset of items that fit the knapsack
9)Mention two reasons to terminate a search path at the current node in a state-space tree of a branch and bound algorithm.
The value of the node's bound is not better than the value of the best solution seen so far. The node represents no feasible solutions because the constraints of the problem are already violated.
10) Explain ²Graph coloring” problem.
The graph coloring problem asks us to assign the smallest number of colors to vertices of a graph so that no two adjacent vertices are the same color.
11) Explain Knapsack Problem
Find the most valuable subset of n items of given positive integer weights and values that fit into a knapsack of a given positive integer capacity.
UNIT V
1) Define tractable and intractable problems
Problems that can be solved in polynomial time are called tractable problems, problems that cannot be solved in polynomial time are called intractable problems.
2) Explain the theory of computational complexity
A problem's intractability remains the same for all principal models of computations and all reasonable input encoding schemes for the problem under consideration
3)Explain class P problems
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.
4)Explain undecidable problems
If the decision problem cannot be solved in polynomial time, and if the decision problems cannot be solved at all by any algorithm. Such problems are called Undecidable.
5) Explain the halting problem
Given a computer program and an input to it,determine whether the program will halt on that input or continue working indefinitely on it.
6) Explain class NP problems
Class NP is the class of decision problems that can be solved by nondeterministic polynomial algorithms.Most decision problems are in NP. First of all, this class includes all the problems in P. This class of problems is called Nondeterministic polynomial.
7)Explain NP-complete problems
A decision problem d is said to be NP-complete if
1) it belongs to class NP
2) every problem in NP is polynomially reducible to D.
8)When a decision problem is said to be polynomially reducible
A decision problem Dl is said to be polynomially reducible to a decision problem D2 if there exists a function t that transforms instances of Dl to instances ofD2 such that
i) t maps all yes instances of d1 to yes instances odf d2 and all no instances of dl to no instances ofd2
ii) t is computable by a polynomial time algorithm
9) Define a Heuristic
A heuristic is a common-sense rule drawn from experience rather than from a mathematically proved assertion.
Ex: Going to the nearest unvisited city in the traveling salesman problem is a good illustration for Heuristic
10) Explain NP-Hard problems
The notion of an NP-hard problem can be defined more formally by extending the notion of polynomial reducability to problems that are not necessary in class NP including optimization problems.
11)Define Traversals.
When the search necessarilyinvolves the examination of every vertex in the object being searched it is called a traversal.
12)List out the techniques for traversals in graph.
Breadth first search
Depth first search
13)What is articulation point.
A vertex v in a connected graph G is an articulation point if and only if the deletion of vertex v together with all edged incident to v disconnects the graph in to two or more nonempty components.
PART-B
I-UNIT
1. (a) Describe the steps in analyzing & coding an algorithm. (10)
(b) Explain some of the problem types used in the design of
algorithm. (6)
2.(a) Discuss the fundamentals of analysis framework . (10)
(b) Explain the various asymptotic notations used in algorithm design. (6)
3. (a) Explain the general framework for analyzing the efficiency of algorithm. (8)
(b) Explain the various Asymptotic efficiencies of an algorithm. (8)
4. (a) Explain the basic efficiency classes. (10)
(b) Explain briefly the concept of algorithmic strategies. (6)
5. Describe briefly the notions of complexity of an algorithm. (16)
6. (a) What is Pseudo-code?Explain with an example. (8)
(b) Find the complexity C(n) of the algorithm for the worst
case,best case and average case.(Evaluate average case complexity for n=3,Where n is the
number of inputs) (8)
7. Set up & solve a recurrence relation for the number of key comparisons made by above
pseudo code. (4)
II-UNIT
1) Write a pseudo code for divide & conquer algorithm for merging two sorted arrays in to a single sorted one.Explain with example. (12)
2) Construct a minimum spanning tree using Kruskal’s algorithm with your own example. (10)
3)Explain about Knapsack Problem with example
4) Explain Dijikstra algorithm (8)
5) Define Spanning tree.Discuss design steps in Prim’s algorithm to construct minimum spanning
tree with an example. (16)
6)Explain Kruskal’s algorithm. (8)
7)Explain about binary search with example.
III-UNIT
1) Solve the all pair shortest path problem for the diagraph with the weighted matrix given below:-
a b c d
a 0 ∞ 3 ∞
b 2 0 ∞ ∞
c ∞ 7 0 1
d 6 ∞ ∞ 0(16)
2) Explain Warshall’s & Floyd’s Algorithm. (16)
3) Explain about Multistage graphs with example.
4) Define optimal binary search trees with example.
5) Explain 0/1 knapsack problem with example.
6) Discuss the solution for Travelling salesman problem using branch & bound technique. (16)
VI-UNIT
1. Explain the 8-Queen’s problem & discuss the possible solutions. (16)
2. Solve the following instance of the knapsack problem by the branch & bound algorithm. (16)
3. Apply backtracking technique to solve the following instance of subset sum problem :
S={1,3,4,5} and d=11 (16)
5. Explain subset sum problem & discuss the possible solution strategies using backtracking.(16)
6. Explain Graph coloring with example.
7. Explain about Knapsack Problem using back tracking with example.
V-UNIT
1. Give a suitable example & explain the Breadth first search & Depth first search. (16)
2. Explain about biconnected components with example.
3. Briefly explain NP-Hard and NP-Completeness with examples.
4. Explain about 0/1 Knapsack Problem using branch and bound with example.
0 comments:
Post a Comment