204213: Theory of Computation

General Information

  • 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.
  • Grading scheme: 2 midterm exams (25% each), 1 final exam (35%), homework (15%). 2 big quizes (10% each), small quiz (5%), midterm (25%), final (35%), homework (15%)

Announcement

  • While waiting for the grades, you can watch this 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 (ที่จะประกาศเร็ว ๆ นี้)
  • 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
  • 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 ในห้องสอบที่จะประกาศต่อไป จากนั้นจะมีคนพาไปสอบวิชากฎหมายต่อไป
  • 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) | pdf
  • Homework 2 (due 21 Nov 08)
  • Homework 3 (due 28 Nov 08)
  • Homework 4 (due 8 Dec 08)
  • Practice 1 (for Big Quiz 1)
  • Homework 5 (due 14 15 Jan 09) (deadline extended!)
    • See announcement for how to submit homework.
  • Homework 6 (due 29 Jan 09) extended to Homework 7 due date.
  • 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 | slides | video
  • Week 3. Nondeterminism, equivalence of NFA and DFA, regular expressions, equivalence between regular expressions and finite automata (1st part) | slides | video
  • Week 4. Equivalence between regular expressions and finite automata (2nd part), non-regular languages (pumping lemma), examples of applications | slides | video (with download links)
  • Week 5. Context-free grammars, push-down automata. | slides | video (with download links)
  • Week 6. Chomsky normal form, equivalence between languages described by CFGs and languages recognized by PDAs, pumping lemma for CFL. | slides | video
  • Week 7. Quiz 1. Proof of pumping lemma. Finish equivalence between CFGs and PDAs. Brief intro to Turing machines | slides | video
  • Week 8. Intro to Turing machines. Variants of TM. | slides | video
  • Week 9. Finish Turing machines. Decidability. | slides | 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) | slides | video
  • Week 11. Reducibility (Part 2). Time complexity. SMALL QUIZ (5%) in class | slides | video
  • Week 12. Class P, Class NP. NP-Completeness. | slides | video
  • Week 13. NP-Completeness (cont.) BIG QUIZ (10%) in this week | slides | video

Links

  • cs172: A similar course at UC Berkeley.
  • CN314: A similar course at TU
theory_of_computation.txt · Last modified: 2009/03/09 08:51 by jittat
 
 
©2008 Another cool website by 80KV