CmpE 415 - Theory of Computation

Fall Semester 2002

Announcements

The final results are announced. You may see your papers at ETA 203 on January 24 Friday from 12 pm to 13 pm. Please note that the objection time is limited and please try to respect this limited time.

Old Announcements

Here is a link for the summary of the languages problems.

The final date and place is announced. It will take place at 17 January 15 PM at ETA Z04.
Important announcement:

You are supposed to send your OTHER final exam dates to the instructor by email by Friday, December 13, at 13:00 at the latest. If you miss the deadline, that means you accept whatever we will fix as the exam date.
Important announcement:

The registrar's office has announced the final exam date as Saturday, Jan.4, 15:00. THIS DATE WILL BE CHANGED! CHECK YOUR OTHER EXAM DATES FROM THE SCHEDULE AT registration.boun.edu.tr, AND PREPARE A LIST OF NON-SATURDAY DATES WHICH ARE SUITABLE FOR YOU! YOU ARE SUPPOSED TO ADD YOUR NAME TO THE SIGNATURE LIST THAT WE ARE PREPARING FOR THIS PURPOSE!

Midterm 2 results are announced. You may see your papers at ETA 203 on December 11 Wednesday from 15 pm to 17 pm and on December 13 Friday from 15 pm to 17 pm.

"Primes is in p". Interested ones are invited to visit this site!
http://www.cse.iitk.ac.in/news/primality.html

A new homework is assigned. (due November 13 Wednesday, 5 PM.) Please again submit your homeworks to TA at ETA 203 or leave to his mailbox in secretary office in his absence.
1. Problem 6.13 of the book
2. Problem 6.15 of the book

Midterm 1 results are announced. The results are here. You may see your papers on November 1 Friday from 15 pm to 17pm and November 6 Wednesday from 15 pm to 17pm.

A new homework is assigned. (due November 6 Wednesday, 5 PM.) Please again submit your homeworks to TA at ETA 203 or leave to his mailbox in secretary office in his absence.
1. Problem 6.7 of the book
2. Problem 6.21 of the book
3. Problem 6.22 of the book

The course on October 22 will be held at YD204 at 11 AM. Please come to the class having previouly solved the problem 1.25.

Even if this is not for certain, there is a high chance for the course on October 22, to take place 1 hour earlier, at 11 AM. Please see the anouncements frequently. News will be posted to the web site as soon as the subject is clarified.

A very important anouncement. Here is how you can make money by learning about time complexity:

http://www.claymath.org/prizeproblems/milliondollarminesweeper.htm
A new homework is assigned. (due October 16 Wednesday, 5 PM.) Please again submit your homeworks to TA at ETA 203 or leave to his mailbox in secretary office in his absence.
1. Problem 4.17 of the book
2. Problem 5.22 of the book
A new homework is assigned in addition to below ones:
1. Try to prove that EQ_CFG, the topic of our first homework, is co-Turing-recognizable. (Due Tuesday October 8, in the classroom.)
New homeworks are assigned:
1. Try to find out a way of deciding whether a given pair of CFGs generate the same language or not. (Due Thursday, October 3, classroom)
2. Solve problems 3.16 and 3.17 from Sipser's book. (Due Tuesday, October 8 5 pm, to be collected by the assistant). You may bring your homeworks directly to the assistant's room ETA 203 or leave them to his mailbox in secretary office in the case of his absence.

You are supposed to do the exercises in the chapter 3 of the book as an homework. This homework will not be collected and graded.

The course hours are as described in the schedule for now on but they are subject to change. Please follow this announcements page frequently.

Catalog Data:	Basic concepts of computation. The theory and representation of algorithms and models of computation. Computability and recursive functions. Formal specification and proofs of programs. Automata theory.
Textbook:	Michael Sipser. Introduction to the theory of Computation. PWS Publishing Company.
Instructor:	Assoc. Prof. Cem Say
Assistants:	M. Okan Irfanoglu ETA 203 , irfanogl@boun.edu.tr

Prerequisite:

CMPE220 , CmpE 350

Topics:

1. The Church-Turing Thesis
2. Decidability
3. Reducibility
4. Advanced Topics in Computability Theory
5. Time Complexity
6. Space Complexity
7. Intractability
8. Advanced Topics in Complexity Theory

Exams:

Midterm 1: October 24 ; Course hours
Midterm 2: November 28; Course hours

Computer Usage:

None

Laboratory projects:

None.

last updated: 21 January 2003