Introduction
This is the web page of the course Data Structures and Algorithms for Computational Linguistics III, WS 2020-2021 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
Please note that although we have a room reserved, due to COVID-19 prevention regulations, the course will start with online (synchronous) sessions.
| Lectures | Wednesday 14:00-16:30, room 0.02 |
| Friday 14:00-16:30, room 0.02 | |
| Computer lab | Monday 14:00-19:30, room 0.02 |
| First Lecture | November 11 |
| Lecturer | Çağrı Çöltekin <ccoltekin@sfs.uni-tuebingen.de> |
| Tutors | Anna-Katharina Dick <anna-katharina.dick@student.uni-tuebingen.de> Lea Grüner <lea.gruener@student.uni-tuebingen.de> |
Goals
By the end of the course you will be able to:
- Become (more) familiar with important data structures and algorithms, such as trees, priority queues, searching and sorting
- Analyze algorithms for proving their correctness and complexity
- Write programs for common string processing tasks, such as pattern matching
- 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
To register, and access to some of the course material, you need to complete an introductory assignment. Please submit this assignment before Friday, Nov 6th.
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)