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
Growth of Functions
Master Theorem
Heap Sort
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
1
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
1
x
x-1
1
1
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
3
1
5
9
2
1
4
8
5
1
3
6
8
1
2
5
6
115
0
1
0
4
2
93
6
83
0
72
5
62
2
52
0
41
5
31
0
27120-4inde
x
valu
e
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
3
1
5
9
2
1
4
8
5
1
3
6
8
1
2
5
6
115
0
1
0
4
2
93
6
83
0
72
5
62
2
52
0
41
5
31
0
27120-4inde
x
valu
e
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
v
30
1
2
n
Item1
.
....
.
+
20
ww
w
10 $60
1
2
n
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
0
0
0
0
2
2
2
6
12 6 8
4
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.
0 Comments
Please do not post any spam link