## Introduction

This is the web page of the course
*Data Structures and Algorithms for Computational Lingustics III*
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 12:15-13:45, Monday 18:00-19:30, room 0.02 |
---|---|

Computer lab | Wednesday 14:15-18:00, room 0.01 |

First Lecture | October 22 |

Lecturers | Claus Zinn <claus.zinn@uni-tuebingen.de> |

Çağrı Çöltekin <ccoltekin@sfs.uni-tuebingen.de> | |

Tutors | Marko Lozajic <marko.lozajic@student.uni-tuebingen.de> |

Michael Watkins <michael.watkins@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 24th.

### Literature

- Algorithms, 4th Edition, Robert Sedgewick & Kevin Wayne
- Dependency Parsing, 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)