1st. Lab Session

The purpose of this lab is to check if the theory explained in class,
about the search algorithms for only one pattern, is still true. For
this goal you will execute the four algorithms (brute force,
horspool,BNDM and BOM) over three alphabets of length m-1,m,m+1 with
random files of, at least 2Gb, and random patterns of length k such
that (1<=k<=inf)(I will give to
everyone the value of m).

You can find the code of the algorithms in the web page
http://www-igm.univ-mlv.fr/~lecroq/string/index.html
and for every algorithm there is a usefull applet that can help you to
understand the algorithm. Also you can download from my web page the
code of brute force and Horspool algorithms.

You should deliver a report with three graphs:

- a first graf (running time/length of the pattern) with the running
time of the four algorithms. Note that the running time should not
compress the time to read, generate or print data.
- a second graph (algorithm/length of the pattern) with the most
efficient algorithm for every length.
-a third graph (number of patterns found/length of the pattern) that
,of course, should be the same for all algorithms.


El contingut de la 1a sessio es el seguent:

Algorismes de cerca (http://www-igm.univ-mlv.fr/~lecroq/string/index.html)
   1.  Implementacio i execucio
   2.  Calcul del temps d'execucio
   
La finalitat d'aquest practica es comprobar si avui en dia continua
essent valida la grafica dels algorismes mes eficients presentada a
classe. Per tal motiu la feina pel proper dia sera avaluar, per a tres
alfabet de mida m-1,m i m+1 caracters, que jo assignare a cada estudiant,
els algorismes mes eficients (en temps d'execucio) per a patrons de
longitud k (1<=k<=inf). Els algorismes que heu de tenir en compte son
els de Força bruta, Horspool, BNDM, BOM.

Podeu trobar el codi dels algorismes a 
(http://www-igm.univ-mlv.fr/~lecroq/string/index.html) i uns exemples
a la meva pagina.

Tingueu en compte que el temps d'execucio no ha de tenir en compte
l'impressio dels resultats ni la lectura o generacio de dades i que
necessiteu textos de longitud de minim dos Gb (genereu-los
aleatoriament amb una distribucio equiprobable).

El document que m'heu de lliurar ha de tenir 3 grafiques:

- una grafica (temps/long. del patro) amb els temps dels quatre
  algorismes.  
- un grafic (algorisme/long del patro) amb l'algorisme
  mes eficient per cada longitud.
- una grafica (nombre de patrons trobats/long del patro) que ha de ser
  independent de l'algorisme escollit.