# utu B.Tech DAA Analysis of Algorithm

Here you can find utu( Uttarakhand technical university) previous year paper with solutions along with notes of utu btech first year,second year,third year,fourth year/final year from semester 1st(first),2nd(second),3rd(third),4th(fourth),5th(fifth),6th(sixth),7th(seventh),8th(eighth).

in future we will go for other courses like BBA,BCA,MCA,BSC(Agriculture)..etc

Todays UTU notes will be on DAA (Design and Analysis of Algorithm).

TOPIC – ANALYSIS OF ALGORITHM UNIT -1

Subject Title:

#### Design and Analysis of Algorithm

Subject Code: TCS- 503

Total Number of Units: 5 Maximum Marks: 100

Unit I: Contains 7 Chapters:
Introduction
Growth of Functions
Master Theorem
Heap Sort
Quick Sort
Sorting in Linear Time
Order Statistics

This is the second post in which we will discuss about the following:

UNIT 1 – ANALYSIS OF ALGORITHM

Random Access Machine Model

Algorithms can be analyzed in a machine-independent
way using the Random Access Machine (RAM) model.
This model assumes a single processor.
Executes operations sequentially.
In the RAM model, instructions are executed one after the
other, with no concurrent operations.

Each memory access takes one time step.

Each simple operation(+,-,*,/,if) takes 1 time step.

All ops cost 1 unit.

Loops and subroutines are notconsidered simple

operations.

Simplifying assumption:

Eliminates dependence on the speed of our computer,

otherwise impossible to verify and to compare.

### Algorithm Analysis: Example

int sum(int n)

int psum;

Total No. of increments =5 =n

1 psum=0; 1

Total cost of line 2 =1 + n+1 +n

2 for(int i=1;i<=n;i++) 2n+2

3 sum+=i*i*i; 4n =2n +2

4 return sum; 1 Line 3: Explanation

Line 3 will be executed n times,

each time 4 units of time.

Lines 1 and 4 count for one unit each

Line 2: Explanation : Suppose n=5 So, Total Cost of line 3==4*n units

1: for initialization

1<=5: Yes; 2<=5: Yes; 3<=5: Yes

4<=5: Yes; 5<=5: Yes; 6<=5: No

Total No. of Comparison =6 =5+1 =n+1

Total cost: 6n + 4 . linear with respect to n

Algorithm Analysis: Example

Alg.: MIN (a, …, a[n])

m . a; a; 1

for i . a; 2 to n n-1 +1=n

if a[i] < m n-1

then m . a; a[i]; n-2

T(n) =1 [first step] + (n) [for loop] + (n-1) [if

condition] + (n-2) [the assignment in then] = 3 n -2

11 2 9 13 60 1

12

3456

Algorithm Analysis: Example

LinearSearch(A, key) cost times

1 i. 1 c1 1

2 while i= n and A[i] != key do c2 x

3. i++ c3 x-1

4. if i. n c4 1

5. then return true 5

c1

6. else return false c6 1

Best case: x=1

11 2 9 13 60 1

11

1 2 3 4 5 6 Key

T(n) =c1.1 +c2. 1 +c3.0 +c4.1 +c5.1

Worst case: x=n+1

T(n)=c1+ c2(n+1)+c3n+ c4 +c6

1 2 3 4 5 6 Key

11 2 9 13 60 1

100

Algorithm Analysis: Example

LinearSearch(A, key) cost1 i.

1 1

2 while i=n and A[i] != keydo 1

3. i++

1

4. if i.

n 1

5. then return true

1

6. else return false

Assign a cost of 1 to all statement executions.

Best case:

T(n) = c1.1 + c2. 1 + c3.0 +c4.1 + c5.1

= 1 + 1 + 0 + 1 + 1 =4

Worst case:

T(n) =c+ c2(n+1) +c3n+ c+c

1 46

=1 + (n+1) + n + 1 +1 = 2n+4

times

x-1

Algorithm Analysis: Example

LinearSearch(A, key) cost times

1 i.

1 11

2 while i=n and A[i] != keydo 1 x

3. i++

1 x-1

4. if i.

n 11

5. then return true

1 1

6. else return false 1 1

