Introduction

This is the web page of the course Data Structures and Algorithms for Computational Lingustics III, WS 2019-2020 taught at the Department of Computational Linguistics, University of Tübingen.

This programming course provides an introduction to algorithms and data structures that are commonly used in computational linguistics, such as string distance measures, data structures for approximate string search, finite state automata, and parsing algorithms. The course is driven by assignments where participants implement these algorithms and data structures in small, but practical, applications.

Practical information

Lectures	Monday 10:15-11:45, room 0.01
	Wednesday 10:15-11:45, room 0.01
Computer lab	Friday 8:15-11:45, room 0.01
First Lecture	October 21
Lecturers	Corina Dima <corina.dima@uni-tuebingen.de>
	Çağrı Çöltekin <ccoltekin@sfs.uni-tuebingen.de>
Tutors	Kevin Glocker <kevin.glocker@student.uni-tuebingen.de>
	Teslin Roys <teslin.roys@student.uni-tuebingen.de>

Goals

By the end of the course you will be able to:

• Write programs to query directed and undirected graphs, such as:
  • Are two vertices connected?
  • What is the shortest path between two vertices?
  • Does a directed graph contain cycles?
• Implement a spell-checker.
• Implement a recognizer for finite state grammars.
• Implement a simple dependency parser.
• Implement parsing algorithms that are discussed in the Computational Linguistics: Parsing course.

GitHub registration

To register, and access to some of the course material, you need to complete an introductory assignment. Please do this before Wednesday 23rd.

Literature

• Data Structures and Algorithms in Python, 2013, Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
• Dependency Parsing, 2009, Sandra Kübler, Ryan McDonald & Joakim Nivre
• Speech and Language Processing, 2nd edition, Dan Jurafsky & James H. Martin (Draft chapters from the third edition are available online)