Fall Semester 1999

Corrected Syllabus

The fall semester 1999 class meets in **351 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/ `
and the anonymous FTP site is
` ftp://ftp.cs.olemiss.edu/pub/cunningham/csci311/.`

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

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.

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.

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.

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

Successful completion of CSci 112 and Math 301.

- Required textbook:
- Peter Linz. An Introduction to Formal Languages and
Automata, Second Edition, Jones and Bartlett
Publishers, 1997. ISBN: 0-7637-0296-X.
Ole Miss Bookstore price: $65.35 new, $49.00 used.
Note: You might want to check one of the other bookstores in town (Rebel Bookstore or Campus Book Mart) or online at sites such as Borders, amazon.com, or Computer Literacy (fatbrain.com).

- 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.

- Introduction (.5 week)
- Finite automata (2 weeks)
- Regular languages (2 weeks)
- Context-free languages (2 weeks)
- Normal forms (1.5 weeks)
- Pushdown automata (1 week)
- Context-free languages (1 week)
- Turing machines (2 weeks)
- Languages (.5 week)
- Computability (1 week)
- Exams (1.5 weeks)

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:

- You may discuss
*ideas*for homework and programming assignments with your classmates. However, you**cannot**collaborate on writing the solution or the program code. That is, you can*talk*about the problems and ideas for solving them, but you cannot write things down with anyone else. You are, of course, prohibited from copying or seeing another student's written solution, and you are not allowed to show your work to anyone else. -
**You should accept help with care.**If you work too closely with another student, you might mislead yourself into believing that you understand the concepts and techniques better than you actually do. Don't forget that the instructor has office hours and can probably give you hints or suggestions to get you started. -
**You should give help with care.**Do not help anyone too much. When you have solved a problem, it is tempting to just tell other students how you solved it. Instead, try to allow them to come to the solution on their own. Maybe give them a hint to help them get "over a hump." Remember that helping someone too much will hurt them in the long term if they can't work through problems on the exams by themselves. So avoid the temptation to do so. If you can't help other students without giving away the whole solution, direct them to see the instructor (who may or may not have a way to "edge" them toward the solution). -
**You are not obligated to help anyone.**If you feel uncomfortable helping another student for any reason, please direct them to see the instructor. -
**Except as described above, all work in this class is covered by the School of Engineering's Honor Code statement on plagiarism.**It is plagiarism "to knowingly deceive, copy, paraphrase, or otherwise misrepresent your work in a manner inconsistent with professional conduct".

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/Quizzes | 40% |

Exams (2) | 40% |

Final Exam | 20% |

- 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 eight homework assignments are planned for the
semester.
- Several of the assignments will consist of problem-solving
homework exercises similar to exercises given in the textbook. In
preparing and submitting these homework 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.

- A few of the assignments may consist of programming exercises
or laboratory exercises using computer-based tools. For these
exercises, you will need to submit a listing of your program code,
documentation, and appropriate printed output from your program
testing. Make sure that you clearly label the assignment as described
above. You will also be asked to submit your program source code in
electronic form using EASE, the Electronic
Assignment Submission Environment.
- 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. - 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 | Current Courses ]**

**[ Department's Home | Courses | Graduate Courses | Undergraduate Courses ]**

Send any comments or suggestions to Prof. Conrad Cunningham, cunningham@cs.olemiss.edu.

Copyright © 1999, H. Conrad Cunningham

Last modified: Thu Aug 19 18:19:32 1999 - There will be two regular examinations and a final examination.