====== 204213: Theory of Computation ======

===== General Information =====
  * **Instructor:**  [[http://www.cpe.ku.ac.th/~jtf|Jittat Fakcharoenphol]]
  * **TA:** (TBA)
  * **Sections:**
    * 1 (cpe): W 9 - 12, Room 202
    * 450 (ske): Tu 9 -12, Room 204
  * **TA's office hours:** Fri 13 - 17, Room 806.
  * Textbook: [[http://www-math.mit.edu/~sipser/book.html|Sipser, Theory of Computation (2nd Edition), 2006.]]
  * Grading scheme: <del>2 midterm exams (25% each), 1 final exam (35%), homework (15%).</del>  2 big quizes (10% each), small quiz (5%), midterm (25%), final (35%), homework (15%)
===== Announcement =====
  * While waiting for the grades, you can watch this [[http://www.youtube.com/watch?v=cYw2ewoO6c4|LEGO Turing machine video at YouTube]].
  * **Homework deadline is over. No more homework will be accepted.**
  * **Homework 6, 7, and 8 should be submitted to the homework box.**
  * **BIG QUIZ is postponed to next week.**
  * Homework 6 due date is extended.  เลื่อนส่งการบ้าน 6 ไปพร้อมการบ้าน 7 (ที่จะประกาศเร็ว ๆ นี้)
  * [[theory of computation/midterm sect 1|คะแนนมิดเทอมหมู่ 1]], [[theory of computation/midterm sect 450|Midterm score section 450]]
  * **MAKE-UP**: Section 450, Sunday 18th Jan, 10:00-12:00.  Room 507.
  * **HOMEWORK SUBMISSION:** You can submit homework 5 with the TA and the lecturer on the following times and places
    * Jittat: 
      * Thursday 13:00 - 15:30 at IUP office at 4th floor building 10 (อาคารชูชาติกำภู)
      * Friday 13:00 - 16:00 at room 411 (or as announced on the door of room 411)
    * Eig and Champ: Thursday 16:05 - 18:00 at 806
  * [[theory_of_computation:homework5|Homework 5]] is out.  การบ้าน 5 ออกแล้ว.
  * **MIDTERM** will be on December 24th, 2008 from 16:00 to 19:00.  It'll be an open-note, open-book exam. For those who have conflict schedule, you will have to take the exam at 12:50 - 15:50; then someone will accompany you to the Law and Ethics examination room.
  * **การสอบกลางภาค** จะมีในวันที่ 24 ธันวาคม 2551 เวลา 16:00 - 19:00.  สามารถเปิดเอกสารและหนังสือได้.  สำหรับนิสิตสาขาวศ.ซอฟต์แวร์และความรู้ที่ตารางชนกับวิชากฎหมายจะสอบเวลา 12:50 - 15:50 ในห้องสอบที่จะประกาศต่อไป จากนั้นจะมีคนพาไปสอบวิชากฎหมายต่อไป
  * [[theory of computation/practice1|Practice 1]] for Big Quiz 1 is up.
  * **Midterm Announcement** The midterm will be moved to be according to the faculty schedule.  There'll be only 1 midterm now.  However, to reduce the load on the midterm, on Tuesday 16th and Wednesday 17th of December there'll be a 1-hour **BIG** quiz in class (worth 10%).   **Materials include 1.1, 1.2, and 1.3.** (You can think of it as a tiny midterm.)
  * **ประกาศเกี่ยวกับการสอบกลางภาค** การสอบกลางภาคเลื่อนไปสอบตามกำหนดเดิมของคณะ เหลือการสอบครั้งเดียว อย่างไรก็ตาม เพื่อลดภาระในการสอบมิดเทอม ในวันที่ 16 และ 17 จะมีการสอบเก็บคะแนนย่อย (คิดคะแนน 10% ใช้เวลา 1 ชั่วโมง) ในห้อง  **เนื้อหาคือ 1.1, 1.2, และ 1.3** (สามารถพิจารณาว่านี่เป็นมิดเทอมย่อยก็ได้)
  * **Homework Submission:** After homework 4 (starting homework 5), each student has to submit the homework **in person** with the instructor or the TA.  There'll be time slots allocated for homework submission and homework discussion.  Please wait for announcement. For now, you should submit homework 4 normally.
  * **การส่งการบ้าน:** หลังจากการบ้าน 4 (เริ่มการบ้าน 5) นิสิตแต่ละคนต้องส่งการบ้านโดยตรงกับอาจารย์ผู้สอนหรือนิสิตผู้ช่วยสอน สำหรับเวลาที่สามารถส่งได้ และเวลาสำหรับการปรึกษาการบ้านจะประกาศเร็ว ๆ นี้ สำหรับการบ้านปัจจุบัน (การบ้าน 4) ให้ส่งที่ช่องการบ้านตามปกติก่อน
  * **LATE HOMEWORK POLICY:**  This course allows submission of late homework.  However, there's some penalty.  You'll get 90% if you make a 1-week-late submission.  You'll get 70% for 2-week-late submissions.  After that you'll get at most 50% more than 1-week late.  At some point, the hard deadline maybe enforced (so that the TAs can do their work).
  * **นโยบายเกี่ยวกับการส่งการบ้านล่าช้า** คุณสามารถส่งการบ้านล่าช้าได้ โดยคุณจะโดนหักคะแนนเหลือ 90% ถ้าส่งช้า 1 อาทิตย์ เหลือ 70% ถ้าส่งช้ากว่านั้นแต่ไม่เกิน 2 อาทิตย์ ถ้าช้ากว่านั้นจะได้ 50%  นอกจากนี้ อาจมีการระบุเส้นตายสุดท้ายในการรับการส่งการบ้านด้วย เพื่อความสะดวกของผู้ช่วยสอนในการตรวจให้คะแนน
  * The due date for homework 1 changed to Friday 14th.
  * If you have problems doing homework, go to see your nice TA.  The TA's office hours are Friday 13 - 17 in Room 805.
  * Homework 1 is up.
  * The textbooks have not arrived on time.  KU Book will bring a few of them (I don't know how many) that have arrived to the department office on Monday.  The other lot of books will be arrived on next Friday (7 Nov).
  * No homework for the first week of class. Sorry.

===== Homework =====
//**LATE HOMEWORK POLICY:**  This course allows submission of late homework.  However, there's some penalty.  You'll get 90% if you make a 1-week-late submission.  You'll get 70% for 2-week-late submissions.  After that you'll get at most 50% more than 1-week late.  At some point, the hard deadline maybe enforced (so that the TAs can do their work).//

//**นโยบายเกี่ยวกับการส่งการบ้านล่าช้า** คุณสามารถส่งการบ้านล่าช้าได้ โดยคุณจะโดนหักคะแนนเหลือ 90% ถ้าส่งช้า 1 อาทิตย์ เหลือ 70% ถ้าส่งช้ากว่านั้นแต่ไม่เกิน 2 อาทิตย์ ถ้าช้ากว่านั้นจะได้ 50%  นอกจากนี้ อาจมีการระบุเส้นตายสุดท้ายในการรับการส่งการบ้านด้วย เพื่อความสะดวกของผู้ช่วยสอนในการตรวจให้คะแนน//

  * Homework 1 (due 14 Nov 08) | [[http://www.cpe.ku.ac.th/~jtf/204213/hw01.pdf|pdf]]
  * [[theory of computation/homework2|Homework 2]] (due 21 Nov 08)
  * [[theory of computation/homework3|Homework 3]] (due 28 Nov 08)
  * [[theory of computation/homework4|Homework 4]] (due 8 Dec 08)
  * [[theory of computation/practice1|Practice 1]] (for Big Quiz 1)
  * [[theory of computation/homework5|Homework 5]] (due <del>14</del> 15 Jan 09)  (deadline extended!)
    * See announcement for how to submit homework.
  * [[theory of computation/homework6|Homework 6]] <del>(due 29 Jan 09)</del> extended to Homework 7 due date.
  * [[theory of computation/homework7|Homework 7]] (due 17 Feb 09)
  * Homework 8.  Will be out 15 Feb.  Due 20 Feb.
===== Class schedule =====

  * Week 1. Introduction, review of mathematical background, introducing finite automata | [[http://www.cpe.ku.ac.th/~jtf/204213/lect01_intro.pdf|slides]] | [[http://www.cpe.ku.ac.th/~jtf/204213/video-oct29.html|video]]
    * Download video: [[http://www.cpe.ku.ac.th/~jtf/204213/video/oct29-1.flv|part 1]] | [[http://www.cpe.ku.ac.th/~jtf/204213/video/oct29-2.flv|2]] | [[http://www.cpe.ku.ac.th/~jtf/204213/video/oct29-3.flv|3]] | [[http://www.cpe.ku.ac.th/~jtf/204213/video/oct29-4.flv|4]] | [[http://www.cpe.ku.ac.th/~jtf/204213/video/oct29-5.flv|5]]

  * Week 2. Finite automata | [[http://www.cpe.ku.ac.th/~jtf/204213/lect02_dfa.pdf|slides]] | [[http://www.cpe.ku.ac.th/~jtf/204213/video-nov05.html|video]]
    * Simulator: [[http://ozark.hendrix.edu/~burch/proj/autosim/index.html|Automaton Simulator]]
    * Download video: [[http://www.cpe.ku.ac.th/~jtf/204213/video/nov05-1.flv|part 1]] | [[http://www.cpe.ku.ac.th/~jtf/204213/video/nov05-2.flv|2]]

  * Week 3. Nondeterminism, equivalence of NFA and DFA, regular expressions, equivalence between regular expressions and finite automata (1st part) | [[http://www.cpe.ku.ac.th/~jtf/204213/lect03_nfaregex.pdf|slides]] | [[http://www.cpe.ku.ac.th/~jtf/204213/video-nov12.html|video]]
    * Download video: [[http://www.cpe.ku.ac.th/~jtf/204213/video/nov12-1.flv|part 1]] | [[http://www.cpe.ku.ac.th/~jtf/204213/video/nov12-2.flv|2]] | [[http://www.cpe.ku.ac.th/~jtf/204213/video/nov12-3.flv|3]] | [[http://www.cpe.ku.ac.th/~jtf/204213/video/nov12-4.flv|4]]

  * Week 4. Equivalence between regular expressions and finite automata (2nd part), non-regular languages (pumping lemma), examples of applications | [[http://www.cpe.ku.ac.th/~jtf/204213/lect04_regexeq_pumping.pdf|slides]] | [[http://www.cpe.ku.ac.th/~jtf/204213/video-nov19.html|video]] (with download links)

  * Week 5. Context-free grammars, push-down automata.  | [[http://www.cpe.ku.ac.th/~jtf/204213/lect05.pdf|slides]] | [[http://www.cpe.ku.ac.th/~jtf/204213/video-nov26.html|video]] (with download links)

  * Week 6. Chomsky normal form, equivalence between languages described by CFGs and languages recognized by PDAs, pumping lemma for CFL. | [[http://www.cpe.ku.ac.th/~jtf/204213/lect06.pdf|slides]] | [[http://www.cpe.ku.ac.th/webcast/20081220/204213-3-2551|video]]

  * Week 7. Quiz 1.  Proof of pumping lemma.  Finish equivalence between CFGs and PDAs.  Brief intro to Turing machines  | [[http://www.cpe.ku.ac.th/~jtf/204213/lect07.pdf|slides]] | [[http://www.cpe.ku.ac.th/webcast/20081217/204213-17-2551|video]]

  * Week 8. Intro to Turing machines.  Variants of TM. | [[http://www.cpe.ku.ac.th/~jtf/204213/lect08.pdf|slides]] | [[http://www.cpe.ku.ac.th/webcast/20090112/204213-7-52|video]]

  * Week 9. Finish Turing machines. Decidability.  | [[http://www.cpe.ku.ac.th/~jtf/204213/lect09.pdf|slides]] | [[http://www.cpe.ku.ac.th/webcast/20090120/204213-14-52|video]]

  * Week 10. Finish decidability.  Reducibility (Part 1).  Applications 1 (or, how to do software verification even when the most basic question in software verification is undecidable).  Applications 2 (bioinformatics) | [[http://www.cpe.ku.ac.th/~jtf/204213/lect10.pdf|slides]] | [[http://www.cpe.ku.ac.th/webcast/20090124/204213-21-52|video]]

  * Week 11. Reducibility (Part 2).  Time complexity.  **SMALL QUIZ (5%) in class** | [[http://www.cpe.ku.ac.th/~jtf/204213/lect11.pdf|slides]] | [[http://www.cpe.ku.ac.th/webcast/20090129/204213-28-52|video]]

  * Week 12. Class P, Class NP.  NP-Completeness. | [[http://www.cpe.ku.ac.th/~jtf/204213/lect12.pdf|slides]] | [[http://www.cpe.ku.ac.th/webcast/20090220/204213-11-52|video]]

  * Week 13. NP-Completeness (cont.)  **BIG QUIZ (10%) in this week** | [[http://www.cpe.ku.ac.th/~jtf/204213/lect13.pdf|slides]] | [[http://www.cpe.ku.ac.th/webcast/20090220/204213-18-52|video]]

===== Links =====
  * [[http://www.eecs.berkeley.edu/~sseshia/172/|cs172]]: A similar course at UC Berkeley.
  * [[http://chanathip.ee.engr.tu.ac.th/courseware/index.php?action=course&course_id=11&course_page=home|CN314]]: A similar course at TU