CHAPTER 1
The Role of Algorithms in
Computing
July 2013
1.1 Algorithms
Definition
An algorithm is any well-defined computational procedure that
takes some value, or set of values, as input and produces some
value, or set of values, as output.
An algorithm is thus a sequence of computational steps that
transform the input into the output.
We can also view an algorithm as a tool for solving a wellspecified computational problem.
The statement of the problem specifies in general terms the
desired input/output relationship.
The algorithm
describes a
specific computational
procedure for achieving that input/output relationship.
9 4444 260
Physics I/II, English 123, Statics, Dynamics, Strength, Structure I/II, C++, Java, Data, Algorithms, Numerical, Economy
eng-hs.com, eng-hs.net
info@eng-hs.com 9 4444 260 .
July 2013
Example
One might need to sort a sequence of numbers into
nondecreasing order.
Here is how we formally define the
sorting problem:
Input: A sequence of n numbers a1, a2, , an.
Output: A permutation (reordering) a1, a2, , an of the input
sequence such that a1 a2 an.
Given the input sequence 31, 41, 59, 26, 41, 58.
A sorting algorithm returns as output the sequence
26, 31, 41, 41, 58, 59.
Such an input sequence is called an instance of the sorting
problem.
3
2
1
.
9 4444 260
Physics I/II, English 123, Statics, Dynamics, Strength, Structure I/II, C++, Java, Data, Algorithms, Numerical, Economy
eng-hs.com, eng-hs.net
info@eng-hs.com 9 4444 260 .
July 2013
In general, an instance of a problem consists of the input
(satisfying whatever constraints are imposed in the problem
statement) needed to compute a solution to the problem.
Sorting is a fundamental operation in computer science,
and as a result a large number of good sorting algorithms have
been developed.
Which algorithm is best for a given application depends on:
- The number of items to be sorted.
- The extent to which the items are already sorted.
- Possible restrictions on the item values.
- The kind of storage device: main memory, disks, tapes.
An algorithm is said to be correct if, for every input
instance, it halts with the correct output.
We say that a correct algorithm solves
the given computational problem.
An incorrect algorithm might not
halt at all on some input instances,
or it might halt with an answer
other than the desired one.
9 4444 260
Physics I/II, English 123, Statics, Dynamics, Strength, Structure I/II, C++, Java, Data, Algorithms, Numerical, Economy
eng-hs.com, eng-hs.net
info@eng-hs.com 9 4444 260 .
July 2013
Exercise 1.1-1
Give a real-word example in which one of the following
computational problems appears: sorting.
Solution
Real world examples:
1- In web service if we need to see the mails by date we use
sorting.
2- A simple example is when we are working with a PC, on
the desktop we can arrange the icons by name, type, size.
These are all using sorting.
..
:
.
:
!
9 4444 260
Physics I/II, English 123, Statics, Dynamics, Strength, Structure I/II, C++, Java, Data, Algorithms, Numerical, Economy
eng-hs.com, eng-hs.net
info@eng-hs.com 9 4444 260 .
July 2013
Exercise 1.1-3
Select a data structure that you have seen previously, and
discuss its strengths and limitations.
Solution
Data Structure : Arrays.
Strengths:
1- Arrays permit efficient ( constant time , O(1) ).
2- Most appropriate for sorting a fixed amount of data which
we need to access in random fashion.
3- Iterating through an array has an easier way of reference.
Limitations:
1- It is not efficient for insertion and deletion of elements
(O(n)).
2- It can not grow or shrink dynamically.
:
.
:
!
9 4444 260
Physics I/II, English 123, Statics, Dynamics, Strength, Structure I/II, C++, Java, Data, Algorithms, Numerical, Economy
eng-hs.com, eng-hs.net
info@eng-hs.com 9 4444 260 .
July 2013
Exercise 1.1-5
Come up with a real-word problem in which only the best
solution will do. Then come up with one in which a solution
that is approximately the best is good enough.
Solution
1- Hard real time systems: These are typically found
interacting at a low level with physical hardware in
embedded
systems.
In
which
time
is
critical.
If we have an algorithm of time complexity O(1) needed,
we need to use only this algorithm. This is the best
solution.
2- Soft real time systems: These are not critical time
requirements we can use on desired algorithms with
desired running time. Theres no need for best solution.
Approximately best solution can also be used.
9 4444 260
Physics I/II, English 123, Statics, Dynamics, Strength, Structure I/II, C++, Java, Data, Algorithms, Numerical, Economy
eng-hs.com, eng-hs.net
info@eng-hs.com 9 4444 260 .
July 2013
1.2 Algorithms as a technology
Suppose computers were infinitely fast and computer
memory was free. Would you have any reason to study
algorithms? The answer is yes, because you would still like to
demonstrate that your solution method terminates and does so
with the correct answer.
If computers were infinitely fast, any correct method for
solving a problem would do. You would probably want your
implementation to be within the bounds of good software
engineering practice (i.e., well designed and documented),
but you would most often use whichever method was the
easiest to implement.
Of course, computers may be fast, but they are not
infinitely fast. And memory may be cheap, but it is not free.
Computing time is therefore a bounded resource, and so is
space in memory. These resources should be used wisely, and
algorithms that are efficient in terms of time or space will help
you do so.
9 4444 260
Physics I/II, English 123, Statics, Dynamics, Strength, Structure I/II, C++, Java, Data, Algorithms, Numerical, Economy
eng-hs.com, eng-hs.net
info@eng-hs.com 9 4444 260 .
July 2013
Efficiency
Algorithms devised to solve
the same problem often differ
dramatically in their efficiency.
These differences can be much
more significant than differences
due to hardware and software.
Example
Two algorithms for sorting:
First: insertion sort, takes time roughly equal to c1n2 to
sort n items, where c1 is a constant that does not depend on n.
That is, it takes time roughly proportional to n2.
Second: merge sort, takes time roughly equal to c2n lg n,
where lg n stands for log2 n and c2 is another constant that also
does not depend on n.
Note: Insertion sort usually has a smaller constant factor
than merge sort, so that c1 < c2. The constant factors can be far
less significant in the running time than the dependence on the
input size n.
9 4444 260
Physics I/II, English 123, Statics, Dynamics, Strength, Structure I/II, C++, Java, Data, Algorithms, Numerical, Economy
eng-hs.com, eng-hs.net
info@eng-hs.com 9 4444 260 .
July 2013
Continue
Where merge sort has a factor of lg n in its running time,
insertion sort has a factor
of n, which is much larger.
Although insertion sort is usually faster than merge sort for
small input sizes, once the input size n becomes large enough,
merge sorts advantage of lg n vs. n will compensate for the
difference in constant factors.
No matter how much smaller c1 is than c2, there will always
be a crossover point beyond which merge sort is faster.
Assume that a faster computer (computer A) is running
insertion sort against a slower computer (computer B) running
merge sort.
A: executes one billion instructions per second with an
Insertion code that requires 2n2 instructions to sort n numbers.
(c1 = 2).
B: executes only ten million instructions per second with a
Merge sort code using a high-level language with
an inefficient compiler, which takes 50 n lg n
instructions to sort n numbers (c2 = 50).
9 4444 260
Physics I/II, English 123, Statics, Dynamics, Strength, Structure I/II, C++, Java, Data, Algorithms, Numerical, Economy
eng-hs.com, eng-hs.net
info@eng-hs.com 9 4444 260 .
July 2013
Continue
To sort one million numbers:
2. 106 instructions
109 instructions / second
2000 seconds,
50.106 lg 106 instructions
107 instructions / second
100 seconds.
Notice that computer B runs 20 times faster than computer A.
The advantage of merge sort is even more pronounced
when we sort ten million numbers: Insertion sort takes
approximately 2.3 days, merge sort takes under 20 minutes.
In general, as the problem size increases, so
does the relative advantage of merge sort.
9 4444 260
Physics I/II, English 123, Statics, Dynamics, Strength, Structure I/II, C++, Java, Data, Algorithms, Numerical, Economy
eng-hs.com, eng-hs.net
info@eng-hs.com 9 4444 260 .
July 2013
Exercise 1.2-2
Suppose we are comparing implementations of insertion sort
and merge sort on the same machine.
For inputs of size n, merge sort runs in 64n lg n steps, while
insertion sort runs in 8n2 steps. For which values on n does
insertion sort beat merge sort ?
Solution
Insertion sort beats merge sort when
8n2 < 64 n lg n
n < 8 lg n
2n/8 < n
This is true for 2 n 43 (found by using a calculator).
Rewrite merge sort to use insertion sort for
input size 43 or less in order to improve
the running time.
9 4444 260
Physics I/II, English 123, Statics, Dynamics, Strength, Structure I/II, C++, Java, Data, Algorithms, Numerical, Economy
eng-hs.com, eng-hs.net
info@eng-hs.com 9 4444 260 .
July 2013
Exercise 1.2-3
What is the smallest value of n such that an algorithm whose
running time is 100n2 runs faster than an algorithm whose
running time is 2n on the same machine?
Solution
The smallest value of n is 15. Where algorithm having running
time 100n2 runs faster than algorithm having running time 2n
on the same machine.
If
2n
100(n2)
n=0
n=1
100
n=2
400
n = 13
8,192
16,900
n = 14
16,384
19,600
n = 15
32,768
22,500
(where 0 not considered)
Thus n = 15 is the smallest value at which 100 n2 runs faster
than 2n.
9 4444 260
Physics I/II, English 123, Statics, Dynamics, Strength, Structure I/II, C++, Java, Data, Algorithms, Numerical, Economy
eng-hs.com, eng-hs.net
info@eng-hs.com 9 4444 260 .
