CSci 500: Fundamental Concepts of Computing
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.

Transition Course for Graduate Students

CSci 500, Fundamental Concepts in Computing, 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 an insufficient background in automata theory, formal languages, or other foundational topics. Enrollment in this courses is limited to computer science graduate students who have been admitted in conditional, qualifying, or nondegree standing. Qualifying and nondegree students must have the permission of both the Department and the Graduate School to enroll. Credit for this course cannot be applied to MS or PhD degrees in computer science.

Graduate students in other fields cannot enroll in this class.

Undergraduate students should enroll in CSci 311, Models of Computation, instead of CSci 500. CSci 500 is restricted to graduate students.

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

An intensive study of the formal concepts needed for graduate study in computer science. CSci graduate students only.

Prerequisites

Consent of the instructor.

All students in this class expected to have successfully completed (1) an undergraduate degree in some field related to computer science, (2) an introductory sequence in programming and data structures similar to CSci 111 and 112, and (3) sufficient mathematics courses to handle the formal concepts in this class (e.g., Math 261 and 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 500, 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. Similarly, you are not allowed to copy text or program code from a book or a page on the Web unless explicitly authorized to do so by the instructor.

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