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 