In mathematics and computer science, an algorithm is a finite sequence of well-defined instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing.
You can implement this sequence of steps in a Programming Language.
Properties of Algorithms
| Algorithm | Program |
|---|---|
| Design time | Implementation |
| Need domain knowledge | Need to understand code |
| Any language (formal better) | Programming language |
| Hardware & software independent | Hardware & OS specific |
| Analyze complexity | Testing required |
Analysis of Algorithms
- Priori Analysis: “From the earlier” in latin is about knowledge by deduction and reasoning.
- Posteriori Analysis: “From the later” in latin is about knowledge by induction - observing how something works.
| Priori Analysis | Posteriori Testing |
|---|---|
| Analysis of algorithm | Analysis of program |
| Independent of language | Language dependent |
| Hardware independent | Hardware dependent |
| Time & Space function | Watch time & bytes |
How to analyse an algorithm
- Time - how long it takes to run
- Space - Amount of memory used
- Network consumpiton - amount of data transferred
- Power Consumpiton - how much power is needed
- CPU Registers - how much CPU time
Sample Algorithm to analyse
Simple algorithm to swap values of A and B:
swap(a, b){
temp ← a;
a ← b;
b ← temp;
}
Note: there are no data types, and assignment can be specified using ←, = or := symbols. If we look above:
- there are 3 lines in the function - so time is f(n) = 3 (we assume constant time).
- there are 3 variables a,b,temp so space is equal to 3 - s(n) = 3.
When we translate that to code in C:
#include <stdio.h>
void swap(int *ap, int *bp){
int temp = *ap;
*ap = *bp;
*bp = temp;
}
int main(){
int a = 8;
int b = 9;
swap(&a, &b);
printf("A=%d, B=%d",a,b);
return 0;
}
| A=9 | B=8 |
Sum of Array Example
Using this array:
When we translate that to code in C:
#include <stdio.h>
int main(){
int sum = 0;
int arr[] = {8, 3, 9, 7, 2};
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < n; i++)
sum += arr[i];
printf("Sum of array = %d", sum);
return 0;
}
Sum of array = 29
Characteristics of Algorithm
- Input - 0 or more
- Ouput - at least 1
- Definiteness - can’t have unknown or imaginary values
- Finiteness - must terminate at some point.
- Effectiveness - don’t do anything unnecessary