COMP272 THEORY OF COMPUTATION
Spring 2010

Chiew-Lan TAI , Room 3515, Tel 2358-7020, Email taicl@cse.ust.hk

Lectures Tutorials Assignments Marks

Annoucements

  • Tutorials will start on Friday, February 12.
  • Midterm I: 6-8pm, Thursday, March 11 (Venue: TBA)
    Midterm II: 6-8pm, Thursday, April 22 (Venue: TBA)
    Please let me know by February 12 if you have time conflict.
  • Solutions to selected problems in the question banks will be distributed. However, solutions to assignments and the midterm will NOT be distributed; instead, the TA will discuss selected problems during tutorial. You can also approach the TA for the answers if you miss the tutorial class.
  • The midterms and final exam will be open-book. You may bring in the lecture notes and textbook.

    Objectives

    Warning: This is a very rigorous mathematical course with emphasis on theorems and proofs. The materials for the last part of the course are especially difficult for most students. So you are strongly advised to put in your best efforts right from the beginning of the course so as to gain maximum marks in the earlier assessments.

    Textbook
    Elements of the Theory of Computation, Second Edition, by Harry R. Lewis and Christos H. Papadimitriou, Prentice-Hall International Inc. [Errata]

    Further readings

    Theory of Computing: A Gentle Introduction, by Efim Kinber, Carl Smith, Prentice Hall.
    Introduction to the Theory of Computation,     Second Edition, by Michael Sipser, PWS Publishing Company. [Errata]
    Introduction to Automata Theory, Languages, and Computation. by John E. Hopcroft and Jeffrey D. Ullman, Addison-Wesley, 2001.

    Assessment
    Your final grade will be based on your scores in three assignments (5% each), two midterms (20% each) and one final exam (45%).

    Absence from these examinations strictly requires prior approval granted by the instructor, or physician's documentation supporting unfavorable medical condition on the day of the examination.

    Question Banks
    We will be distributing exercises that you may complete. The exercises are purely for your benefit; doing the exercises will help you understand the material taught in class and prepare for the exams. It is your choice as to whether to complete the exercises or not. If you do, you may hand them in to the instructor for "grading". Again, this is only for your benefit, so that you receive some indication as to how well you understand the material. The grades will not be recorded and will not count towards your final class grade. Finally, solutions of many of the exercises will be given in the tutorials.

    Lectures
    Days Time Room
    Mon, Wed 09:00-10:20 3412

    Tutorials

    Section Day Time Room TA
    1A Fri 10:30-11:20 3412 Youyi Zheng

    Contacts

    Name Office Email Office Hours
    TAI Chiew Lan Room 3515 taicl@ust.hk after class / by appointment
    Youyi ZHENG Room youyi@cse.ust.hk after tutorial / by appointment
    Ge LUO Room 4209 luoge@cse.ust.hk Mon 2:30-3:30pm / by appointment