CSci 311: Models of Computation
Fall Semester 2000
Syllabus


Locations

The fall semester 2000 class meets in 352 Weir Hall at 11:00 to 12:00 noon on Mondays, Wednesdays, and Fridays.

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 p.m. until 3:30 p.m. on Tuesdays and Thursdays and by appointment at other times.

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

The WWW home page for this class is http://www.cs.olemiss.edu/~hcc/csci311/.

The final examination for this class is scheduled for 8:00 a.m. on Wednesday, 13 December.


Course Revision

The Department changed the title of the course CSci 311 from Automata Theory to Models of Computation during the summer of 1998. The Department also updated the course description and prerequisites at that time.


Graduate Students

Computer science graduate students in conditional, qualifying, or nondegree standing should be enrolled in CSci 500, Fundamental Concepts in Computing, instead of CSci 311. CSci 500 is a transition course designed for students with undergraduate degrees in related fields who wish to study computer science at the graduate level but who have insufficient background in automata theory, formal languages, or other foundational topics. Enrollment in this courses See your academic advisor for more information.

Graduate students in other fields should not be enrolled in this class without the explicit permission of their home department. Any students in this category are expected to provide the instructor with a note from their advisor or department chair indicating such permission.


Student Disabilities Services Statement

"It is the responsibility of any student with a disability who requests a reasonable accommodation to contact the Office of Disability Services (915-7128). Contact will then be made by that office through the student to the instructor of this class. The instructor will then be happy to work with the student so that a reasonable accommodation of any disability can be made."


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.


Course Description from Catalog

Introduction to the theoretical foundations of computer science, including automata and formal languages.


Prerequisites

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 (2 weeks)
  4. Context-free languages (2 weeks)
  5. Normal forms (1.5 weeks)
  6. Pushdown automata (1 week)
  7. Context-free languages (1 week)
  8. Turing machines (2 weeks)
  9. Languages (.5 week)
  10. Computability (1 week)
  11. Exams (1.5 weeks)


Professional Conduct

As a student in CSci 311, you are expected to conduct yourself 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.

Limited Collaboration Policy. Unless otherwise indicated, any homework assignment or programming exercise given in this class will be an individual assignment. The work you submit is to reflect the knowledge, understanding, and skill that you have attained as an individual. However, the instructor does want to encourage the development of a community of scholars who are actively engaged in discussion of the ideas related to this course. With this in mind, you are allowed to discuss solutions of the homework and programming problems with other students if done so according to the following guidelines:


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 one-third
Regular Exams (4) four ninths
Final Exam two ninths


Assignments