Advanced Text Algorithms – 2014

Description

Text algorithms are essential in many areas of science and information processing. Very often the information is represented as a written text in the form of, e.g., newspapers, books, computer hard-drives, optical disks, the genetic information of living organisms, etc. Specific text algorithms are needed when processing the information, whether in text editors or in (web)-searching engines. The intricacies of text algorithms represents a major topic of investigation in computer science. This course will present several advanced, practically relevant text algorithms and their interconnections. They include pattern matching and data compression algorithms, detection of periodicities, repetitions and symmetries in texts, and other algorithms.

Content

  • Pattern-matching algorithms: Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm
  • String alignment algorithms: edit distance, optimal alignment, longest common subsequence, alignments with gaps
  • Approximate patter-matching algorithms
  • Suffix trees and text search applications
  • Symmetries and repetitions in texts
  • Constant-space algorithms
  • Text compression algorithms

Prerequisites

  • Algorithmics
  • Data structures
  • Note:
    • the prerequisites are preferable, though not compulsory. The course is self-contained, all the background will be introduced

Course format

  • Lectures: 28h, 14 lectures
  • Exercises: 7 homework+demonstration sessions
  • Final examination:
    • 15 points – pass, mark 1/5
    • over 27 points -, mark 5/5
    • Bonus points from exercises
      • with enough gained bonus points one can skip the final exam, and even obtain the highest mark

Literature

  1. Maxime Crochemore, Wojciech Rytter, Jewels of stringology, World Scientific, 2002.
  2. Maxime Crochemore, Christophe Hancart, Thierry Lecroq, Algorithms on strings, Cambridge University Press, 2001.
  3. Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, 1999.

Credits

  • 5sp

Time schedule

  • Start date: 3rd of September, 2014
  • End date: 24th of October, 2014
  • Wednesdays:
    • 13-15, Cobol
  • Fridays:
    • 13-15, Cobol
  • Course exam: 31.10.2014
  • Check the list below for more details (SUBJECT OF CHANGE):

[google-calendar-events id=”875″ type=”list”]

Lecturer

  • Vladimir Rogojin,
  • Department of IT,
  • Åbo Akademi University,
  • vrogojin at abo.fi, room B5078, ICT-house

Course assistant

Bogdan Iancu

Department of IT,

Åbo Akademi University,

biancu at abo.fi, room B5058, ICT-house

Previous course page