Text Searching and Processing

King's College London

Course Description

  • Course Name

    Text Searching and Processing

  • Host University

    King's College London

  • Location

    London, England

  • Area of Study

    Computer Programming, Computer Science, Information Sciences

  • Language Level

    Taught In English

  • Course Level Recommendations

    Upper

    ISA offers course level recommendations in an effort to facilitate the determination of course levels by credential evaluators.We advice each institution to have their own credentials evaluator make the final decision regrading course levels.

    Hours & Credits

  • UK Credits

    15
  • Recommended U.S. Semester Credits
    4
  • Recommended U.S. Quarter Units
    6
  • Overview

    Module description:

    Aims:
    This unit is devoted to algorithms processing strings and texts efficiently. These types of algorithms are used
    for software design in the domains of operating systems utilities, search engines on the Internet, data retrieval
    systems, analysis of genetic sequences, and natural language processing, for example.

    Learning Outcomes:
    On completing the module the students will have the basic tools to design exact and efficient algorithms for
    matching patterns in textual data and building indexes on files.

    Provisional Syllabus:
    Introduction:
    Basic concepts
    Periods in strings
    Finite automata and regular expressions
    Exact pattern matching:
    Brute-force algorithms for pattern matching
    The Knuth-Morris-Pratt algorithm
    The Boyer-Moore algorithm
    The Karp-Rabin algorithm
    Horspool's algorithm
    Multiple pattern matching:
    The Aho-Corasick automaton
    Structures for indexes:
    Suffix arrays
    Suffix trees

Course Disclaimer

Courses and course hours of instruction are subject to change.

Eligibility for courses may be subject to a placement exam and/or pre-requisites.

Some courses may require additional fees.

Credits earned vary according to the policies of the students' home institutions. According to ISA policy and possible visa requirements, students must maintain full-time enrollment status, as determined by their home institutions, for the duration of the program.

Please reference fall and spring course lists as not all courses are taught during both semesters.

Please note that some courses with locals have recommended prerequisite courses. It is the student's responsibility to consult any recommended prerequisites prior to enrolling in their course.