MinMax (and Alpha-Beta pruning) - This program ( main.c , jeu.c and jeu.h ) is an example of using MinMax with alpha/beta pruning for a chess game.
See the README.txt file for a small explanation of the main source code variables and functions.
B Tree - The btree.h et btree.c source files represent a module for handling a data file organized as a B-Tree.
Access operations (search, insertion, deletion, etc.) are implemented. The recovery of freed blocks (during deletions) is done by managing an empty block list. See the description of the header block (struct bloc0) in the source (btree.h).
The main.c source file is an example of an application using this module.
External Sorting - The tri_externe.c represents an implementation of the external merge-sort algorithm. The input file is organized as a sequence of contiguous blocks of integers. Adapting the program to the case of linked blocks is quite easy.
The principle of external sorting consists in using a number of buffers in main memory (depending on the size available) to first fragment the input file into several small sorted fragments, then to carry out a serie of multi-merge operations (merging several fragments at the same time using the same buffers available in main memory) until a single sorted fragment is obtained.
This algorithm has a complexity in physical I / O operations in O (N log [N / M]), with N the size of the input file (in blocks) and M + 1 the number of buffers available in memory .
Parallel Sorting - This small project shows a simple solution to the problem of parallel sorting on a clustered architecture. The chosen approach is to use interval partitioning to fragment the file to be sorted. The project uses PVM and is composed of three types of tasks:
- 'master.c' : the main task which initializes the other slave tasks ('frag' and 'tri')
- 'frag.c' : slave tasks responsible for parallel interval partitioning
- 'tri.c' : slave tasks responsible for carrying out the local sorting of the n fragments resulting from the 'frag' tasks.
The header file for this project is 'tpc.h'
To build binaries with gcc, just link with libpvm3:
$ gcc master.c -lpvm3 -o master
$ gcc frag.c -lpvm3 -o frag
$ gcc tri.c -lpvm3 -o tri
To run the project:
- create input files in each node (file_in__0, file_in_1, ... file_in_n)
- start pvm (it is enough just to launch the console) and add all nodes composing the cluster
- run the master task specifying as argument, the number of nodes, ex: $ ./master 10
The detailed description of the solution is presented in this pdf document.
Sorting - The tri_interne_complexite.c source file contains the implementation of some sorting algorithms (selection sort, insertion sort, sort-merge and quick sort). We can use this program to perform performance tests and thus be able to compare the different implemented sorting algorithms. A very large difference in execution time, for large values of n (the size of the array), can be observed between the solutions in O (n * n) (selection and insertion sorts) and the solutions in O (n * log n ) (sort-merge and quick sort).
Intersection - The intersection_complexite.c source file is an implementation of three algorithms for the intersection problem of two arrays.
The first algorithm is a "nested loops" approach. It has a complexity O (n * n). The second algorithm sorts one of the arrays and uses binary search in the other array, for the "probe" phase. Its complexity is O (n * log n). The last algorithm sorts the two arrays then performs a "merge" type sequential scan. Its complexity is also O (n * log n).
Nesting of function calls - The fact_recursivite.c source file shows the flow of recursive calls in the recursive implementation of the "factorial" function.
Runtime stack and return addresses - The inc_recursivite.c program shows in more detail the flow of recursive calls and return addresses. This program requires the gcc compiler because it uses internal (non-standard) functions for access to the runtime stack (__builtin_return_address and __builtin_frame_address).
Classic Binary Search Trees (BST) - The bst.c source file contains an implementation of the main access algorithms (search, insertion and deletion ...) for a classic binary search tree (not necessarily balanced) ). Two types of insertion are used (iterative and recursive).
AVL trees (balanced BST) - The avl.c source file contains an implementation of the main access algorithms (search, insert and delete ...) for an AVL tree. Two types of insertion are also used (iterative and recursive).
In the iterative version, the climb phase along a branch is performed using an explicit stack of pointers built during the descent phase. In the recursive version, the climb phase is carried out through the instructions placed after the recursive calls.
Red-Black trees (balanced BST) - The rb.c source file contains an implementation of the main access algorithms (search, insertion and deletion ...) for a Red-Black Tree . In the source code of the insert and delete functions ("inserer" and "supprimer"), the equivalence with the original tree (2-3-4 Tree) is recalled through some comments.
For a small experimental comparison between AVL and Red-Black done using the C programs above, see the end of this presentation related to "Red-Black trees" in the ALSDD course.
In the three implementations of binary search trees (classic BST, AVL and Red-Black) a graph drawing tool Graphviz / dot is used as well as the eog image viewer. The latter can easily be replaced by any other image viewer (like gpicview, xviewer, ...).
'dot' program takes as input a text file (.dot) describing the nodes and the links between them and outputs a multitude of graphic formats. In "bst.c", "avl.c" and "rb.c" programs, the generated format is 'png'.
The text file describing the tree to be viewed ("sortie*.dot") is generated by a preorder traversal of the tree (see "preordre" function in the sources).
In order to improve the graphic representation obtained, intermediate and invisible nodes are added during the generation of the .dot file (in the "preordre" function) to better separate (visually) the left child from the right child.
Advice
For a solid academic training I recommend the use of open source systems and tools : GNU Toolchain, GNU Linux, *BSD, PostgreSQL, PVM, ...