Preliminaries:
Floor Function: Floor (3.14) == 3
Ceiling Function: ceiling(3.14) == 4
Reminder Function: The result remaining after dividing x on y.
Absolute Value: Abs(-233) == 233 and Abs(233) == 233
Factorial Function: Factorial(4) == (4*3*2*1) ; factorial symbol is !
Permutations: There are n! of arrangement alternatives when using n elements
Exponents: 3^2 == 3 * 3 == 9
Logarithm: b^y = x is equivalent to y = Logb(x)
Log 100 = 2 and Log 1000 = 3
Linear Search: If you have a list of items, you have to check all list items to find a given x value. Worst case;
worst = n [i.e. checking all the items as the searched item is the last item]
average = (n+1)/2
The Big O Notation:
As number of items n increases, the algorithm will take more time, but the order of increase can be quiet different:
Log2 n: grows most slowly
2^n grows the most rapidly
n^m grows depends on the value of m, but generally rapid more than Log2 n.
Arrays:
Linear arrays: a set of elements that has sequential locations in memory.
Bubble Sort: Sorting n numbers means swapping elements until all elements be located in increasing order.
Phases, so that each phase will pass on all elements to push the largest element to the end of the list. Obviously, on each phase, we will pass on n-1, n-2, n-3, elements and so on.
void Bubble(int *data, int n)
{
int phases = n – 1;
int last = phases;
for(int j=0; j <= phases; j++) { last--; for(int i=0; i<=last; i++) { if(data[i] > data[i+1])
swap(data[i], data[i+1]);
}
}
}
Bubble sort has the O(n^2) in comparisons and n-1 phases.
Linear/sequential Search:
Given n elements, and trying to find some value, just pass on all the array elements, comparing each element with the given one.
int Linear(int *data, int value)
{
int loc = -1;
for (int i=0, i< loc =" i;">
Binary Search:
Binary search is extremely efficient given that the input data is sorted and you have direct access to the middle(actually any data element).
The algorithm is similar to what you do when you search a word in paper based dictionary, first you open the middle page to know if the word is in the first have or second half, and so on. A recursive function usually make developing the algoithim is so simple.
Complexity is order of Log2 n
Sparse Matrix:
A matrix that has many element as zeros or empty. It is efficient to store sparse matrixes in list that array to save space.
Linked Lists:
A groups of elements, each has a pointer to the next, the last has a NULL pointer, and there is a pointer to the first element.
Given a list of items that not sorted, and we need to search for a specific value, we can start for head of list until tail and compare each element with the given one. This is similar to linear search.
If the linked list is sorted in ascending order, we can just terminate the linear search once reach an element that is greater than the given value. The complexity order is just like linear search, Order on n.
Memory Allocation: Instead of dynamically allocate and free memory for each item in the linked list, we can just allocate a pool and take from it, this pool could be a list of the same data structure.
Header Linked List: A linked list that has aground node – the last node – and a header node, usually has a circular that the last node points at the first node.
Double Linked List: A linked list that each item has a pointer to next item and another pointer to previous item.
Stacks:
Just like a stack of dishes, so that last in is first out, and first in is last out.
Push > pushes an element at the top of the stack.
Pop > removes an element from the stack, at the top.
Stacks can be implemented easily using lists.
Quick Sort:
Quick sort is an algorithm of the divide-and-conquer type, the problem of sorting a set is reduced to the problem of sorting two sets and so on. Recursive algorithm is usually used in this sort.
1- given an element, scan from left to make sure no element is smaller than it, if so swap.
2- scan from right to left to find a value that is lower than it, if so swap.
3- if no swapping, so you have two sets and your value is now at the middle.
4- Treat each subset with the same steps form 1 to 3, if you have just a set of one or two sorted elements, just return.
The running time is measured by the number of comparison, which is: f(n) = O( n*Log n).
Recursion:
One function that requires a call to itself in order to finish. There are rules to avoid forever loop, with each recursive call you should be near the base value.
Usually recursive algorithms can be modified to normal algorithms using stacks.
Towers Of Hanoi:
Very interesting algorithm that is very easy to implement using recursion, it is based also on the concept of divide-and-conquer.
The base algorithm:
You have n disks stacked on peg A so that no disk is over a smaller disk. And you need to move all disks from A to C using auxiliary peg B, without violating the rule.
Look at this pseudo code:
Tower(n, BEG, END, AUX)
{
if (n == 1)
{
move from BEG to END
return;
}
Tower(n-1, BEG, AUX, END);
move BEG to END;
Tower(n-1, AUX, END, BEG);
}
Implementation of Recursive Function using Stack:
By using stack to store all info, we can convert the recursive routine to a non-recursive routine.
Queues:
First in First out. The queue has rear and front, all new items are added to rear, and all removed items are removed from front.
Dequeus:
Elements can be added or removed at either rear or front but not the middle.
Priority Queue:
First in First out for all items with the same priority, but higher priority is processed first.