University questions


Worst Case Analysis (Usually Done)



Download 0.58 Mb.
Page4/4
Date28.05.2018
Size0.58 Mb.
#51062
1   2   3   4
Worst Case Analysis (Usually Done)

In the worst case analysis, we calculate upper bound on running time of an algorithm. We must know the case that causes maximum number of operations to be executed. For Linear Search, the worst case happens when the element to be searched (x in the above code) is not present in the array. When x is not present, the search() functions compares it with all the elements of arr[] one by one. Therefore, the worst case time complexity of linear search would be .


Average Case Analysis (Sometimes done)

In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs. We must know (or predict) distribution of cases. For the linear search problem, let us assume that all cases are uniformly distributed (including the case of x not being present in array). So we sum all the cases and divide the sum by (n+1). Following is the value of average case time complexity.


Average Case Time =
=
=

Best Case Analysis (Bogus)

In the best case analysis, we calculate lower bound on running time of an algorithm. We must know the case that causes minimum number of operations to be executed. In the linear search problem, the best case occurs when x is present at the first location. The number of operations in the best case is constant (not dependent on n). So time complexity in the best case would be




Unit II - BRUTE FORCE AND DIVIDE-AND-CONQUER

PART - A

  1. What is the time complexity of binary search? (May/June 2012)

Compare x with the middle name in the book. If x comes before y, recursively look for x in the first half. Otherwise recursively look for x in the second half. The search is finished when the beginning and end of the list are within one.

Best case Performance – O(1)

Average Case Performance – O(log n)

Worst Case Performance – O(log n)



  1. List down the problems that can be solved using divide and conquer approach. (Nov/Dec 2012)

  2. What do you mean by Divide and Conquer strategy? (May/June 2013)

Given a function to compute on ‘n’ inputs the divide-and-comquer strategy suggests splitting the inputs in to’k’ distinct susbsets, 1

  1. Write control abstraction for the ordering paradigm. (May/June 2013)

The general rule is that program i is stored on tape Ti mod m .on any given tape the programs are stored in nondecreasing order of their lengths
Greedy method control abstraction for the ordering paradigm

Algorithm store(n,m)


{
J=0;
For i=1 to n do
{
Write(“append program”,I,”to permutation for tape”,j);
J=(j+1) mod m;
}
}

PART - B

  1. Explain in detail how the divide and conquer technique can be applied to binary tree traversals. (Nov/Dec 2012) (16)

  2. Distinguish between Quick sort and merge sort and arrange the following numbers in increasing order using merge sort (18, 29, 68, 32, 43, 37, 87, 24, 47, 50) (May/June 2013) (16)

  3. Trace the steps in merge sort algorithm for the elements 122, 25, 70, 175, 89, 90, 95, 102, 123 and also compute its time complexity (16) (Nov/Dec 2012)

  4. Explain the binary search algorithm with example. And explain its best, worst and average case time complexities. (8) (Nov/Dec 2012)

  5. Explain how greedy method can be applied to solve the Knapsack problem.(16) (Nov/Dec 2012)

  6. Discuss the algorithm for finding a minimum cost binary search trees. Explain with suitable example. (Nov/Dec 2012) (8)

  7. Find the optimal and all feasible solution for the knapsack problem. The sack maximum capacity is 100. The item weights and corresponding profits are W=(10,20,30,40,50) and P=(20,30,66,40,60). Fill the sack such that the sack capacity should not exceed the maximum capacity and objective of the problem is to be maximize the profit. (8) (Nov/Dec 2012)

  8. Define Greedy Algorithm and find an optimal solution to the knapsack instance n=7, m=15. (p1, p2, p3,…..p7) = (10, 5, 15, 7, 6, 18, 3) and (w1,w2,w3,….w7) = (2, 3, 5, 7, 1, 4, 1) (May/June 2013) (16)



Unit III - DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE

