1.1 Algorithm Specification:

 

An algorithm is a step by step procedure to solve a problem. In normal language, algorithm is defined as a sequence of statements which are used to perform a task. These Algorithms are used to convert our problem solution into step by step statements. These statements can be converted into computer programming instructions which form a program. This program is executed by computer to produce solution

 

                                                                                                   Fig 1.1: Flow chat of Algorithm

Every algorithm must satisfy the following specifications…

Input – Every algorithm must take zero or more number of input values from external.

Output – Every algorithm must have an output as result.

Definiteness – Every statement in an algorithm must be clear

Finiteness – For all different cases, the algorithm must produce result within a fixed number of steps.

Effectiveness – Every instruction must be basic enough to be carried out and it also must be sufficient

 

An Example Algorithm [2]

 

Let’s look at a very simple algorithm called find_max ().

Problem:

Given a list of positive numbers, return the largest number on the list.

Inputs: A list P of positive numbers. This list must contain at least one number. (Asking for the largest number in a list of no numbers is not a meaningful question.)

Outputs: A number N, which will be the largest number of the list.

 

Algorithm:

Set max to 0.

For each number x in the list P, compare it to max. If x is larger, set max to x.

max is now set to the largest number in the list.

 

An implementation in Python:

def find_max (L):

max = 0

for x in P:

if x > max:

max = x

return max

 

 

 

Recursive story of find_max () [2]

 

If P is of length 1, return the first item of P.

Set v1 to the first item of P.

Set v2 to the output of performing find_max () on the rest of P.

If v1 is larger than v2, return v1. Otherwise, return v2.

 

Implementation:

 

def find_max (L):

if len(P) == 1:

return P [0]

v1 = P [0]

v2 = find_max (L [1:])

if v1 > v2:

return v1

else:

return v2

 

 

Performance of an algorithm means predicting the resources which are required to an algorithm to perform its task. It depends upon two factors i.e. amount of memory used and amount of compute time consumed on any CPU. Formally they are notified as complexities in terms of: [3]

 

Performance Analysis of an Algorithm: There are many criteria upon which we can judge an algorithm. [Ref]

1. Does it do what we want it to do? Results
2. Does it work correctly according to original specifications of the task? Quality
3. Is there documentation that describes how to use it and how it works? Documentation
4. Are procedures created in such a way that they perform logical sub-functions? Modularity
5. Is the code readable? Readability These criteria are all important when it comes to writing software for large systems.

 

1.2 Performance analysis:

 

Performance analysis of algorithms are analyzed on following things:

• Correctness

correctness is asserted when it is said that the algorithm is correct with respect to its requirement (correctly).

• Simplicity

Program can easily be verified, modifying is easy and also debugging.

• Readability

Code in the Algorithm must be readable.

• Space Complexity: Ref to 1.3 topic
• Time Complexity: Ref to 1.4 topic

 

1.3 Space Complexity:

 

For any algorithm, memory is required for the following purposes:

Memory required to store program instructions

Memory required to store constant values

Memory required to store variable values

And for few other things

 

In algorithm Space Complexity is the amount of memory it needs to run to completion i.e. from start of execution to its termination. Space need by any algorithm is the sum of following components:

• C represent the fixed space required which is independent of the characteristics of the inputs and output which include Instruction space, space for simple variable, fixed -size structure, constant.
• Fixed Component: This is independent of the characteristics of the inputs and outputs. which includes: Instruction Space, Space of simple variables, fixed size component variables, and constants variables.
• Variable Component: This consist of the space needed by component variables whose size is dependent on the particular problems instances (Inputs/Outputs) being solved, also this included the data structure components like Linked list, heap, trees, graphs etc.

Therefore, the total space requirement of any algorithm ‘A’ can be provided as

 

Space (A) = C + Fixed Components (A) + Variable Components (A)

 

The C Programming Language compiler requires the following:

2 bytes to store Integer value,

4 bytes to store Floating Point value,

1 byte to store Character value,

6 (OR) 8 bytes to store double value

 

Example: Space Complexity

 

