The information in this course page is likely to change.

In particular, there are still uncertainties about the mode of lectures.

Introduction

This is the web page of the course Data Structures and Algorithms for Computational Lingustics III, WS 2021-2022 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.

Practical information

Lectures	Mon 14:00-16:00, room 0.02
	Wed 12:00-14:00, room 0.02
Computer lab	Fri 14:00-18:00, room 0.02
First Lecture	October 25
Lecturer	Çağrı Çöltekin <ccoltekin@sfs.uni-tuebingen.de>
Tutors	Klara Lennerman, Siena Biales

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)