DESIGN AND ANALYSIS OF ALGORITHMS – QUESTION BANK (CSE)

 

ISL ENGINEERING COLLEGE

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

DESIGN AND ANALYSIS OF ALGORITHMS

QUESTION BANK

                                BE III Year II Semester (A & B Sections) –PC 603 CS

   

Academic Year: 2020-21

SHORT ANSWER QUESTIONS

 

UNIT-I

1.      Why is an algorithm analysis required?

2.      State about UNION & FIND operations.

3.      List out the UNION algorithm using weighting rule.

4.      Given f(n)=10n²+4n+3, then prove that f(n)=O(n²).

5.      List and define operations performed on sets?

6.      What do you mean by performance analysis of an algorithm? Explain.

7.      Explain the significance of input size of a problem.

8.      State the weighting, collapsing rules in sets.

9.      Explain set representation and write algorithm for FIND.

10.  Solve T(n)=3T(n/3)+√n.

11.  Define the terms direct recursive and indirect recursive algorithms.

 

UNIT-II

1.      Briefly differentiate quick sort and merge sort.

2.      Define optimal storage on tapes.

3.      Write control abstraction for

i.             greedy method.

ii.             divide and conquer approach?

4.      Define feasible solution w.r.t greedy knapsack problem.

5.      What do you understand by worst-case time complexity? Give it for merge sort algorithm.

6.      Define the terms feasible solution, optimal solution and objective function.

7.      What is job sequencing using deadlines?

8.      Solve fractional knapsack problem for the given problem instance weights W:{1,4,8,2,6} Profit P:{4,10,5,15,20}. The Knapsack capacity is 30.

9.      Write an algorithm for finding minimum element in a list of elements.

10.  What is the time required to compute a minimum weight spanning tree for any given weighted graph with E edges and V vertices?

UNIT-III

1.      State travelling sales person problem

2.      Differentiate knapsack problem and 0/1 knapsack problem.

3.      When do you apply dynamic programming to solve a problem?

4.      What do you mean by forward and backward approach of problem solving in dynamic programming?

5.      Differentiate greedy method and dynamic programming.

6.      Explain All pairs shortest path problem with suitable example?

7.      Define principle of optimality

8.      Solve the fractional knapsack problem by considering the instance: Weights are W : {1,3,5,6,7}, profits

,P: {3,9,7,11,18}. The knapsack capacity is 15.

9.      Is dynamic programming better than greedy algorithm design technique? Justify?

10.  Differentiate greedy method and dynamic programming.

11.  Define chromatic number of a graph

12.  Explain about explicit and implicit constraints of 8-queen’s problem.

13.  What is Hamiltonian cycle? How it is different from the tour of travelling salesperson problem?

14.  Define the properties of LC search

15.  Differentiate FIFO and LC branch and bound techniques

16.  State 4-Queens’ problem.

17.  What is meant by lower bound theory?

18.  Explain graph coloring problem.

19.  What is the objective of m-colorability optimization problem?

20.  Differentiate FIFO, LIFO branch and bound.

21.  Differentiate Backtracking with branch and bound.

22.  What are explicit and implicit constraints in backtracking algorithm?

23.  What is a Hamiltonian cycle? Give an example.

24.  Write about Least Count Search.

25.  Define Chromatic number

26.  Differentiate LCBB and FIFO branch and bound?

27.  What is chromatic number? Give an example.

UNIT-IV

1.      Explain bi-connected components with an example.

2.      Define articulation point. Give an example

3.      What is B-Tree?

4.      What is a Bi-connected component?

5.      Give an example of a biconnected graph.

6.      Define Tries and different types of tries?

7.      List out the properties of biconnected graphs

8.      What is a tree edge and back edge. Explain with an example.

UNIT-V

1.      State node cover decision problem

2.      What is NP completeness

3.      Define the terms cliques, node cover.

4.      Differentiate between NP-hard and NP-complete.

5.      State Cook’s theorem.

6.      Discuss Clique Decision problem.

7.      List out the functions used to specify non deterministic algorithm?

8.      Define NP-complete and NP-hard problems. Give an example for each.

9.      List out the NP-Hard code generation problems

10.  What is meant by satisfiability?

11.  State the problem of selection

12.  Define Satisfiability problem.

13.  List out the various NP-Hard graph problem

14.  What is meant by Halting Problem?

15.  Show the relationship between P, NP, NP-Complete and NP-Hard and explain.

16.  Differentiate NP-Hard and NP-complete problems.

17.  Define the terms cliques, node cover.

18.  What are NP-Hard code generation problems?

19.  What is satisfiability?

20.  Differentiate between NP-hard and NP-complete.

 

 

LONG ANSWER QUESTIONS

 

UNIT-I

 

