Data Structures and Algorithms_Unit 5

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 5

Short Questions and Answers
(2 Marks )
Prepared By,
Mr. S. P. Santhoshkumar M.E.,
Assistant Professor,
Department of CSE.

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.

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 problem. ALGORITHM

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.

1.     Then move the largest disk directly from peg1 to peg3
2.       Finally move recursively n-1 disks from peg2 to peg3 with peg1 as auxiliary
3.       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 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

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.

Data Structures and Algorithm_ Unit 4

 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

Short Questions and Answers
(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<b^d

  ^T(n)

  

θ(ndlog n) if a=b^d

     

θ(nlogba) if a>b^d

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.

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.