CSci 311: Models of Computation (Automata Theory)
Fall Semester 1998
Syllabus

New Course Name

The title of the course CSCI 311 was changed from Automata Theory to Models of Computation during the summer of 1998.

Locations

The fall semester 1998 class meets in 352 Weir Hall at 2:30 p.m. to 3:45 p.m. on Tuesdays and Thursdays.

The class is taught by Prof. Conrad Cunningham, whose office is in 312 Weir Hall. The official office hours for this class are 1:30 to 3:00 p.m. on Mondays and Wednesdays, 1:00 to 2:30 p.m. on Tuesday, and by appointment at other times.

Prof. Cunningham's voice telephone number is (601) 232-5358 and fax number is (601) 232-5623. His WWW home page is http://www.cs.olemiss.edu/~hcc/ and his email address is cunningham@cs.olemiss.edu.

The WWW home page for this class is http://www.cs.olemiss.edu/~hcc/csci311/ and the anonymous FTP site is http://ftp.cs.olemiss.edu/pub/cunningham/csci311/98fall/ .

The final examination for this class is scheduled for 4:00 p.m. on Tuesday, 15 December.

Course Goals

This course gives students an introduction to the theoretical foundations of computer science, which include topics such as automata, formal languages, Turing machines, and computability. The course also examines how these theoretical topics are closely associated with practical issues such as compiler construction and programming language design.

New Course Description for 1999 Catalog

Introduction to the theoretical foundations of computer science, including automata and formal languages. (3 hours)

New Prerequisites for 1999 Catalog

Successful completion of CSCI 112 and MATH 301.

Source Materials

Required textbook:

Peter Linz. An Introduction to Formal Languages and Automata, Second Edition, Jones and Bartlett Publishers, 1997. ISBN: 0-7637-0296-X.

Readings:

Various journal, conference, or WWW materials as appropriate.

Software:

This will be determined as the semester progresses. It is not anticipated that any special commercial software will need to be purchased by the student.

Course Topics

1. Introduction (.5 week)
2. Finite automata (2 weeks)
3. Regular languages (1.5 weeks)
4. Properties of regular languages (1 week)
5. Context-free languages (2 weeks)
6. Normal forms (1.5 weeks)
7. Pushdown automata (1 week)
8. Properties of context-free languages (1 week)
9. Turing machines (2 weeks)
10. Languages (.5 week)
11. Computability (1 week)
12. Exams (1 week)

Professional Conduct

All students in CSCI 311 are expected to conduct themselves in a professional manner according to the Honor Code of the School of Engineering, the Information Technology Appropriate Use Policy, the M Book, and any other relevant policies.

"The Honor Code shall apply to all students, both undergraduate and graduate, registered in and/or seeking degrees through the School of Engineering. The Honor Code shall be understood to apply to all academic areas of the School such as examinations, quizzes, laboratory reports, themes, computer programs, homework, and other possible assignments. Only that work explicitly identified by the class instructor not to be under the Honor Code is excluded. The intent of the Honor Code is to recognize professional conduct and, thus, it shall be deemed a violation of the Honor Code to knowingly deceive, copy, paraphrase, or otherwise misrepresent your work in a manner inconsistent with professional conduct."

Grading

The grading scale for this class is A [90..100], B [80..90), C [70..80), D [60..70), and F [0..60).

Credit toward the semester grade will be allocated to each of the components as follows:

Assignments

• All students are expected to study the relevant portions of the textbook and handouts in conjunction with our class discussions (i.e., before coming to class). Explicit reading assignments will not always be given.

• Approximately ten homework assignments are planned for the semester.

• Most of the assignments will consist of problem-solving exercises similar to those in the textbook.

• Some of the assignments may consist of programming exercises or laboratory exercises using computer-based tools.

• Unless otherwise stated in the assignment description, an assignment is to be carried out by each individual student without inappropriate collaboration with others. The School of Engineering Honor Code and other relevant policies apply.

• In preparing and submitting assignment papers make sure that:
  • your name, the course number or name, the assignment number, and individual exercises are clearly marked on the paper.
  • you write legibly on only one side of the paper in a black or blue pen or dark pencil. (Do NOT use red or green ink!)
  • your paper is stapled together in the upper left corner.
  • you include a signed copy of the following Honor Code statement:

             In keeping with the Honor Code of the School of Engineering, I 
    affirm that I have neither given nor received assistance in preparing
    this assignment.
                                      
    Signature:___________________________________ 
    

• All students are expected to complete their homework assignments by their due dates. If an assignment is submitted late, a penalty of 10 percent of that assignment's grade will be assessed for each day it is late. A homework paper will not be accepted after graded papers have been returned, after a solution has been distributed, or after the final examination.

Quizzes

From time to time during the semester, short in-class quizzes will be given. The quizzes will cover the basic terminology and concepts in the material being discussed and/or problems similar to homework exercises.

Examinations

• There will be two regular examinations and a final examination.

• The first regular examination will be given in mid-September, the second in late October. The second exam will focus primarily on the material covered since the first examination.

• The final examination will be given during the scheduled final exam period. It is a comprehensive examination over the entire semester.

• Each exam may consist of a combination of in-class and take-home components.

• If you cannot take an examination at the scheduled time because of an illness or other special circumstances, please notify Prof. Cunningham in advance. Without advance notification, it may not be possible to give a make-up examination.

• Please do not ask to take the final examination earlier than the time set for the entire class.

[ CSci 311 Home ]
[ Cunningham's Home | Teaching ]
[ Department's Home | Courses | Undergraduate Courses | Graduate Courses ]