Integer multiplication:

Name of the Algorithm Recurrence relation complexity

1 Normal multiplication (brute -- O(n^2)
force multiplication)
2 Divide and conquer T(n)=4T(n/2) + O(n) O(n^2)
3 Karastuba method T(n)=3T(n/2) + O(n) O(n^1.59)

1.Normal Multiplication:

Input two numbers

Multiply

12345 X 34567 5*5=25 n*n=n^2 f(n)=mul+add=n^2+n= O(n^2)

86415

74070

61725

49380

37035

------------

426729615

-------------

2. Divide and conquer method:

Input:

Integers X and Y

No. of digits : n

Output:

Z=X*Y

23=2 * 10 + 3

2345=23 * 10 ^2 +45

X=235678=235 * 10 ^ 3+ 678

Y=435890=435 * 10 ^3 + 890

Z= X * Y=(235 * 10 ^ 3+ 678) . (435 * 10 ^3 + 890)=(a+b).(c+d)=a.c+a.d+b.c+b.d

=235*10^3*435 * 10^3+235*10^3 *890+678*435 * 10 ^3+678 * 890

=(235*435)10^6+(235*890+678*435)10^3+678*890

No. of digits in the integers (X and Y)=n

No. of multiplications=6

No. multiplications of 10^x=2

 No. of multiplication of n/2 digits =4

Size of the subproblems=n/2

Recurrence relation= T(n)= 4 T(n/2) + O(n)

A= 4

B=2

Logba= Log24=2

N^ Logba=n^2

F(n)=n

Case 1 of master method epsilon=1

T(n)=O(N^ Logba)=O(n^2)

3. Karastuba method:

X=235678=235 * 10 ^ 3+ 678=a.10^(n/2) + b

Y=435890=435 * 10 ^3 + 890=c. 10^(n/2)+d

A=235 b=678

C=435 d=890

Z= X * Y=

V 10 ^n+ ( U –V-W) . 10^(n/2) +W

U=(a+b).(c+d)

V=a.c

W=b.d

X*Y=V10^n+(U-V-W)10 ^(n/2)+W

No. of digits in the integers (X and Y)=n

No. of multiplications=5

No. multiplications of 10^x=2 adding zeroes on the right side

No. of multiplication of n/2 digits =3

Size of the subproblems=n/2

Recurrence relation= T(n)= 3 T(n/2) + O(n)

A= 3

B=2

Logba= Log23=1.59

N^ Logba=n^1.59

F(n)=n
Case 1 of master method epsilon=0.59

T(n)=O(N^ Logba)=O(n^1.59)

X=1235678=1235 * 10 ^ 3+ 678=a.10^(n/2) + b

Y=0435890=0435 * 10 ^3 + 890=c. 10^(n/2)+d

N=7 n/2=7/2=3.5= c(3.5)=3

