Project in String Processing Algorithms
Vuosi | Lukukausi | Päivämäärä | Periodi | Kieli | Vastuuhenkilö |
---|---|---|---|---|---|
2015 | kevät | 13.01-24.02. | 3-3 | Englanti | Juha Kärkkäinen |
Luennot
Aika | Huone | Luennoija | Päivämäärä |
---|---|---|---|
Ti 12-14 | C220 | Juha Kärkkäinen | 13.01.2015-24.02.2015 |
Yleistä
The project consists of
- implementation of one or more string processing algorithms
- experimental comparison and/or analysis of the algorithm(s)
- presentation of the results
The project can be done in groups of at most three students. In a group each student is responsible for specific algorithms and the group together is responsible for the experiments and the presentation.
The course assumes String Processing Algorithms -course or similar knowledge as background.
Kurssin suorittaminen
Algorithm implementation
The algorithms can be implemented with any programming language under the restriction that the programs can be compiled and executed on the department computers.
The algorithm implementations are returned to the instructor by Thu 12.2. The contributions of each group member should be stated clearly. See the opening slides below for more details.
Experiments
The purpose of the experiments is to determine how the performance of the algorithms changes with different inputs, different parameters settings, different algorithms etc.. An important part is choosing the test data.
Poster
The results of the experiments are presented as a poster. There will be an open poster presentation session on the last week, where other students and staff of the department can come to view the posters and ask questions.
Grading
Each part of the project (implementation, experiments, presentation) contributes one third to the total score. In general,
the experiment and presentation score will be the same for all members of a group. The implementation scores will be personal.
Kirjallisuus ja materiaali
LINKS
- Exact String Matching Algorithms
- SMART: String Matching Research Tool
- Parallel String Sorting
- Pizza & Chili
- Yuta Mori's implementations of suffix array construction algorithms: SAIS and divsufsort
TEST DATA
- Pizza & Chili standard corpus and repetitive corpus
- SMART corpus
- Yuta Mori's SACA benchmark page has links to many text collections
POSTER
- example_poster.tgz (unpack with tar xvzf example_poster.tgz and see the file README)