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:

link for the previous post OF UNIT 1-  click here
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[1], …, a[n]) 

m . a[1]; a[1]; 1 

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

if a[i] < m n-1 

then m . a[1]; 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 

dead end 

dead end 

dead end 

start 

dead end 

dead end 

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 

FAQs (Frequently asked Questions)

1. how to find utu btech notes of  Uttarakhand technical university ?

ANSWER. you can find utu(Uttarakhand technical university) notes exclusively on utupapers.com

2.how to find utu previous year paper with solutions ?

ANSWER. click on this link to see utu previous year paper with solutions.

Leave a Comment