Algorithm Sum (number, size) \\ procedure will produce sum of all numbers provided in ‘number’ list

{

result=0.0;

for count = 1 to size do                      \\will repeat from 1,2,3, 4….size times

result= result + number[count];

return result;

}

 

In above example, when calculating the space complexity, we will be looking for both fixed and variable components. Here we have

 

Fixed components as ‘result’, ‘count’ and ‘size’ variable there for total space required is three (3) words.

 

Variable components are characterized as the value stored in ‘size’ variable (suppose value store in variable ‘size ‘is ‘n’). Because of this will decide the size of ‘number’ list and will also drive the for loop. Therefore, if the space used by size is one word then the total space required by ‘number’ variable will be ‘n’ (value stored in variable ‘size’).

 

Therefore, the space complexity can be written as Space (Sum) = 3 + n;

 

1.4 Time Complexity:

 

The time complexity of an algorithm is the total amount of time required by an algorithm to complete its execution the time taken by a program is the sum of the compile time and the run/execution time. The compile time is independent of the instance (problem specific) characteristics. Following factors affect the time complexity: [3]

• Characteristics of compiler used to compile the program.
• Computer Machine on which the program is executed and physically clocked.
• Multiuser execution system.
• Number of program steps.

Therefore, the again the time complexity consist of two components fixed (factor 1 only) and variable/instance (factor 2, 3 & 4), so for any algorithm ‘A’ it is provided as:

 

Time (A) = C + Fixed Time (A) + Instance Time (A)

 

Example: Table 1.1: Time Complexity [3]

Statement	Steps per execution	Frequency	Total Steps
Algorithm Sum (number, size)	0	–	0
{	0	–	0
result=0.0;	1	1	1
for count = 1 to size do	1	size+1	size + 1
result= result + number[count];	1	size	size
return result;	1	1	1
}	0	–	0
Total			2size + 3

In above example if you analyze carefully frequency of “for count = 1 to size do” it is ‘size +1’ this is because the statement will be executed one time more die to condition check for false situation of condition provided in for statement. Now once the total steps are calculated they will resemble the instance characteristics in time complexity of algorithm. Also, the repeated compile time of an algorithm will also be constant every time we compile the same set of instructions so we can consider this time as constant ‘C’. Therefore, the time complexity can be expressed as: Time (Sum) = C + (2size +3)  

 

Performance analysis of algorithms are analyzed on following things:

• Correctness

correctness is asserted when it is said that the algorithm is correct with respect to its requirement (correctly).

• Simplicity

Program can easily be verified, modifying is easy and also debugging.

• Readability

Code in the Algorithm must be readable.

 

 

 

 

1.5 Asymptotic Notation:

 

 

Asymptotic analysis of an algorithm refers to defining the mathematical framing of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case, and worst-case scenario of an algorithm.

 

Asymptotic analysis is input bound i.e., if there’s no input to the algorithm, it is concluded to work in a constant time. Other than the “input” all other factors are considered constant.

 

Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. For example, the running time of one operation is computed as f(n) and may be for another operation it is computed as g(n2). This means the first operation running time will increase linearly with the increase in n and the running time of the second operation will increase exponentially when n increases. Similarly, the running time of both operations will be nearly the same if n is significantly small.

 

Usually, the time required by an algorithm falls under three types −

 

Best Case − Minimum time required for program execution.

Average Case − Average time required for program execution.

Worst Case − Maximum time required for program execution.

 

Following are the commonly used asymptotic notations to calculate the running time complexity of an algorithm. [4]

1. Ο Notation
2. Ω Notation
3. θ Notation

 

1. Big Oh Notation, Ο

The notation Ο(n) is the formal way to express the upper bound of an algorithm’s running time. It measures the worst-case time complexity or the longest amount of time an algorithm can possibly take to complete.

n

For example, for a function f(n)

Ο(f(n)) = {g(n): there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0.}

Example:         F(n) =2n+3

≤

or

≤

1. Omega Notation, Ω

The notation Ω(n) is the formal way to express the lower bound of an algorithm’s running time. It measures the best-case time complexity or the best amount of time an algorithm can possibly take to complete.