PART – A


  1. What is principle of optimality? (Nov/Dec 2012)

  2. Define multistage graphs. (May/June 2013)

  3. What is the drawback of greedy algorithm? (May/June 2012)

  4. What is knapsack problem? (May/June 2013)

  5. What is dynamic programming? (May/June 2012)

  6. State principle of optimality. (May/June 2012)

  7. Differentiate greedy method and dynamic programming. (May/June 2012)

PART - B

  1. Apply backtracking to solve the following instance of subset sum problem. S = {1, 3, 4, 5}; d = {11} (Nov/Dec 2012) (16)

  2. Explain the multistage graph problem with an example. (May/June 2013) (8)

  3. Explain multistage graph. Find the minimum cost path from source to destination for the given graph using both forward and backward approach




  1. Describe all pairs shortest path problem and write procedure to compute lengths of shortest paths. (May/June 2013) (16)

  2. With a suitable example, explain all – pair shortest paths problem.(16) (May/June 2012)


Unit V - COPING WITH THE LIMITATIONS OF ALGORITHM

PART – A


  1. Compare backtracking and branch- and- bound techniques. (Nov/Dec 2012)

  2. What is Hamiltonian cycle? (May/June 2013)

  3. Define sum of subset problem. (May/June 2013)

  4. Define promising and non promising nodes in a state space tree. (May/June 2012)

  5. State Knapsack problem. (May/June 2012)

  6. What is the difference between explicit and implicit constraints? (May/June 2012)

  7. Define the basic principles of back tracking. (May/June 2012)

  8. Explain the control abstraction for Backtracking method. How 8 Queens problem could be solved using backtracking method? Explain. (Nov/Dec 2012) (8)

  9. An NP-hard problem can be solved in deterministic polynomial time, how? (May/June 2013)

  10. What is an articulation point in a graph? (May/June 2012)

  11. What is the difference between BFS and DFS methods? (May/June 2012)

PART - B

  1. Differentiate depth first search and breadth first search. (Nov/Dec 2012)

  2. For the following graph identify and explain the articulation points and draw the bi-connected components (May/June 2013) (16)





  1. Write a complete LC branch and bound algorithm for the job sequencing with deadlines problem. Use the fixed tuple size formulation. (May/June 2013) (16)

  2. How backtracking works on the 8 Queens problem with suitable example? (May/June 2013) (16)

  3. Write a backtracking program for solving the knapsack optimization problem. (May/June 2013) (8)

  4. Explain elaborately recursive backtracking algorithm. (May/June 2013) (8)

  5. Explain Hamilton Cycles. (Nov/Dec 2012) (8)

  6. Discuss the following with example (May/June 2012)

      1. n queen’s problem (8)

      2. Hamiltonian circuit problem (8)

  7. Write down and explain the procedure for tackling the 8 – queens problem using a backtracking approach. (16) (May/June 2012)

  8. Let w = {5,7,10,12,15,18,20} and m=35. Find all possible subset of w whose sum is equivalent to m. Draw the portion of state space tree for this problem. (Nov/Dec 2012) (8)

  9. Discuss in detail about the biconnected components of a graph. (16) (May/June 2012)

  10. Compare and contrast FIFO and LC branch – and – bound search techniques. (16) (May/June 2012)

  11. Give an algorithm to identify articulation points and to construct biconnected components Explain with an example. (Nov/Dec 2012) (8)

  12. Compare and contrast LC-BB and FIFO BB. (Nov/Dec 2012) (8)

  13. Let n=4 and m=15 the profits for the instances are (p1, p2, p3, p4, p5) = (10, 10, 12, 18) and the weights are (w1, w2, w3, w4, w5) = (2,4,6,9). Explain the working of 0/1 Knapsack problem using LC branch and bound technique. (Nov/Dec 2012) (8)

  1. Solve the travelling salesperson problem for the following graph using branch-and-bound algorithm. (Nov/Dec 2012) (16)






SNSCT – Department of Compute Science and Engineering Page



Download 0.58 Mb.

Share with your friends:
1   2   3   4



The database is protected by copyright ©ininet.org 2024
send message
    Main page
minimum number
same order
time complexity
space complexity