3 3 P

m - CS5
o rit h
A lg
ysis of
A n a l
a n d
sig n Dr. Jeno

De Dept. of CSE

U4- SESSION 4: Space and Time trade off strategy -

sorting by counting
 Space and time trade off algorithms
A tradeoff is a situation where one thing increases and another
thing decreases. It is a way to solve a problem in:

• Either in less time and by using more space, or

• In very little space by spending a long amount of time.
• Trade off space in order to save the time or Trade off time
inorder to save the space.
• Storage memories are available at cheaper rate.
• Focus on space trade off
 Sorting by counting
• Not a comparison sort
• Example for linear sorting algorithm
• We define range of elements from 0 to k
• K is th largest element in the given array.
- Time efficient
 Sorting by counting-comparison
count how many elements are lesser than a given element
Sorting by counting

39 51 67 83 87 104 116
Sorting by counting

O(n2)
 Sorting by counting - To think

u = 7, v=8

u u+v 7 + 8 = 15

v u-v 15 - 8 = 7

u u-v 15-7 = 8

u = 8, v = 7
 Sorting by counting - Drawback
• The counting idea does work productively in a situation
in which elements to be sorted belong to a known small
set of values.

Distribution counting sort

Distribution counting sort
 Distribution counting sort

unique values

Generate frequency table

Whereever 23 occurs in the

22 should be placed in 4-1 21 should place
sorted array(first instance), its
location and continue till 1st in 1-1 location
first position should be at
location
location 6- 1. It should
continue till 4th location.
 Distribution counting sort

23 21 22 23 22 22

22

22

23

22

21

23
Distribution counting sort
 3 3 P
m - CS5
o rit h
A lg
ysis of
A n a l
a n d
sig n Dr. Jeno

De Dept. of CSE

U4- SESSION 6: Sorting by counting

 Sorting by counting- Try it yourself

• A [ 80,23,76,234,100,9,56]

• B [ 45, 50,49,49,43,45,43,48, 48]

 3 3 P
m - CS5
o rit h
A lg
ysis of
A n a l
a n d
sig n Dr. Jeno

De Dept. of CSE

U4- SESSION 6: Space tradeoff - Horspool string matching

 Horspool String matching Algo.
• Find the substring from a given text.
• comparision of brute force and horsepool method of
pattern matching.
pattern matching is very slow

comparision

shift by one character to the right

 Horspool String matching Algo.

shifting - more than one character

Shift table - decide the [Link] chacters to be shifted to the right

Brute force Horspool
Shifting by one character Shifting by more than one character

comparioson is left to right comparioson is right to left

 Horspool Algorithm - shift table construction

Initialize all the character shift value - length of the pattern

Look for first character “B”. 8 characters are infront of B

A-7
 Horspool Algorithm - shift table construction
Last character - don’t do

N-6

G-5

A-4

L-3

O-2

R-1
Horspool Algorithm - shift table construction

//Last charcter is not considering (m-2)

// ST[P[ j ] ] = m-1-j, s j increase SV decreases

 CHRIST
Deemed to be University

Shift Table - Example-3

B A R B E R m=6

j =0 Table[P[0]] = 6-1-0 Table[B] = 5

B A R B E R

Excellence and
Service 22
 CHRIST
Deemed to be University

Shift Table - Example

B A R B E R m=6

j =1 Table[P[1]] = 6-1-1 Table[A] = 4

B A R B E R

5 4

Excellence and
Service 23
 CHRIST
Deemed to be University

Shift Table - Example

B A R B E R m=6

j =2 Table[P[2]] = 6-1-2 Table[R] = 3

B A R B E R

5 4 3

Excellence and
Service 24
 CHRIST
Deemed to be University

Shift Table - Example

B A R B E R m=6

j =3 Table[P[3]] = 6-1-3 Table[B] = 2

B A R B E R

5 4 3 2

Excellence and
Service 25
 CHRIST
Deemed to be University

Shift Table - Example

B A R B E R m=6

j =4 Table[P[4]] = 6-1-4 Table[E] = 1

