P. A. COLLEGE OF ENGINEERING AND TECHNOLOGY
POLLACHI, COIMBATORE – 642 002.
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
ME – DEGREE COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES AND ALGORITHMS_Unit 4
UNIT IV – GREEDY & DIVIDE AND CONQUER
POLLACHI, COIMBATORE – 642 002.
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
ME – DEGREE COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES AND ALGORITHMS_Unit 4
Short Questions and Answers
(2 Marks )
Prepared By,
Mr. S. P. Santhoshkumar M.E.,
Assistant Professor,
Department of CSE.
(2 Marks )
Prepared By,
Mr. S. P. Santhoshkumar M.E.,
Assistant Professor,
Department of CSE.
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 themethods 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.
No comments:
Post a Comment