1.      What is asymptotic complexity of an algorithm? Give an example of an algorithm whose complexity is O(nlogn).

2.      Explain Disjoint set operation in detail.

3.      What is basic data structures.

Write short notes on

i.            Big Oh notation & Theta notation

ii.            DAG for common sub expression

iii.            Priori and posteriori analysis

iv.            Disjoint set union

v.                Asymptomatic Notations

 

 

UNIT-II

1.      Write algorithm to find maximum and minimum from a set.

2.      Write algorithm to find maximum and minimum using divide and conquer.

3.      Explain Binary Search?

4.      Explain Single Source Shortest Path Problem using Greedy Method with suitable example?

5.      Write an algorithm for merge sort and write the time complexities.

6.      Derive the time complexity of quick sort algorithm.

7.        Find feasible solution for given jobs with deadlines.

            N=7, (p1,p2,….p7)=(3,5,20,18,1,6,30), (d1,d2,……d7)=(1,3,4,3,2,1,2)

8.      What is a knapsack problem? Explain. Find an optimal solution to the knapsack problem when (W1,W2,W3,W4)=(10,15,6,9) , (P1,P2,P3,P4)=(2,5,8,1) , Knapsack Capacity=25.

9.      Find the minimum cost spanning tree for the given graph (Consider any example.)

10.  Define spanning tree and explain Prim’s algorithm for finding minimum spanning tree of the graph using any graph.

11.  Briefly explain spanning tree and their application.

12.  Explain job sequencing with deadline algorithm with an example.

13.  Explain in detail any two problems that can be solved using divide & conquer strategy.

14.  Write short notes on:

i.             Job scheduling with deadlines using greedy approach.

UNIT-III

1.      Explain the forward and backward approaches of problem solving in dynamic programming.

2.      Solve the travelling salesperson problem using dynamic programming for the following

3.      Explain about all pairs shortest path problem with example and write algorithm.

4.     
Using dynamic programming approach, identify the articulation points in the graph below

5.      Solve the all pairs shortest path problem for a digraph with the following weight matrix

6.      Write an algorithm for all pairs shortest paths

7.      Solve the 0/1 Knapsack instance where

n=3, (w1,w2,w3) = (2,3,4) , (p1,p2,p3) =( 1,2,5) and using dynamic programming.

8.      Define m – coloring problem. Write an algorithm to solve it using backtracking.

9.      Write an algorithm to find all m-coloring of a graph.

10.  Explain about DFS with example. Write algorithm and its time complexity.

11.  Differentiate between back tracking and branch and bound strategies.

12.  Write an algorithm for N-Queens problem.

13.  Explain solution of graph coloring problem using backtracking.

14.  What is branch and bound strategy? Explain.

15.Consider travelling sales person instance

Obtain the state space tree that is generated by LCBB.

16.  Explain back tracking. Give the various applications of backtracking.

17.  Solve the 8-Queens’s problem using backtracking.

18.  Write an algorithm for 8-Queen’s problem using backtracking.

19.  What are Hamiltonian cycles? Present an algorithm that finds all the Hamiltonian cycles of a given graph.

20.  What is Hamiltonian cycle? How is it different from the tour of traveling sales person problem? Explain.

21.  Write short notes on

i.             State space tree

ii.             Graph Coloring

iii.             Lower bound theory

22.  Write short notes on

i.             Control abstraction for dynamic programming

ii.             Reliability Design

iii.             Divide & Conquer

iv.             State Space Tree

v.               Principle of optimality

vi.                 Control abstraction for Least cost Search

 

 

UNIT-IV

1.      Define biconnected component of a graph. Identify articulation point and draw biconnected components of (Consider any example from this topic)

2.      Explain about DFS with example. Write algorithm and its time complexity.

3.      Explain in detail Breath First Search (BFS) with suitable example?

4.      Explain Tries in detail.

5.      What is B-tree explain in detail.

6.      Define chromatic number. Draw the state space tree for the following graph with n=5, m=3.

UNIT-V

1.      Explain in brief NP hard and NP complete problems.

2.      Differentiate between NP-complete and NP-hard.

3.      Briefly explain three NP-hard graph problems.

4.      Explain the terms NP-Complete and NP-hard.

5.      Define node covering problem. Give an example.

6.      Write non deterministic algorithm for searching.

7.      Write non deterministic algorithm for sorting.

8.      Explain about NP-Hard scheduling problems.

9.      State Cooks theorem and prove it. Explain its significance in NP- Complete theory.

10.  Discuss NP-Hard code generation problems.

11.  Difference between NP-Hard and NP-Complete.

12.  Write short notes on

i.             Node Cover Decision Problem

ii.             DAG for common sub expression

iii.             Satisfiability problem

iv.             Non deterministic algorithms

v.            Reducibility