Unit 9 Space and Time Tradeoffs
Structure:
9.1 Introduction
Objectives
9.2 Sorting
Distribution counting
9.3 Input Enhancement in String Matching
Horspool's algorithm
Boyer-Moore algorithm
9.4 Hashing Methodology
Hash function
Collision resolution
9.5 Indexing Schemes
B-Tree technique
9.6 Summary
9.7 Glossary
9.8 Terminal Questions
9.9 Answers
9.1 Introduction
By nowyou must be familiar with different methods of problem
solving using
algorithms. This unit deals with space and time tradeoffs in algorithmns.
Algorithm analysis determines the amount of resources necessary to
execute the algorithm. The vital resources are time
and storage. Most
algorithms are constructed to work with inputs of arbitrary length. Usually
the efficiency of an algorithm is stated as a function
to the number of steps (time
relating the input length
complexity) or storage locations (space
complexity).
A balance has to
be maintained in the space and time
aspects of
Research in Computer Science these days is more towards computing.
achieving time
efficiency.
With continuous reduction in prices,
space availability is perhaps not a
significant problem. But with respect to networking and robotics, however,
the necessity of a balance becomes
apparent. Memory has to be used
conservatively.
,Space-time or time-memory tradeoff in context with algorithms relates to the
execution of an algorithm. The execution of an algorithm can be done in a
short time by using more memory or the execution time becomes more
when memory used is less. Therefore selecting one alternative over the
other is the tradeoff here.
Many problems such as sorting or matrix-multiplication, have many choices
of algorithms to use, of which some are extremely space-efficient and some
extremely time-efficient. Space-time tradeoff proves that no algorithm exists
where efficiency is achieved by small space and small time simultaneously.
This unit includes the various approaches such as sorting by counting, input
enhancement in string matching, hashing, and B-Tree technique where time
is an important factor and the result of computation is quick at the cost of
space.
Objectives:
After studying this unit you should be able to:
explain the importance of space-time tradeoff in programming
t h e process of sorting by counting
analyze the process of input enhancement in string matching
define the role of hashing in space and time tradeoff
explain B-Tree technique with respect to space and time tradeoff
9.2 Sorting
Input enhancement is based on preprocessing the instance to obtain
additional information that can be used to solve the instance in less time.
Sorting is an example of input enhancement that achieves time efficiency.
First, let us study distribution counting.
9.2.1 Distribution counting
Distribution counting is a sorting method that uses some associated
information of the elements and places the elements in an array at their
relative position. In this method elements are actually distributed in the array
from 0th to (n-1)th position. This method ensures that the elements do not get
over written. The accumulated sum of frequencies also called as distribution
in statistics is used to place the elements at proper positions. Therefore this
method of sorting is called distribution counting method for sorting.
, 6 4 2 6|4 4 2
Figure 9.1: Array a1
The figure 9.1 depicts the values of array a[ ]. Observing the array we find
that the list contains only {2, 4, 6}. We will count the frequencies of each
element and the distribution count. Distribution count value represents the
last occurrence of corresponding element in the sorted array. These values
are given in table 9.1.
Table 9.1: Distribution Values of Elements of Array a[]
Elements 2 4 6
Frequencies 2 3 2
| Distribution values|2 5 7
We will have two arrays as shown in figure 9.2, one to store distribution
values in an array called Dval [0.2] and another array to store the sorted list
of elements called b[O..6] and then scan the unsorted list of elements from
right to left. The element that is scanned first is 2 and its distribution value
is 2.
0 1 2 O 1 2 3 4 5 6
2 57 2 N
array Dval[] array b[ ]
Figure 9.2: Sorted Element Stored in Array b[
Decrement the distribution value of 2, that is
Dval[0]=Dval[O]-1.
After which
move to left and scan the element at a[5]. So insert element 4 at 5-1 = 4
i.e bl4] position as shown in figure 9.3.
6 4 26 44 2
5 7 214
Figure 9.3: After Scanning Element a[5]
Now decrement the distribution value of 4 that is Dval 5-1 4. Scan al4
which is 4 then find the distribution value of 4 Dval[1]= 4 put 4 at 4 1 = 3.
at b[3] location. This is depicted in figure 9.4.
Structure:
9.1 Introduction
Objectives
9.2 Sorting
Distribution counting
9.3 Input Enhancement in String Matching
Horspool's algorithm
Boyer-Moore algorithm
9.4 Hashing Methodology
Hash function
Collision resolution
9.5 Indexing Schemes
B-Tree technique
9.6 Summary
9.7 Glossary
9.8 Terminal Questions
9.9 Answers
9.1 Introduction
By nowyou must be familiar with different methods of problem
solving using
algorithms. This unit deals with space and time tradeoffs in algorithmns.
Algorithm analysis determines the amount of resources necessary to
execute the algorithm. The vital resources are time
and storage. Most
algorithms are constructed to work with inputs of arbitrary length. Usually
the efficiency of an algorithm is stated as a function
to the number of steps (time
relating the input length
complexity) or storage locations (space
complexity).
A balance has to
be maintained in the space and time
aspects of
Research in Computer Science these days is more towards computing.
achieving time
efficiency.
With continuous reduction in prices,
space availability is perhaps not a
significant problem. But with respect to networking and robotics, however,
the necessity of a balance becomes
apparent. Memory has to be used
conservatively.
,Space-time or time-memory tradeoff in context with algorithms relates to the
execution of an algorithm. The execution of an algorithm can be done in a
short time by using more memory or the execution time becomes more
when memory used is less. Therefore selecting one alternative over the
other is the tradeoff here.
Many problems such as sorting or matrix-multiplication, have many choices
of algorithms to use, of which some are extremely space-efficient and some
extremely time-efficient. Space-time tradeoff proves that no algorithm exists
where efficiency is achieved by small space and small time simultaneously.
This unit includes the various approaches such as sorting by counting, input
enhancement in string matching, hashing, and B-Tree technique where time
is an important factor and the result of computation is quick at the cost of
space.
Objectives:
After studying this unit you should be able to:
explain the importance of space-time tradeoff in programming
t h e process of sorting by counting
analyze the process of input enhancement in string matching
define the role of hashing in space and time tradeoff
explain B-Tree technique with respect to space and time tradeoff
9.2 Sorting
Input enhancement is based on preprocessing the instance to obtain
additional information that can be used to solve the instance in less time.
Sorting is an example of input enhancement that achieves time efficiency.
First, let us study distribution counting.
9.2.1 Distribution counting
Distribution counting is a sorting method that uses some associated
information of the elements and places the elements in an array at their
relative position. In this method elements are actually distributed in the array
from 0th to (n-1)th position. This method ensures that the elements do not get
over written. The accumulated sum of frequencies also called as distribution
in statistics is used to place the elements at proper positions. Therefore this
method of sorting is called distribution counting method for sorting.
, 6 4 2 6|4 4 2
Figure 9.1: Array a1
The figure 9.1 depicts the values of array a[ ]. Observing the array we find
that the list contains only {2, 4, 6}. We will count the frequencies of each
element and the distribution count. Distribution count value represents the
last occurrence of corresponding element in the sorted array. These values
are given in table 9.1.
Table 9.1: Distribution Values of Elements of Array a[]
Elements 2 4 6
Frequencies 2 3 2
| Distribution values|2 5 7
We will have two arrays as shown in figure 9.2, one to store distribution
values in an array called Dval [0.2] and another array to store the sorted list
of elements called b[O..6] and then scan the unsorted list of elements from
right to left. The element that is scanned first is 2 and its distribution value
is 2.
0 1 2 O 1 2 3 4 5 6
2 57 2 N
array Dval[] array b[ ]
Figure 9.2: Sorted Element Stored in Array b[
Decrement the distribution value of 2, that is
Dval[0]=Dval[O]-1.
After which
move to left and scan the element at a[5]. So insert element 4 at 5-1 = 4
i.e bl4] position as shown in figure 9.3.
6 4 26 44 2
5 7 214
Figure 9.3: After Scanning Element a[5]
Now decrement the distribution value of 4 that is Dval 5-1 4. Scan al4
which is 4 then find the distribution value of 4 Dval[1]= 4 put 4 at 4 1 = 3.
at b[3] location. This is depicted in figure 9.4.
