Lecturer

Paulo Fonseca

Schedule & room

TBA

Office hours

TBA

Pre-requisites

There are no formal pre-requisites but students are strongly advised to take IF672-"Algorithms and data structures" before. You will need familiarity with the design, analysis and implementation of basic data structures and algorithms such as sorting and searching.

Syllabus (tentative)

• Basic concepts
  1. Alphabets, strings, substrings
  2. String distances
• String matching
  1. Exact string matching
     (Sliding window methods, semi-numerical methods, bit-parallelism methods)
     
  2. Approximate string matching
     (Distance-matrix methods, automata-theoretic methods, bit-parallelism)
     
• Indexing
  1. Suffix trees
     (Efficient construction and representation, string matching, other applications)
     
  2. Suffix arrays
     (Efficient construction and representation, string matching)
     
• Text compression
  1. Huffman coding
  2. Lempel-Ziv factorisation

Basic bibliography

1. Dan Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge Univ Press, 1997.
2. M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press, New York, 1994.

Links to supplementary material will be given along the course.

Grading

The final grade will be weighted as follows

1. 40% will correspond to 4 individual written assignments
2. 60% will correspond to an implementation project in groups up to 2 (two) students

Academic ethics

Students are expected to do their own work, to understand what they have done, and to be able to explain their reasoning without assistance. It is OK to discuss with colleagues about problems in written assignments, but one must write down the detailed solutions in one's own words. It is also OK to study existing code, but it is not OK to copy and paste substantial parts of it and present as one's own work. Plagiarism and cheating do not contribute to the educational process and will not be accepted.