B A R B E R

5 4 3 2 1

Excellence and
Service 26
 CHRIST
Deemed to be University

Shift Table - Example

B A R B E R m=6

B A R B E R

5 4 3 2 1

B A R E

2 4 3 1

Excellence and
Service 27
 CHRIST
Deemed to be University

Horspool’s Algorithm: Example

B A R E
2 4 3 1

J I M - S A W - M E - I N - A - B A R B E R S H O P
B A R B E R
B A R B E R
B A R B E R
B A R B E R
B A R B E R

Excellence and
Service 28
 CHRIST
Deemed to be University

Horspool’s Algorithm: Example

B A R E
2 4 3 1

J I M - S A W - M E - I N - A - B A R B E R S H O P
B A R B E R
B A R B E R
B A R B E R
B A R B E R
B A R B E R
B A R B E R

Found at 17th Position

Excellence and
Service 29
 CHRIST
Deemed to be University

Shift Table - Example-4

B A 0 B A B m=6

j =0 Table[P[0]] = 6-1-0 Table[B] = 5

B A 0 B A B

Excellence and
Service 30
 CHRIST
Deemed to be University

Shift Table - Example

B A O B A B m=6

j =1 Table[P[1]] = 6-1-1 Table[A] = 4

B A 0 B A B

5 4

Excellence and
Service 31
 CHRIST
Deemed to be University

Shift Table - Example

B A O B A B m=6

j =2 Table[P[2]] = 6-1-2 Table[O] = 3

B A 0 B A B

5 4 3

Excellence and
Service 32
 CHRIST
Deemed to be University

Shift Table - Example

B A 0 B A B m=6

j =3 Table[P[3]] = 6-1-3 Table[B] = 2

B A 0 B A B

5 4 3 2

Excellence and
Service 33
 CHRIST
Deemed to be University

Shift Table - Example

B A 0 B A B m=6

j =4 Table[P[4]] = 6-1-4 Table[A] = 1

B A 0 B A B

5 4 3 2 1

Excellence and
Service 34
 CHRIST
Deemed to be University

Shift Table - Example

B A 0 B A B m=6

B A 0 B A B

5 4 3 2 1

B A O

2 1 3

Excellence and
Service 35
 CHRIST
Deemed to be University

Horspool’s Algorithm: Example

B A O
2 1 3

B E S S - K N E W - A B O U T - B A O B A B S
B A O B A B

Excellence and
Service 36
 CHRIST
Deemed to be University

Horspool’s Algorithm: Example

B A O
2 1 3

B E S S - K N E W - A B O U T - B A O B A B S
B A O B A B

Excellence and
Service 37
 CHRIST
Deemed to be University

Horspool’s Algorithm: Example

B A O
2 1 3

B E S S - K N E W - A B O U T - B A O B A B S
B A O B A B
B A O B A B

Excellence and
Service 38
 CHRIST
Deemed to be University

Horspool’s Algorithm: Example

B A O
2 1 3

B E S S - K N E W - A B O U T - B A O B A B S
B A O B A B
B A O B A B

Excellence and
Service 39
 CHRIST
Deemed to be University

Horspool’s Algorithm: Example

B A O
2 1 3

B E S S - K N E W - A B O U T - B A O B A B S
B A O B A B
B A O B A B
B A O B A B

Excellence and
Service 40
 CHRIST
Deemed to be University

Horspool’s Algorithm: Example

B A O
2 1 3

B E S S - K N E W - A B O U T - B A O B A B S
B A O B A B
B A O B A B
B A O B A B

Excellence and
Service 41
 CHRIST
Deemed to be University

Horspool’s Algorithm: Example

B A O
2 1 3

B E S S - K N E W - A B O U T - B A O B A B S
B A O B A B
B A O B A B
B A O B A B
B A O B A B

Excellence and
Service 42
 CHRIST
Deemed to be University

Horspool’s Algorithm: Example

B A O
2 1 3

B E S S - K N E W - A B O U T - B A O B A B S
B A O B A B
B A O B A B
B A O B A B
B A O B A B

