CSCD 420 Oct 21 2026

Overview

Chris Cain reports a 54% average on Exam 1, with about two-thirds of the class earning an F, and proposes more exam points based on class engagement while offering flexible office-hour support. He then works through the CYK membership algorithm on the string aabbb, showing how a Chomsky normal form grammar fills a substring table, and previews a project implementing the algorithm with cubic-time complexity.

Key takeaways

Exam 1 averaged 54%, with about two-thirds of the class earning an F; Chris Cain plans to add future exam points in proportion to class engagement rather than change the assessed material.
CYK requires a grammar in Chomsky normal form and decides membership by recording, for every substring, the nonterminals that can derive it.
For substrings longer than two characters, CYK tests every possible split, combines the corresponding nonterminal sets, and unions the production matches.
A CYK table entry is a set, so duplicate derivations do not affect the result, and the table need not store the derivation sequence when the goal is only membership testing.
A string is accepted exactly when the start symbol appears in the cell for the entire string; in Cain's aabbb example, S appears in the final cell.
CYK uses a quadratic-size table and checks split points for each substring, yielding cubic-time complexity and forming the basis of the course's first project.

Chapters

0:00 Exam 1 Results: 54% Average and a Plan for Recovery

Chris Cain reports a 54% class average on Exam 1, with roughly two-thirds of students receiving an F and three perfect scores, including extra credit.
Exam scores are available during office visits, but will not be posted until the remaining student has taken the exam.
Cain plans to increase the points available on future exams in proportion to class effort, without changing what the exams assess.

6:00 Office-Hour Access and Building Better Study Habits

Cain says the mismatch between submitted homework quality and Exam 1 performance suggests that homework may not be producing durable, independent problem-solving skills.
Students can email Cain their schedules to arrange afternoon or early-morning help, or meet with Akiba when available.
The course is moving from about six larger assignments toward roughly eight assignments, with more regular feedback before exams.

11:14 CYK Membership Testing and Substring Index Notation

The Cocke–Younger–Kasami (CYK) algorithm is a dynamic-programming method that tests whether a context-free grammar can produce a query string.
Each table entry records the nonterminals that can derive the substring from position i through position j, inclusive.
CYK requires productions in Chomsky normal form (CNF); a grammar must be converted to CNF before applying the algorithm.

14:31 Building the CYK Table for the String aabbb

Cain uses the five-character string aabbb and arranges its substrings in a triangular table indexed from 1 to 5.
The base row handles length-one substrings: positions 1 and 2 contain a, while positions 3 through 5 contain b.
Each cell stores a set of nonterminals, so it can represent multiple ways for the grammar to derive the same substring.

18:28 Length-Two Substrings: Combining Adjacent Cells

For each length-two substring, CYK combines the nonterminal sets for its two single-character parts and checks the resulting pairs against grammar productions.
The substring aa has no matching production pair in Cain's example, so its table entry is empty.
For ab, the pair AB matches productions with left-hand sides S and B; for bb, the pair BB yields A.

25:17 Length-Three Substrings: Trying Every Split Point

A length-three substring has two possible split points, so CYK tests both a + ab and aa + b for the first three characters.
For each split, the algorithm takes the Cartesian product of the two referenced table sets, then unions the results across split points.
For the substring aab, the matching pair AB contributes the nonterminals S and B, while an empty component contributes no candidates.

34:13 Length-Four Substrings: Extending the Dynamic-Programming Table

For a length-four substring, CYK checks three split points, including partitions of lengths 1+3, 2+2, and 3+1.
The previously computed entries for shorter substrings are reused, avoiding repeated derivation work.
Cain's example produces A for the substring aabb after candidate pairs from the splits are checked against the grammar.

40:29 Interpreting CYK Entries Before the Final String Check

An entry such as N₁,₃ records which nonterminals can derive the substring in positions 1 through 3, not the specific production sequence used.
For the full query, acceptance depends only on whether the grammar's start symbol S appears in the final table cell.
Duplicate candidate pairs do not change an entry because CYK stores results as sets.

42:37 Length-Five Calculation: Checking Whether S Derives aabbb

The full five-character substring has four possible split points, each combining two entries already computed for shorter substrings.
Cain finds an AB pair that matches the production for S, so S appears in the final cell and the grammar generates aabbb.
Once S is found, the acceptance decision is established; completing every remaining candidate calculation is unnecessary.

48:15 CYK Project Requirements and Cubic-Time Analysis

Cain's first project asks students to read a grammar in a specified format and a query string, build the CYK table, and report whether the grammar generates the string.
The table has quadratic size in the string length, while considering split points adds another factor, giving CYK cubic-time complexity.
Cain invites students to revisit the worked aabbb example and use office hours for help with indexing or table construction.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Chris Cain.