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

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT III QUESTIONS

UNIT III

1)Define Dynamic Programming

Dynamic programming is a technique for solving problems with overlapping problems. Typically, these subproblems arise from a recurrence relating a solution to a given problem with solutions to its smaller subproblems of the same type. Rather than solving overlapping subproblems again and again, dynamic programming suggests solving each of the smaller sub problems only once and recording the results in a table from which we can then obtain a solution to the original problem.

2) Define Binomial Coefficient

                                                                                         n

The Binomial Coefficient, denoted C(n,k) or   k     is the number of Combinations(subsets) of k elements from an n-element set(0<k<n). The name "binomial coefficients" comes from the participation of these numbers in the so called binomial formula

(a+b)ⁿ =(n,0)aⁿ+..........+C(n,i)a^n-ibⁱ+.......+C(n,n)bⁿ

3) Define Transitive closure

The transitive closure of a directed graph with n vertices can be defined as the n by n Boolean matrix T = {ti,}, in which the element in the i^th row (1<i<n) and the j^th column (l<j<n) is 1 if there exists a non trivial directed path from the i^th vertex to j^th vertex ; otherwise , t_ij is 0.

4) Explain Warshalls algorithm

Warshall's algorithm constructs the transitive closure of a given digraph with n vertices through a series of n by n Boolean matrices  R⁽⁰⁾, ………, R^(k-l)R^(k),…….., R⁽ⁿ⁾

Each of these matrices provides certain information about directed paths in the digraph.

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT II QUESTIONS

UNIT II

1) Explain divide and conquer algorithms

Divide and conquer is probably the best known general algorithm design technique. It work according to the following general plan

i)A problem's instance is divided into several smaller instances of the same problem, ideally of about the same size.

ii) The smaller instances are solved

iii) If necessary, the solutions obtained for the smaller instances are combined to get a solution to the original problem

2) Define Merge Sort

Merge sort is a perfect example of a successful application of the divide and conquer technique. It sorts a given array A[0...n-l] by dividing it into two halves A[0...[n/2] - 1] and A[[n/2]....n-l], sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one.

3) Define Binary Search

Binary Search is remarkably efficient algorithm for searching in a sorted array. It works by comparing a search key K with the array's middle element A[m]. If they match, the algorithm stops; Otherwise, the same operation is repeated recursively for the first half of the array if K< A[m] and for the second half if K > A[m]

A[0].............A[m-l] A[m] A[m+l]............. A[n-l]

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.

DESIGN AND ANALYSIS OF ALGORITHMS SYLLABUS 2012

SYLLABUS

CS 2251                  DESIGN AND ANALYSIS OF ALGORITHMS                                  3 1 0 4

UNIT I                                                                                                                                 9

Algorithm Analysis – Time Space Tradeoff – Asymptotic Notations – Conditional asymptotic notation – Removing condition from the conditional asymptotic notation - Properties of big-Oh notation – Recurrence equations – Solving recurrence equations – Analysis of linear search.

UNIT II                                                                                                                               9

Divide and Conquer: General Method – Binary Search – Finding Maximum and Minimum – Merge Sort – Greedy Algorithms: General Method – Container Loading – Knapsack Problem.

UNIT III                                                                                                                             9

Dynamic Programming: General Method – Multistage Graphs – All-Pair shortest paths – Optimal binary search trees – 0/1 Knapsack – Travelling salesperson problem .

UNIT IV                                                                                                                             9

Backtracking: General Method – 8 Queens problem – sum of subsets – graph coloring – Hamiltonian problem – knapsack problem.

UNIT V                                                                                                                               9

Graph Traversals – Connected Components – Spanning Trees – Biconnected components – Branch and Bound: General Methods (FIFO & LC) – 0/1 Knapsack problem – Introduction to NP-Hard and NP-Completeness.

TUTORIAL  = 15                                         Total = 60

TEXT BOOK:

1.                  Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, Computer Algorithms/ C++, Second Edition, Universities Press, 2007. (For Units II  to V)

2.                  K.S. Easwarakumar, Object Oriented Data Structures using C++, Vikas Publishing House pvt. Ltd., 2000 (For Unit I)

REFERENCES:

1.      T. H. Cormen, C. E. Leiserson, R.L.Rivest, and C. Stein, "Introduction to Algorithms",      Second Edition, Prentice Hall of India Pvt. Ltd, 2003.

2.      Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, "The Design and Analysis of Computer Algorithms",  Pearson Education, 1999.

DESIGN AND ANALYSIS OF ALGORITHMS ANNA UNIVERSITY PREVIOUS YEAR QUESTION PAPER DOWNLOAD

CS2251 - DESIGN AND ANALYSIS OF ALGORITHMS ANNA UNIVERSITY PREVIOUS YEAR QUESTION PAPER DOWNLOAD

B.E./B.Tech. DEGREE EXAMINATION, APRIL/MAY 2010.

Fourth Semester

Computer Science and Engineering

CS2251 - DESIGN AND ANALYSIS OF ALGORITHMS

(Regulation 2008)

Time: Three hours                                                                                                  Maximum:100 marks

Answer ALL Questions.

PART A- (10 X 2= 20 marks)

1. Differentiate Time complexity from Space complexity.

2. What is a Recurrence Equation?

3. What is called Substitution method?

4. What is an Optimal solution?

5. Define Multistage Graphs.

6. Define Optimal Binary Search Tree.

7. Differentiate Explicit and Implicit Constraints.

8. What is the difference between a Live Node and a Dead Node?

9. What is a Biconnected Graph?

10. What is a FIFO branch - and - bound algorithm?

PART B- (5 X 16 = 80 Marks)