CMPUT 474/570 -- FORMAL LANGUAGES, AUTOMATA AND COMPUTABILITY -- Winter 2007

DYNAMIC INFORMATION

•  Assignments
• Assignments are available here

•  Schedule
• Detailed Course Outline

• On line Notes
• I typically avoid these, but there may be  exceptions, check here.
• TA note on Assignment 7
  

Course Description

• Calendar Description (Copied from Bear Tracks Nov, 2006)
• Formal grammars; normal forms; relationship between grammars and automata; regular expressions; finite state machines; state minimization; pushdown automata; Turing machines; computability; the halting problem; introduction to recursive function theory. Prerequisite: CMPUT 325 and one of MATH 225, 228 or 229 or consent of Instructor..

Instructor, TA, Room

• Joseph Culberson
• Office Schedule
• Section B1: TTH 9:30-10:50 Mec 3 1
•  Teaching Assistants
• Please check with the TA indicated in the detailed course outline for assignment assistance and marking questions.
  
• Yi Cao 
• email: cao1@cs.ualberta.ca
• Office: Ath 113, Tues 2:00-3:00 pm
• Zhipeng Cai
• email: zhipeng@cs.ualberta.ca
• Office: Ath 143, Mon 2:00-3:00 pm
  

  Sources

• Required Textbook:
  • Introduction to the Theory of Computation , Michael Sipser, 2nd Edition  Thompson 2006
• Suggested Reading 
  • Fundamentals of the Theory of Computation Raymond Greenlaw and H. James Hoover
  • Introduction to Automata Theory, Languages and Computation John E. Hoprcroft, Rajeev Motwani and Jeffrey D. Ullman

Course Workload and Grading

• Distribution, Grading Information

  Assignments	10  worth  2% Each	20%
  Midterm	Feb. 15 In Class (70 minutes)	30%
  Final		50%


Final Exam Location TBA.

Deferred exam: Date May 10, 2007   



• As of September 2003, the University of Alberta is using a 4-point grading system. General information on this system can be found at http://www.grades.ualberta.ca .Final grades will be assigned in general accordance with the UofA grade distribution guidelines, with these caveats. Instructors will take into account the meaning of the letter grades given on the grades web site, when assigning a final letter grade to an overall term mark. In deciding the break point between each different letter grade (e.g., "A-" vs. "B+")an instructor will take into account the meaning of these grades and a student's entire term performance. There is no direct mapping between a final percentage mark and a letter grade (e.g., an 80% does not necessarily mean a B).
• One Excused Absence for an assignment may be granted if adequate reason is given. In this case the mark will be distributed over the remaining assignments. An excused absence on the midterm will be granted only with a sufficiently convincing doctor's note. The weight will be adjusted to the final exam.
  
• The University of Alberta is committed to the highest standards of academic integrity and honesty. Students are expected to be familiar with these standards regarding academic honesty and to uphold the policies of the University in this respect. Students are particularly urged to familiarize themselves with the provisions of the Code of Student Behaviour (online at www.ualberta.ca/secretariat/appeals.htm) and avoid any behaviour which could potentially result in suspicions of cheating, plagiarism, misrepresentation of facts and/or participation in an offence. Academic dishonesty is a serious offence and can result in suspension or expulsion from the University.
  
• Code of student behavior

Other Support

• Specialized Support and Disability Services (SSDS) 2-800 Students' Union Building, 492-3381 (phone) or 492-7269
• The UACS tutor registry.
• ACADEMIC SUPPORT CENTRE