Introduction

This is the web page of the course Data Structures and Algorithms for Computational Lingustics III, WS 2023-2024 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, and finite state automata and related algorithms. The course is driven by assignments where participants implement these algorithms and data structures in small, but practical, applications.

Goals

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

• Become (more) familiar with important data structures and algorithms.
• 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.

GitHub registration

We will make use of git through GitHub classroom. Please obtain a GitHub account before the beginning of the course.

Literature

• Data Structures and Algorithms in Python, 2013, Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
• Speech and Language Processing, 2nd edition, Dan Jurafsky & James H. Martin (Draft chapters from the third edition are available online)

Practical information

Lectures	Mon 14:00-16:00, Seminarraum 301 (Lothar-Meyer-Bau)
	Wed 14:00-16:00, Seminarraum 301 (Lothar-Meyer-Bau)
Computer lab	Fri 14:00-18:00, Seminarraum 301 (Lothar-Meyer-Bau)
First Lecture	October 23
Lecturer	Çağrı Çöltekin <ccoltekin@sfs.uni-tuebingen.de>
Tutors	Darja Jepifanova and Giulio Cusenza