Algorithm Design

Details

1 Define computer algorithm. What are the characteristics of an algorithm that must be met?

Question Define computer algorithm. What are the characteristics of an algorithm that must be met? 2012

2 With example define computational procedure. How can you analyze and test an algorithm?

Question With example define computational procedure. How can you analyze and test an algorithm? 2012

3 How program performance can be evaluated? Explain with example.

Question How program performance can be evaluated? Explain with example. 2012

4 Let two matrix A and B; where A be an M*P and B be a P*N matrix. Write an algorithm format

Question Let two matrix A and B; where A be an M*P and B be a P*N matrix. Write an algorithm formatrix multiplication. Find out its time complexity. 2012

5 What is growth function? With example, briefly explain each type of it.

Question What is growth function? With example, briefly explain each type of it. 2012

6 Depict the general philosophy of D and C method. Write down the control abstraction of D and C.

Question Depict the general philosophy of D and C method. Write down the control abstraction of D and C. 2012

7 Show that the following recurrence relation has the growth function of O(n log)

Question Show that the following recurrence relation has the growth function of O(n log) 2012

8 Write the recursive and iterative process of binary search algorithm.

Question Write the recursive and iterative process of binary search algorithm. 2012

9 Consider the following adjacency matrix. Construct a shortest path using all-pair shortest path alg

Question Consider the following adjacency matrix. Construct a shortest path using all-pair shortest path algorithm: 2012

10 What is binary search tree? Mention the properties of binary search tree.

Question What is binary search tree? Mention the properties of binary search tree. 2012

11 What is Hamilton cycle? Give one example. Let G= (V, E) is an undirected graph with four vertices.

Question What is Hamilton cycle? Give one example. Let G= (V, E) is an undirected graph with four vertices. Draw the state space tree for coloring all the four nodes using only tree colors. 2012

12 Show that first 10 steps of 15 puzzle problem using DFS where the problem state is given below: 1 2

Question Show that first 10 steps of 15 puzzle problem using DFS where the problem state is given below: 1 2 3 4 5 6 8 9 10 7 11 13 14 15 12 2012

13 What is Knapsack problem? Consider a Knapsack problem to find out the optimal solution where

Question What is Knapsack problem? Consider a Knapsack problem to find out the optimal solution where 2012 2009

14 What is dynamic programming? Write the general procedure of dynamic programming.

Question What is dynamic programming? Write the general procedure of dynamic programming. 2012

15 Consider the following multistage graph. Using backward reasoning find the shortest path from S to

Question Consider the following multistage graph. Using backward reasoning find the shortest path from S to T. 2012

16 Discuss the complexity analysis of the following algorithm: a. Merge sort. b. Selection sort. c.

Question Discuss the complexity analysis of the following algorithm: a. Merge sort. b. Selection sort. c. Binary search. 2012

17 What is state-space tree? What is the manner in which the state-space tree for a back-tracking algo

Question What is state-space tree? What is the manner in which the state-space tree for a back-tracking algorithm in constructed? 2012

18 What is n-queen problem? Draw the solution for the 4-queens problem?

Question What is n-queen problem? Draw the solution for the 4-queens problem? 2012

19 What is an optimal solution and feasible solution? In which situations a search path can be termina

Question What is an optimal solution and feasible solution? In which situations a search path can be terminated in a branch and bound algorithm? 2012

20 What is the travelling salesman problem? Consider the following directed graph for travelling sales

Question What is the travelling salesman problem? Consider the following directed graph for travelling salesman problem. You are asked to find the minimum cost tour using dynamic algorithm approach: 2012

21 Define implicit and explicit constraint with example.

Question Define implicit and explicit constraint with example. 2012

22 Define the following terms: a. Tree edge. b. Back edge. c. Cross edge.

Question Define the following terms: a. Tree edge. b. Back edge. c. Cross edge. 2012

23 Explain the subset sum problem and discuss the possible solutions strategies using backtracking.

Question Explain the subset sum problem and discuss the possible solutions strategies using backtracking. 2012

24 Briefly explain the BFS algorithm with example.

Question Briefly explain the BFS algorithm with example. 2012

25 What are the criteria’s an algorithm must satisfy? Describe them.

Question What are the criteria’s an algorithm must satisfy? Describe them. 2012

26 What is pseudocode? Write ten convention of pseudocode.

Question What is pseudocode? Write ten convention of pseudocode. 2011

27 Explain time complexity of an algorithm.

Question Explain time complexity of an algorithm. 2011

28 Define ‘Big oh’, ‘Big theta’ and ‘Big omega’.

Question Define ‘Big oh’, ‘Big theta’ and ‘Big omega’. 2011

29 What are the general plans for divide-and-conquer algorithms?

Question What are the general plans for divide-and-conquer algorithms? 2011

30 Write the algorithms for finding the maximum and minimum and explain it.