n

 

For example, for a function f(n)

Ω(f(n)) ≥ {g(n): there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0.}

 

Example:

 

1. Theta Notation, θ

The notation θ(n) is the formal way to express both the lower bound and the upper bound of an algorithm’s running time. It is represented as follows −

θ(f(n)) = {g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0.}

 

 

Example:

 

1.6 Randomized Algorithms:

 

 

Deterministic Algorithms:

 

An algorithm whose behavior can be completely predicted from the input. Which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm [6,7]

 

Deterministic Algorithm

O/P

I/P

 

 

 

 

Randomized Algorithms:

In addition to input, algorithm it takes a source of random numbers as input and makes random choices during execution; [8] Behavior can vary even on a fixed input. These algorithms are used in situation where no exact and fast algorithm is known.

 

 

O/P

Randomize Algorithm

I/P

 

 

 

R.no

 

 

 

 

i/p    o/p {input union random number = output}

it is divided into two parts which is given below:

Las Vegas Algorithm:

Monte Carlo Algorithm

Randomize Algorithm

 

 

 

 

 

 

 

 

 

Las Vegas Algorithm: Algorithm that use random input so that they always terminate with correct answer, but where the expected running time is finite. Example Quick Sort.

Consider array of “A”, size “n”, and searching an element “a” in that array which is shown below:

LasVegas Search (A, n)

{

While (true)

{

Randomly select an element out of n element;

if (a is found)

return true;

}

}

In the above example the number of iteration varies and be arbitrarily large, but it will give always true value, as it is infinite loop.

 

Monte Carlo Algorithm: Which have a chance of producing an incorrect answer but the running time is fixed. Bounded by a function, the input size and its parameters x., Here the iteration is fixed.

Consider array of “A”, size “n”, and searching an element “a” in that array which is shown below:

Mantocarlo Search (A, n, x)

i=0, tag=false

{

While ( )

{

Randomly select an element out of an element;

i=i+1

if (a is found)

tag= true;

}

return tag;

}

 

 

1.7 Heap Sort:

 

Algorithm for Heap Short (Ref: book)

1. Heapify
2. Take first element in sorted array.
3. Replays the first position with the last element.
4. Check if the tree is Heapify

If yes go to step 2

If no go to step 1

 

 

 

Fig 1.2: Heap Sort [book]

 

1. 8 Divide and Conquer:

 

It breaks a problem into subproblems that are similar to the original problem, recursively solves the subproblems, and finally combines the solutions to the subproblems to solve the original problem. Because divide-and-conquer solves subproblems recursively, each subproblem must be smaller than the original problem, and there must be a base case for subproblems. [9]

1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
2. Conquer the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.
3. Combine the solutions to the subproblems into the solution for the original problem.

You can easily remember the steps of a divide-and-conquer algorithm as divide, conquer, combine. Here’s how to view one step, assuming that each divide step creates two subproblems (though some divide-and-conquer algorithms create more than two):

 

Fig 1.3: Divide and conquer one subproblems [9]

 

 

Fig 1.4: Divide and conquer two subproblems [9]

 

 

 

 

 

 

 

1.9 Binary Search:

 

Binary search algorithm works on the principle of divide and conquer. This algorithm to work properly, the data collection should be in the sorted form. It looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the subarray reduces to zero. [10]

Location of value 31 using binary search.

 

Here it is, 0 + (9 – 0) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

 

Now we compare the value stored at location 4, with the value being searched, i.e. 31. We find that the value at location 4 is 27, which is not a match. As the value is greater than 27 and we have a sorted array, so we also know that the target value must be in the upper portion of the array.

 

 

Our new mid is 7 now. We compare the value stored at location 7 with our target value 31.

              

The value stored at location 7 is not a match, rather it is more than what we are looking for. So, the value must be in the lower part from this location.

 

Hence, we calculate the mid again. This time it is 5.

 

We compare the value stored at location 5 with our target value. We find that it is a match.

 

We conclude that the target value 31 is stored at location 5.