Excellence and
Service 43
 CHRIST
Deemed to be University

Horspool’s Algorithm: Example

B A O
2 1 3

B E S S - K N E W - A B O U T - B A O B A B S
B A O B A B
B A O B A B
B A O B A B
B A O B A B
B A O B A B

Found at 17th Position

Excellence and
Service 44
 CHRIST
Deemed to be University

Puzzle time

Excellence and
Service
 CHRIST
Deemed to be University

Apply Horspool's algorithm to

search for the pattern THREE in the
text ONE TWO THREE.
T H R E
4 3 2 1

O N E T W O T H R E E

T H R E E

T H R E E

T H R E E

Excellence and
Service 46
 Horspool’s Algorithm CHRIST
Deemed to be University

Algorithm Horspool (T[0..n-1], P[0..m-1])

{
n= length(T)
m=length(P)
ShiftTable (P,ST)
i = m – 1 // comparison starts from last character
while (i <= n-1)
{
k = 0 // pattertn string
while (k<=m-1 and T[i – k] == P[m – 1 – k])
{ // if the character matches and still there are characters
k=k+1 left to match
}
if (k == m) // all the characters are matched, return the position of the pattern
return i – m + 1
else
i = i + ST [ T[i] ] // shift to the rigt by shift value
}
return -1
}
Excellence and
Service 47
 CHRIST
Deemed to be University

Horspool’s Algorithm: Example

● Pattern String = T C C T A T T C T T

T C C T A T T C T T
9 8 7 6 5 4 3 2 1

A C T
5 2 1

Excellence and
Service 48
 CHRIST
Deemed to be University

A
Horspool’s Algorithm:
C T
Example
Pattern String: TCCTATTCTT
5 2 1

T T A T A G A T C T C G T A T T C T T T T A T A G A T C T C C T A T T C T T
T C C T A T T C T T
T C C T A T T C T T
T C C T A T T C T T
T C C T A T T C T T
T C C T A T T C T T
T C C T A T T C T T
T C C T A T T C T T
T C C T A T T C T T
T C C T A T T C T T
T C C T A T T C T T
T C C T A T T C T T
T C C T A T T C T T
T C C T A T T C T T
T C C T A T T C T T
Excellence and
Service 49
Brute force
 3 3 P
m - CS5
o rit h
A lg
ysis of
A n a l
a n d
sig n Dr. Jeno

De Dept. of CSE

U4- SESSION 7: Space tradeoff - Boyer Moore string matching

Boyer moore- Video
 Boyer moore-

Note:
Value of * - length of pattern

Value of last character - length of

pattern
Boyer moore-
 Boyer moore-

Overwrite the vale of M

Boyer moore-
Overwrite the vale of A

For Last letter, value – length of pattern

Boyer moore-
Boyer moore-
 Boyer moore-

• See the value of “ T “ shift that many characters to right .

Boyer moore-
Boyer moore-
0 1 2 3 4 5 6
U N I V E R S *
6 5 4 3 2 1 7 7

Shift value = Length of pattern - index -1

U =7-0-1=6

N = 7- 1-1 =5

I = 7- 2-1 = 4

V = 7-3-1=3

E= 7-4-1 =2

R = 7-5-1 = 1

S = length of pattern = 7
 Boyer Moore string matching
C H R I S T U N I V E R S I T Y B A N G L O R E

U N I V E R S

n - length of the text = 26

m - length of the pattern = 7

 Boyer Moore string matching
C H R I S T U N I V E R S I T Y B A N G L O R E

U N I V E R S

U N I V E R S

n - length of the text = 26

m - length of the pattern = 7

Boyer moore-
Boyer moore-
Boyer moore-
Boyer moore-
Boyer moore-
Boyer moore-
 Boyer moore-

• The Bad Character Heuristic may take time in worst case.

• The worst case occurs when all characters of the text and pattern are same.
• txt[] = “AAAAAAAAAAAAAAAAAA” and pat[] = “AAAAA”.
Puzzle time
 3 3 P
