This course will cover the mathematical foundations of the theory of computation, a branch of mathematics and computer science focused on different models of computation and their ability to solve problems. Possible topics may include: finite state automata and regular expressions; push down automata and context-free grammars; Turing machines and the Church-Turing thesis; computability; undecidability; and Godel's Incompleteness Theorem. The course will also include applications of several of these topics to other areas, particularly the mathematical field of combinatorics. Prereq: MATH 2100, MATH 2350 or MATH 3100.
Lectures: |
M, W, F | 9:00am - 9:50am |
| Cudahy Hall 120 | ||
Office Hours: |
Monday, | 1:00pm - 2:00pm |
| in person, Cudahy 307 | ||
| Wednesday, | 2:30pm - 3:30pm | |
| on Microsoft Teams | ||
| and by appointment (just email me!) | ||
| Tues, Jan 17 | Classes begin |
| Wed, Jan 25 | Last day to add/drop classes or request CR/NC option |
| Mon, Mar 6 — Sat, Mar 11 | Midterm exam period |
| Mon, Mar 13 — Fri, Mar 17 | Spring break, no classes |
| Thurs, Apr 6 — Mon, Apr 10 | Easter break, no classes |
| Fri, Apr 14 | Last day to withdraw from classes |
| Fri, May 5 | Last day of classes |
| # | Date | Topics | Announcements / Homework |
|---|---|---|---|
| Week 1 | |||
| 1 | Wed, Jan 18 |
Syllabus Topic 1 - Preliminaries (started) |
|
| 2 | Fri, Jan 20 |
Topic 1 - Preliminaries (finished) Topic 2 - Strings and Languages (started) |
|
| Week 2 | |||
| 3 | Mon, Jan 23 |
Topic 2 - Strings and Languages (finished) Topic 3 - Regular Expressions (started) XKCD #208 XKCD #1171 |
|
| 4 | Wed, Jan 25 |
Topic 3 - Regular Expressions (continued) |
|
| 5 | Fri, Jan 27 |
Topic 3 - Regular Expressions (continued) |
|
| Week 3 | |||
| 6 | Mon, Jan 30 |
Topic 3 - Regular Expressions (finished) Topic 4 - Finite State Automata (started) |
|
| 7 | Wed, Feb 1 |
Homework 1 Assigned Topic 4 - Finite State Automata (continued) |
|
| 8 | Fri, Feb 3 | Topic 4 - Finite State Automata (continued) | |
| Week 4 | |||
| 9 | Mon, Feb 6 | Topic 4 - Finite State Automata (continued) | |
| 10 | Wed, Feb 8 |
Topic 4 - Finite State Automata (finished) Topic 5 - Nondeterministic Finite Automata (started) |
|
| 11 | Fri, Feb 10 |
Homework 1 Due Homework 2 Assigned Topic 5 - Nondeterministic Finite Automata (continued) |
|
| Week 5 | |||
| 12 | Mon, Feb 13 | Topic 5 - Nondeterministic Finite Automata (continued) | |
| 13 | Wed, Feb 15 | Topic 5 - Nondeterministic Finite Automata (continued) | |
| 14 | Fri, Feb 17 | Topic 5 - Nondeterministic Finite Automata (basically finished) | |
| Week 6 | |||
| 15 | Mon, Feb 20 |
Topic 5 - Nondeterministic Finite Automata (basically finished) Topic 6 - Regular vs. Recognizable Languages (started) |
|
| 16 | Wed, Feb 22 | Class Cancelled Today | |
| 17 | Fri, Feb 24 |
Homework 2 Due Topic 6 - Regular vs. Recognizable Languages (continued) |
|
| Week 7 | |||
| 18 | Mon, Feb 27 |
Homework 3 Assigned Topic 6 - Regular vs. Recognizable Languages (finished) |
|
| 19 | Wed, Mar 1 | Topic 7 - Nonregular Languages (started) | |
| 20 | Fri, Mar 3 | Topic 7 - Nonregular Languages (continued) | |
| Week 8 | |||
| 21 | Mon, Mar 6 | Topic 7 - Nonregular Languages (continued) | |
| 22 | Wed, Mar 8 |
Topic 7 - Nonregular Languages (finished) Topic 8 - Applications of Regular Languages (started) assorted links |
|
| 23 | Fri, Mar 10 |
Homework 3 Due Topic 8 - Applications of Regular Languages (continued) |
|
| Spring Break | |||
| Mon, Mar 13 | Spring Break — no classes | ||
| Wed, Mar 15 | Spring Break — no classes | ||
| Fri, Mar 17 | Spring Break — no classes | ||
| Week 9 | |||
| 24 | Mon, Mar 20 |
Homework 4 Assigned Final Project Assigned and Discusssed (see pdf at top of page under Homework) Topic 8 - Applications of Regular Languages (continued) |
|
| 25 | Wed, Mar 22 | Topic 8 - Applications of Regular Languages (continued) | |
| 26 | Fri, Mar 24 | Topic 8 - Applications of Regular Languages (continued) | |
| Week 10 | |||
| 27 | Mon, Mar 27 | Topic 8 - Applications of Regular Languages (continued) | |
| 28 | Wed, Mar 29 | Topic 8 - Applications of Regular Languages (finished) | |
| 29 | Fri, Mar 31 |
Topic 9 - Context-Free Grammars (started) |
|
| Week 11 | |||
| 30 | Mon, Apr 3 |
Homework 4 Due Final Project Progress — paper selection or one-page report Topic 9 - Context-Free Grammars (continued) |
|
| 31 | Wed, Apr 5 | Topic 9 - Context-Free Grammars (continued) | |
| Fri, Apr 7 | Easter Break – no classes | ||
| Week 12 | |||
| Mon, Apr 10 | Easter Break – no classes | ||
| 32 | Wed, Apr 12 | Topic 9 - Context-Free Grammars (finished) | |
| 33 | Fri, Apr 14 |
Topic V1 - The Myhill-Nerode Lemma (started) Pre-recorded Video |
|
| Week 13 | |||
| 34 | Mon, Apr 17 |
Topic V1 - The Myhill-Nerode Lemma (finished) Pre-recorded Video |
|
| 35 | Wed, Apr 19 |
Topic V2 - DFA Minimization Pre-recorded Video Homework 5 Assigned |
|
| 36 | Fri, Apr 21 | Topic 10 - Pushdown Automata (started) | |
| Week 14 | |||
| 37 | Mon, Apr 24 | Topic 10 - Pushdown Automata (finished) | |
| 38 | Wed, Apr 26 | Presentations — NN, DR | |
| 39 | Fri, Apr 28 | Presentations — TM, ER | |
| Week 15 | |||
| 40 | Mon, May 1 | Presentations — DC, TC | |
| 41 | Wed, May 3 | Presentations — AG, BB, MI | |
| 42 | Fri, May 5 |
Homework 5 Due Presentations — JN, AO |