Review Session Wednesday (2-4 PM)

We are going to have a review session for the final exam.

Date: Wednesday, May 9th (tomorrow)
Time: 2-4 PM
Where: GHC 6002.

Note: The final will emphasize topics from the last third of the course, but the rest is also fair game.

TA Evaluations

Please take time to complete your Teaching Assistant evaluation surveys. The links will remain active until end of business on May 12th, so evaluations will need to be completed before then. Thank you.

http://www.surveymonkey.com/s/3KHD8YV Blocki

http://www.surveymonkey.com/s/3KPCCHP Hanneman

Project presentation slides

Student presentations can be found at: http://www.cs.cmu.edu/~lblum/flac/ProjectPresentations

Final Project Presentations (Locations)

Here are the locations for the two time slots that are not during class.

Tuesday, May 1, 2-3 PM  (GHC 7501)
Thursday, May 3, 3 - 4 PM (GHC 9115)

We encourage everyone in the class to come (even if you are not presenting). 

Midterm 2 Solutions

A few people have asked where the solutions to the second midterm were posted. We did not going to post a link to the course page, but the solutions can be found here.

Project Meetings

I am going to be gone April 7-April 20th. If am I your project advisor and you have not already met with me since you turned in your progress report then you should plan to meet with me either this week or April 23rd-27th.

Thanks,

Jeremiah

Project Presentation Sign Up

Presentation slots will be given out on a first come first, first serve basis.

Sign Up

Homework 8 Posted

Due Tuesday, April 3rd.

FIN is m-hard

FIN is m-hard for $\Sigma_2^0$

Homework 7, Problem 3 Clarification

For Problem 3 on relative decidability:  If H is the Halting Problem solver, you can assume you have access to <H>, the code for H.  The assignment PDF has also been updated with this clarification.

Homework 7 Posted

Due Tuesday, March 20th (after spring break).

Homework 5 Solutions Posted

Homework 6, Problem 4 Clarification

In problem 4 you should assume that the input of a Turing Machine M is always a binary string (the input alphabet is {0,1}).

Homework 5 Typo

There was a small typo in problem 1(B=>t_kBa_k should have been B=>b_kBa_k). The problem has been corrected on the web site.

Homework 4 (Solutions Correction)

There was an error in the Turing machine diagram for the Problem 1 solution.  The figure has been corrected, and an updated PDF of the solutions was uploaded this afternoon.  Sorry for the confusion!

Project Advisors

Greg
Chase Brownell
Will Devanny
Wade Gordon
Max Illfelder
Joseph Lee
Kellie Medlin
Laura Scharff

Jeremiah
Igor Balla
Rick Benua
Eric Cheek
Alex Crichton
Robert Liu
Paul Schultz
Max Tucker

Lenore
Ved Basu
Andrew Israel
Jason MacDonald
William Macrae
Mohith Muddasani
Sanjeev Reddy
Divya Sharma

Homework 3 (Revised Hint)

We had originally intended for the state "101" in problem 1(b) to be an accept state. For problem 1(b) you may either
(1) minimize the original DFA (presented in the homework).
(2) minimize the new DFA (after changing "101" to an accept state).

You will be given full credit for either answer. We will assume that you are minimizing the original DFA (option 1) unless clearly indicated.

Note: If you have not solved the problem yet (or even if you have) we would recommend minimizing the new DFA. The hint for homework 3 problem 2 will make more sense if you make "101" an accept state.

Monday Office Hours Moved to NSH 1505

The super office hours (Monday 3:30-5:30 PM) have been relocated to NSH 1505 for the rest of the semester. Formerly, the problem solving session was held in GHC 2109.

Homework 1

There are two minor errors in Homework 1. In Problem 1(b), "0", "1", and "2" should be called "digits", not letters. In the definition of min(A) in Problem 2, both instances of "L" should be "A" instead. The homework PDF was modified to reflect these corrections as of 11:30 p.m. on Wednesday, Jan. 18.

Fun Applications of the Pigeonhole Principle

http://mindyourdecisions.com/blog/2008/11/25/16-fun-applications-of-the-pigeonhole-principle/