Average Case:

Suppose Array contains n=2 elements and key=50

If we assume that we search for a

random item in the list, on an12 12

50 10 50 50 10 10

average, Statements 2 and 3 will

Line 2 will be executed n/2=2/2=1

be executed n/2 times.

time

Hence, average-case complexity is

Then consider key=10.

Line 3 will be executed n/2=2/2=1 1+ n/2+n/2 + 1 +1 = n+ 3

time

16

10

115

93

83

72

62

52

41

31

27120-4inde

valu

Binary Search Technique: Example

Locates a target value in a sorted array / list by successively

eliminating half of the array from consideration.

Example: Searching the array below for the value 42:

Which Indexes does the algorithm examine to find value 42?

12

10

max

min

mid

16

10

115

93

83

72

62

52

41

31

27120-4inde

valu

Binary Search Technique: Example

For an array of size N, it eliminates ½ elements until 1 element

remains.

N, N/2, N/4, N/8, …,8, 4, 2, 1

How many divisions does it take?

Think of it from the other direction:

How many times do we have to multiply 1 by 2 to reach N?

1, 2, 4, 8, …, N/4, N/2, N

Call this number of multiplications “x”.

2x= N x= log2 N

min

mid

max

Binary Search Technique: Example

Search for 45

1 2 3 4 5 6 7 8 9 10 11

12 15 21 23 27 45 76 77 90 95 98

mid

Found on first step, 45 equals the middle item

Search for 27

1 2 3 4 5 6 7 8 9 10 11

12 15 21 23 27 45 76 77 90 95 98

mid

Search for 27

1 2 3 4 5 6 7 8 9 10 11

12 15 21 23 27 45 76 77 90 95 98

mid

Binary Search Technique: Example

Search for 27

1 2 3 4 5 6 7 8 9 10 11

12

15

21

23

27

45

76

77

90

95

98

mid

Found !

Search for 91

1 2 3 4 5 6 7 8 9 10 11

12 15 21 23 27 45 76 77 90 95 98

mid

Search for 91

1 2 3 4 5 6 7 8 9 10 11

12 15 21 23 27 45 76 77 90 95 98

91 < 95

mid

Search Completed, No value found

int lb = 0;

int ub = N – 1;

int mid = (lb + ub) / 2;

12 15 21 23 27 45 76 77 90 95 98

mid

Binary Search Technique : Algorithm

int BinarySearch(int A[], int N, int Num)

{ 0 1 2 3 4 5 6 7 8 9 10

while ((A[mid] != Num) && (lb <= ub))

{ For an array of size N, it eliminates ½

if (A[mid] > Num) elements until 1 element remains.

ub = mid – 1;

N, N/2, N/4, N/8, …,8, 4, 2, 1

else

How many divisions does it take?

lb = mid + 1;

Think of it from the other direction:

mid = (lb + ub) / 2;

How many times do we have to

multiply by 2 to reach N?

if (A[mid] == Num)

1, 2, 4, 8, …, N/4, N/2, N

return mid;

else Call this number of multiplications “x”.

return -1; 2x= N x= log2 N

### Example: Fractional Knapsack Problem

20

\$80

+

Item3

50

50

20 \$100

Item2

vv

30

Item1

….

+

20

ww

10 \$60

10

\$60 \$100 \$120

\$240

\$6/pound \$5/pound \$4/pound

Example: 0/1 Knapsack Problem

Item3

10

Item1

20

Item2

30

50 50

10

20

\$60

\$100

\$60 \$100 \$120 \$160

\$6/pound \$5/pound \$4/pound

### Backtracking

start

success!

Sum of subset Problem:

State SpaceTree for 3 items

w1 = 2, w2 = 4, w3 = 6 and S= 6

w1 +w2 +w3 w2 + w3

Solution

i1

i2

i3

yes no

12 6 8

410 6

yes no yes

yes no

no

no

no no yes

yes

yes

w1

w2

w1 +w2 w2 w3

w1 +w2 w1

w1 +w3

w1

Nodes are ordered in DFS

:-Preorder: Root-Left-Right

Solution

The sum of the included integers is stored at the

node.

Backtracking to solve n=4 queens problem