↑ Return to Advanced Text Algorithms

Advanced text algorithms – 2016

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: 5th of September, 2016
  • End date: 26th of October, 2016
  • Mondays:
    • 13-15, K124B, Agora
  • Wednesdays:
    • 15-17, XX, Agora
  • Course exam:
    • 28th of October, 2016
    • 11th of November, 2016
  • General exam:
    • 20th of January, 2017
    • 10th of March, 2017
    • 12th of May, 2017
  • Check the list below for more details (SUBJECT OF CHANGE):
September 5, 2016
September 7, 2016
September 12, 2016
September 14, 2016
September 19, 2016
September 21, 2016
September 26, 2016
September 28, 2016
October 3, 2016
October 5, 2016
October 10, 2016
October 12, 2016
October 17, 2016
October 19, 2016
  • October 19, 2016: Lecture 14:
    3:15 pm - 4:45 pm, XX, Agora,
October 24, 2016
  • October 24, 2016:
    1:30 pm - 3:00 pm, K124B, Agora,
October 26, 2016
  • October 26, 2016:
    3:15 pm - 4:45 pm, XX, Agora,
Powered by Simple Calendar

Lecturer

  • Vladimir Rogojin,
  • Faculty of Science and Engineering,
  • Åbo Akademi University,
  • vrogojin at abo.fi

Course assistant

Abdul Rasheed

Faculty of Science and Engineering,

Åbo Akademi University,

abrashee at abo.fi

Previous course page

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 …

View page »

Protected: Projects and Gained Scores

There is no excerpt because this is a protected post.

View page »