m - CS5
o rit h
A lg
ysis of
A n a l
a n d
sig n Dr. Jeno

De Dept. of CSE

U4- Hashing
 Hashing
- Useful for searching purpose.

Elements can be arranged randomly

Elements be arranged in sorted order.

Extra time in sorting

 Introduces hashing
 Hashing

Store the element upon its index. Take the value of the element as its index , store in
that index

To search an element (key=10) , directly go to that index and search

Search time
O(1)
 Hashing

Time reduced
Space wasted

Improvement – mathematical model

Map the elements to hash table

List of elements
 Hashing
Properties of functions : one - one , Many – one
h( x) = x - one-one

Modify the function to efficiently utilize the space in the hash table.

Hash function, h(x) = x % size of hash table

Hashing
 Hashing

Time complexity is more than 1 but faster than O(logn)

Hashing
Hashing
Hashing
 Hashing
Search key element - 24

Drawback :clustering of elements at

consecutive locations.
When reaches the empty space stop the search. Takes lot of time to search an element
Hashing
h’(23) =[ h(23) + f(0) ] % 10

= [ 23%10 + 0] % 10
= [3 + 0] % 10
=3

h’(23)=[ h(23) + f(1) ] % 10

= [ 23%10 + 12] % 10
= [3 + 1] % 10
=4

h’(23)=[ h(23) + f(2) ] % 10

= [ 23%10 + 22] % 10
= [3 + 4] % 10
=7

Avoid clustering,
improve searching
time
 Hashing- Try it later
input {4371, 1323, 6173, 4199, 4344, 9679, 1234, 6788, 3445,
3421, 4567, 6792 and 1989} and a hash function H(X) = X (mod13)

show the resulting hash table when each of the collision resolution
technique is used:

i. Separate chaining table

ii. Open addressing hash table using linear probing
Block size – 512 bytes
Data can not be processed in the disk. Bring the data to the main memory process it
and write it back o to the disk.

Organizing the data directly in to the memory that is used by the program,- Data structure
Organizing the data on the disk efficiently , so that it can be accessed easily - DBMS
How data stored on the disk

Each row is 128 bytes

Each block contains 4 records .
100 records – 25 blocks are
required to store the DB table on
the disk.

To access any query from the

table – at most 25 blocks to be
accessed.

Block access time is more.

 Store the index in the disk

How much space index takes ?

Each entry takes

Whenever we want to search Each block

Access index. 4 blocks of index to contains 32
be accessed. Once you get the entries
index entry. Search that block in
the disk.
4 blocks
4+1 = 5 blocks to be searched.
 Multilevel indexing
100 records – 4 blocks

1000 records – 40 blocks

First level index

Second level index

Self managed indexing - automatic addition and deletion of index based on table size
B trees are originated from M-way search trees

Same DS is used in B trees

Drawback of M- way search tree

No guidelines on inserting the node.

B trees are M-way search tree with guidelines

Creation process
 Creation of B Trees
Insert keys . Degree
Is 4 hence 3 keys

Insert 50 , no space.
Split the node.
Insert 35. split
BT are useful in
Multilevel indexing.

Insert 5
Insert 60,70,80
Insert 15 . Split

Split the parent

3 levels of indices. BT node has child pointer(block pointer , record pointer) -> DB
 Prims algorithm
• SAK
Greedy Technique : Dijkstra’s Algorithm
Single path
Greedy Technique : Dijkstra’s Algorithm
Greedy Technique : Dijkstra’s Algorithm
Greedy Technique : Dijkstra’s Algorithm
Greedy Technique : Dijkstra’s Algorithm
Greedy Technique : Dijkstra’s Algorithm
Greedy Technique : Dijkstra’s Algorithm
Greedy Technique : Dijkstra’s Algorithm
 t h m -
l gori
o f A
l y s is
A na
and 5 3 3 P
s i gn C S
De Dr. Jeno
Dept. of CSE

U4- SESSION 1: Dynamic programming - Warshall Floyd algo.

 Dynamic programming
