CS2251 Design and Analysis of Algorithms Important 16marks Questions

16 MARKS

UNIT-I

1) What are the important problem types focused by the researchers? Explain all the

types with example

2) What is empirical analysis of an algorithm? Discuss its strength and weakness.

3) Discuss the fundamentals of analysis framework.

4) Explain the various asymptotic notations used in algorithm techniques.

5) Describe briefly the notions of complexity of algorithm.

6) What is pseudo code? Explain with an example.

7) Explain various criteria used for analyzing algorithms.

8) Discuss briefly the sequence of steps in designing and analyzing algorithm

9) Explain the general framework for analyzing the efficiency of algorithm

10) Explain the fundamentals of algorithmic problem solving with algorithm design

and analysis process diagram

11) Explain simple factoring algorithm with example

12) Explain the Euclid’s algorithm with example

UNIT-II

1) Discuss the general plan for analyzing the efficiency of non recursive algorithms

2) Write an algorithm for a given numbers to n generate the nth number of the

Fibonacci sequences.

3) Explain the necessary steps for analyzing the efficiency of recursive algorithms.

4) Write short notes on algorithm visualization

5) Design a recursive algorithm to compute the factorial function F(n) =n! for an

arbitrary non negative integer n also derive the recurrence relation.

6) Explain the general plan for mathematical analysis of recursive algorithms with

example.

7) Explain algorithm visualization with examples.

8) Write an algorithm to find the number of binary digits in the binary representation

of a positive decimal integer and analyze its efficiency

9) Write an algorithm for finding of the largest element in a list of n numbers

10) Differentiate mathematical analysis of algorithm and empirical analysis of

algorithm

11) Explain static algorithm visualization and dynamic algorithm visualization with

example

12) Explain algorithm animation with example

UNIT-III

1) Explain Brute force method with proper example

2) Explain selection sort and bubble sort algorithm with proper example

3) Explain sequential searching algorithm with example

4) Explain brute force string matching algorithm with example

5) Explain the divide and conquer algorithms with example

6) Explain merge sort algorithm with example

7) Explain quick sort algorithm with example

8) Explain binary search algorithm with example

9) Explain binary tree traversals and related properties with example

10) Explain insertion sort with example

11) Explain Depth First Search and Breadth First Search

12) Write an algorithm to sort a set of N numbers using insertion sort

13) Trace the algorithm for the following set of number 20, 35, 18, 8 14, 41, 3, 39

14) Mention any three search algorithms which is preferred in general? why?

UNIT-IV

1) Explain Transform and conquer techniques with example

2) Explain pre sorting

3) Explain balanced search tree with example

4) Explain Binary Search Tree with example

5) Explain AVL Trees with example

6) Explain Warshall’s algorithm with example

7) Explain Floyd’s algorithm with example

8) Explain Optimal Binary search trees with example

9) Explain Prim’s algorithm with example

10) Explain Kruskal’s Algorithm

11) Explain Dijkstra’s Algorithm

12) Explain Huffman Trees

13) Explain the method of finding the minimum spanning tree for connected graph

using prim’;s algorithm

14) How will you find the shortest path between two given vertices using Dijkkstra’s

Algorithm? Explain

UNIT-V

1) Explain backtracking with example

2) Explain n-Queen’s problem with example

3) Explain Hamiltonian circuit problem with proper example

4) Explain subset problem with proper example

5) Explain Branch and bound Techniques with proper example

6) Explain Knapsack problem with example

7) Explain travelling salesman problem with example

8) Explain strassen’s matrix multiplication problem with example

9) Discuss the features of travelling salesman problem

10) Given a graph G={V,E,W} shown in the figure where vertices refer to cities,

edges refer to connection between cities, weight associated with each edge

represents the cost. Find out the minimum cost for the salesman

11) Discuss NP completeness in Knapsack problem with justification

12) Apply backtracking technique to solve the following instance of the subset sum

problem S={1,3,4,5} and d=11

13) Explain subset problem and discuss the possible solution strategies using

backtracking