CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT I QUESTIONS 1

16.            What do you mean by ²Best case-Efficiency” of an algorithm?

The ²Best case-Efficiency” of an algorithm is its efficiency for the Best-case input of size n, which is an input(or inputs)  of size n for which the algorithm runs the fastest among all possible inputs of that size.

    Ex: if you want to sort a list of numbers in ascending order when the numbers are given in ascending order. In this running time will be the smallest.

17.            Define the ²Average-case efficiency” of an algorithm?

The ²Average-case efficiency” of an algorithm is its efficiency for the  input of size n,  for which the algorithm runs between the best case and the worst case among all possible inputs of that size.

18.            What do you mean by “Amortized efficiency”?

The “Amortized efficiency” applies not only a single run of an algorithm but rather to a sequence of operations performed on the same data structure. It turns out that in some situations a single operation can be expensive ,but the total  time for an entire sequence of n such operations is always significantly better than the worst case efficiency of that single operation multiplied by n. This is known as “Amortized efficiency”.

19.            How to measure the algorithm’s efficiency?

It is logical to investigate the algorithm’s efficiency as a function of some parameter n indicating the algorithm’s input size.

Example: It will be the size of the list for problems of sorting, searching, finding the list’s smallest element, and most other problems dealing with lists.

20.            What is called the basic operation of an algorithm?

            The most important operation of the algorithm is the operation contributing the most to the total running time is called basic operation of an algorithm.

21.            How to measure an algorithm’s running time?

Let C_op be the time of execution of an algorithm’s basic iteration on a particular computer and let C (n) be the number of times this operation needs to be executed for this algorithm.  Then we can estimate the running time T(n) of a program implementing this algorithm on that computer by the formula

                                    T(n)   ≈  C_op C(n)

22.            Define order of growth.

            The efficiency analysis framework concentrates on the order of growth of an algorithm’s basic operation count as the principal indicator of the algorithm’s efficiency.  To compare and rank such orders of growth we use three notations

1)                                                      O (Big oh) notation

2)                                                      Ω (Big Omega) notation &

3)                                                      Θ (Big Theta) notation

23.            Define Big oh notation May/June 2006, April/May 2008

A function t(n) is said to be in O(g(n)) denoted t(n) ε O (g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some non negative integer n₀ such that

                                    T (n) < c g (n) for n > n₀

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT I QUESTIONS

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS

UNIT –I

  1.                What is an Algorithm?  May/June 2006, Nov/Dec 2008

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time

2.                State the Euclid’s algorithm for finding GCD of two given numbers.

ALGORITHM Euclid (m, n)

// Computes gcd(m,n) by Euclid’s algorithm

//Input   : Two nonnegative, not-both-zero integers m and n

//Output: Greatest common divisor of m and n

while n ¹ 0 do

                                    r ß m mod n

                                    m ß n

                                    n ß r

return m.

3.                What are Sequential Algorithms?

The central assumption of the RAM model is that instructions are executed one after another, one operation at a time. Accordingly, algorithms designed to be executed on such machines are called Sequential algorithms.

4.                What are Parallel Algorithms?

The central assumption of the RAM model does not hold for some newer computers that can execute operations concurrently, i.e., in parallel algorithms that take advantage of this capability are called Parallel algorithms.

5.                What is Exact and Approximation algorithm?

The principal decision to choose solving the problem exactly is called exact algorithm.

The principal decision to choose solving the problem approximately is called Approximation algorithm.

6.                What is Algorithm Design Technique?  Nov/Dec 2005

            An algorithm design technique is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.

7.                Define Pseudo code.

A Pseudo code is a mixture of a natural language and programming language like constructs. A pseudo code is usually more precise than a natural language, and its usage often yields more succinct algorithm descriptions.

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS PART B QUESTIONS

PART-B

I-UNIT

1. (a) Describe the steps in analyzing & coding an algorithm. (10)

    (b) Explain some of the problem types used in the design of

          algorithm. (6)

2.(a) Discuss the fundamentals of analysis framework . (10)

   (b) Explain the various asymptotic notations used in algorithm design. (6)

3. (a) Explain the general framework for analyzing the efficiency of algorithm. (8)

    (b) Explain the various Asymptotic efficiencies of an algorithm. (8)

4. (a) Explain the basic efficiency classes. (10)

    (b) Explain briefly the concept of algorithmic strategies. (6)

5. Describe briefly the notions of complexity of an algorithm. (16)

6. (a) What is Pseudo-code?Explain with an example. (8)

    (b) Find the complexity C(n) of the algorithm for the worst

     case,best case and average case.(Evaluate average case complexity for n=3,Where n is the   

     number of inputs) (8)

7. Set up & solve a recurrence relation for the number of key comparisons made by above  

     pseudo code. (4)

II-UNIT

1) Write a pseudo code for divide & conquer algorithm for merging two sorted arrays in to a single sorted one.Explain with example. (12)

2) Construct a minimum spanning tree using Kruskal’s algorithm with your own example. (10)

3) Explain about Knapsack Problem with example

4) Explain Dijikstra algorithm (8)

5) Define Spanning tree.Discuss design steps in Prim’s algorithm to construct minimum spanning   

    tree with an example. (16)

6)Explain Kruskal’s algorithm. (8)

7) Explain about binary search with example.

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT V QUESTIONS

UNIT V

1) Define tractable and intractable problems

Problems that can be solved in polynomial time are called tractable problems, problems that cannot be solved in polynomial time are called intractable problems.

2) Explain the theory of computational complexity

A problem's intractability remains the same for all principal models of computations and all reasonable input encoding schemes for the problem under consideration

3)Explain class P problems

Class P is a class of decision problems that can be solved in polynomial time by(deterministic) algorithms. This class of problems is called polynomial.

4)Explain undecidable problems

If the decision problem cannot be solved in polynomial time, and if the decision problems cannot be solved at all by any algorithm. Such problems are called Undecidable.

5) Explain the halting problem

Given a computer program and an input to it,determine whether the program will halt on that input or continue working indefinitely on it.

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT IV QUESTIONS

UNIT IV

l) Explain Backtracking

The principal idea is to construct solutions one component at a time and evaluate such partially constructed candidates as follows.

> If a partially constructed solution can be developed further without violating the problem's constraints, it is done by taking the first remaininig legitimate option for the next component.

> If there is no legitimate option for the next component, no alternatives for any remaining component need to be considered.

In this case, the algorithm backtracks to replace the last component of the partially constructed solution with its next option

2) Explain State Space Tree

If it is convenient to implement backtracking by constructing a tree of choices being made, the tree is called a state space tree. Its root represents an initial state before the search for a solution begins.

3) Explain promising and nonpromising node

A node in a state space tree is said to be promising if it corresponds to a partially constructed solution that may still lead to a complete solution;otherwise it is called nonpromising

4) Explain n-Queens problem

The problem is to place n queens on an n by n chessboard so that no two queens attack each other by being in the same row or same column or on the same diagonal.

5) Explain Subset-Sum Problem