Tutorial & Answers- Design and Analysis of Algorithms I

1.

a. Define the term Algorithm in your own words.

Algorithm is finite set of well defined instructions for accomplishing some task given an initial state that will terminate in a defined end state.

source:http://www.newworldencyclopedia.org/entry/Algorithm

b. What are the important properties of an algorithm?

• Finiteness      :- an algorithm terminates after finite number of steps.
• Definiteness  :-each step of algorithm is unambiguous.{ This means that actions specify by the steps cannot be interpreted in multiple ways & can be performed without any confusion. }
• input              :-an algorithm accepts zero or more inputs.
• output            :-it produces at least one output.
• effectiveness :-it consists of basic instructions that are realizable.{ This means that the instructions performed by using the given input in a finite amount of time. }

source:http://www.newworldencyclopedia.org/entry/Algorithm

 

c. List the different way we can express an algorithm.

natural languages, pseudo codes, flow charts, and programming languages.

source:http://en.wikipedia.org/wiki/Algorithm#Expressing_algorithms

 

d. List the different classes of algorithms and give a short account on each of them including advantages and comparisons where relevant?

 

e. Why is the worst case complexity more important than the average case and the best case?

Because it give an assurance of the upper bound for how much of resources an algorithm would use

f. What is time complexity and what is space complexity, in computer science context?

• The time complexity of a problem is the number of steps that it takes to solve an instance of problem as a function of the size of the input(n),using the most efficient algorithm.

         { R(n)=>T(n) where R(n):worst case steps T(n)=time complexity }

• The space complexity of a problem is a related concept, that measures the amount of space, or memory required by the algorithm.

         Space complexity is also measured with Big O notation.

g. Define the terms efficient algorithm, inefficient algorithm and a correct algorithm.

• efficient algorithm :For each “efficient” run-time there is a constant, k, such that the running time is at most n^k when n is large enough.
• inefficient algorithm :For each “inefficient” run-time there is No constant, k, such that the running tine is at most n^k when n is large enough

          {Here we consider an algorithm with worst case run-time complexity of 2^n,3^n,4^n,n^logn}

• correct algorithm :algorithm is correct if for each input it produces the correct output

h. Define the terms polynomial time complexity and non-polynomial time complexity.

• Polynomial time complexity :There are problem f, fror which there is an algorithm a taking atmost n^k steps, an inputs of length n. i.e. f in T(n^k)
• Non-polynomial time complexity :There are problem f, fror which there is not an algorithm a taking atmost n^k steps, an inputs of length n. i.e. f not in T(n^k)

i. Define the three complexity classes of algorithms.

j. Define the terms deterministic algorithm and non-deterministic algorithm.

k. Differentiate between a decision problem and an optimization problem.

2.

a. What is computational complexity?

b. Why is the `Big-O' Notation is useful?

c. What is meant by NP-completeness?

d. List down 5 problems that belong to the NP-Complete category.

3. A farmer has a goat, a wolf and cabbages. He is on the eastern shore of the river and has to take the goat, the wolf and the cabbages to the western shore. He has a boat where he can travel with only one other item. The rules are that he cannot leave the cabbage along with the goat, and he cannot leave the goat alone with the wolf.

If you were to apply the Alpha-Beta Pruning method, the Branch and Bound Algorithm or the Backtracking Algorithm, which will give you a faster solution?

4. Write a recursive algorithm for merge sort in pseudo code together with the pseudo code for the merging operation.