CSci 311: Models of Computation
CSci 500: Fundamental Concepts in Computing
Fall Semester 2015
Syllabus

Course Times and Places

Sections:

CSci 311-1: 235 Weir, Tuesday-Thursday, 9:30-10:45 a.m.

CSci 311-2: 235 Weir, Tuesday-Thursday, 8:00- 9:15 a.m.

CSci 500-1: 235 Weir, Tuesday-Thursday, 8:00- 9:15 a.m.

Final Exam (specific arrangements will be discussed the last week of classes):

CSci 311-1: Thursday, December 10, 8:00 a.m.

CSci 311-2: Tuesday, December 8, 8:00 a.m.

CSci 500-1: Tuesday, December 8, 8:00 a.m.

Home page: http://www.cs.olemiss.edu/~hcc/csci311/

Blackboard: Use for gradebook, submission of digital materials, and possibly other purposes

Course Staff

Instructor: Dr. H. Conrad Cunningham, Professor

Email: hcc@cs.olemiss.edu

Office: 211 Weir Hall -- 662-915-5358

Office hours: Mondays and Wednesdays 1:00-3:00 p.m. (or by arrangement at other times)

Teaching Assistant: Clay McLeod

Email: clmcleod@go.olemiss.edu

Office: 232 Weir Hall

Office hours: Tuesdays and Thursdays 9:00-1:00 p.m. (or 5:15-5:45 p.m. by arrangement)

Teaching Assistant: Eli Allen

Email: eeallen1@go.olemiss.edu

Office: 232 Weir Hall

Office hours: Mondays and Wednesdays 2:00-5:00 p.m. and Fridays 9:00-12:00 noon

Catalog Descriptions

CSci 311: Models of Computation

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

Corequisite: Math 301. Prerequisite: CSci 112 with a minimum grade of C-

CSci 500: Fundamental Concepts in Computing

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

Prerequisite: Graduate standing in computer science

Graduate Students

CSci 500 is a transition course designed for computer science graduate students with previous study 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. See your academic advisor for more information.

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

The homework assignments and other activities for CSci 500 students will have additional required components that are optional for CSci 311 students.

Course Outcomes

This course introduces students to the theoretical foundations of computing science and examines how these relate to practical concerns such as programming, programming language design, and compiler construction.

Upon successful completion of this course, the students:

1. can interpret and design automata that describe simple languages
2. know about regular expressions and their use in programming
3. can distinguish between regular and non-regular languages
4. understand grammars, parsing, and ambiguity
5. understand the Chomsky hierarchy
6. are aware of the limits of computation

Source Materials

Required textbook:

Peter Linz. An Introduction to Formal Languages and Automata, Fifth Edition, Jones and Bartlett Learning, 2012. ISBN: 978-1-4496-1552-9.

Software:

JFLAP, http://www.jflap.org

Course Topics

The instructor plans to cover the following topics, but the precise set of topics covered is subject to change as the semester progresses.

1. Introduction
2. Deterministic Finite Accepters (DFAs)
3. Nondeterministic Finite Accepters (NFAs)
4. Regular expressions
5. Regular grammars
6. Relationships among DFAs, NFAs, regular expressions, regular grammars, and regular languages
7. Closure properties of regular languages
8. Pumping lemma to identify nonregular languages
9. Context-free languages
10. Parsing and ambiguity
11. Nondeterministic pushdown automata
12. Turing machines
13. The Chomsky Hierarchy
14. Halting problem and undecidability

Campus Emergencies

The campus Emergency website http://emergency.olemiss.edu informs us about campus-related emergencies arising from weather or other circumstances. It helps us know what we should do in the event of an emergency. All should read the RebAlert text messages and emails and then respond accordingly. RebAlerts enable the University to communicate essential information to the campus community when a disaster occurs.

Class Attendance

The instructor expects all students to participate regularly by attending class; participating in classroom discussions, quizes, and examinations; and submitting homework assignments by their due dates. The instructor will track attendance using various measures. According to University policy (and Federal requirements), the instructor must verify that every student participates in the course during the first two weeks. Any student not participating during that period will be dropped from the course.

Student Disabilities Services

It is University policy to provide, on a flexible and individual basis, reasonable accommodations to students who have disabilities that may affect their ability to participate in course activities or meet course requirements. Students with disabilities are encouraged to contact their instructors to discuss their individual needs for accommodations.

Students should contact the Office of Student Disability Services (http://sds.olemiss.edu/) in 234 Martindale to inquire about the services available and how to request them. Students must submit an Instructor Notification of Classroom Accommodation form to each instructor before direct classroom accommodations will be provided. This must be done on a timely basis so that appropriate accommodations can be arranged.

Academic Misconduct Statement

The academic discipline policy of the University of Mississippi will be strictly followed in this course. Violation of the policy may result in anything from failure on an assignment to expulsion from the course, depending on the severity of the violation. The student should refer to the "M" book for general definitions of academic misconduct.

Grading

The grading scale for this class is A [90..100], B [80..90), C [70..80), D [60..70), and F [0..60). However, the instructor will be using the +/- grading scale, as appropriate, to provide more fine-grained grading within these ranges.

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

Assignments

• The course staff expects all students to study the relevant portions of the textbook and other assigned materials in conjunction with class discussions and activities (i.e., before coming to class). The instructor will not always give explicit reading assignments.
• The course staff plans approximately five homework assignments during the semester. These will be graded and used in calculating the semester grade.
• 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, course and section, assignment number, and individual exercises are clearly indicated 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 using Blackboard.
• 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.
• The course staff also plans to provide several self-tests. We will not collect or grade these, but students should use them in preparing for examinations and other activities.

Examinations

• There will be three regular examinations and a final examination. The lowest grade of the four will be dropped from the calculation of the semester grade.
• The regular examinations will be given approximately every four weeks throughout the semester. Each regular examination will primarily focus on the material covered since the previous examination. But, of course, the later concepts and methods build on the earlier material.

• 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. In some circumstances, it may not be possible to make up an exam. The final exam can substitute for the missed exam.
• Please do not ask to take the final examination earlier than the time set for the entire class.
• There will be one or more short quizes given during the semester. These grades will not be dropped. They will count no more than 10% of the semester grade (one-sixth of the exam grade).

UP to CSCI 311 root document? to CSCI 500?