Homework 12

DUE: Last day of classes, May 2.

This homework is an opportunity for you to explore a topic we did not cover and share what you learn with the rest of the class.

What to explore

Things we did:

1 functional programming in Scheme

2 lambda calculus, currying and partial application

3 finite automata, regular expressions, pumping lemma

4 proof techniques: construction, contradiction, induction

5 context-free grammars/languages, push-down automata, pumping lemma

6 declarative programming in Prolog

7 Turing machines, Church-Turing thesis

8 decidability, countability, diagonalization, the Halting problem

9 Godel's incompleteness theorem

10 time complexity, Big-O complexity classes

11 dynamic programming and memoization

12 P and NP, reducibility, NP completeness

13 recursive descent parser

Things we didn't do:

1 first-order logic http://en.wikipedia.org/wiki/First-order_logic

2 R and PR http://en.wikipedia.org/wiki/Primitive_recursive_function

3 concurrent programming in Io or Go

4 object-oriented programming in Smalltalk or Scala

5 more parsing: shift-reduce parser for LR grammars

6 Primes is in P

Ways to look for other ideas:

1 Parts of Sipser we did not read

2 Syllabi of other classes like this

3 Random walk from relevant Wikipedia pages

4 Relevant research since Sipser's book

5 Seven Languages in Seven Weeks, Language Implementation Patterns, other books

What to present

Imagine that you are teaching a one-week module on your topics for a class like FOCS. You would need the following materials:

    1. Readings: identify the readings you would like your hypothetical students to do before class.

    2. Reading questions: write some questions to guide readers to the most important points and smooth out rough spots.

    3. Lecture notes: what would you present in class?

    4. In class activities: what would students do in class?

    5. Quiz questions and solutions.

    6. Homework exercise and solutions.

I have created a page on this site which you should have permission to modify:

    1. Navigate to DIY. You should see buttons in the upper right to edit the page or add a page.

    2. Add a page and give it a title relevant you your topic. Be sure to click on "Put page under DIY".

    3. Put all your material on the new page, except the solutions to your quiz and homework questions, which you can put on a subpage or an attachment.

The goal is that another student in the class should be able to read your page, learn something interesting about your topic, and do an exercise to test and develop their knowledge.

Finally, during the last two class sessions, you will have a chance to present a 10-minute version of what you learned. We will talk in class about the format and goals for the presentation.