**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)