n/2=(n/2

karastuba(x,y,n)

If (n==1)

Return(x*y);

i=n/2

Divide x--- a and b

Divide y --- c and d

U=karastuba((a+b),(c+d),i)

V=karstuba(a,c,i)

W=karastuba(b,d,i)

Return(v.10^n+(u-v-w)10^i+w)

(a+b).(c+d)=a.c.10^n+(a.d+b.c).10^n/2+b.d
Graph

G(V,E)

Two dimensional matrix

1.weighted graph – entries will be cost of the edge

2. unweighted graph – entries 0 or 1

//input graph --------------------------------O(n^2)

//variables

Int g[5][5],I,j;

//loop for input

For(i=0;i<5;i++)

For(j=0;j<5;j++

Scanf(“%d”,&g[i][j]);

//display graph in matrix(adjacency matrix)

For(i=0;i<5;i++)

Printf(“\n”);

For(j=0;j<5;j++)

printf(“%d”,g[i][j]);

}
Adjancency list

Array – pointer to linked list

For each vertex we require one linked list

//create node structure

Struct node

Int data;

Struct node *next;

//one array – pointer to node

//create linked list for each vertex

DFS

12345

13245

Bfs

12345

13245

bfs

75
1. Unvisited 2 7 5 10 6 9 11 4
2 7 5 10 6 9 11 4

2. Visited but adjacents not visited yet 7 5

3. Visited its adjacents are also visited 2
4.

Bfs

Visit a node

Visit all its adjacents

First adjacent
 0 1 1 0 0
1 0 1 1 0
1 1 0 0 1
0 1 0 0 1
0 0 1 1 0
V1 V2 V3 V4 V5

Queue initialisatioin

Within the loop for dfs

Visit
 1 2 3 4 5
0 0 0 0 0
12345

Visit vertex visit[v]=1

Add adjacent

If (a[2][j]==1 && not visited[j])

Add j to the queue

Remove from queue 1 2 3 4 5

T(n)=3t(n/4)+n^2 =O(n^2)

N^(loga)= F(n)

Log3<1+e 2

Log4=1

level Size of the Steps in the node No. of Total steps in the
subproblem subproblems level
0 root n N^2 1 N^2
1 n/4 (n/4)^2 3 3(n/4)^2
2 n/16=n/4^2 (n/16)^2 9=3^2 9(n/16)^2
3 n/64=n/4^3 (n/64)^2 27 27(n/64)^2
…
k n/4^k (n/4^k)^2 3^k 3^k(n/4^k)^2
Total steps required by the algorithm=N^2+3(n/4)^2+9(n/16)^2+27(n/64)^2+…+3^k(n/4^k)^2

= n^2+(3/16) n^2+(9/16^2) n^2+(27/64^2) n^2+…..+((3^k)/(4^k)^2) n^2

=O(n^2)

Find the value of K

n/4^k=1

4^k=n

K=log4n

T(n)=3T(n/5)+n

T(n)=T(n/3)+T(2n/3)+n

Graph:

G(V,E) weighted and connected

V={v1,v2,v3,v4,v5,v6}

E={(v1,v2,6)

Single source shortest path

Source vertex- v1

Output

Destinations

V1V2

V1V3

V1V4

V1V5

V1V6
step A=source B C D E Shortest path
1 0 infinity infinity infinity infinity
2 0 10 3 infinity infinity a-c 3
3 acb 7 acd 8 a-ce 5 a-ce 5
4 A10 Ainfi aCb=7
aCb=7 aCd=11
einfini E14

5 Ainfi aCbd=9
C11
E14
aCbd=9
t

Session 6

1. T(n)=2T(n/2) +O(n) case 2: O(nlogn)

2. T(n)=9T(n/3)+n case 1 : O(n^2)
3. T(n)=T(2n/3)+1
A=1 b=3/2 log1=0 case 2 : O(logn)
4. T(n)=3T(n/4)+n case 3: O(n)

Log44=1

Log43=0.8

5. T(n)=2T(n/2)+nlogn

A=2 b=2 n^logba=n^log22=n^1

n^logba is asymptotically lesser than f(n)

But n^logba is not polynomially lesser than f(n)

N < nlogn by a factor or nlogn/n = logn

Hence master method cannot be applied to solve this recurrence.

6. T(n)=4T(n/2)+nlogn
A=4 b=2 n^logba=n^log24=n^2
F(n)=nlogn
N^2 > nlogn case1 O(n^2)
7. T(n)=2T(n/2)+n/logn
A=2 b=2 n^logba=n^log22=n^1
n^logba is asymptotically greater than f(n)
But n^logba is not polynomially greater than f(n)
N > n/logn by a factor or n/( n/logn)= n.logn/n= logn

8. T(n)=T(n/2)+T(3n/2)+ O(n)

Since the size of the sub problems are not same master method cannot be applied

9. T(n)=4T(n/2)+n case 1 O(n^2)

10. T(n)=4T(n/2)+n^2 case 2 O(n^2logn)
11. T(n)=4T(n/2)+n^3 case 3: O(n^3)
12. T(n)=4T(n/2)+n.sqrt(n) case 1 O(n2)

N < nlogn is not polynomially

N < nlogn by a factor or nlogn/n = logn

1. Substitution method
2. Iteration method
3. Recurrence tree method
4. Master method
//input : array and element to be searched

//output: whether the element is found or not

Master method:

Linear search=for loop =t(n)=3n

Recursive call function by

Merge sort

Array size n

Divide the array into 2 subarrays of equal size

Size of the subarray n/2

No of subarrays 2

Merge sorted sub arrays

T(n)= 2T(n/2)+ O(n)

1.check whether recurrence relation is in the format

T(n)=a.T(n/b) + f(n)

2. polynomial greater or smaller and asymptotically greater or smaller

N less complex than nlogn by a factor of logn

Asymptotically

Not polynomialy greater

N^2 less complex than n^2.logn by a factor of logn

Asymptotically

Not polynomialy greater

N^2 less complex than n^3 by factor of n

Asymptotically

polynomically greater

N^2 less complex than n^4 by a factor of n^2

Asymptotically

polynomially greater

n < n^2 logn by a factor of nlogn

 Asymptotically

polynomially greater

(Logn)^2 and nlogn

n (Logn)^2 base 10 Nlogn base 10

10 1 10
20 1.69 26
100 (Log100)^2=(log(10)^2)^2=(2log10)^2=(2)^2=4 100log100=100(2log10)=100.2.1=200
1000 9 1000

Fibnocci= T(n)= t(n-1)+T(n-2)+ O(1)

X^n T(n)= T(n-1)+O(1)

n (Logn)^2 base 10 Nlogn base 10 N^0.5

10 1 10
20 1.69 26
100 4 200
1000 9 1000

Recurrence tree:

Tree:

Root: f(n): non recursive part

Intermediatery nodes - recursion

Leaf nodes: terminate: base case