A well-defined computational procedure that has an input (set of) value(s) and produces an output (set of) value(s).
A tool to solve a well-specified computational problem.
Selecting an algorithm & correctness:
depending on the size of the input
the complexity of the input
restrictions on the input values
Correct algorithms stop with correct output for every input instance and solve the computational problem. Incorrect algorithms can still be useful, if we can control their incorrect algorithms.
NP-Complete problems
No efficient algorithm has been found, but it has never been proved that an efficient algorithm doesn’t exist.
If an efficient algorithm exists for any problem, then efficient algorithms exist for all of them
A small change in a problem can turn it into a NP-complete
Pseudocode:
Formalised, self-explanatory notation that represents algorithms. Language-specific constructions are reduced as much as possible. Not concerned with issues of software engineering.
Analysing algorithms:
Predicting the resources an algorithm requires memory storage, communication bandwidth, hardware, but most often computational time. Model RAM (random-access machine) has generic one processor, instructions are executed one after another, without concurrent operations. The model allows for arithmetic, data movement, control statements, each instruction in constant amount of time. It also has integer and floating point data type, limits on the size of each word of data is also applied.
In general, the running time of an algorithm is a function of the size of its input. The input size is defined by the problem being solved by an algorithm:
sorting, discrete Fourier transforms: the number of items
multiplying two integers: the number of bits that represent them
graph algorithm: the number of vertices and the number of edges
The running time is:
number of primitive operations that are executed by the algorithm
primitive operation must be as machine-independent as possible
Pseudo code for insertion sort & running time
procedure Insertion-Sort(A)
for j = 2 to A.length do
key = A[j]
i = j - 1
while i > 0 and A[i] > key do
A[i + 1] = A[i]
i = i - 1
end while
A[i + 1] = key
end for
end procedure
Lets assume the execution of the line takes time .
In the case of the input being already sorted:
In the case of the input being sorted in reverse order:
Many algorithms have recursive structure, breaking the problem into several subproblems that are similar to the original, but with smaller size. The idea is to solve the subproblems recursively and combine their solutions.
On each level of the recursion three steps are involved:
Divide the problem into subproblems that are smaller instances
Conquer the subproblems by solving them recursively
Combine the solutions to the subproblems in to the general solution
procedure MERGE-SORT(A, p, r)
if p < r then
q = ⌊(p + r )/2⌋
MERGE-SORT(A, p, q)
MERGE-SORT(A,q + 1,r)
MERGE(A,p,q,r)
end if
end procedure
note: stands for
Merge sort
Time complexity:
Better for bigger input sizes & is not performed in place. Closely follows the “Divide-and-conquer” paradigm.
#include <iostream>void copy_array(int a[], int b[], int begin, int end) { for (int i = begin; i < end; i++) { b[i] = a[i]; }}void top_down_merge(int b[], int a[], int begin, int middle, int end) { int i = begin, j = middle; for (int k = begin; k < end; k++) { if (i < middle && (j >= end || a[i] <= a[j])) { b[k] = a[i]; i++; } else { b[k] = a[j]; j++; } }}void top_down_split_merge(int b[], int a[], int begin, int end) { // if size is <= 1, consider it sorted if (end - begin <= 1) return; int middle = (end + begin) / 2; top_down_split_merge(a, b, begin, middle); top_down_split_merge(a, b, middle, end); top_down_merge(b, a, begin, middle, end);}void merge_sort(int a[], int b[], int n) { copy_array(a, b, 0, n); top_down_split_merge(a, b, 0, n);}int main() { int a[] = {7, 6, 4, 2, 1, 5}; int b[] = {0, 0, 0, 0, 0, 0}; int n = 6; merge_sort(a, b, n); for (size_t i = 0; i < n; i++) { std::cout << b[i] << ", "; }}