Week 6 to 12

a. Readings for the remaining half of the semester are sent via email to the registered students of the course. They can also be obtained here R1 and R2.

b. Next Problem set will be sent soon.

c. PS1a and 1b EXTENDED submission date: 2 November 2020.

===ooOoo===

Week 4 & 5:

a. Readings for weeks 4 & 5 were sent to all registered students. It is also available here.

b. Commented Exercises 1b and 1c were sent to registered students

c. Problem set 1b was sent last Sunday 11 October 2020. Please inform instructor if you are registered for the course but unable to receive copy of PS1b.

d. Here is an out of print book by Hopcroft and Ullmann in Foundation of Computer Science.

===ooOoo===

Week 3

The book What can be computed ? by John MacCormick is a nice book to read that could help one appreciate this course.

oo0oo

The following were sent to all registered students:

-Comments and remarks on suggested solutions to Exercise 1a..

-Group Exercise 1b. which is also available here.

-Assigned readings (Decidability and Rice Theorem) for week3.

Exercise 1c is now available here.

Problem set 1a has been emailed to all registered students of the course.

Please inform instructor if you're registered but unable to receive PS1a.

Reminders:

a. Suggested solutions to Exercise 1b is DUE 2 October 2020.

b. Suggested solutions for Exercise 1c is DUE 5 October 2020.

===ooOoo===

Week 2:

To help everyone to start doing some proof, you may consult the following:

1. Steps to Proving a Theorem

2. Proof-and-Reasoning.pdf

oo0oo

1. Readings for week2&3 are now available here.

2. Also, readings are sent through email this weekend to registered students.

3. Please email the instructor if you did not get copies of the readings.

Reminders:

• Exercise 1a: (Due: 22 September 2020, 11:59pm) [pdf]

Send your group suggested solution to the above Exercises on or before Wednesday next week, i.e. 22 Sept 2020. 11:59pm. to < hnadorna@up.edu.ph>

• Please join study group organized by students via Discord, contact your classmate Mabelle Saludares <mis.saludares@gmail.com> for info.

===ooOoo===

Week 1:

Exercise 1a: (Due: 22 Sept. 2020 11:59pm) [pdf]

Posted:16 September 2020, 1500H

1. Use the results of Exercises no. 1.51 and 1.52 in Sipser's IToC to realize a state minimization of any DFA.

2. Suggest a solution for Exercise No. 1.59 from IToC of Sipser.

Send your group suggested solution to the above Exercises

on or before Wednesday next week, i.e. 22 Sept 2020. 11:59pm to < hnadorna@up.edu.ph>

This will be your first, CS204 My Update and CS 204 My Submission.

Note:

CS204 My Update : narrative feedback of the lesson read... (to be sent individually by student)

CS 204 My Submission : Exercise 1a

(to be submitted by a group representative only, with proper acknowledgement of

who participated and how each participated.)

ooOoo

• Please answer the following questions precisely, completely and correctly.

Send your answers by REPLYING to this email sent last weekend.

1. What is your undergraduate degree?

2. From which university did you obtain your undergraduate degree from?

3. What is/are your motivation(s) for attending graduate school in computer science?

4. What do you expect to learn from taking graduate courses?

5. What do you expect from CS 204, Theory of computation?

6. What do you plan to do after graduation?

I hope to obtain your reply before 6pm on Monday 14 September 2020.

• Readings for week o and week 1 are already sent via email last weekend.

• Please email the instructor if you did not get copies of the readings.

• Here is the slide presentation for tonights Meet and Greet Session!

===ooOoo===

Week 0:

• This course, CS 204 is listed in UVLE. You must enroll to this course.

Students must activate their UVLe accounts; they need to log-in at UVLe using their DilNet accounts and (for first time users) must accept the UP Academic Use Policy after logging in.

FOR STUDENTS, this is HOW TO ENROLL TO A COURSE in UVLE.

• The syllabus of the course can be obtained here.

• Notes, problem sets and exercises for each topic will be posted weekly to this course webpage.

• Please allow your self to acquire the required at least ([S]) in the main references.

  • [S] Sipser, Introduction to Theory of Computation (2ed): pdfs (2ed) (3ed)

  • [HS] Homer and Selman, Computability and Complexity (2ed) pdf (2ed) errata issues?

• We will follow sequence of topics from [S] for the first six weeks and then [HS] for the last six weeks.

• You can now start reading the following chapters (0 to 2) from Sipser's book on ITC 2ed.

• Chapters 0-3 of Sipser's book ITC 2ed are the minimum requirements to appreciate the course. (Undergraduate Automata and Computability Theory course.)

• Please allow yourself to be familiar with doing proofs. You might want to start watching Methods of Proofs from patrickJMT from YouTube.

• Godel's Incompleteness Theorem - Intro to Theoretical Computer Science