Schedule & Material
Lecture schedule
The course plan is subject to change. The slides of future classes are linked to the slides from the last year’s course. However, slides with a (*) have been updated. ‘A’ below indicates the noon session starting at 12:15, and ‘B’ indicates the evening sessions starting at 18:00.
| Week | Monday (lectures) | Wednesday (lab) |
|---|---|---|
| 01 | Oct 22 A: Introduction (incl. Language Guessing) (*) B: Complexity theory (*) |
Oct 24 lab: Language Guessing |
| 02 | Oct 29 A: Elemenary sorts (*) B: Quicksort (*) |
Oct 31 lab: Computational Complexity |
| 03 | Nov 05 A: Quicksort (cont'd) (*) B: Binary heaps & heapsort (*) |
Nov 07 lab: Sorting / Graded Assignment |
| 04 | Nov 12 A: Undirected graphs (*) B: Undirected graphs (cont'd) (*) |
Nov 14 lab: Graded Assignment |
| 05 | Nov 19 A: Directed graphs (*) B: Directed graphs (cont'd) (*) |
Nov 21 lab: Undirected graphs |
| 06 | Nov 26 A: Formal languages and automata (slides, 8up) B: Formal languages and automata |
Nov 28 lab: Directed graphs |
| 07 | Dec 03 A: Regular grammars and finite state automata (slides, 8up) B: Regular grammars and finite state automata |
Dec 05 lab: Introduction to Python (slides) |
| 08 | Dec 10 A: Minimum Spanning Trees B: Shortest Paths |
Dec 12 lab: Graded Assignment |
| 09 | Dec 17 A: Finite-state transducers (slides, 8up) B: Finite-state applications in CL (slides, 8up, xfst-demo) |
Dec 19 lab: Finite-state automata plus take-home exam practise. |
| Sem. break | No class |
No class |
| 10 | Jan 7 A: Dependency grammars (slides, 8up) B: Universal Dependencies |
Jan 9 lab: Discussion of graded assignment \& practise exam |
| 11 | Jan 14 A: Dependency parsing (slides, 8up) B: A hands-on introduction to classification |
Jan 16 lab: Discussion of Finite-state automata exercises |
| 12 | Jan 21 A: Dependency parsing (contd.) B: Context-free languages and constituency parsing (slides, 8up) |
Jan 23 lab: Finite-state morphology and finite-state transducers |
| 13 | Jan 28 A: Context-free languages and constituency parsing (contd.) B: Summary / discussion |
Jan 30 lab: Assignment 11 (continued) |
| 14 | Feb 04 A: Exam B: Exam solutions/discussion |
Feb 06 lab: Discussion of Assignment 11 and introduction of Assignment 12 |
Extra Reading and Lecture Material
- Language Guessing (Cavnar and Trenkle, 1994)
- Animation for Selection Sort
- Animation for Insertion Sort
- Animation for Shell Sort
- Animation for Knuth Shuffle
- Animation of Quicksort partitionings
- Animation for Binary Heap
- Animation for Heapsort
- Animation for DFS in graphs
- Animation for BFS in graphs
- Animation for graph connectedness
- Animation for DFS in directed graphs
- Animation for BFS in directed graphs
- Animation for Kosaraju-Sharir algorithm
- Animation for Topological sort algorithm
- Animation for Greedy Algorithm
- Animation for Kruskal's Algorithm
- Animation for Prim's Algorithm
- Animation for Dijkstra's Algorithm
- Animation for Acyclic Shortest Paths
- Animation for 44 Bellman-Ford Algorithm