Instructor	Steve Hedetniemi
Office	208 McAdams
Office Hours	MW 8:00-11:30am and MW 1:30-4:00pm
Class meets	TTh 8:00 - 9:15pm 415 Daniel or 3:30pm - 4:45pm 117C McAdams
Final Exam	Fri Dec 12 7:00pm - 9:30pm or Fri Dec 12 11:30am - 2:00pm
Phone	656-5858
E-mail	hedet@cs.clemson.edu

• Text (Optional)
  John Hopcroft, Rajeev Motwani and Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation, Second Edition, Addison-Wesley, 2001

   

• Class Attendance Policy
  Attendance is required and records will be kept. If you miss a class, you are responsible for knowing all information covered in class. In order to receive a grade of A for the course, it is necessary (*but not sufficient) that you attend at least 90% of the classes. Similarly, in order to receive a grade of B, it is necessary that you attend at least 80% of the classes. A 70% attendance is required in order that you qualify for a grade of C. If the instructor is more than 10 minutes late to class, you can assume that class has been cancelled for the day.

   

• Grade Distribution
  • Homework 25%
  • Mid-term Exam I 25%
  • Mid-term Exam II 25%
  • Final Exam 25%

  
  Extra credit work can also improve your homework grade, and in borderline cases can make the difference between one letter grade and the next.

   

• Course Objectives
  

  This course is designed to expose the student to most of the basic concepts, results and proof techniques in computation theory. This includes the study of finite state machines, pushdown automata, linear bounded automata and Turing machines and many other models of computation. Also included is the study of the formal language counterparts to these classes of machines, including regular languages, context-free, context- sensitive and phrase structure languages. Two fundamental questions are covered in this course: (i) what are the theoretical limits of computations that can be carried out by machines? and (ii) what do we mean by an algorithm?

   

• Course Content (selected topics from)
  • Chap 1 Automata: The Methods and the Madness
  • Chap 2 Finite Automata
  • Chap 3 Regular Expressions and Languages
  • Chap 4 Properties of Regular Languages
  • Chap 5 Context-Free Grammars and Languages
  • Chap 6 Pushdown Automata
  • Chap 7 Properties of Context-Free Languages
  • Chap 8 Introduction to Turing Machines
  • Chap 9 Undecidability
  • Chap 10 Intractable Problems

  
  

Academic Integrity Statement

"As members of the Clemson University community, we have inherited Thomas Green Clemson's vision of this institution as a "high seminary of learning." Fundamental to this vision is a mutual commitment to truthfulness, honor, and responsibility, without which we cannot earn the trust and respect of others. Furthermore, we recognize that academic dishonesty detracts from the value of a Clemson degree. Therefore, we shall not tolerate lying, cheating, or stealing in any form."

I. Academic Integrity Policy

A. Any breach of the principles outlined in the Academic Integrity Statement is considered an act of academic dishonesty.

B. Academic dishonesty is further defined as:


1. Giving, receiving, or using unauthorized aid on any academic work;
   
2. Plagiarism, which includes the copying of language, structure, or ideas of another and attributing the work to one's own efforts;
   
3. Attempts to copy, edit, or delete computer files that belong to another person or use of Computer Center account numbers that belong to another person without the permission of the file owner, account owner, or file number owner;
   
   
C. All academic work submitted for grading contains an implicit pledge and may contain, at the request of an instructor, an explicit pledge by the student that no unauthorized aid has been received.

D. It is the responsibility of every member of the Clemson University community to enforce the Academic Integrity Policy.

Policy on Cheating/Honor Code
All work handed in must reflect your own work. Duplicate homework and programs will not be accepted. Any such instances will result in an F for the assignment, and may result in an F for the course. Some joint work can be submitted with the permission of the instructor, but only if properly identified as joint work.

 

Return to homepage