Linguistics 5801: Computational Linguistics I

This introduction for graduates and advanced undergraduates provides an introduction to theory-driven computational linguistics (CL), focusing on syntax and parsing. The course includes some formal background and emphasizes linking the theoretical discussions to practical experience implementing algorithms and small grammars.

The course is part of the two-course introduction to CL. The second half, 5802, focuses on data-intensive, statistical CL and is offered in Spring.

Instructor: William Schuler

Meeting time: Tuesday and Thursday 3:55pm-5:15pm in Jennings 136

Prereqs: LING 2001 or 3802 or 3802H or 4200 or 4400 or any 5000-level LING course or any CSE course or grad standing or permission of instructor.

Web site: The updated syllabus, assignments, slides, etc. will be posted here, so check it regularly.

Network account: If you are not able to run python or do assignments on your own computer, you can get a linguistics network account to use lab machines in Oxley Hall. You can set this up with Jim Harmon in Oxley 118 during normal working hours.

Computer lab facilities: With your linguistics network account, you can use the linguistics computer lab in Oxley 218. The computers in this lab are installed with all software required for this course. If software does not appear to be working, you should contact Jim Harmon (Oxley 118) during normal working hours.

Textbook: (optional) Natural Language Toolkit Textbook -- a nice introduction to text processing in Python.

Course Content: (blue highlighted lectures focus on programming language concepts, orange are due dates)

Wk Due Monday 11:59PM Lecture: Tuesday Due Wednesday 11:59PM Lecture: Thursday
1 8/22
welcome, set notation, finite state automata
regular expressions, regular languages, tools: grep, sed, perl
2 8/29 --- PS1 handout, sample Makefile, sample text
unix scripts, tools: make
3 9/5
programming concepts, implementing FSAs, tools: python
4 9/11 PS1 due 9/12 --- PS2 handout
data files and projects
5 9/19
program correctness, complexity, generalization
context-free grammars, context-free languages
6 9/25 PS2 due 9/26
9/28 --- PS3 handout
string recursion, pushdown automata
7 10/3
recursion in functions and data structures, tools:,
dynamic programming, implementing CFG recognizers
8 10/10
parsing, semiring abstraction
(autumn break) (autumn break)
9 10/16 PS3 due 10/17 --- PS4 handout
10/19 LN13.9 practice 3 solution
generative models
10 10/24
(no class)
11 10/31
message passing
12 11/6 PS4 due 11/7
sequence model inference, incremental parsing
13 11/14 --- PS5 handout simplewiki.gcg15.linetrees
linear algebra
14 11/21
semantic parsing
(Thanksgiving) (Thanksgiving)
15 11/27 PS5 due 11/28 --- PS6 handout
dimensionality reduction and vector semantics
functional programming
16 12/5
lambda calculus semantics
(end of term) (end of term)
17 12/11 PS6 due (end of term) (end of term) (end of term)

Successful course participation involves:

Grading scale: OSU standard scheme
A A- B+ B B- C+ C C- D+ D
93%+ 90%+ 87%+ 83%+ 80%+ 77%+ 73%+ 70%+ 67%+ 60%+

Faculty feedback and response time:

Student participation requirements: Consistent engagement is expected. If any problems arise relative to attendance, please contact the instructor as soon as possible. Communication is important. You are encouraged to participate during class, ask questions, work on in-class problems in small groups, and share your experiences relative to the subjects and discussion that day.

Attendance and active participation often impacts your performance in a meaningful way, so it will be beneficial for you to attend this course synchronously as much as possible. The lecture slides will be posted on CarmenCanvas, so if you do miss a lecture, you are expected to view the missed material before the next lecture.

Weather or other short-term closing: Should in-person classes be canceled, we will meet virtually via CarmenZoom during our regularly scheduled time. I will share any updates via email.

Students with Disabilities: The University strives to make all learning experiences as accessible as possible. If you anticipate or experience academic barriers based on your disability (including mental health, chronic or temporary medical conditions), please let me know immediately so that we can privately discuss options. To establish reasonable accommodations, I may request that you register with Student Life Disability Services. After registration, make arrangements with me as soon as possible to discuss your accommodations so that they may be implemented in a timely fashion. SLDS contact information:; 614-292-3307;; 098 Baker Hall, 113 W. 12th Avenue.

Academic Misconduct: It is the responsibility of the Committee on Academic Misconduct to investigate or establish procedures for the investigation of all reported cases of student academic misconduct. The term "academic misconduct" includes all forms of student academic misconduct wherever committed; illustrated by, but not limited to, cases of plagiarism and dishonest practices in connection with examinations. Instructors shall report all instances of alleged academic misconduct to the committee (Faculty Rule 3335-5-487). For additional information, see the Code of Student Conduct

Mental Health Services: As a student you may experience a range of issues that can cause barriers to learning, such as strained relationships, increased anxiety, alcohol/drug problems, feeling down, difficulty concentrating and/or lack of motivation. These mental health concerns or stressful events may lead to diminished academic performance or reduce a student's ability to participate in daily activities. The Ohio State University offers services to assist you with addressing these and other concerns you may be experiencing. If you or someone you know are suffering from any of the aforementioned conditions, you can learn more about the broad range of confidential mental health services available on campus via the Office of Student Life's Counseling and Consultation Service (CCS) by visiting or calling 614-292-5766. CCS is located on the 4th Floor of the Younkin Success Center and 10th Floor of Lincoln Tower. You can reach an on call counselor when CCS is closed at 614-292-5766 and 24 hour emergency help is also available through the 24/7 National Suicide Prevention Hotline at 1-800-273-TALK or at

Sexual Misconduct / Relationship Violence: Title IX makes it clear that violence and harassment based on sex and gender are Civil Rights offenses subject to the same kinds of accountability and the same kinds of support applied to offenses against other protected categories (e.g., race). If you or someone you know has been sexually harassed or assaulted, you may find the appropriate resources at or by contacting the Ohio State Title IX Coordinator, Kellie Brennan, at

Diversity: The Ohio State University affirms the importance and value of diversity in the student body. Our programs and curricula reflect our multicultural society and global economy and seek to provide opportunities for students to learn more about persons who are different from them. We are committed to maintaining a community that recognizes and values the inherent worth and dignity of every person; fosters sensitivity, understanding, and mutual respect among each member of our community; and encourages each individual to strive to reach his or her own potential. Discrimination against any individual based upon protected status, which is defined as age, color, disability, gender identity or expression, national origin, race, religion, sex, sexual orientation, or veteran status, is prohibited.

Religious Beliefs: It is Ohio State's policy to reasonably accommodate the sincerely held religious beliefs and practices of all students. The policy permits a student to be absent for up to three days each academic semester for reasons of faith or religious or spiritual belief. Students planning to use religious beliefs or practices accommodations for course requirements must inform the instructor in writing no later than 14 days after the course begins. The instructor is then responsible for scheduling an alternative time and date for the course requirement, which may be before or after the original time and date of the course requirement. These alternative accommodations will remain confidential. It is the student's responsibility to ensure that all course assignments are completed.