Instructor : Robert W. Robinson
Email : rwr at cs dot uga dot edu
Office : 423 Boyd GSRC
Office hours : Tuesday, Wednesday, and Thursday 12:30--1:30 and 2:15--3:15, & by appointment

• Lectures : 3:30--4:45 Tue., Thu. & 3:35--4:25 Wed., in room 208 Boyd
  
  
• Required Text : Languages and Machines : An Introduction to the Theory of Computer Science, 3rd edition, by Thomas A. Sudkamp, Addison-Wesley, 2006.
  
  
• Prerequisite : CSCI(MATH) 2610 Discrete Mathematics for Computer Science is a prerequisite course which is relied on frequently.
  
  
• Course Description : An introduction to the theory of formal languages and computation. Topics include finite automata, regular expressions, pushdown automata, context-free grammars, Turing machines, undecidability and time complexity. The theory provides a conceptual framework for the wealth of problems and algorithms which arise in computing, as well as many useful tools for solving specific problems and recognizing intractable problems.
  
  
• Course Homepage : The URL for the course homepage is http://www.cs.uga.edu/~rwr/cs2670.html. The readings, homework, announcements, corrections, hints, and other basic course information can be found there.
  
  
• Teaching Assistant : Rachel Harnishfeger
  Email: rachel dot harnishfeger at gmail dot com
  Office hours : 11:00--12:00 Monday in room 201 Boyd, and 1:30--2:30 Wednesday in room 307 Boyd.
  
  
• Grading :
  • Homework : 25% (assignments due most Thursdays at the start of class)
  • Midterm Tests : 45% (3 tests, each 15%; 9-17, 10-15, and 11-12)
  • Final Exam : 30% (12-16, 3:30--6:30 PM, 208 Boyd)
  
  Course assessment will be based on the following scale: if your final average is at least 85, you're guaranteed an A, if 81 an A-, if 76.5 a B+, if 72.5 a B, if 68.5 a B-, if 64 a C+, if 60 a C, if 57 a C-, and if 50 a D.
  
  
• Topics and their location in the text:
  • Chapter 1 ---- Proofs, Induction
  • Chapter 2 ---- Languages, Regular Expressions
  • Chapter 3 ---- Context-free Grammars
  • Chapter 4 ---- Chomsky Normal Form, Greibach Normal Form
  • Chapter 5 ---- Finite Automata
  • Chapter 6 ---- Properties of Regular Languages
  • Chapter 7 ---- Pushdown Automata and Context-free Languages
  • Chapter 18 -- Top-down and Bottom-up Parsing
  • Chapter 8 ---- Turing Machines
  • Chapter 9 ---- Turing Computable Functions
  • Chapter 10 -- Chomsky Hierarchy
  • Chapter 11 -- Decision Problems, Church-Turing Thesis
  • Chapter 12 -- Undecidability
  • Chapter 14 -- Time Complexity
  • Chapter 15 -- Tractability and Decision Problems
  • Chapter 16 -- NP-Complete Problems
  
  
• Policies: Attendance will not be taken but the class sessions are an integral part of the course. If you are absent it is your responsibility to find out what was covered in class and to catch up.

  Late homework may not be accepted, and if accepted will be subject to a 30% penalty. If you can't be in class to turn in a homework, notify the instructor before that homework is due to arrange an alternate time for you to turn in the homework.

  If you are going to be absent on the day of an examination, you must provide a University-approved excuse for your absence before the day of the examination.

• Deviations: The course syllabus is a general plan for the course; deviations announced to the class by the instructor may be necessary.

• Academic Honesty : The overall UGA policy applies. All academic work must meet the standards contained in "A Culture of Honesty". Students are responsible for informing themselves about those standards before performing any academic work. The link to more detailed information about academic honesty can be found at http://www.uga.edu/honesty/ahpd/procedures.html

  The Computer Science Department Honesty Policy also applies (see below).
  
  Students are encouraged to consult with the instructor whenever help is needed. In addition to the instructor's scheduled office hours, students can make appointments for other times. E-mail is often a convenient way to ask short questions or to make an appointment.
  

The Computer Science Department recognizes honesty and integrity as necessary to the academic function of the University. Therefore all students are reminded that the CS faculty requires compliance with the conduct regulations found in the University of Georgia Student Handbook. Academic honesty means that any work you submit is your own work.

Common forms of academic dishonesty which students should guard against are :

1. copying from another student's test paper or laboratory report, or allowing another student to copy from you;
2. fabricating data (computer, statistical) for an assignment;
3. helping another student to write a laboratory report or computer software code that the student will present as his own work, or accepting such help and presenting the work as your own;
4. turning in material from a public source such as a book or the Internet as your own work.
   

Three steps to help prevent academic dishonesty are :

1. Familiarize yourself with the regulations.
2. If you have any doubt about what constitutes academic dishonesty, ask your instructor or a staff member at the Office of Judicial Programs.
3. Refuse to assist students who want to cheat.
   

All faculty, staff and students are encouraged to report all suspected cases of academic dishonesty. All cases of suspected academic dishonesty (cheating) will be referred to the Office of Judicial Programs. Penalties imposed by the Office of Judicial Programs may include a failing grade in the course and a notation on the student's transcript. Repeated violations are punishable by expulsion from the University. For further information please refer to the UGA Code of Conduct, available at the URL below.
http://www.uga.edu/judicialprograms/2006-07%20Code%20of%20Conduct.pdf