CS 4510

Overview

CS 4510 is a 3 credit hour theoretical CS/math class in the CS department taken by both Intelligence and Theory threads (CS). The class has no lab or recitation.

Topics Covered

1. Finite Automata
2. Regular Expressions
3. Context-Free Grammars
4. Turing Machines

The course closely follows this textbook: Introduction to the Theory of Computation, 3rd edition by Michael Sipser.

The textbook is extremely well-written and concise, and you can easily search for pdfs online.

How it fits in the Curriculum

CS 4510 is required for Theory threads and Intelligence threads (as the Theory class). Since it is at the end of a rather long prerequisite chain (requiring all of CS 2050, MATH 3012, CS 1332, MATH 3215 and CS 3510), it is generally taken in your late third year or fourth year. The class is not a prereq for any other class.

Current Registration Info

This class is a regular class, meaning there is no linked section, no lab, or no recitation.

The course also has an honors section, marked with an "X", which has extra worksheets and more difficult assignments/tests, but you get a nice letter at the end saying you're super cool.

TL;DR: If you want to register for a regular version of CS 4510, register for any section except Section X. If you want to take the honors section, register for section X.

Prerequisites

All of the following:

• C or higher in MATH 3215 or MATH 3670 or ISYE 3770
• D or higher in MATH 3012
• C or higher in CS 3510 or CS 3511

Past Semesters

Fall 2021

Prof: Faulkner

The lectures were in-person. The professor and TAs took questions in class, and there were plenty of office hours (both in-person and virtual). There were also extra credit opportunities (up to 3% of the assignment’s worth) on all homework and exams.

Spring 2021

Prof: Zvi

The lectures were pre-recorded (from Fall 2020), but the prof and TAs took questions and there were plenty of office hours.