**Design And Analysis of Algorithm Important Questions For External Exams**

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

2 Marks

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 bi±(ai

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

v Decide on a parameter indicating input’s size.

v Identify the algorithms basic operation.

v Check whether the number of times the basic operation is
executed depends on size of input. If it depends on some additional property
the worst, average and best-case efficiencies have to be investigated
separately.

v Set up a sum expressing the number of times the
algorithm’s basic operation is executed.

v Using standard formulas and rules of manipulation, find
a closed-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ÃŸC[I,j] ] + A[I,k]*B[k,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

v Decide on a parameter indicating input’s size.

v Identify the algorithms basic operation.

v Check whether the number of times the basic operation is
executed depends on size of input. If it depends on some additional property
the worst, average and best-case efficiencies have to be investigated
separately.

v Set up a recurrence relation with the appropriate
initial condition , for the number of times the basic operation is executed.

v Solve 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

v To move n>1 disks from peg1 to peg3, with peg2 as
auxiliary, first move recursively n-1 disks from peg1 to peg2 with peg3 as
auxiliary.

v Then move the largest disk directly from peg1 to peg3

v Finally move recursively n-1 disks from peg2 to peg3
with peg1 as auxiliary

v If 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
fibonacci number that manipulates only integers. It is based on the equalityQThere
exists a

= 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

v Understand the experiment’s purpose.

v Decide on the efficiency metric M to be measured &
the measurement unit.

v Decide on characteristics of the input sample

v Prepare a program implementing the algorithm for the
experimentation

v Generate a sample of inputs

v Run the algorithm on the sample input and record the
data observed

v Analyze 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”

v Static algorithm visualization: It shows the algorithm’s
progress through a series of still images

v Dynamic 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

v Be consistent

v Be interactive

v Be clear and concise

v Be forgiving to the user

v Adapt to the knowledge level of the user

v Emphasize the visual component

v Keep the user interested

v Incorporate both symbolic and iconic representations

v Include algorithm’s analysis & comparisons with
other algorithms for the same problem

v Include execution history

26. What are the applications of algorithm
visualization?

The two applications are

v Research: Based on expectations that algorithm
visualization may help uncover some unknown feature of the algorithm

v Education: 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

2 Marks

1. Define Brute force approach?

Brute force is a straightforward approach to
solving a problem, usually directly based on the problem’s statement and
definitions of the concepts involved. The brute force approach is one that is
easiest to apply.

2. What are the advantages of brute force
technique?

The various advantages of brute force
technique are

v Brute force applicable to a very wide variety of
problems. It is used for many elementary but important algorithmic tasks

v For some important problems this approach yields
reasonable algorithms of at least some practical value with no limitation on
instance size

v The expense to design a more efficient algorithm may be
unjustifiable if only a few instances of problems need to be solved and a brute
force algorithm can solve those instances with acceptable speed

v Even if inefficient in general it can still be used for
solving small-size instances of a problem

v It can serve as a yardstick with which to judge more
efficient alternatives for solving a problem

3. What is selection sort?

Selection sort is started by scanning the
entire list to find the smallest element and exchange it with the first
element, putting the first element in the final position in the sorted list.
Then the scan starts from the second element to find the smallest among n-1
elements and exchange it with the second element.

A0 A1 ………… Ai-1 | Ai……..…,Amin,………,An-1

In their final position The last n-I elements

4. Mention the pseudocode for selection sort.

ALGORITHM SelectionSort(A[0..n-1])

//The algorithm sorts a given array by
selection sort

//Input: An array A[0..n-1] of orderable
elements

//Output: Array A[0..n-1] sorted in ascending
order

0 to n-2 doÃŸfor
I

IÃŸmin

I+1 to n-1 doÃŸfor
j

if A[j] < jÃŸA[min]
min

swap A[I] and A[min]

5. What is bubble sort?

Another brute force approach to sort a
problem is to compare adjacent elements of the list and exchange them if they
are out of order, so we end up “bubbling up” the largest element to the last
position in the list. The next pass bubbles up the second largest element, and
so on until n-1 passes , the list is sorted. Pass I can be represented as
follows

?

A0,……, Aj Aj+1,……, An-I-1 | An-I …… An-1

In their final positions

6. Give an algorithm for bubble sort?

ALGORITHM BubbleSort(A[0..n-1])

//The algorithm sorts array A[0..n-1] by
bubble sort

//Input: An array A[0..n-1] of orderable
elements

//Output: Arrar A[0..n-1] sorted in ascending
order

0 to n-2 doÃŸfor
I

0 to n-2-I doÃŸfor
j

if A[j+1]<A[j] swap A[j] and A[j+1]

7. Give the benefit of application of brute
force technique to solve a problem.

With the application of brute force strategy,
the first version of an algorithm obtained can often be improved with a modest
amount of effort. So a first application of the brute force approach often
results in an algorithm that can be improved with a modest amount of effort.

8. Explain about the enhanced version of
sequential search.

Sequential search simply compares successive
elements of a list with a given search key until either a match is encountered
or the list is exhausted without finding a match. The enhancement in this
version is to append the search key to the end of the list , then the search
for the key will have to be successful & so we can eliminate a check for
the list’s end on each iteration.

9. Give the algorithm for the enhanced
version of sequential search.

ALGORITHM SequentialSearch2(A[0..n-1],K)

//The algorithm implements sequential search
with the search key as sentinael

//Input: An array A of n elements and a
search key K

//Output: The position of the first element
in a[0..n-1] whose value is equal to K or //–1 if no such element is found

KÃŸA[n]

0ÃŸI

K do¹while A[I]

I+1ÃŸI

If I < n return I

else return -1

10. What is the improvement that can be
applied to sequential search if the list is sorted?

The straightforward improvement that can be
incorporated in sequential search if a given list is known to be sorted is that
searching in the list can be stopped as soon as an element greater than or
equal to the search key is encountered.

11. Define brute force string matching.

The brute force string matching has a given
string of n characters called the text and a string of m characters called the
pattern, find a substring of the text that matches the pattern. And find the
index I of the leftmost character of the first matching substring in the text.

12. Mention the algorithm for brute force
string matching

ALGORITHM
BruteForceStringMatching(T[0..n-1],P[0..m-1])

//The algorithm implements brute force string
matching

//Input: an array T[0..n-1] of n characters
representing text

//An array P[0..m-1] of m characters
representing pattern

//Output : The position of the first
characters in the text that starts the first //matching substring if search is
successful and –1 otherwise

0 to n-m doÃŸfor
I

0ÃŸj

while j < m and P[j] = T[I+j] do

j+1ÃŸj

if j =m return I

return –1

13. Give the general plan for
divide-and-conquer algorithms.

The general plan is as follows

v A problems instance is divided into several smaller
instances of the same problem, ideally about the same size

v The smaller instances are solved, typically recursively

v If necessary the solutions obtained are combined to get
the solution of the original problem

14. State the Master theorem and its use.

0 in recurrence equation T(n) =
aT(n/b)+f(n), then³(nd) where d q ÃŽIf f(n)

(nd)q if a<bd

ÃŽT(n) (ndlog n)q if a=bd

(nlogba)q if a>bd

The efficiency analysis of many
divide-and-conquer algorithms are greatly simplified by the use of Master
theorem.

15. What is the general divide-and-conquer
recurrence relation?

An instance of size ‘n’ can be divided into
several instances of size n/b, with ‘a’ of them needing to be solved. Assuming
that size ‘n’ is a power of ‘b’, to simplify the analysis, the following
recurrence for the running time is obtained:

T(n) = aT(n/b)+f(n)

Where f(n) is a function that accounts for
the time spent on dividing the problem into smaller ones and on combining their
solutions.

16. Define mergesort.

Mergesort sorts a given array A[0..n-1] by
dividing it into two halves a[0..(n/2)-1] and A[n/2..n-1] sorting each of them
recursively and then merging the two smaller sorted arrays into a single sorted
one.

17. Give the algorithm for mergesort.

ALGORITHM Mergesort(A[0..n-1])

//Sorts an array A[0..n-1] by recursive
mergesort

//Input: An array A[0..n-1] of orderable
elements

//Output: Array A[0..n-1] sorted in
nondecreasing order

if n > 1

copy A[0..(n/2)-1] to B[0..(n/2)-1]

copy A[(n/2)..n-1] to C[0..(n/2)-1]

Mergesort(B[0..(n/2)-1])

Mergesort(C[0..(n/2)-1])

Merge(B,C,A)

18. Give the algorithm to merge two sorted
arrays into one.

ALGORITHM Merge(B[0..p-1], C[0..q-1],
A[0..p+q-1])

//Merges two sorted arrays into one sorted array

//Input: arrays B[0..p-1] and C[0..q-1] both
sorted

//Output: sorted array A[0..p+q-1] of the
elements of B & C

0ÃŸ 0; k ÃŸ 0; j ÃŸI

while I < p and j < q do

C[j]£if B[I]

I+1ÃŸ B[I]; I ÃŸA[k]

else

j+1ÃŸ C[j]; j ÃŸA[k]

k+1ÃŸk

if I = p

copy C[j..q-1] to A[k..p+q-1]

else

copy B[i..p-1] to A[k..p+q-1]

19. What is the difference between
quicksort and mergesort?

Both quicksort and mergesort use the
divide-and-conquer technique in which the given array is partitioned into
subarrays and solved. The difference lies in the technique that the arrays are
partitioned. For mergesort the arrays are partitioned according to their
position and in quicksort they are partitioned according to the element values.

20. Give the algorithm for Quicksort.

ALGORITHM Quicksort(A[l..r])

//Sorts a array by quicksort

//Input: A subarray A[l..r] of A[0..n-1],
defined by the left and right indices l & r

//Output: the subarray A[l..r] sorted in
nondecreasing order

if l < r

Partition(A[l..r])ÃŸs

Quicksort(A[l..s-1])

Quicksort(A[s+1..r])

21. Mention the algorithm used to partition
an array for quicksort.

ALGORITHM Partition(A[l..r])

//Partitions a subarray using the first
element as pivot

//Input: A subarray A[l..r] of A[o..n-1]

//Output: A partition of A[l..r] with split
position returned as function’s value

A[l]ÃŸp

r+1ÃŸ l; j ÃŸI

repeat

I+1 until A[I] pÃŸrepeat
I

j-1 until A[j] pÃŸrepeat
j

swap(A[I],A[j])

until i j

swap(A[I],A[j])

swap(A[l],A[j])

return j

22. What is binary search?

Binary search is a remarkably efficient
algorithm for searching in a sorted array. It works by comparing a search key K
with the arrays middle element A[m]. if they match the algorithm stops;
otherwise the same operation is repeated recursively for the first half of the
array if K < A[m] and the second half if K > A[m].

K

A[0]………A[m-1] A[m] A[m+1]………A[n-1]

search here if K<A[m] search here if
K>A[m]

23. What is a binary tree extension and what
is its use?

The binary tree extension can be drawn by
replacing the empty subtrees by special nodes in a binary tree. The extra nodes
shown as little squares are called external & the original nodes shown as
little circles called internal. The extension of a empty binary tree is a
single external node. The binary tree extension helps in analysis of tree
algorithms.

24. What are the classic traversals of a
binary tree?

The classic traversals are as follows

v Preorder traversal: the root is visited before left
& right subtrees

v Inorder traversal: the root is visited after visiting
left subtree and before visiting right subtree

v Postorder traversal: the root is visited after visiting
the left and right subtrees

25. Mention an algorithm to find out the
height of a binary tree.

ALGORITHM Height(T)

//Compares recursively the height of a binary
tree

//Input: A binary tree T

//Output: The height of T

if T = return –1

else return max{Height(TL), Height(TR)}+1

26. Draw the extension tree of the given
binary tree.

27. What is decrease and conquer
approach and mention its variations?

The decrease and conquer technique based on
exploiting the relationship between a solution to a given instance of a problem
and a solution to a smaller instance of the same problem. The three major
variations are

v Decrease by a constant

v Decrease by a constant-factor

v Variable size decrease

28. What is insertion sort?

Insertion sort in an application of
decrease-by-one technique to sort an array A[0..n-1]. We assume that the
smaller problem of sorting an array A[0..n-2] has already been solved to give
us a sorted array of size n-1. Then an appropriate position for A[n-1] is found
among the sorted element and then the element is inserted.

29. Give the algorithm for insertion sort.

//Sorts a given array by insertion sort

//Input: An array A[0..n-1] of n orderable
elements

//Output: Array A[0..n-1] sorted in
non-decreasing order

1 to n-1 doÃŸfor
I

A[I]ÃŸv

I-1ÃŸj

while j 0 and A[j] > v do

A[j]ÃŸA[j+1]

j – 1ÃŸj

vÃŸA[j+1]

30. What is a tree edge and back edge?

In the depth first search forest, whenever a
new unvisited vertex is reached for the first time, it is attached as a child
to the vertex from which it is being reached. Such an edge is called tree edge
because the set of all such edges forms a forest. The algorithm encounters an
edge leading to a previously visited vertex other than its immediate
predecessor. Such an edge is called a back edge because it connects a vertex to
its ancestor, other than the parent, in the depth first search forest.

31. What is a tree edge and cross edge?

In the breadth first search forest, whenever
a new unvisited vertex is reached for the first time, it is attached as a child
to the vertex from which it is being reached. Such an edge is called tree edge.
If an edge is leading to a previously visited vertex other than its immediate
predecessor, that edge is noted as cross edge.

16 Marks

1. Explain about Brute force 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

2 Marks

1. What is transform and conquer technique?

The group of design techniques that are based
on the idea of transformation is called transform and conquer technique because
the methods work as two stage procedures. First in the transformation stage,
the problem’s instance is modified to be more amenable (agreeable) to the
solution. Then in the second or conquering stage, it is solved.

2. What are the three variations by which a
given instance of a problem is transformed into?

The three major variations are

v Transformation to a simpler or more convenient instance
of the same problem called instance simplification

v Transformation to a different representation of the same
instance called representation change

v Transformation to an instance of a different problem for
which the algorithm is already available called problem reduction.

3. What is presorting?

Presorting is the idea of sorting a list so
that problems can be solved more easier than in an unsorted list. The time
efficiency of the algorithm that involve sorting before solving the problem
depends on the sorting algorithm being used.

4. Give the algorithm for element uniqueness
using presorting?

ALGORITHM PresortElementUniqueness(A[0..n-1]0

//Solves the element uniqueness problem by
sorting the array first

//Input An array A[0..n-1] of orderable
elements

//Output Returns “true” if A has no equal
elements, “false” otherwise

Sort the array A

0 to n-2 doÃŸfor
I

If A[I] = A[I+1] return false

return true

5. Compare the efficiency of solving the
problem of element uniqueness using presorting and without sorting the elements
of the array?

(n2).qThe brute force algorithm compares pairs of
the array’s elements until either two equal elements were found or no more
pairs were left. It’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.

(n2).qThe 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 algorithm in creating the
frequency list is

(n log n).qThe 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 algorithm is

8. Define AVL trees and who was it invented
by?

An AVL tree is a binary search tree in which
the balance factor of every node, which is defined as the difference between
the heights of the node’s left and right subtrees, is either 0 or +1 or –1. the
height of an empty subtree is defined as –1. AVL trees were invented in 1962 by
two Russian scientists, G.M.Adelson-Velsky and E.M.Landis, after whom the data
struture is named.

9. What are binary search trees and what is
it mainly used for?

Binary search trees is one of the principal
data structures for implementing dictionaries. It is a binary tree whose nodes
contain elements of a set of orderable items, one element per node, so that all
elements in the left subtree are smaller than the element in the subtree’s root
and all elements in the right subtree are greater than it.

10. What is a rotation in AVL tree used for?

If an insertion of a new node makes an AVL
tree unbalanced, the tree is transformed by a rotation. A rotation in an AVL
tree is a local transformation of its subtree rooted at a node whose balance
has become either +2 or –2; if there are several such nodes, then the tree
rooted at the unbalanced node that is closest to the newly inserted leaf is
rotated.

11. What are the types of rotation?

There are four types of rotations, in which
two of them are the mirror images of the other two rotations. The four
rotations are

v Single right rotation or R-rotation

v Single left rotation or L-rotation

v Double left-right rotation or LR-rotation

v Double right-left rotation or RL-rotation

12. Write about the efficiency of AVL trees?

As with any search tree , the critical
characteristic is the tree’s height. The tree’s height is bounded above and
below by logarithmic functions. The height ‘h’ of any AVL tree with ‘n’ nodes
satisfies the inequalities

h£log2 n < 1.4405 log2(n+2) – 1.3277

(log n) in the worst case. The operation of
key deletion in an AVL tree is more difficult than insertion, but it turns out
to have the same efficiency class as insertion i.e., logarithmic.qThe
inequalities imply that the operations of searching and insertion are

13. What are the drawbacks of AVL trees?

The drawbacks of AVL trees are

v Frequent rotations

v The need to maintain balances for the tree’s nodes

v Overall complexity, especially of the deletion
operation.

14. What are 2-3 trees and who invented them?

A 2-3 tree is a tree that can have nodes of
two kinds:2-nodes and 3-nodes. A 2-node contains a single key K and has two
children, the left child serves as the root of a subtree whose keys are less
than K and the right child serves as the root of a subtree with keys greater
than K.

A 3-node contains two ordered keys K1 &
K2 (K1<K2). The leftmost child serves as the root of a subtree with keys
less than K1, the middle child serves as the root of a subtree with keys
between K1 & K2 and the rightmost child serves as the root of a subtree
with keys greater than K2. The last requirement of 2-3 trees is that all its
leaves must be on the same level, a 2-3 tree is always height balanced. 2-3
trees were introduced by John Hopcroft in 1970.

15. What is a heap?

A heap is a partially ordered data structure,
and can be defined as a binary tree assigned to its nodes, one key per node,
provided the following two conditions are met

v The tree’s shape requirement-The binary tree is
essentially complete, that is all the leaves are full except possibly the last
level, where only some rightmost leaves will be missing.

v The parental dominance requirement-The key at each node
is greater that or equal to the keys of its children

16. What is the main use of heap?

Heaps are especially suitable for
implementing priority queues. Priority queue is a set of items with orderable
characteristic called an item’s priority, with the following operations

v Finding an item with the highest priority

v Deleting an item with highest priority

v Adding a new item to the set

17. Give three properties of heaps?

The properties of heap are

v There exists exactly one essentially complete binary
tree with ‘n’ nodes. Its height is equal to log2n

v The root of the heap is always the largest element

v A node of a heap considered with all its descendants is
also a heap

18. Give the main property of a heap that is
implemented as an array.

A heap can be implemented as an array by
recording its elements in the top-down, left-to-right fashion. It is convenient
to store the heap’s elements in positions 1 through n of such an array. In such
a representation

v The parental node keys will be in the first n/2
positions of the array, while the leaf keys will occupy the last n/2 positions

v The children of a key in the array’s parental position
‘i’ (1 i n/2) will be in positions 2i and 2i+1and correspondingly, the parent
of the key in position ‘i’ (2 i n) will be in position i/2.

19. What are the two alternatives that are
used to construct a heap?

The two alternatives to construct a heap are

v Bottom-up heap construction

v Top-down heap construction

20. Give the pseudocode for Bottom-up heap
construction.

ALGORITHM HeapBottomUp(H[1..n])

//Constructs a heap from the elements of the
given array

//Input An array H[1..n] of orderable
elements

//Output A heap H[1..n]

n/2 downto 1 doÃŸfor
I

H[k]ÃŸ I ; v ÃŸk

falseÃŸheap

while not heap and 2*k n do

2*kÃŸj

if j < n

if H[j] < j+1ÃŸH[j+1]
j

if v H[j]

trueÃŸheap

jÃŸ H[j]; k ÃŸelse H[k]

vÃŸH[k]

21. What is the algorithm to delete the
root’s key from the heap?

ALGORITHM

v Exchange the root’s key with the last key K of the heap

v Decrease the heap’s size by one

v “Heapify” the smaller tree by sifting K down the tree exactly
in the same way as bottom-up heap construction. Verify the parental dominance
for K: if it holds stop the process, if not swap K with the larger of its
children and repeat this operation until the parental dominance holds for K in
its new position.

22. Who discovered heapsort and how does it
work?

Heapsort was discovered by J.W.J. Williams.
This is a two stage process that works as follows

v Stage 1 Heap construction: construct a heap for a given
array.

v Stage 2 Maximum deletions: Apply the root deletion
operation n-1 times to the remaining heap

23. What is dynamic programming and who
discovered it?

Dynamic programming is a technique for
solving problems with overlapping subproblems. These subproblems arise from a
recurrence relating a solution to a given problem with solutions to its smaller
subproblems only once and recording the results in a table from which the
solution to the original problem is obtained. It was invented by a prominent
U.S Mathematician, Richard Bellman in the 1950s.

24. Define transitive closure.

The transitive closure of a directed graph
with ‘n’ vertices is defined as the n-by-n Boolean matrix T={tij}, in which the
elements in the ith row (1 i n) and the jth column (1 j n) is 1 if there exists
a non trivial directed path from the ith vertex to the jth vertex otherwise,
tij is 0

25. What is the formula used by Warshall’s
algorithm?

The formula for generating the elements of
matrix R(k) from the matrix R(k-1) is

rij(k) = rij(k-1) or rik(k-1) and rkj(k-1)

This formula implies the following rule for
generating elements of matrix R(k) from the elements of matrix R(k-1)

v If an element r¬ij is 1 in R(k-1), it remains 1 in R(k)

v If an element rij is 0 in R(k-1), it has to be changed
to 1 in R(k) if and only if the element in its row ‘i’ and column ‘k’ and the
element in its row ‘k’ and column ‘j’ are both 1’s in R(k-1)

26. Give the Warshall’s algorithm.

ALGORITHM Warshall(A[1..n,1..n])

//Implements Warshall’s algorithm for
computing the transitive closure

//Input The adjacency matrix A of a digraph
with ‘n’ vertices

//Output The transitive closure of the
digraph

AÃŸR(0)

1 to n doÃŸfor k

1 to n doÃŸfor i

1 to n doÃŸfor j

R(k-1)[I,j] or R(k-1)[I,k] and
R(k-1)[k,j]ÃŸR(k)[I,j]

return R(n)

27. Give the Floyd’s algorithm

ALGORITHM Floyd(W[1..n,1..n])

//Implements Floyd’s algorithm for the
all-pair shortest–path problem

//Input The weight matrix W of a graph

//Output The distance matrix of the shortest
paths’ lengths

WÃŸD

1 to n doÃŸfor k

1 to n doÃŸfor i

1 to n doÃŸfor j

min{D[I,j], D[I,k] + D[k,j]}ÃŸD[I,j]

return D

28. How many binary search trees can be
formed with ‘n’ keys?

The total number of binary search trees with
‘n’ keys is equal to the nth Catalan number

c(n) = for n >0, c(0) = 1,

which grows to infinity as fast as 4n/n1.5.

29. Give the algorithm used to find the
optimal binary search tree.

ALGORITHM OptimalBST(P[1..n])

//Finds an optimal binary search tree by
dynamic programming

//Input An array P[1..n] of search
probabilities for a sorted list of ‘n’ keys

//Output Average number of comparisons in
successful searches in the optimal //BST and table R of subtrees’ roots in the
optimal BST

1 to n doÃŸfor I

0ÃŸC[I,I-1]

P[I]ÃŸC[I,I]

IÃŸR[I,I]

0ÃŸC[n+1,n]

1 to n-1 doÃŸfor
d

1 to n-d doÃŸfor
i

i +dÃŸj

ÃŸminval

I to j doÃŸfor k

if C[I,k-1]+C[k+1,j] < minval

kÃŸ C[I,k-1]+C[k+1,j]; kmin ÃŸminval

kÃŸR[I,j]

sum + P[s]ÃŸ I+1
to j do sum ÃŸP[I]; for s ÃŸSum

minval+sumÃŸC[I,j]

Return C[1,n], R

30. What is greedy technique?

Greedy technique suggests a greedy grab of
the best alternative available in the hope that a sequence of locally optimal
choices will yield a globally optimal solution to the entire problem. The
choice must be made as follows

v Feasible : It has to satisfy the problem’s constraints

v Locally optimal : It has to be the best local choice
among all feasible choices available on that step.

v Irrevocable : Once made, it cannot be changed on a
subsequent step of the algorithm

31. Mention the algorithm for Prim’s
algorithm.

ALGORITHM Prim(G)

//Prim’s algorithm for constructing a minimum
spanning tree

//Input A weighted connected graph G=

//Output ET, the set of edges composing a
minimum spanning tree of G

VT ÃŸ {v0}

ET ÃŸ

for i ÃŸ 1 to |V|-1 do

Find the minimum-weight edge e*=(v*,u*) among
all the edges (v,u) such that v is in VT and u is in V-VT

VT ÃŸ VT {u*}

ET ÃŸ ET {e*}

return ET

32. What are the labels in Prim’s algorithm
used for?

Prim’s algorithm makes it necessary to
provide each vertex not in the current tree with the information about the
shortest edge connecting the vertex to a tree vertex. The information is
provided by attaching two labels to a vertex

v The name of the nearest tree vertex

v The length of the corresponding edge

33. How are the vertices not in the tree
split into?

The vertices that are not in the tree are
split into two sets

v Fringe : It contains the vertices that are not in the
tree but are adjacent to atleast one tree vertex.

v Unseen : All other vertices of the graph are called
unseen because they are yet to be affected by the algorithm.

34. What are the operations to be done after
identifying a vertex u* to be added to the tree?

After identifying a vertex u* to be added to
the tree, the following two operations need to be performed

v Move u* from the set V-VT to the set of tree vertices
VT.

v For each remaining vertex u in V-VT that is connected to
u* by a shorter edge than the u’s current distance label, update its labels by
u* and the weight of the edge between u* and u, respectively.

35. What is a min-heap?

A min-heap is a mirror image of the heap
structure. It is a complete binary tree in which every element is less than or
equal to its children. So the root of the min-heap contains the smallest
element.

36. What is the use of Kruskal’s algorithm
and who discovered it?

Kruskal’s algorithm is one of the greedy
techniques to solve the minimum spanning tree problem. It was discovered by
Joseph Kruskal when he was a second-year graduate student.

37. Give the Kruskal’s algorithm.

ALGORITHM Kruskal(G)

//Kruskal’s algorithm for constructing a
minimum spanning tree

//Input A weighted connected graph G=

//Output ET, the set of edges composing a
minimum spanning tree of G

sort E in non decreasing order of the edge
weights w(ei1) ……… w(ei|E|)

ET ÃŸ

Ecounter ÃŸ 0

k ÃŸ 0

while ecounter < |V|-1

k ÃŸ k+1

if ET {eik} is acyclic

ET ÃŸ ET {eik}; ecounter ÃŸ ecounter + 1

return ET

38. What is a subset’s representative?

One element from each of the disjoint subsets
in a collection is used as the subset’s representative. Some implementations do
not impose any specific constraints on such a representative, others do so by
requiring the smallest element of each subset to be used as the subset’s
representative.

39. What is the use of Dijksra’s algorithm?

Dijkstra’s algorithm is used to solve the
single-source shortest-paths problem: for a given vertex called the source in a
weighted connected graph, find the shortest path to all its other vertices. The
single-source shortest-paths problem asks for a family of paths, each leading
from the source to a different vertex in the graph, though some paths may have
edges in common.

40. What is encoding and mention its types?

Encoding is the process in which a text of
‘n’ characters from some alphabet is assigned with some sequence of bits called
codewords. There are two types of encoding they are

v Fixed-length encoding

v Variable-length encoding

41. What is the problem faced by variable-length
encoding and how can it be avoided?

Variable-length encoding which assigns
codewords of different lengths to different characters introduces a problem of
identifying how many bits of an encoded text represent the first character or
generally the ith character. To avoid this prefix-free codes or prefix codes
are used. In prefix codes, no codeword is a prefix of a codeword of another
character.

42. Mention the Huffman’s algorithm.

ALGOITHM Huffman

v Initialize n one-node trees and label them with the
characters of the alphabet. Record the frequency of each character in its
tree’s root to indicate the tree’s weight.

v Repeat the following operation until a single tree is
obtained. Find two trees with the smallest weight. Make them the left and right
subtree of a new tree and record the sum of their weights in the root of the
new tree as its weight.

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 Tree

• Algorithm

• Diagram

2 Marks

1. What is backtracking?

Backtracking constructs solutions one
component at a time and such partially constructed solutions are evaluated as
follows

v If a partially constructed solution can be developed
further without violating the problem’s constraints, it is done by taking the
first remaining legitimate option for the next component.

v If there is no legitimate option for the next component,
no 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.

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

v Exploit the symmetry often present in combinatorial
problems. So some solutions can be obtained by the reflection of others. This
cuts the size of the tree by about half.

v Preassign values to one or more components of a solution

v Rearranging 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:

v A way to provide, for every node of a state space tree,
a bound on 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.

v The 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

v The value of the node’s bound is not better than the
value of the best solution seen so far

v The node represents no feasible solution because the
constraints of the problem are already violated.

v The subset of feasible solutions represented by the node
consists 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

v It is typically applied to difficult combinatorial
problems for which no efficient algorithm for finding exact solution possibly
exist

v It holds hope for solving some instances of nontrivial
sizes in an acceptable amount of time

v Even if it does not eliminate any elements of a problem’s
state 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

## 0 comments:

## Post a comment