CS 204 Theory of Computation
CS 204 Theory of Computation
Schedule : Mondays, 1800H to 2100H
Schedule : Mondays, 1800H to 2100H
Semester : 1st, AY 2021-2022
Semester : 1st, AY 2021-2022
Instructor : Henry N. Adorna
Instructor : Henry N. Adorna
email : <hnadorna@up.edu.ph>
email : <hnadorna@up.edu.ph>
Office : Rm 319
Office : Rm 319
3/F UPAE Centennial Hall
3/F UPAE Centennial Hall
The theory of computing provides computer science with concepts, models, and formalisms for reasoning about the resources needed to carry out computations and about the efficiency of the computations that use these resources. In addition, it provides tools to measure the difficulty of combinatorial problems both absolutely and in comparison with the other problems
The theory of computing provides computer science with concepts, models, and formalisms for reasoning about the resources needed to carry out computations and about the efficiency of the computations that use these resources. In addition, it provides tools to measure the difficulty of combinatorial problems both absolutely and in comparison with the other problems
Steven Homer and Alan L. Selman
Steven Homer and Alan L. Selman
Computability and Complexity Theory (2001)
Computability and Complexity Theory (2001)
This will be the official course website of CS 204 Mon, 6pm to 9pm class under Henry.
This will be the official course website of CS 204 Mon, 6pm to 9pm class under Henry.
This class will not meet physically but will be conducting classes remotely with occasional online meetings.
This class will not meet physically but will be conducting classes remotely with occasional online meetings.
Announcements for the class will be posted here, aside from emails that registered students will receive from the Instructor.
Announcements for the class will be posted here, aside from emails that registered students will receive from the Instructor.
Below will be the is the list of tentative topics to be covered for the class this semester of AY 2021-2022.
Below will be the is the list of tentative topics to be covered for the class this semester of AY 2021-2022.
List of free online (videos) resources that hopes to guide the students in appreciating the course can be obtained from HERE (the previous CS 204 course page).
List of free online (videos) resources that hopes to guide the students in appreciating the course can be obtained from HERE (the previous CS 204 course page).
Main Text References
Main Text References
Maligayang Pagdating, Mabuhay!
Maligayang Pagdating, Mabuhay!
Announcements !
Announcements !
Week 0:
Week 0:
- The syllabus of the course is show below.
- Notes, problem sets and exercises for each topic will be emailed to enrolled students (and could be posted to this course webpage) weekly, every after the meeting.
- Please allow your self to acquire the required at least ([S]) in the main references.
- 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.
Schedule of Activities
Schedule of Activities
Learning Materials, Exercises, Problem Sets
Learning Materials, Exercises, Problem Sets
Week 1: Slides
Week 2: Slides
Week 3: Slides
Week 4: Slides
Week 5: Slides
Week 6: Slides
Week 7: Slides
Week 8: Slides
Week 9: Slides
Week 10: Slides
Week 11: Slides
Week 12: Slides
Week 13: Slides
Week 14: Slides
Week 15: Slides
Week 16: Slides
Some Previous Conferences in TCS
Some Previous Conferences in TCS
