TrueFalse 1 An algorithm is a sequence of unambiguous instru

True/False

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

2) We can sort, search and manipulate large volume of data without using arrays.

3) To perform a sequential search the data set must be sorted.

4) To perform a binary search the data set must be sorted.

5) Hackers use exhaustive search for an element with special property.

6) BFS has same efficiency as DFS and can be implemented with graphs.

7) A dag: a directed acyclic graph, i.e. a directed graph with no (directed) cycles.

8) To generate permutation for a set of N object we can use brute force.

9) Binary search can be done using divide and conquer.

10)Exponentiation can be done by Squaring

Algorithms Analysis

( 4 questions)

1.Write a Brute Force Algorithm to compute the exponent of an integer number using loop . (20 points).

2.Find gcd(31415, 14142) by applying Euclid’s algorithm, Show all steps. (10 points)

3.Assume that array A contains the following data:

A[0] A[1] A[2] A[3] A[4] A[5]

Use the algorithm Maximum element on page 25 pp slides chapter 2 Analysis of algorithms posted under week 2 and show ( write down) all the values for index i, A[i] and maxval.

In simple word show what is the content of i , A[i] and maxval for each iteration of the loop. (20 points).

4.For each of the following algorithms indicate (30 points)

(i) a natural size metric for its inputs,

(ii) its basic operation, and

(iii) whether the basic operation count can be different for inputs of the same size:

Algorithms

A) computing the sum of N umbers

B) computing N! (computing N factorial)

C) finding the largest element in a list of N numbers

D) Euclid’s algorithm

Solution

Here is the solution for True or False questions:

True/False
1) An algorithm is a sequence of unambiguous instructions for solving a problem, i.e.,
for obtaining a required output for any legitimate input in an infinite amount of time. TRUE.
2) We can sort, search and manipulate large volume of data without using arrays.   TRUE. (This can be done using linked lists also.)   
3) To perform a sequential search the data set must be sorted.                       FALSE. (Here the search will be done from first to last element.)  
4) To perform a binary search the data set must be sorted.                           TRUE. (Here a search technique must be applied by dividing array.)  
5) Hackers use exhaustive search for an element with special property.               TRUE.     
6) BFS has same efficiency as DFS and can be implemented with graphs.               TRUE.
7) A dag: a directed acyclic graph, i.e. a directed graph with no (directed) cycles.TRUE.
8) To generate permutation for a set of N object we can use brute force.           TRUE.
9) Binary search can be done using divide and conquer.                               TRUE.
10)Exponentiation can be done by Squaring                                           TRUE.