Short question and answer for Data Structure and Analysis Of Algorithms
UNIT I – COMPLEXITY
ANALYSIS & ELEMENTARY DATA STRUCTURES
1. What do asymptotic notation means?
Asymptotic notations are terminology that
is introduced to enable us to make meaningful statements about the time and
space complexity of an algorithm. The different notations are
Big – Oh notation
Omega notation
Theta notation.
2. What are the basic asymptotic efficiency classes?
The various basic efficiency
classes are
Constant : 1
Logarithmic :
log n
Logarithmic :
log n
Linear : n
N-log-n : nlog n
Quadratic : n2
Cubic : n3
Exponential : 2n
Factorial : n!
3. 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
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. What is the formula used in Euclid’s
algorithm for finding the greatest common divisor of two numbers?
Euclid’s
algorithm is based on repeatedly applying the equality Gcd(m,n)=gcd(n,m mod n) until m mod n is
equal to 0, since gcd(m,0)=m.
10. Define articulation points.
If a graph is
not biconnected,the vertices whose removal would disconnect the graph are known
as articulation points.
11. Give some example of NP complete problems.
i. Hamiltonian
circuit.
ii. Travelling
salesmen problems
iii. Longest
path problems
iv. Bin packing
v. Knapsack
problem
vi. Graph
colouring problem
12. 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
13. 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
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/5(Φn - Φn)
Where
Φ =(1+5)/2
Φ =(1-5)/2
16. Define Data Structures
Data Structures is defined as the way of organizing all
data items that consider not
only the elements stored but also stores the relationship
between the elements.
17. Define Linked Lists
Linked list consists of a series of structures, which are not necessarily
adjacent in memory. Each structure contains the element and a pointer
to a structure containing its successor. We call this
theNext Pointer. The last cell’sNext pointer points to NULL.
18. State the different types of
linked lists
The different types of linked list include singly linked
list, doubly linked list and
circular linked list.
11. List the basic operations carried out in a linked
list
The basic operations carried out in a linked list
include:
• Creation of a list
• Insertion of a node
• Deletion of a node
• Modification of a node
• Traversal of the list
19. List out the advantages of using a
linked list
• It is not necessary to specify the number of elements
in a linked list during its
declaration
• Linked list can grow and shrink in size depending upon
the insertion and deletion
that occurs in the list
• Insertions and deletions at any place in a list can be
handled easily and efficiently
• A linked list does not waste any memory space
20. List out the applications of a
linked list
Some of the important applications of linked lists are manipulation
of
polynomials, sparse matrices, stacks and queues.
21. State the difference between
arrays and linked lists
Arrays
|
Linked
Lists
|
Size
of an array is fixed
|
Size
of a list is variable
|
It
is necessary to specify the number of elements during declaration.
|
It is not necessary to specify the number of
elements during declaration
|
Insertions
and deletions are
somewhat
difficult
|
Insertions
and deletions are carried
out
easily
|
It occupies less memory than a linked list
for the same number of elements
|
It
occupies more memory
|
22. What do you
mean by balanced trees?
Balanced trees have the structure of binary trees and obey binary search tree
properties. Apart from these properties, they have some special constraints,
which differ from one data structure to another. However, these
constraints are aimed only at reducing the height of the
tree, because this factor determines the time
complexity.
Eg: AVL trees, Splay trees.
23. What is the use of threaded binary
tree?
In threaded binary tree, the NULL pointers are replaced by some addresses.
The left pointer of the node points to its predecessor and the right
pointer of the node points to its successor.
24.Construction of
expression trees?
1.convert the given infix
expression into postfix notation
2. Create a stack and read each
character of the expression and push into the stack, if operands are encountered.
3.when an operator is encountered
pop 2 values from the stack. From a tree using the operator.
25. Why you need a data structure?
A data structure helps you to understand the relationship of one data
element with the other and organize it within the memory. Sometimes the
organization might be simple and can be very clearly
visioned. Eg) List of names of months in a year –Linear Data Structure, List of historical places in the world- Non-Linear Data
Structure. A data structure helps you to analyze the
data, store it and organize it in a logical and mathematical
manner.
UNIT II – HEAP
STRUCTURES
1. Define 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
i.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.
ii.The parental
dominance requirement-The key at each node is greater that or equal to the keys
of its children
2. What are the
properties of binary heap?
i) Structure Property
ii) Heap Order Property
3. 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.
4. what is maxheap?
If we want the elements in the
more typical increasing sorted order,we can change the ordering property so
that the parent has a larger key than the child.it is called max heap
5. What do you mean by structure
property in a heap?
A heap is a binary tree that is completely filled with the possible
exception at the bottom level, which is filled from left to right. Such a tree
is known as a complete binary tree.
6. What do you mean by heap order
property?
In a heap, for every node X, the key
in the parent of X is smaller than (or
equal to) the key in X, with the exception of the root
(which has no parent).
7. What are the applications of
priority queues?
• The
selection problem
•
Event simulation
8. 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
i. Finding an
item with the highest priority
ii.Deleting an
item with highest priority
iii.Adding a new
item to the set
9. Give three
properties of heaps?
The properties of heap are
There exists exactly one
essentially complete binary tree with ‘n’ nodes. Its height is equal to log2n
The root of the heap is
always the largest element
A node of a heap considered
with all its descendants is also a heap
10. 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
i. 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
ii.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.
11. What are the two
alternatives that are used to construct a heap?
The two alternatives to construct
a heap are
Bottom-up heap construction
Top-down heap construction
12. What is the
algorithm to delete the root’s key from the heap?
ALGORITHM
i.Exchange the
root’s key with the last key K of the heap
ii.Decrease the
heap’s size by one
iii.“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.
13. What do you mean by the term
“Percolate up”?
To insert an element, we have to create a hole in the next available heap location.
Inserting an element in the hole would sometimes violate the heap order property, so we have to slide down the parent into the hole. This
strategy is continued until the correct location for the
new element is found. This general strategy is known as
a percolate up; the new element is percolated up the heap until the correct location is found.
14. What do you mean by the term
“Percolate down”?
When the minimum element is removed, a hole is created at the root. Since
the heap now becomes one smaller, it follows that the last element X in
the heap must move somewhere in the heap. If X can be
placed in the hole, then we are done.. This is unlikely,
so we slide the smaller of the hole’s children into the hole, thus pushing the hole down one level. We repeat this step until X can be
placed in the hole. Thus, our action is to place X in
its correct spot along a path from the root containing
minimum children. This general strategy is known as percolate down. 15. What is meant by Implicit Heaps?
A
particularly simple and beautiful implementation of the heap structure is the
implicit heap. Data is simply put into an array 
and the
childrens of element x[i] are defined to be the elements x[2i]
and x[2i+1]. Thus the parent of the element c can be found
at c/2 (integer division).
16.What is a skew
heap?
A heap data
structure that is stored in a binary tree (not necessarily complete and
balanced). The insertion and deletion of elements in the tree come from merging
two skew heaps together in such a way that the heap property is preserved and
the tree does not degrade to a linear tree.
17. How to merging 2 skew heaps?
Suppose
we are merging a heap containing the elements 2, 5, and 7 with a heap
containing the elements 4 and 6.
7 <-
merge -> 6
/ \ /
5 2 4
i.
Identify the root, thus 7 becomes the new root and the left
subtree of the heap with root 7 becomes the
right subtree of
the other heap:
7 2 <- merge -> 6
(to form the left subtree
\ /
of the new skew heap)
5 4
ii.
7
/ \
6
5
\
4 <-
merge -> 2
iii.
7
/ \
6
5
/ \
2 4
18. Define Fabinacci Heap.
The Fibonacci heap is a data structure that supports all
the basic heap operations in O(1) amortized time, with the exception of
delete_min and delete, which take O (log n) amortized time. It immediately
follows that the heap operations in Dijkstra's algorithm will require a total
of O(|E| + |V| log |V|) time.
19. What is Lazy merging?
Two heaps are merged only when it is required to do so. This is similar to lazy deletion. For lazy merging, merges are cheap, but because lazy merging does not actually combine trees, the delete_min operation could encounter lots of trees, making that operation expensive. Any one delete_min could take linear time, but it is always possible to charge the time to previous merge operations. In particular, an expensive delete_min must have been preceded by a large number of unduly cheap merges, which have been able to store up extra potential.
20. Write the amortized analysis of Lazy Binomial Queues
To carry out the
amortized analysis of lazy binomial queues, we will use the same potential
function that was used for standard binomial queues. Thus, the potential of a lazy
binomial queue is the number of trees.
21. Binomial heaps:
A set of binomial trees satisfying the following:
1. Each
binomial tree in H is heap-ordered:
the
key of a node is greater than or equal to the key of its parent
2. There is at most one binomial tree in H whose
root has a given degree
22.Write the Dijkstra’s shortest path algorithm
Let G = (V,E) be a weighted (weights are non-negative)
undirected graph, let s Î
V. Want to find the distance (length of the shortest path), d(s,v) from s to every
other vertex.
UNIT III – SEARCH
STRUCTERS
1. 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]
2. 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.
3. What are the classic traversals of a binary tree?
The classic traversals are as follows
i. Preorder
traversal: the root is visited before left & right subtrees
ii. Inorder
traversal: the root is visited after visiting left subtree and before visiting
right subtree
iii. Postorder
traversal: the root is visited after visiting the left and right subtrees
4. 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
5. 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.
6. 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.
7. Define AVL Tree.
An empty tree is height balanced. If T
is a non-empty binary tree with TL and
TR as its left and right subtrees, then T is height
balanced if
i) TL and TR are height balanced and
ii) │hL - hR│≤ 1
Where hL and hR are the heights of TL and TR
respectively.
8. What are the various transformation performed in AVL tree?
1.single rotation - single L rotation - single R rotation
2.double rotation -LR rotation -RL rotation
9. What are the categories of AVL rotations?
Let A be the nearest ancestor of the newly inserted nod which has the balancing
factor ±2. Then the rotations can be classified into the following four categories:
Left-Left: The newly inserted node is in the
left subtree of the left child of A.
Right-Right: The newly inserted node is in the
right subtree of the right child of A.
Left-Right: The newly inserted node is in the
right subtree of the left child of A.
Right-Left: The newly inserted node is in the
left subtree of the right child of A.
10. What do you mean by balance factor of a node in AVL tree?
The height of left subtree minus height of right subtree is called balance factor of a
node in AVL tree.The balance factor may be either 0 or +1 or -1.The height of an empty tree is -1.
11. 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
log2 n ≤ h <
1.4405 log2(n+2) – 1.3277
The inequalities imply that the operations of searching and insertion
are θ(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
12. What is the minimum number of nodes in an AVL tree of height
h?
The minimum number of nodes S(h), in an AVL tree of height
h is given
by S(h)=S(h-1)+S(h-2)+1. For h=0, S(h)=1.
13. 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.
14. What do you
mean by 2-3-4 tree?
A B-tree of order 4 is called 2-3-4 tree. A B-tree of
order 4 is a tree that is not
binary with the following structural properties:
• The root is either a leaf or has between 2 and 4
children.
• All non-leaf nodes (except the root) have between 2 and
4 children.
• All leaves are at the same depth.
14. Define
B-tree of order M.
A B-tree of order M is a tree that is not binary with the
following structural
properties:
• The root is either a leaf or has between 2 and M
children.
• All non-leaf nodes (except the root) have between ┌M/2┐
and M children.
• All leaves are at the same depth.
15. What are the
applications of B-tree?
• Database implementation
• Indexing on non primary key fields
16. Definition of a red-black tree
A red-black tree is a binary
search tree which has the following red-black properties:
|
 
A basic red-black tree
|
|
Basic red-black tree with the sentinel nodes added.
Implementations of the red-black tree algorithms will usually include the
sentinel nodes as a convenient means of flagging that you have reached a leaf
node.
They are the NULL black nodes of property 2. |
17. Define splay
tree.
A splay tree is a binary search tree in which restructuring is done using a scheme called
splay. The splay is a heuristic method which moves a given vertex v to the root of the splay tree using a sequence of rotations.
18. What is the idea behind splaying?
Splaying reduces the total accessing time if the most frequently accessed node is moved
towards the root. It does not require to maintain any information regarding the height or balance factor and hence saves space and
simplifies the code to some extent.
19. List the types of rotations available in Splay tree.
Let us assume that the splay is
performed at vertex v, whose parent and
grandparent are p and g respectively. Then, the three
rotations are named as:
i. Zig: If p is the root and v is the left child of p,
then left-left rotation at p would
suffice. This case always terminates the splay as v
reaches the root after this
rotation.
ii. Zig-Zig: If p is not the root, p is the left child
and v is also a left child, then a left-
left rotation at g followed by a left-left rotation at p,
brings v as an ancestor of g
as well as p.
iii. Zig-Zag: If p is not the root, p is the left child
and v is a right child, perform a
left-right rotation at g and bring v as an ancestor of p
as well as g.
20. 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.
21. What are the advantages of brute force technique?
The various advantages of brute
force technique are
i. Brute force
applicable to a very wide variety of problems. It is used for many elementary
but important algorithmic tasks
ii.For some
important problems this approach yields reasonable algorithms of at least some
practical value with no limitation on instance size
iii.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
iv. 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
22. What are the
properties of binary heap?
i) Structure Property
ii) Heap Order Property
UNIT IV – GREEDY
& DIVIDE AND CONQUER
1. Give the general
plan for divide-and-conquer algorithms.
The general plan
is as follows
i.A problems instance is divided
into several smaller instances of the same problem, ideally about the same size
ii.The smaller instances are
solved, typically recursively
iii.If necessary the solutions
obtained are combined to get the solution of the original problem
2. State the Master
theorem and its use.
If f(n) εθ(nd) where d ≥ 0 in recurrence equation T(n) =
aT(n/b)+f(n), then
θ(nd) if a<bd
T(n)
θ(ndlog n) if a=bd
θ(nlogba) if a>bd
The efficiency analysis of many divide-and-conquer
algorithms are greatly simplified by the use of Master theorem.
3. 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.
4. 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
Decrease by a constant
Decrease by a
constant-factor
Variable size decrease
5. 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.
6. 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.
7. 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.
8. 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
i.Feasible : It
has to satisfy the problem’s constraints
ii.Locally
optimal : It has to be the best local choice among all feasible choices
available on that step.
iii.Irrevocable
: Once made, it cannot be changed on a subsequent step of the algorithm
9. 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.
10. 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.
11. 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.
12. 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.
13. 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.
14. 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.
15. Define Divide and Conquer algorithm?
Divide and
Conquer algorithm is based on dividing the problem to be solved into several,
smaller sub instances, solving them independently and then combining the sub
instances solutions so as to yield a solution for the original instance.
16. Mention some application of Divide and Conquer algorithm?
a. Quick Sort b. Merge Sort
c. Binary search
17. What are the two stages for heap sort?
Stage 1 : Construction
of heap Stage 2 : Root deletion N-1 times
18. What is divide and conquer strategy ?
In divide and
conquer strategy the given problem is
divided into smaller
Problems and solved recursively. The conquering phase consists of
patching together the answers . Divide –
and – conquer is a very powerful use of
recursion that we will see many times.
19. What do you
mean by separate chaining?
Separate chaining is a collision resolution technique to keep the list of
all elements that hash to the same value. This is called separate
chaining because each hash table element is a separate
chain (linked list). Each linked list contains all the
elements whose keys hash to the same index.
20. Write the
advantage and Disadvantages of separate
chaining.
Adv:
• More number of elements can be inserted as it uses
linked lists.
Dis Adv.
• The elements are evenly distributed. Some elements may
have more
elements and some may not have anything.
• It requires pointers. This leads to slow the algorithm
down a bit because of
the time required to allocate new cells, and also essentially requires the
implementation of a second data structure.
the time required to allocate new cells, and also essentially requires the
implementation of a second data structure.
21. What do you
mean by open addressing?
Open addressing is a collision resolving strategy in which, if collision
occurs alternative cells are tried until an empty cell is found. The cells
h0(x), h1(x), h2(x),…. are tried in succession, where
hi(x)=(Hash(x)+F(i))mod Tablesize with F(0)=0. The function
F is the collision resolution strategy.
22. What do you
mean by Probing?
Probing is the process of getting next available hash
table array cell.
23. What do you
mean by linear probing?
Linear probing is an open addressing collision resolution strategy in which
F is a linear function of i, F(i)=i. This amounts to trying sequentially in
search of an empty cell. If the table is big enough, a
free cell can always be found, but the time to do so can
get quite large.
24. What do you
mean by primary clustering?
In linear probing collision resolution strategy, even if
the table is relatively
empty, blocks of occupied cells start forming. This
effect is known as primary
clustering means that any key hashes into the cluster
will require several attempts
to resolve the collision and then it will add to the
cluster.
25. What do you
mean by quadratic probing?
Quadratic probing is an open addressing collision resolution strategy in
which F(i)=i2. There is no guarantee of finding an empty cell once the
table gets half full if the table size is not prime.
This is because at most half of the table can be used as alternative locations to resolve collisions.
26. What do you
mean by secondary clustering?
Although quadratic probing eliminates primary clustering, elements that hash to the
same position will probe the same alternative cells. This is known as secondary clustering.
27. List the
limitations of linear probing.
• Time taken for finding the next available cell is
large.
• In linear probing, we come across a problem known as
clustering.
28. Mention one
advantage and disadvantage of using quadratic probing.
Advantage: The problem of primary clustering is
eliminated.
Disadvantage: There is no guarantee of finding an
unoccupied cell once the table
is nearly half full.
UNIT V –DYNAMIC
PROGRAMMING AND BACKTRACKING
1. Define Graph.
A graph G
consist of a nonempty set V which is a set of nodes of the graph, a set E which is
the set of edges of the graph, and a mapping from the set for edge E to a set
of pairs of elements of V. It can also be represented as
G=(V, E).
2. What is meant by strongly and
Weekly connected in a graph?
An undirected graph is connected, if there is a path from
every vertex to every
other
vertex. A directed graph with this property is called strongly connected.
When a directed graph is not strongly connected but the
underlying graph is
connected,
then the graph is said to be weakly connected.
3. List the two important key points
of depth first search.
i) If
path exists from one node to another node, walk across the edge – exploring
the
edge.
ii)
If path does not exist from one specific node to any other node, return to the
previous
node where we have been before – backtracking.
4. What do you mean by breadth first
search (BFS)?
BFS performs simultaneous
explorations starting from a common point and
spreading out independently.
spreading out independently.
5. Differentiate
BFS and DFS.
No.
|
DFS
|
BFS
|
1.
|
Backtracking
is possible from a
dead
end
|
Backtracking
is not possible
|
2.
|
Vertices
from which exploration is
incomplete are processed in a LIFO order |
The
vertices to be explored are organized as a
FIFO
queue
|
3.
|
Search
is done in one particular
Direction
|
The
vertices in the same level are maintained
parallely
|
6. What do you mean by articulation
point?
If a graph is not biconnected, the vertices whose removal
would disconnect the
graph
are known as articulation points.
7. 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.
8. 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.
9. 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.
10. 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.
11. 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.
12. What is
backtracking?
Backtracking constructs solutions
one component at a time and such partially constructed solutions are evaluated
as follows
i. 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.
ii.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.
13. 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.
14. 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.
15. 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 for each element x[Si+1
]consistent with X[1..i] and the constraints do X[i+1]
x
Backtrack(X[1..i+1]
16. Write a recursive
algorithm for solving Tower
of Hanoi
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.
Then move the largest disk
directly from peg1 to peg3
Finally move recursively
n-1 disks from peg2 to peg3 with peg1 as auxiliary
If n=1 simply move the
single disk from source peg to destination peg.
17. What is the basic
operation in the Tower
of Hanoi
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
18. 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.
19Define 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.
20. 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)
21. What are the additional
features required in branch-and-bound when compared to backtracking?
Compared to backtracking, branch-and-bound requires:
i.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.
ii.The value of the best solution
seen so far
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 v
i+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
i.It is typically applied to
difficult combinatorial problems for which no efficient algorithm for finding
exact solution possibly exist
ii.It holds hope for solving some
instances of nontrivial sizes in an acceptable amount of time
iii.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.
