21-09-2012, 02:56 PM
Lecture Notes for Algorithm Analysis and Design
1Lecture Notes for Algorithm.pdf (Size: 745.5 KB / Downloads: 114)
Model and Analysis
When we make a claim like Algorithm A has running time O(n2 log n), we have an
underlying computational model where this statement is valid. It may not be true if
we change the model. Before we formalize the notion of a computational model, let
us consider the example of computing Fibonacci numbers.
Model of Computation
Although there are a few thousand variations of the computer with different architectures
and internal organization, it is best to think about them at the level of the
assembly language. Despite architectural variations, the assembly level language support
is very similar - the major difference being in the number of registers and the word
length of the machine. But these parameters are also in a restricted range of a factor
of two, and hence asymptotically in the same ball park. In summary, think about any
computer as a machine that supports a basic instruction set consisting of arithmetic
and logical operations and memory accesses (including indirect addressing). We will
avoid cumbersome details of the exact instruction set and assume realistically that
any instruction of one machine can be simulated using a constant number of available
instruction of another machine. Since analysis of algorithms involves counting the
number of operations and not the exact timings (which could differ by an order of
magnitude), the above simplification is justified.
Other models
There is clear trade-off between the simplicity and the fidelity achieved by an abstract
model. One of the obvious (and sometimes serious) drawback of the RAM model is
the assumption of unbounded number of registers since the memory access cost is
uniform. In reality, there is a memory hierarchy comprising of registers, several levels
of cache, main memory and finally the disks. We incur a higher access cost as we
go from registers towards the disk and for techological reason, the size of the faster
memory is limited. There could be a disparity of 105 between the fastest andthe
slowest memory which makes the RAM model somewhat suspect for larger input
sizes. This has been redressed by the external memory model.
External memory model
In this model, the primary concern is the number of disk accesses. Given the rather
high cost of a disk access compared to any CPU operation, this model actually ignores
all other costs and counts only the number of disk accesses. The disk is accessed as
contiguous memory locations called blocks. The blocks have a fixed size B and the
simplest model is parameterized by B and the size of the faster memory M. In this
two level model, the algorithms are only charged for transferring a block between the
internal and external memory and all other computation is free. It turns out that in
this model, the cost of sorting n elements is O