On it’s core this file is a resume containing answers and notes of the book “Introduction to Algorithms, 3rd ed (2009), Thomas H. Cormen..” published by MIT. It also have stuff from my data structure class.
Algorithm efficiency is actually something, and to measure it you need to consider two things: First being a constant c, that will resolve around many variables from languague compiler/interpreter/assembler binary speed to the computer itself. The second one focus on the number of interactions, and it’s represented by a mathematical expression based on the algorithm. Combine the two, and you have how many instructions you need to run certain algorithm.
The constant c often impacts little on the run, so it’s pretty much useless.
A good example for measuring efficiency it’s comparing the Linear Seach to the Binary Search.
int linear_search(int *v, int size, int item){
int i;
for(i=0;i<size;i++){
if(v[i] == item){
return i;
}
}
return 0;
}
int binary_search(int *v, int bottom, int top, int item){
int middle = floor((top + bottom) * pow(2, -1));
if(v[middle] < item){
binary_search(v, middle, top, item);
}
else if (v[middle] > item){
binary_search(v, bottom, middle, item);
}
return middle;
}For a 0-100 array number, let’s compare both when searching for 73.
Linear search found 73 with 73 interactions! Binary search at 50 Binary search at 75 Binary search at 62 Binary search at 68 Binary search at 71 Binary search at 73 Binary search found 73 with 6 interactions!
Binary found with 67 less intructions! That’s because linear runs at (n) and binary at log(n): 
Sorting algorithms are also nice for comparing efficiency. Let’s see how little the constant does when comparing a Merge sort c1 versus Insertion sort c2, c1 > c2.
Merge runs at n * log(n), insertion 2^n and n = objects.
double insertion(double n){
return 8 * pow(2, n);
}
double merge(double n){
return 64 * (n * log(n));
}Output:
2 objects: Insert = 32 Merge = 89 3 objects: Insert = 64 Merge = 211 4 objects: Insert = 128 Merge = 355 5 objects: Insert = 256 Merge = 515 6 objects: Insert = 512 Merge = 688 7 objects: Insert = 1024 Merge = 872 At 7 objects, Merge has 872 instructions nedded to sort, 152 less than insert
Even with a 8 times bigger c, merge outruns the insertion from few as 7 numbers.
Insertion takes a array index number as a key and compares to all previous positions possible until key > array[previous].
void insertion(int *v, int size){
int key_t, i, j;
for(j=1;j<size;++j){
key_t = v[j];
i = j - 1;
while(i>=0 && v[i] > key_t){
v[i+1] = v[i];
v[i] = key_t;
--i;
}
}
}Note that it starts with j = [left_index + 1] array position, since of course you’ll be comparing to previous numbers.
The divide-and-conquer is a recursive approach to solve problems.
- Divide the problem in smaller ones.
- Conquer the smaller problems by solving them.
- Combine those smaller problems into the original one, solved.
A D&C sorting algorithm works just like that, sort the small pieces and glue then later.
The idea here is use the key_t to sort the array by small partitions.
void quick(int *v, int l_index, int r_index){
if(l_index >= r_index){
return ;
}
int l, r, pivot, aux;
l = l_index;
r = r_index;
pivot = v[(l_index + r_index)/2];
while(l <= r){
while(v[l] < pivot) ++l;
while(v[r] > pivot) --r;
if(l <= r){
aux = v[r];
v[r] = v[l];
v[l] = aux;
++l; --r;
}
}
quick(v, l_index, r);
quick(v, l, r_index);
}The two major partitions could be defined as left and right recursive calls at the end, following a sub-partition for individual pivots.
Merge is the very definition of D&C, the first you divide, setting L[] and R[] as your v universe (first and second for() loops), then you sort then (first while loop), and combine with the rest (2nd or 3rd while).
void sort(int *v, int l, int m, int r){
int nl = m-l+1;
int nr = r-m;
int i, j, k;
int L[nl];
int R[nr];
for(i=0;i<nl;++i){
L[i] = v[l+i];
}
for(j=0;j<nr;++j){
R[j] = v[m+j+1];
}
i = 0;
j = 0;
k = l;
while(i<nl && j<nr){
if(L[i] <= R[j]){
v[k] = L[i];
++i;
}
else{
v[k] = R[j];
++j;
}
++k;
}
while(i<nl){
v[k] = L[i];
++i;
++k;
}
while(j<nr){
v[k] = R[j];
++j;
++k;
}
}This function is responsible for breaking the array into half/half on every recursive call.
void merge(int *v, int l, int r){
if(l<r){
int m = floor((l+r) * pow(2, -1));
merge(v, l, m);
merge(v, m+1, r);
sort(v, l, m, r);
}
}With the <stdlib.h> qsort function it’s possible to sort almost everything as it uses pointer to void. This is a example of sorting dynamic-allocated strings, adapted from the qsort manual.
static int cmpstringp(const void *p1, const void *p2){
return strcmp(* (char * const *) p1, * (char * const *) p2);
}
int main(void){
int track, size_t, slen, i, j;
char **v;
char aux[255];
scanf("%d", &size_t);
v = malloc(sizeof(char) * size_t);
for(i=0;i<size_t;++i){
scanf("%s", aux);
slen = strlen(aux);
v[i] = malloc(sizeof(char) * slen);
for(j=0;j<slen;++j){
v[i][j] = aux[j];
}
}
qsort(&v[0], size_t, sizeof(char *), cmpstringp);
for(i=0;i<size_t;++i){
puts(v[i]);
}
exit(EXIT_SUCCESS);
}It sorts all input words (as strings) in alphabetical order.
Now a more basic example, sorting integers.
int cmparray(const void *n1, const void *n2){
return (*(int*)n1 - *(int*)n2);
}
qsort(v, size, sizeof(int), cmparray);Syntax is qsort(vector, vector-size, data-type, external-function);
- Pointers are used to link each node of our list
fa -> fb -> nil where fX is the guy, and arrow is the pointer.
- Versatility
The liked list is powerful. It can easily be resized, just point it to (eg; ff) instead of nil.
- Why?
It can be used to write specifically FREE-Memory instead of overwriting it.
- How?
Look how it recursively the structure is called with a pointer. It has a structure with a item and a pointer to a new structure.
typedef struct{
int data;
struct node* next;
}node;Yep.
node *new_node = NULL;void add(node **head, int item){
node *new_node = (node*) malloc(sizeof(node));
new_node->item = item;
new_node->next = *head;
*head = new_node;
}Alternatively, you can add in the tail of the list, thus making the list equal to the input order
void add_tail(node **head, int new_data){
node *new_node = malloc(sizeof(node));
node *current = *head;
new_node->data = new_data;
while(current != NULL){
if(current->next == NULL){
current->next = new_node;
return ;
}
curent = current->next;
}
new_node->next = *head;
*head = new_node;
} node* search(node *head, int item){
while(head != NULL){
if(head->data == item){
return head;
}
head = head->next;
}
return NULL;
}Basic stuff, might be usefull for sorting and other things
node* l_len(node *head){
int len = 0;
node* current;
for(current=head;current!=NULL;current=current->next){
++len;
}
return len;
}This is a tricky one, you’ll need to use a pointer to save the previous position and point it to the current->next
void l_remove(node **head, int item){
node* current = *head;
node* last = NULL;
while(current != NULL && current->data != item){
last = current;
current = current->next;
}
if(current == NULL){
return ;
}
if(last == NULL){
*head = current->next;
}
else{
last->next = current->next;
}
free(current);
}- “LIFO” - Last In, First Out.
LIFO consists in tree main operations:
Push, adds a element to the stack topPop, removes the stack top elementPeek, shows the stack top element
This is a stack with a list.
typedef struct node{
int data;
struct node *next;
}node;
typedef struct{
int size;
node *top;
}stack;You can also create a stack with a array, but please don’t.
push will be adding a element in top of the stack, just like this;
| nil | ||||||
| -> | -> | nil | -> | 18 | ||
| nil | 22 | 22 | ||||
| nil | 90 | 90 | 90 |
|---|
void push_list(stack *stk, int item){
node *new_top = malloc(sizeof(node));
new_top->data = item;
new_top->next = stk->top;
stk->top = new_top;
++stk->size;
}pop removes the top data of the stack making the bottom element the new top.
void pop(stack* stk){
if(stk == NULL){
return;
}
node *aux = st->top;
st->top = st->top->next;
--stk->size;
}For peak, it’s very trivial really.