Warshall’s - Floyd’s Algorithm
All pairs shortest path

Dijikstra’s algorithm : SP from one vertex to all other vertices. TC = O(n 2)

Greedy method – Apply Dijikstra’s on all the vertices TC = n2 * n = O(n3)

 Dynamic programming
Warshall’s - Floyd’s Algorithm
Dynamic programming : problems should be solved by taking series of decision.

Prepare a matrix
 Dynamic programming
Warshall’s - Floyd’s Algorithm
Prepare a matrix by referring the previous matrix, consider 1 as intermediate vertex.
All the paths that belong to vertex 1 remain unchanged. Diagonals also unchanged

Find the remaining values

 Dynamic programming
Warshall’s - Floyd’s Algorithm
 Dynamic programming
Warshall’s - Floyd’s Algorithm
Prepare a matrix by referring the previous matrix, consider 2 as intermediate matrix.
All the paths that belong to vertex 2 remain unchanged. Diagonals also unchanged
 Dynamic programming
Warshall’s - Floyd’s Algorithm

Follow the same procedure for all the vertices

 Dynamic programming
Warshall’s - Floyd’s Algorithm
Prepare a matrix by referring the previous matrix, consider 3 as intermediate matrix.
All the paths that belong to vertex 3 remain unchanged. Diagonals also unchanged
 Dynamic programming
Warshall’s - Floyd’s Algorithm
Prepare a matrix by referring the previous matrix, consider 4 as intermediate matrix.
All the paths that belong to vertex 4 remain unchanged. Diagonals also unchanged
 Dynamic programming
Warshall’s - Floyd’s Algorithm
 Dynamic programming
Warshall’s - Floyd’s Algorithm
Steps for generating matrices ( n * n)

Time complexity
 3 3 P
m - CS5
o rit h
A lg
ysis of
A n a l
a n d
sig n Dr. Jeno

De Dept. of CSE

U4- SESSION 2: Dynamic programming - Warshall Floyd algo.

 Dynamic programming
Warshall’s - Floyd’s Algorithm
Try it !!!!
 Dynamic programming
Warshall’s - Floyd’s Algorithm
Transitive closure of directed graph
-A matrix with order n * n
-- A[i,j] = 1 , if there is a path from i to j
= 0 , otherwise
 Dynamic programming
Warshall’s - Floyd’s Algorithm
Transitive closure of directed graph

Try it !!!!
 3 3 P
m - CS5
o rit h
A lg
ysis of
A n a l
a n d
sig n Dr. Jeno

De Dept. of CSE

U4- SESSION 3: Dynamic programming - Knapsack

 Knapsack - Dynamic programming

Solution

Condition:
1. sum of the weight is max
2. sum of the weight < = bag capacity.
 Knapsack - Dynamic programming

1. Otimization problem
2. Every stage, decision- sequence of decision
3. All possible solution -pick up the best

4 objects - 24 possible solutions

n objects - 2n possible solutions

Time taken - O(2n) - not a good approach

 Knapsack - Dynamic programming-
Tabulation method

weights --->
0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
p w
 0 0 1 1 1 1 1
capacity <------

1 1 1
1 2
 2 0 0 1 2 2 3 3 3 3
2 3 0 1 2 5 5 7
3 0 6 7

4 0
5 4

6 5
 Knapsack - Dynamic programming

weights --->
0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
p w
 0 0 1 1 1 1 1
capacity <------

1 1 1
1 2
 2 0 0 1 2 2 3 3 3 3
2 3 0 1 2 5 5 7
3 0 6 7

4 0 0
5 4

6 5
 Knapsack - Dynamic programming

weights --->
0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
p w
 0 0 1 1 1 1 1
capacity <------

1 1 1
1 2
 2 0 0 1 2 2 3 3 3 3
2 3 0 1 2 5 5 7
3 0 6 7

4 0 0 1 2 5
5 4

6 5 till before 5th weight , will get negative weight, fill with previous
values
 Knapsack - Dynamic programming

weights --->
0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
p w
 0 0 1 1 1 1 1
capacity <------

