CS 407 Computational Learning Theory
Course Syllabus -- Fall 1997

Instructor: C. Tamon
Office: SC369
Phone: x6521
email: tino@sun.mcs

Lecture Hours: M,W,F, 1:00p.m.

Office Hours: M,W 2:00-4:00 p.m. and F 2:00-3:00 (tentative)

Syllabus: This course is an introduction to computational learning theory. Computational learning theory is an area that studies machine learning problems from a mathematical perspective. Tentative topics that will be covered include basic learning models (Valiant's PAC model, Littlestone's online mistake-bound model, and Angluin's exact identification model), simple learning algorithms (learning k-DNF, WINNOW and weighted majority, closure algorithm, decision list), Occam's razor and the Vapnik-Chernovenkis dimension, cryptographic and complexity hardness of learning, boosting methods, and active learning of Finite Automata.


  • Cormen, Leiserson, and Rivest. Introduction to Algorithms. MIT Press, 1990.
  • Kearns, and Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994.
  • Solow. How to Read and Do Proofs. John Wiley and Sons, 1990.


  • Project/Presentation 30%
  • Tests (2) 30%
  • Assignments 40%

Policies: Refer to Clarkson Regulations 1997 for policies on Academic Integrity, Code of Ethics, Sanctions and other matters related to plagiarism.