Skip to main content

DESIGN AND ANALYSIS OF ALGORITHMS – QUESTION BANK (IT)

 


ISL ENGINEERING COLLEGE

DEPARTMENT OF INFORMATION TECHNOLOGY


DESIGN AND ANALYSIS OF ALGORITHMS

QUESTION BANK


BE III Year II Semester – PC 602 IT

Academic Year: 2020-21


SHORT ANSWER QUESTIONS

 

UNIT-I

1.      Explain linear probing in Hashing with an example.

2.      Define Heap.

3.      List out the collision resolution techniques in hashing.

4.      Why is an algorithm analysis required?

5.      State about UNION & FIND operations.

6.      List out the UNION algorithm using weighting rule.

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

8.      List and define operations performed on sets?

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

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

11.  State the weighting, collapsing rules in sets.

12.  Explain set representation and write algorithm for FIND.

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

18.  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 is the time complexity of the optimal storage on tapes problem?

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

7.      State the optimal storage on multiple tapes problem.

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

9.      What is job sequencing using deadlines?

10.  Explain optimal merge pattern with an example.

11.  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.

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

13.  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.      Define articulation point. Give an example

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

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

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

6.      Explain biconnected components with an example.

7.      Differentiate greedy method and dynamic programming.

8.      What is multistage graph?

9.      List out the properties of biconnected graphs

10.  Define principle of optimality

11.  What is a Bi-connected component?

12.  What is depth first search?

13.  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.

14.  Give an example of a biconnected graph.

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

16.  Differentiate greedy method and dynamic programming.

UNIT-IV

1.      Define chromatic number of a graph

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

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

4.      Define the properties of LC search

5.      Differentiate FIFO and LC branch and bound techniques

6.      State 4-Queens’ problem.

7.      What is meant by lower bound theory?

8.      Explain graph coloring problem.

9.      What is Hamiltonian cycle? How is it different from the tour of traveling salesperson problem?

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

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

12.  Differentiate FIFO, LIFO branch and bound.

13.  Differentiate Backtracking with branch and bound.

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

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

16.  State the purging rule and list out its applications

17.  Write about Least Count Search.

18.  Define Chromatic number

19.  Differentiate LCBB and FIFO branch and bound?

20.  What is chromatic number? Give 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 the basic requirement of a planar graph?

15.  What is meant by Halting Problem?

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.      Construct 10-entry Hash table for hashing the keys 15, 32, 12, 77, 85, 67, 26, 48, 113, 54 using the function (i+6) mod 10 using linear probing.

2.      Explain step by step heap sort with example and write an algorithm for heap sort.

3.      Write an algorithm to delete an element from max heap.

4.      Write an algorithm to form a heap using Heapify and discuss its time complexity.

5.      Solve the following recurrence relation using

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

Write short notes on

i.            Big Oh notation & Theta notation

ii.              Priori and posteriori analysis

iii.            Hash Function

iv.          Collision Resolution Techniques

v.              Disjoint set union

vi.              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.      Find an optimal binary merge pattern for ten files whose length are 28, 43, 9, 18, 74,53,94,36,13,11.

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

5.      Derive the time complexity of quick sort algorithm.

6.      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)

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

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.

ii.             Optimal merge pattern


UNIT-III

1.      Solve the following instance of optimal cost binary search tree n=4; (a1-a4)=(do,if,int,while), P(1:4)=(3,3,1,1), Q(0:4)=(2,3,1,1,1)

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

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

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

5.     


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




  

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


 

7.     
Consider the multistage graph. Find the shortest path from S to T.


8.      Write an algorithm for all pairs shortest paths

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

10.  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.

11.  Consider traveling sales person instance

 


Obtain the state space tree that is generated by LCBB

12.  Write short notes on

i.             Control abstraction for dynamic programming

ii.             Reliability Design

iii.             Divide & Conquer

iv.             State Space Tree

v.            Optimal Binary Search Tree

vi.             Principle of optimality

vii.             DFS with example

viii.             Control abstraction for Least cost Search

 

UNIT-IV

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

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

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

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




5.      Write an algorithm for N-Queens problem.

6.      Explain solution of graph coloring problem using backtracking.

7.      What is branch and bound strategy? Explain.

8.  Consider travelling sales person instance

Obtain the state space tree that is generated by LCBB.

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

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

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

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

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

15.  Write short notes on

i.             State space tree

ii.             Graph Coloring

iii.             Lower bound theory

UNIT-V

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

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

3.      Explain in detail about the AND-OR graph decision problem.

4.      Briefly explain three NP-hard graph problems.

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

6.      Define node covering problem. Give an example.

7.      Write non deterministic algorithm for searching.

8.      Write non deterministic algorithm for sorting.

9.      Explain about NP-Hard scheduling problems.

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

11.  Discuss NP-Hard code generation problems.

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

13.  Write short notes on

i.             Node Cover Decision Problem

ii.               Satisfiability problem

iii.             Non deterministic algorithms

iv.          Reducibility




Comments

  1. "Design and analysis design" typically refers to the structured approach of creating and evaluating methodologies, frameworks, or systems. It's a critical process in disciplines ranging from engineering to research, ensuring effectiveness, efficiency, and reliability in achieving desired outcomes.

    ReplyDelete
  2. M and m logico solutions
    Welcome to MandM Logico Solutions, your premier destination for best LIMO rental services in the USA. We are famous for offering a fleet of luxurious vehicles that display elegance and style. Whether you’re in need of a stylish party bus, an exotic or vintage car, or the comfort of chauffeur services, we deliver unforgettable journeys.

    ReplyDelete

Post a Comment

Popular posts from this blog

Web Application Development (WAD)

Web Application Development (WAD) WEB APPLICATION AND DEVELOPMENT ( WAD) Notes Unit Wise Unit I INTRODUCTION   HTML   CSS   WEB APPLICATION FUNDAMENTALS   Unit II XML   Unit III JQuery   JSON Java Script Unit IV AngularJS   Unit V MEAN Stack   SMACK Stack LAB PROGRAMS:  Click Here Important Question for MID I :  Click here WAD Previous Question : Click Here TEXT BOOK:  Click Hear Course Code Course Title Core/Elective PC 601 IT WEB APPLICATION DEVELOPMENT Core Prerequisite Contact hours per week CIE SEE Credits L T D P - 3 1 - - 30 70 3 Course Objective:     Ø    To develop dynamic web applications using the concepts of HTML 5.0 and   CSS     Ø    To understand the document structure and schemas and represent data in  t...

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 2 +4n+3, then prove that f(n)=O(n 2 ). 5.       List and define operations performed on sets? 6.       What do you mean by performance analysis of an algorithm? Explain. 7. ...