Linguistics 545
Computation and Linguistic Analysis
Spring 2013

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: MW 9:30-10:45am

Classroom: Memorial Hall (MM) 401

Course website:

Credits: 3

Course prerequisites: None (open to all upper class and graduate students)

Instructor: Markus Dickinson

Office: Memorial Hall (MM) 317

Phone: (812) 856-2535

E-mail: (remove the social networking name)

Office hours: (at least for the first week)

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


Course requirements:

Academic Misconduct: Academic misconduct is not allowed in this course. The Indiana University Code of Student Rights, Responsibilities, and Conduct ( defines academic misconduct as “any activity that tends to undermine the academic integrity of the institution . . . Academic misconduct may involve human, hard-copy, or electronic resources . . . Academic misconduct includes, but is not limited to . . . cheating, fabrication, plagiarism, interference, violation of course rules, and facilitating academic misconduct” (II. G.1-6).

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. 7Intro to class (.pdf, 2x3.pdf) ch. 1
9Regular expressions & Automata (.pdf, 2x3.pdf)ch. 2

14Regular expressions & Automata
16Morphology (.pdf, 2x3.pdf) ch. 3

21No class, MLK Day
23Finite-State Transducers (FSTs) HW1 due

28FST work (.pdf, 2x3.pdf)
30FST work

Feb. 4Composition (.pdf, 2x3.pdf) Roark&Sproat, ch. 2HW2 due
6N-grams (.pdf, 2x3.pdf) ch. 4

11Part-of-speech (POS) tagging (.pdf, 2x3.pdf) ch. 5
13Basics of set theory (.pdf, 2x3.pdf)

18Context-Free Grammars (CFGs) (.pdf, 2x3.pdf) ch. 12 HW3 due
20CFGs & Parsing (.pdf, 2x3.pdf) ch. 13

25CFGs & Parsing HW4 due
27More on chart parsing

Mar. 4Prolog (.pdf, 2x3.pdf) Code:
6Definite clause grammars, Code: HW5 due

11No class, Spring Break
13No class, Spring Break

18Unification-based parsing (.pdf, 2x3.pdf) ch. 15
20Unification-based parsing (.pdf, 2x3.pdf)

25Grammar complexity (.pdf, 2x3.pdf) ch. 16
27Partial parsing sec. 13.5 HW6 due

Apr. 1Dependency parsing (.pdf, 2x3.pdf)
3Dependency parsing

8Semantics (Knowledge-based) (.pdf, 2x3.pdf) ch. 17 HW7 due
10Semantic analysis ch. 18

15Semantic analysis
17Lexical semantics ch. 19 HW8 due

22Project presentations
24Project presentations

May 1Written projects due

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.