Algorithms | bodom_lx at task3 dot cc

Wiki set up, first meeting

October 14th, 2009 bodom_lx No comments

Both the Wiki and the blog has been set up. Tomorrow I’m going to have the first official meeting at FBK to discuss my first results.
I’ve just finished the grid containing a short description that each paper proposed as a solution (or suggest) for the areas:

System Suggestions
Interface Design
Algorithms
Coordination
Trustiness
Safety/Reputation Systems
Social Aspects
Chicken-Eggs problem
Incentives

The WIKI is located at the following URL: http://www.opensocialcapital.com/dynamic_carpooling/wiki/
The Blog, which currently takes the RSS of the category carpooling-research of my blog, is located at: http://www.opensocialcapital.com/dynamic_carpooling/wiki/.
I will fill the Wiki as soon as I have the time to do it, I promise.

Hash Maps with linear probing and separate chaining

April 28th, 2008 bodom_lx No comments

Time for two new C programs! At the DSA course I learned something about Hash Tables and collision resolutions.
I just implemented insert/search/print operations.

The first source code is an implementation of a Hash Map with open addressing (linear probing) as collision resolution method.
The following are the interesting functions of the program. As always, take a look at the source code for comments:

// hashMapLinear[] is the hash map
void linearProbingInsert(int value){
int probe = hash(value);
while (hashMapLinear[probe]!=0){
probe = fmod((probe+1),SIZE_HASH_MAP);
}
hashMapLinear[probe] = value;
}

int linearProbingSearch(int value){
int probe = hash(value);
int i;
for(i=0;i<size_hash_map ;i++){
if(hashMapLinear[probe]==value)
return TRUE;
probe = fmod((probe+1),SIZE_HASH_MAP);
}
return FALSE;
}

Download: hash-map-linear-probing.c

The second program is an implementation of a Hash Map with chaining as collision resolution method.
Interesting functions:

// t_hashTableNode is a struct that is created as single linked list
void chainedHashInsert(int value){
int probe = hash(value);
if(hashMapChained[probe] == NULL){
hashMapChained[probe] = malloc(sizeof(t_hashTableNode));
hashMapChained[probe]->value = value;
hashMapChained[probe]->next = NULL;
}else{
t_hashTableNode *hashTableNode = hashMapChained[probe];
while(hashTableNode->next!=NULL){
hashTableNode = hashTableNode->next;
}
hashTableNode->next = malloc(sizeof(t_hashTableNode));
hashTableNode->next->value = value;
hashTableNode->next->next = NULL;
}
}

int chainedHashSearch(int value){
t_hashTableNode *hashTableNode = hashMapChained[hash(value)];
while(hashTableNode!=NULL){
if(hashTableNode->value==value){
return TRUE;
}
hashTableNode = hashTableNode->next;
}
return FALSE;
}

Download: hash-map-chaining.c

A Generic Quicksort Implementation in C

April 7th, 2008 bodom_lx No comments

As assignment for Data Structures and Algorithms course, we had to work with a modified version of the quicksort algorithm. It came obvious that for modifying a qsort you need to implement it

It is difficult to find a clear quicksort algorithm implemented, so I wrote it.

Here is the generic C implementation of the Quicksort Algorithm, which sorts an array in place, following the Divide And Conquer design.

Download: quicksort qsort in C language

Interesting methods (look at the source code for comments):

int partition( int A[], int left, int right) {
int pivot;
pivot = A[right];
while(1){
while( A[right] > pivot){
right–;
}
while( A[left] < pivot){
left++;
}
if( left < right ){
swap(A,left,right);
}else{
return left;
}
}
}

void quicksort( int A[], int left, int right){
int m;
if( left < right ) {
m = partition( A, left, right);
quicksort( A, left, m-1);
quicksort( A, m+1, right);
}
}

As you see, there is nothing optimized in this implementation. It just looks elegant and easy to be understood.
If you would like to have a more optimized version of this algorithm, take a look at this one.

Two IT guys and DSA assignments

March 16th, 2008 bodom_lx No comments

This is what happens if you give to two IT students a stressful assignment of “Data Structures
and Algorithms”, 48 hours of their meaningful life, the loss of a saturday night, and the 6th
floor of the most recent building of the Free University of Bolzano:

..they begin to behave like real IT guys..and to build their ideal working habitat..

..and to worship fake idols..

Sorting array elements with C language

February 23rd, 2008 bodom_lx 3 comments

UPDATE 17:19: it seems that the program I implemented today uses a kind of Bubble Sort algorithm, give it a try, it’s quite interesting!

After 3 long days studying C, I think I’ve assimilated a good knowledge base for the incoming semester.
So there is a tiny C program that sorts the elements of a given integer array, using pointers:

Download the source code (well commented)

#include <stdio.h>
void sortArray(int *firstElement, int *lastElement);
void swapArrayElements(int *firstElement, int *secondElement);
void printArray(int array[], int arraySize);

void sortArray(int *firstElement, int *lastElement){
int *currentElement = firstElement;
while (firstElement != lastElement){
while(currentElement != lastElement){
if(*currentElement < *firstElement){
swapArrayElements(currentElement,firstElement);
}
currentElement++;
}
firstElement++;
currentElement = firstElement;
}
}

void swapArrayElements(int *firstElement, int *secondElement){
int tmp;
tmp = *firstElement;
*firstElement = *secondElement;
*secondElement = tmp;
}

void printArray(int array[], int arraySize){
int counter = 0;
while(counter<arraySize){
printf("%d\n",array[counter]);
counter++;
}
}

int main (int argc, char *argv[]){
int array[] = {2929393,1,23239,-66,15,4,3,0,112,45,3,1000,19};
int arraySize = sizeof(array)/sizeof(array[0]);
int *firstElement = &array[0];
int *lastElement = firstElement + arraySize;
printf("————————————————-\n");
printf("Elements of the array:\n");
printf("————————————————-\n");
printArray(array,arraySize);
printf("————————————————-\n");
sortArray(firstElement,lastElement);
printf("Elements sorted:\n");
printf("————————————————-\n");
printArray(array,arraySize);
printf("————————————————-\n");
}

A better program should ask the user to input the array elements, and a better algorithm should not scan every array element n times, where n is the number of the elements.
But I wrote it just for fun and for learning C pointers. I will learn to do better in the Data Structures and Algorithms course in the next semester

bodom_lx at task3 dot cc

Archive

Wiki set up, first meeting

Related posts

Hash Maps with linear probing and separate chaining

Related posts

A Generic Quicksort Implementation in C

Related posts

Two IT guys and DSA assignments

Related posts

Sorting array elements with C language

Related posts

About

Recent Posts

Recent Comments

Meta

Categories

Tags

Twitter