Question Write the algorithms for finding the maximum and minimum and explain it. 2011

31 What are the difference between quicksort and mergesort? Mention the algorithm used to partition an

Question What are the difference between quicksort and mergesort? Mention the algorithm used to partition an array for quicksort. 2011

32 What is the improvement that can be applied to sequential search if the list is sorted?

Question What is the improvement that can be applied to sequential search if the list is sorted? 2011

33 What is the Greedy Choice Property? What are the steps required to develop a Greedy algorithm?

Question What is the Greedy Choice Property? What are the steps required to develop a Greedy algorithm? 2011

34 Explain multistage graph corresponding to backward approach with a suitable example.

Question Explain multistage graph corresponding to backward approach with a suitable example. 2011

35 Describe the steps to find out all pair’s shortest path.

Question Describe the steps to find out all pair’s shortest path. 2011

36 What do you mean by optimal binary search tree? Give an example to demonstrate two possible binary

Question What do you mean by optimal binary search tree? Give an example to demonstrate two possible binary search trees. 2011

37 Write down pseudocode for breadth first search.

Question Write down pseudocode for breadth first search. 2011

38 Draw depth first search (DFS) spanning tree and Breadth first search (BFS) spanning tree.

Question Draw depth first search (DFS) spanning tree and Breadth first search (BFS) spanning tree. 2011

39 What is reachability problem?

Question What is reachability problem? 2011

40 Prove that if G is a connected undirected graph with n vertices and n-1 edges, then G is a tree.

Question Prove that if G is a connected undirected graph with n vertices and n-1 edges, then G is a tree. 2011

41 What do you mean by backtracking? What are the factors that influence the efficiency of the backtra

Question What do you mean by backtracking? What are the factors that influence the efficiency of the backtracking algorithm? 2011

42 What is state-space tree? What is the manner in which the state-space tree for a backtracking algor

Question What is state-space tree? What is the manner in which the state-space tree for a backtracking algorithm is constructed? 2011

43 What is n-queens problem? Explain the solution for the 8-queen problem?

Question What is n-queens problem? Explain the solution for the 8-queen problem? 2011

44 What is the use of Dijkstra’s algorithm? Write the dijkstra’s algorithm for single sources short

Question What is the use of Dijkstra’s algorithm? Write the dijkstra’s algorithm for single sources shortest path problem. 2011

45 What is an algorithm? Write down the characteristics of an algorithm.

Question What is an algorithm? Write down the characteristics of an algorithm. 2011 2008

46 What do you mean by complexity of an Algorithm? Find the average case complexity of quicksort algor

Question What do you mean by complexity of an Algorithm? Find the average case complexity of quicksort algorithm. 2011

47 What is randomized algorithm? Write down the advantage and disadvantages of randomized algorithm.

Question What is randomized algorithm? Write down the advantage and disadvantages of randomized algorithm. 2011

48 Compare the performance between recursive and iterative MAX-MIN algorithm

Question Compare the performance between recursive and iterative MAX-MIN algorithm 2010

49 Write the control abstraction for divide and conquer.

Question Write the control abstraction for divide and conquer. 2010

50 Which application are not suitable for Quick sort and why?

Question Which application are not suitable for Quick sort and why? 2010 2014

51 Write short note on 15 puzzle problem.

Question Write short note on 15 puzzle problem. 2010

52 Differentiate backtracking and Bunch and Bound.

Question Differentiate backtracking and Bunch and Bound. 2010

53 Write the similarity among LC search of BFS and DFS.

Question Write the similarity among LC search of BFS and DFS. 2010

54 Show at least two solutions for 8 queen problem.

Question Show at least two solutions for 8 queen problem. 2010

55 Explain implicit explicit constraints with example.

Question Explain implicit explicit constraints with example. 2010

56 What do you mean by dynamic programming? What is the difference between optimal solution and feasib

Question What do you mean by dynamic programming? What is the difference between optimal solution and feasible solution? 2010

57 With suitable example briefly explain the Depth first search algorithm.

Question With suitable example briefly explain the Depth first search algorithm. 2010

58 What are the steps required to solve a Greedy problem?

Question What are the steps required to solve a Greedy problem? 2010

59 Why asymtotic notation is used?

Question Why asymtotic notation is used? 2010

60 Write an algorithm for n-queen problem.

Question Write an algorithm for n-queen problem. 2010

61 What is graph coloring and why it is used?

Question What is graph coloring and why it is used?

62 Describe sum of subset problem.

Question Describe sum of subset problem. 2010

63 List the important properties of Greedy method. What are different types of problems can be solved

Question List the important properties of Greedy method. What are different types of problems can be solved using Greedy method? 2010

64 What is an algorithm? What are the criteria an algorithm must satisfy?

Question What is an algorithm? What are the criteria an algorithm must satisfy? 2009