1 1 1
1 2
 2 0 0 1 2 2 3 3 3 3
2 3 0 1 2 5 5 7
3 0 6 7

4 0 0 1 2 5
5 4

6 5
 Knapsack - Dynamic programming

weights --->
0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
p w
 0 0 1 1 1 1 1
capacity <------

1 1 1
1 2
 2 0 0 1 2 2 3 3 3 3
2 3 0 1 2 5 5 7
3 0 6 7

4 0 0 1 2 5 6
5 4

6 5
 Knapsack - Dynamic programming

weights --->
0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
p w
 0 0 1 1 1 1 1
capacity <------

1 1 1
1 2
 2 0 0 1 2 2 3 3 3 3
2 3 0 1 2 5 5 7
3 0 6 7

4 0 0 1 2 5 6 6
5 4

6 5
 Knapsack - Dynamic programming

weights --->
0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
p w
 0 0 1 1 1 1 1
capacity <------

1 1 1
1 2
 2 0 0 1 2 2 3 3 3 3
2 3 0 1 2 5 5 7
3 0 6 7

4 0 0 1 2 5 6 6 7
5 4

6 5
 Knapsack - Dynamic programming

weights --->
0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
p w
 0 0 1 1 1 1 1
capacity <------

1 1 1
1 2
 2 0 0 1 2 2 3 3 3 3
2 3 0 1 2 5 5 7
3 0 6 7

4 0 0 1 2 5 6 6 7 8
5 4

6 5
 Knapsack - Dynamic programming

Take the decision

weights --->
0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
p w
 0 0 1 1 1 1 1
capacity <------

1 1 1
1 2
 2 0 0 1 2 2 3 3 3 3
2 3 0 1 2 5 5 7
3 0 6 7

4 0 0 1 2 5 6 6 7 8
5 4

Consider the max. profit - 8 x1 x2 x3 x4

It
6 is generated
5 only in 4th row. Not available in
previous rows. We got this weight because of 
including 4th object only.
 Knapsack - Dynamic programming
profit = 8 , profit of this object = 6 remaining profit = 8-6 = 2

Check 2 is in 3rd row, 2nd row.

Take the decision
weights --->
0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
p w
 0 0 1 1 1 1 1
capacity <------

1 1 1
1 2
 2 0 0 1 2 2 3 3 3 3
2 3 0 1 2 5 5 7
3 0 6 7

4 0 0 1 2 5 6 6 7 8
5 4

x1 x2 x3 x4
profit
6 = 25 , profit of this object = 2
remaining profit = 2-2 = 0 1
1 0
 Knapsack - Dynamic programming
profit = 2 , profit of this object = 2 remaining profit = 2-2 = 0

Check 0 in 1st row, previous row Take the decision

weights --->
0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
p w
 0 0 1 1 1 1 1
capacity <------

1 1 1
1 2
 2 0 0 1 2 2 3 3 3 3
2 3 0 1 2 5 5 7
3 0 6 7

4 0 0 1 2 5 6 6 7 8
5 4

x1 x2 x3 x4
6X2 and5 x4 are included in the bag
0 0 1
1
 Knapsack - Dynamic programming

• Tabulation method 
• Set method - self study
 Knapsack - Dynamic programming

Try it yourself !!!

For the given set of items and knapsack capacity = 5 kg, find the optimal solution
for the 0/1 knapsack problem making use of dynamic programming approach.
 Knapsack - Dynamic programming

Step-01: Draw a table. Fill all the boxes of 0th row and 0th column with 0.
 Knapsack - Dynamic programming
Step-02:

• Start filling the table row wise top to bottom from left to right using the formula-

The last entry represents the maximum possible value that can be put into the
knapsack.
So, maximum possible value that can be put into the knapsack = 7.
 Knapsack - Dynamic programming
Step-03: Identifying Items To Be Put Into Knapsack

• Following Step-04,

• We mark the rows labelled “1” and “2”.

• Thus, items that must be put into the knapsack to obtain the maximum value 7
are-
• Item-1 and Item-2