Binary search halves the searchable items and thus reduces the count of comparisons to be made to very less numbers.

 

Algorithm:

Procedure binary_search

A ← sorted array

n ← size of array

x ← value to be searched

Set lowerBound = 1

Set upperBound = n

while x not found

if upperBound < lowerBound

EXIT: x does not exist.

set midPoint = lowerBound + (upperBound – lowerBound) / 2

if A[midPoint] < x

set lowerBound = midPoint + 1

if A[midPoint] > x

set upperBound = midPoint – 1

 

if A[midPoint] = x

EXIT: x found at location midPoint

end while

end procedure

Binary search is a fast search algorithm with run-time complexity of Ο(log n).

 

1. 10 Merge Sort:

 

Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by definition (the base case). If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted,

Example is shown below [11]

Fig 1.5: Merge Sort Example [11]

 

Algorithm

MergeSort (arr [], l, r)

If r > l

1.    Find the middle point to divide the array into two halves:

middle m = (l+r)/2

2.     Call mergeSort for first half:

Call mergeSort (arr, l, m)

3.    Call mergeSort for second half:

Call mergeSort(arr, m+1, r)

4. Merge the two halves sorted in step 2 and 3:

Callmerge (arr, l, m, r)

1.21 Quick Sort:

 

quick sort uses divide and conquer to gain the same advantages as the merge sort, while not using additional storage.

A quick sort first selects a value, which is called the pivot value. Although there are many different ways to choose the pivot value, we will simply use the first item in the list. The role of the pivot value is to assist with splitting the list. The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.

Below shows that 54 will serve as our first pivot value. Since we have looked at this example a few times already, we know that 54 will eventually end up in the position currently holding 31. The partition process will happen next. It will find the split point and at the same time move other items to the appropriate side of the list, either less than or greater than the pivot value.

Partitioning begins by locating two position markers—let’s call them left mark and right mark—at the beginning and end of the remaining items in the list. The goal of the partition process is to move items that are on the wrong side with respect to the pivot value while also converging on the split point.

 

 

 

Fig 1.6: Quick Sort [12]

 

 

 

 

 

We begin by incrementing leftmark until we locate a value that is greater than the pivot value. We then decrement rightmark until we find a value that is less than the pivot value. At this point we have discovered two items that are out of place with respect to the eventual split point. For our example, this occurs at 93 and 20. Now we can exchange these two items and then repeat the process again.

At the point where rightmark becomes less than leftmark, we stop. The position of rightmark is now the split point. The pivot value can be exchanged with the contents of the split point and the pivot value. In addition, all the items to the left of the split point are less than the pivot value, and all the items to the right of the split point are greater than the pivot value. The list can now be divided at the split point and the quick sort can be invoked recursively on the two halves.[12]

 

Algorithm:

Based on our understanding of partitioning in quick sort, we will now try to write an algorithm for it, which is as follows.

Step 1 − Choose the highest index value has pivot

Step 2 − Take two variables to point left and right of the list excluding pivot

Step 3 − left points to the low index

Step 4 − right points to the high

Step 5 − while value at left is less than pivot move right

Step 6 − while value at right is greater than pivot move left

Step 7 − if both step 5 and step 6 does not match swap left and right

Step 8 − if left ≥ right, the point where they met is new pivot.

 

1.22 Strassen’s Matrix:

Given two square matrices A and B of size n x n each, find their multiplication matrix. [13]

Following is a simple way to multiply two matrices.

void multiply (int A [] [N], int B [] [N], int C [] [N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { C[i][j] = 0; for (int k = 0; k < N; k++) { C[i][j] += A[i][k] *B[k][j]; } } } }

 

Following is simple Divide and Conquer method to multiply two square matrices.
1) Divide matrices A and B in 4 sub-matrices of size N/2 x N/2 as shown in the below diagram.
2) Calculate following values recursively. ae + bg, af + bh, ce + dg and cf + dh.

 

 

 

You just need to remember 5 Rules: [13]

• AHED (Learn it as ‘Ahead’)
• Diagonal
• Last CR
• First CR
• ( )