65 What do you mean by algorithm validation? Explain how to validate an algorithm.

Question What do you mean by algorithm validation? Explain how to validate an algorithm. 2009

66 What are the ways to describe an algorithm? Write down the pseudocode structures for looping and co

Question What are the ways to describe an algorithm? Write down the pseudocode structures for looping and conditional statements. 2009

67 Explain time space complexity of an algorithm.

Question Explain time space complexity of an algorithm. 2009

68 What is big ‘O’ and omega notation? Explain the growth rate of n log n, n^2 and 2^n functions w

Question What is big ‘O’ and omega notation? Explain the growth rate of n log n, n^2 and 2^n functions with n. 2009

69 Write an algorithm to create an n*n magic square for the case in which n is odd. What is the value

Question Write an algorithm to create an n*n magic square for the case in which n is odd. What is the value of its time complexity?

70 Write recursive function to add n numbers of an array with count statements. Write the recurrence r

Question Write recursive function to add n numbers of an array with count statements. Write the recurrence relation for the value of count and solve it. 2009

71 What is divide and conquer method?

Question What is divide and conquer method? 2009

72 Write down an algorithm for binary search.

Question Write down an algorithm for binary search.

73 Simulate the steps that the binary search algorithm goes through for 14 entries: (2009) -15, -6, 0,

Question Simulate the steps that the binary search algorithm goes through for 14 entries: (2009) -15, -6, 0, 7, 9, 23, 50, 81, 99, 113, 230, 231, 142, 151. 2009

74 Explain Hoare’s method of partitioning with suitable example.

Question Explain Hoare’s method of partitioning with suitable example. 2009

75 What is the time complexity of this algorithm?

Question What is the time complexity of this algorithm? 2009

76 Briefly describe about multistage graph.

Question Briefly describe about multistage graph. 2009

77 What is all-pair shortest path problem?

Question What is all-pair shortest path problem? 2009

78 Write an algorithm to determine the all-pair shortest paths.

Question Write an algorithm to determine the all-pair shortest paths. 2009

79 What is optimal binary search tree?

Question What is optimal binary search tree? 2009

80 Write down BFS algorithm.

Question Write down BFS algorithm. 2009

81 Write down recursive backtracking algorithm for sum of subsets problem.

Question Write down recursive backtracking algorithm for sum of subsets problem. 2009

82 Why do we need to analyze algorithms?

Question Why do we need to analyze algorithms? 2008

83 What do you mean by time complexity? Calculate the time complexity of the following algorithm:

Question What do you mean by time complexity? Calculate the time complexity of the following algorithm: 2008

84 What do you mean by performance measurement?

Question What do you mean by performance measurement? 2008

85 Show that the average case complexity of quick sort technique is O (n log n).

Question Show that the average case complexity of quick sort technique is O (n log n). 2008

86 Write down the control abstractions for the divide-and-conquer strategy.

Question Write down the control abstractions for the divide-and-conquer strategy. 2008

87 Write down the algorithm for finding the minimum and maximum number from a number list using divide

Question Write down the algorithm for finding the minimum and maximum number from a number list using divide and conquer method. 2008

88 Define the spanning tree. Describe Prim’s algorithm that finding minimum cost spanning tree with

Question Define the spanning tree. Describe Prim’s algorithm that finding minimum cost spanning tree with suitable example. 2008

89 Write down the difference between Greedy method and Dynamic programming.

Question Write down the difference between Greedy method and Dynamic programming. 2008

90 Differentiate between optimal solution and feasible solution.

Question Differentiate between optimal solution and feasible solution. 2008

91 Write down the algorithm for greedy strategies for the Knapsack problem.

Question Write down the algorithm for greedy strategies for the Knapsack problem. 2008

92 What are the difference between breadth search and bin search?

Question What are the difference between breadth search and bin search? 2008

93 Write down the advantages and disadvantages of BFS and DFS traversal algorithm.

Question Write down the advantages and disadvantages of BFS and DFS traversal algorithm. 2008

94 Discuss the optimal binary search trees problems.

Question Discuss the optimal binary search trees problems. 2008

95 Define binary tree and skewed binary tree with an example.

Question Define binary tree and skewed binary tree with an example. 2008

96 Discuss the different traversal techniques of binary tree.

Question Discuss the different traversal techniques of binary tree. 2008

97 Prove that, BFS (Breadth First Search) visits all vertices reachable from V.

Question Prove that, BFS (Breadth First Search) visits all vertices reachable from V. 2008

98 Write down the principal of optimality.

Question Write down the principal of optimality. 2008

99 Differentiate backtracking and branch-bound method.

Question Differentiate backtracking and branch-bound method. 2008

100 Discuss the 8’queen’s problem.

Question Discuss the 8’queen’s problem. 2008

101 Write down the algorithm for all pair shortest path.

Question Write down the algorithm for all pair shortest path. 2008 