CS4510 Automata and Complexity

Summer 2021, TR 3:30pm - 5:40pm

Instructional Format

This course will be delivered via the hybrid format. All remote sessions will use BlueJeans, accessible through the course page on Canvas.

Course Information

  • Instructor: Abrahim Ladha, office hours TBD
  • TA(s): Somnanth Sarkar & Madhura Keshava
  • Piazza

    • Course Description

    I like to think of this class as the study of two questions:

    The first question is the study of computability theory. We will study some abstract models of computers, and understand their relative power. The second question is the study of complexity theory. Complexity has a lot of questions we can't yet answer, such as P vs. NP, but this doesn't totally prevent us from discussing hardness.

    The textbook we will be using is the Introduction to the Theory of Computation by Michael Sipser. I have a hard copy of the first edition, but I think the third edition is the newest. When I was taking this class, I didn't really like the book. I wanted to be taken seriously, and I thought the book held my hand too much. As I grew up I realized that this book is actually amazing. In a course like this, I would recommend you just start reading through the book until you get stuck. It practically reads itself to you. It makes really hard topics very easy and understandable. I may reference other material from other sources.

    This class has some large number of prerequisites, most of which I disagree are nessessary. All that you really need for this class is strong mathematical maturity. This is mostly unlike any course you have taken before.

    Evaluation Scheme

    The material for this class is pretty laidback, but I don't mind to make you sweat a bit.

    For each homework, I will provide a latex template, and if you latex your assignment, you will receive 5 bonus points. If you find the answer to a homework question online, a citation is enough for full credit. You may collaborate, but you should turn in individual solutions. The exams will be take home, and open notes. You will have a 24 hour period to complete the exams, and a week or more to complete each homeworks.

    Schedule

    This is subject to change as I realize things may take less or more time. Summer classes are pretty long, so we will have a 5-10 minute break in the middle.
    1-1 Introduction, DFAs and NFAs notes
    1-2 Closure and Regular Expressions notes
    2-1 Regexes are Regular, and the Pumping Lemma notes
    2-2 Myhill Nerode Theorem notes
    3-1 Regular and Context Free Grammars notes
    3-2 Chomsky Normal Form notes
    4-1 The Pumping Lemma for CFLS & Closure notes
    4-2 Pushdown Automata notes
    5-1 Every CFG has a PDA notes
    5-2 Turing Machines notes
    6-1 The Church-Turing Thesis notes
    6-2 Turing Completeness notes
    7-1 Diagonalization notes
    7-2 The Halting Problem notes
    8-1 Some Decidable Problems notes
    8-2 Reductions notes
    9-1 Context Sensitive Languages & Computation Histories notes
    9-2 Post Correspondence Problem notes
    10-1 Rice's Theorem notes
    10-2 The Recursion Theorem notes
    11-1 Godel Incompleteness notes
    11-2 Busy Beavers and Kolmogorov Complexity notes
    Expect up to video 16-2 for this course.

    Statement of Intent for Classroom Inclusivity

    As a member of the Georgia Tech community, I am committed to creating a learning environment in which all of my students feel safe and included. Because we are individuals with varying needs, I am reliant on your feedback to achieve this goal. To that end, I invite you to enter into dialogue with me about the things I can stop, start, and continue doing to make my classroom an environment in which every student feels valued and can engage actively in our learning community.