Linguistics 445/ 545 / CSCI B659
Computation and Linguistic Analysis
Spring 2016

Course goals This course will introduce students to computational linguistics (CL) and natural language processing (NLP), a field combining insights from linguistics and computer science. The course is concerned with concepts, models, and algorithms to interpret, generate, and learn natural languages, as well as applications of NLP.

We will look at these different levels of linguistic analysis: morphology, morpho-syntax, syntax, lexical semantics, and to some extent compositional semantics. In so doing, we will move from simple representations of language, such as finite-state techniques and n-gram analysis, to more advanced representations, such as those found in context-free and unification-based parsing. Some emphasis will be placed on parsing techniques in this course.

Meeting time: TR 4:00–5:15pm

Classroom: Lindley Hall (LH) 030

Course website:

Credits: 3

Course prerequisites: Permission of instructor: L555 or a programming equivalent is recommended for this course, as well as some background in linguistics.

Instructor: Markus Dickinson

Office: Memorial Hall (MM) 317

Phone: (812) 856-2535

E-mail: (remove the fruit)

Office hours: (at least for the first week)

R 11:00am-12:00pm
or by appointment


Course requirements:

Academic Integrity: (from the Dean for Academic Standards and Opportunities)

Academic Integrity: As a student at IU, you are expected to adhere to the standards and policies detailed in the Code of Student Rights, Responsibilities, and Conduct ( When you submit an assignment with your name on it, you are signifying that the work contained therein is all yours, unless otherwise cited or referenced. Any ideas or materials taken from another source for either written or oral use must be fully acknowledged. If you are unsure about the expectations for completing an assignment or taking a test or exam, be sure to seek clarification beforehand. All suspected violations of the Code will be handled according to University policies. Sanctions for academic misconduct may include a failing grade on the assignment, reduction in your final course grade, a failing grade in the course, among other possibilities, and must include a report to the Dean of Students who may impose additional disciplinary sanctions.

Students with Disabilities: Students who need an accommodation based on the impact of a disability should contact me to arrange an appointment as soon as possible to discuss the course format, to anticipate needs, and to explore potential accommodations.

I rely on Disability Services for Students for assistance in verifying the need for accommodations and developing accommodation strategies. Students who have not previously contacted Disability Services are encouraged to do so (812-855-7578;


MonthDateTopic Reading Assignments

Jan. 12Intro to class (.pdf, 2x3.pdf) ch. 1
14Regular expressions & Automata (.pdf, 2x3.pdf)ch. 2

19Regular expressions & Automata
21Morphology (.pdf, 2x3.pdf) ch. 3

26Finite-State Transducers (FSTs)
28FST work (.pdf, 2x3.pdf) HW1 due

Feb. 2FST work
4Composition (.pdf, 2x3.pdf) Roark&Sproat, ch. 2

9N-grams (.pdf, 2x3.pdf) ch. 4 HW2 due
11Part-of-speech (POS) tagging (.pdf, 2x3.pdf) ch. 5

16POS tagging
18Tagging work (tutorial, how-to, handout, tt2visl.txt, .gram) Karlsson (1990) HW3 due

23Basics of set theory (.pdf, 2x3.pdf)
25Context-Free Grammars (CFGs) (.pdf, 2x3.pdf) ch. 12

Mar. 1CFGs & Parsing (.pdf, 2x3.pdf) ch. 13 HW4 due
3CFGs & Parsing

8More chart parsing
10Prolog (.pdf, 2x3.pdf) (, HW5 due

15No class, Spring Break
17No class, Spring Break

22Definite clause grammars
24Unification-based parsing (.pdf, 2x3.pdf) ch. 15

29Unification-based parsing (.pdf, 2x3.pdf)
31Grammar complexity (.pdf, 2x3.pdf) ch. 16 HW6 due

Apr. 5Partial parsing sec. 13.5
7Dependency parsing (.pdf, 2x3.pdf)

12Dependency parsing (NASSLI 2010 notes: graph, non-projectivity)
14Parsing work HW7 due

19Semantics (Knowledge-based) (.pdf, 2x3.pdf) ch. 17
21Semantic analysis ch. 18

26Semantic analysis HW8 due
28Lexical semantics ch. 19

May 3Written projects due @ 5pm (description)

Disclaimer This syllabus is subject to change and shift—and most likely will. All important changes will be made in writing, with ample time for adjustment.