Also, consider X as (Row +) and Y as (Column -) matrix

Follow the Steps:

• P1 = A;
• P2 = H;

•  P3 = E;
•  P4 = D
• P5 = (A + D) * (E + H)

• For P6 we will use Last CR Rule i.e. Last Column of X and Last Row of Y and remember that Row+ and Column- so i.e. (B – D) * (G + H), we get
  P6 = (B – D) * (G + H)

 

• For P7 we will use First CR Rule i.e. First Column of X and First Row of Y and remember that Row+ and Column- so i.e. (A – C) * (E + F), we get
  P7 = (A – C) * (E + F)

 

• Come Back to P1: we have A there and its adjacent element in Y Matrix is E, since Y is Column Matrix, so we select a column in Y such that E won’t come, we find F H Column, so multiply A with (F-H)
  So, finally P1 = A * (F – H)

 

 

• Come Back to P2: we have H there and its adjacent element in X Matrix is D, since X is Row Matrix, so we select a Row in X such that D won’t come, we find A B Column, so multiply H with (A + B)
  So, finally P2 = H * (A + B)
• Come Back to P3: we have E there and its adjacent element in X Matrix is A, since X is Row Matrix, so we select a Row in X such that A won’t come, we find C D Column, so multiply E with (C + D)
  So, finally P3 = E * (C + D)

 

 

• Come Back to P4: we have D there and its adjacent element in Y Matrix is H, since Y is Column Matrix, so we select a column in Y such that H won’t come, we find G E Column, so multiply D with (G – E)
  So, finally P4 = D * (G – E) ( )

We are done with P1 – P7 equations, so now we move to C1 – C4 equations in Final Matrix C:

• Remember Counting: Write P1 + P2 at C2
• Write P3 + P4 at its diagonal Position i.e. at C3
• Write P4 + P5 + P6 at 1st position and subtract P2 i.e. C1 = P4 + P5 + P6 – P2
• Write odd values at last Position with alternating – and + sign i.e. P1 P3 P5 P7 becomes
  C4 = P1 – P3 + P5 – P7

Analysis

• T(n)={c7xT(n2) +dxn2ifn=1otherwiseT(n)={cifn=17xT(n2) +dxn2otherwisewhere c and d are constants
• Using this recurrence relation, we get T(n)=O(nlog7) T(n)=O(nlog7)
• Hence, the complexity of Strassen’s matrix multiplication algorithm is O(nlog7)O(nlog7).

 

We write A and B as block matrices

 

A=       B=

 

The C matrix is given by

C₁₁=A₁₁E₁₁+B₁₂G₂₁

C₁₂=A₁₁F₁₂+B₁₂H₂₂

C₂₁=C₂₁E +D₂₂G₂₁

C₂₂=C₂₁F₁₂+D₂₂H₂₂

 

We have

 

P1 = A * (F – H)

P2 = H * (A + B)

P3 = E * (C + D)

P4 = D * (G – E

P5 = (A + D) * (E + H)

P6 = (B – D) * (G + H)

P7 = (A – C) * (E + F)

 

 

T(n)   which will be equal to      =3 for normal matrix multiplication

 

T(n)   which will be equal to      =2.81 for Strassen’s Matrix

 

Algorithm:

MM (A, B, n)

Int mid,

{

If (n≤2)

{

C₁₁=A₁₁E₁₁+B₁₂G₂₁

C₁₂=A₁₁F₁₂+B₁₂H₂₂

C₂₁=C₂₁E +D₂₂G₂₁

C₂₂=C₂₁F₁₂+D₂₂H₂₂

}

Else

{

Mid = n/2

MM (A₁₁, B₁₁, n/2) + MM (A₁₁, B₁₁, n/2)

MM (A₁₁ B₁₂, n/2) + MM (A₁₁ B₁₂, n/2)

MM (A₂₁, B₁₁, n/2) + MM (A₂₁, B₁₁, n/2)

MM (A₂₁, B₁₂, n/2) + MM (A₂₁, B₁₂, n/2)

}

}