CS2251 Design and Analysis of Algorithms Important 16 marks Questions
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 prims 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