CST- 4111 Analysis of Algorithms
Definitions
(i) Time complexity
The time needed by an algorithm expressed as a function of the size of a
problem
is called the time complexity of the algorithm.
(ii) Asymptotic Time complexity
The limiting behavior of the complexity as size increases is called the
asymptotic time complexity.
(iii) Asymptotic Space complexity
Analogous definitions can be made for space complexity and asymptotic
space complexity.
(iv) Worst- case complexity
If for a given size the complexity is taken as the maximum complexity over
all inputs of that size, then the complexity is called worst- case complexity.
(v) Expected complexity
If the complexity is taken as the “average” complexity over all inputs of
given
size, then the complexity is called expected complexity.
(vi) Expected time complexity
The expected time complexity is the average, over all inputs of size n, of the
sum of the time taken by each instruction executed.
(vii) Uniform cost criterion
Under the uniform cost criterion each RAM instruction requires one unit of
time and each register requires one unit of space.
(viii) Bitwise computation
Bitwise computation is the same as straight-line code, except that
(1) All variables are assumed to have the values 0 or 1, i.e., they are bits.
(2) The operations used are logical (^ , v , ) rather than arithmetic.
(ix) Heap sort
Heap sort rearranges the element on the tree until the element on the tree
until the element associated with each vertex is greater than or equal to
the elements associated with its son.
(x) Balancing
The divide and conquer technique partitioned a problem into subproblems
of equal [Link] was not a concidence.A basic guide to good algorithm design
to maintain balance.
(xi) Accumulator
All computation takes place in the first register r0, called the accumulator,
which like every other memory register can hold an arbitrary integer.
(xii) Merge sorting
Instead of dividing a problem of size n into two problems one of size 1 and
one of size n-1, one should divide the problem into two subproblems of
approximately half the size.
Short Notes
(i) Memory
The memory consists of a sequence of registers r0, r1, …., ri each of which is
capable of holding an integer of arbitrary [Link] upper bound on the number
of
Registers that can be [Link] abstraction is valid in cases where:
1. The size of the problem is small enough to fit in the main memory of a
computer
2. The integers used in the computation are small enough to fit in one
computer
world.
(ii) Random Access Machine (RAM)
- A random access machine (RAM) models a one-accumulator computer in
which instructions are not permitted to modify.
- A RAM consists of a read-only input tape, a write-only output tape, a
program, and a memory.
- The input tape is a sequence of squares, each of which holds an integer
and the output is a write-only tape ruled into squares which are initially all
blank.
- The program is merely a sequence of labeled instructions and the memory
consists of a sequence of registers, each of which is capable of holding an
integer of arbitrary size.
(iii) Random Access Stored Program Model (RASP)
- The Random Access Stored Program Model (RASP) is similar to RAM
with the exception that the program is in memory and can modify itself.
- But, indirect addressing is not permitted.
- Each RASP instruction occupies two consecutive memory registers: the
first register holds the encoding of the operation code; the second register
holds the address.
(iv) Divide and conquer
A common approach to solving a problem, is to partition the problem into smaller
parts, find solutions for the parts, and then combine the solutions for the parts into a
solution for the whole. This approach, especially when used recursively, often yields
efficient solutions to problems in which the sub-problems are smaller version of the
original problem.
(v)Decision Tree
There are certain problems where it is realistic to consider the number of branch
instructions executed as the primary measure of complexity.
The usual representation for a program of branches is a binary tree called decision
[Link] interior vertex represents a decision and a leaf represents the output.
(vi)Bit Vector Operation
Instead of restricting the value of a variable to be 0 or 1, we might go in the opposite
direction and allow variables to assume any vector of bits as a value.
In those few algorithms where the bit vector model is used, it will be seen that the
length of the vectors used is considerably above the number of bits required to
represent the size of the problem.
(vii)Process of sorting of a Heap sort
Once the element of A have been rearranged into a heap, elements are removed one
at a time from the [Link] is done by interchanging A[1] and A[n] and rearranging
A[1], A[2], ... A[n-1] into a heap by using Procedure HEAPIFY. This process is
repeated until only one element left at the root and them becomes the sorted
sequence.
(viii) Working process of Bucket sort or Radix sort
Initialize m empty queues, one for each integer in the range 0 to m-1. Each queue is
called a [Link] the sequence a1, a2, . . . , an from left to right, placing element
ai in the a_ith [Link] the queues (the contents of queue i + 1 are
appended to the end of queue i) to obtain the sorted sequence.
(ix) Straight line program
For many problems it is reasonable to restrict attention to the class of RAM
programs in which branching instructions are used solely to cause a sequence of
instructions be repeated a number of times proportional to n, the size of the input.
The unroll program for each size n by duplicating the instructions to be repeatedly
an appropriate number of times. This results in a sequence of straight-line programs
of presumably increasing length one for each n.