Syllabus for CSCE 355
Foundations of Computation
Fall 2017

Time and Place

TR 11:40am to 12:55pm, 300 Main Street, B201.

Instructor

Stephen A. Fenner
Telephone: 803-777-2596 (only if I'm there; email is preferred)
Email: I use gmail (gmail.com) and my user name is fenner.sa
Web: http://www.cse.sc.edu/~fenner
Office: August to mid October: Swearingen 3A65; thenceforth: Horizon II, Room 2249; also via email
Office Hours: MW 2:00pm - 4:00pm or by appointment

Teaching Assistant

Name: Daniel Padé
Office: Swearingen 2D19 (until mid October)
Phone: 901-300-6878
E-mail: pade AT email DOT sc DOT edu
Office hours: MTW 11:00 - 12:00

Prerequisites

CSCE 211, 212, 350. MATH 374 is highly recommended.

Text

Required: J. E. Hopcroft, R. Motwani, J. D. Ullman, Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley-Pearson 2007.

The (somewhat outdated) official departmental syllabus for this course can be found HERE.

Overview

This course is a mathematical introduction to the basic concepts underlying all computation. The goal is to discover the fundamental abilities and limitations of computers and to use mathematical rigor to prove facts about computation. We will study abstract models of computation, such as finite automata, grammars, and Turing machines. We will also set up a formal framework for defining computational problems as formal languages with the goal of studying the ultimate limits of computation. The core topics learned in this course pop up repeatedly in many areas of computer science and have close connections with logic and the foundations of mathematics.

Coursework and Grading

There will be three midterm exams, each worth 15% of your grade. Another 15% of your grade will consist of a programming assignment. The remaining 40% of your grade is a final exam.

Each midterm exam will start at the beginning of class and last approximately 40 minutes, followed by a discussion of the answers. All midterm exams are closed book, closed notes, and no electronic devices allowed, except for legitimate use by students with documented special needs. Each midterm will be number of questions or problems sampled from the preceding homework assignments, possibly modified somewhat.

Here is the schedule of exams.

Exam Date
1st midterm Thursday 9/14
2nd midterm Tuesday 10/10
3rd midterm Tuesday 11/7
final Thursday 12/14 (12:30 - 3:00)

The final exam is 2.5 hours on Thursday December 14, from 12:30pm to 3:00pm. It is open book, open notes, but no electronic devices of any kind except for legitimate use by students with documented special needs. Final exam questions will also be derived from the homework exercises, but more loosely.

PLEASE NOTE:

  1. This course will go by quickly. The subject matter is cummulative and requires time and effort to digest, and so it is vital that you keep up with the homework and reading.
  2. The course is mathematical in nature. The third most important indicator of success in this course (second to hard work and internal motivation) is a certain level of "mathematical maturity," that is, being able to: (a) understand mathematical definitions and theorems, (b) verify proofs, (c) solve mathematical problems, and (d) in simple cases, generate one's own definitions, theorems, and proofs.

The homework problems are intended as a pool for exam questions and as timely feedback for you. They will not be graded.

Letter grades correspond to score percentages as follows:

A 90 or above
B+ at least 86 and less than 90
B at least 80 and less than 86
C+ at least 76 and less than 80
C at least 70 and less than 76
D+ at least 66 and less than 70
D at least 60 and less than 66
F less than 60

Class Policies

Reading and Lectures

You (the student) are expected to read all assigned material before the lecture begins. If for some reason you cannot attend class, you are responsible for any material covered during your absence.

The textbook coordinates with a set of on-line resources (Gradiance). I will neither require nor assume you to have access to these resources. I encourage it if you'd like some extra insight, but it's purely optional. (My rationale for not requiring it is this: it appears that to access Gradiance you need to purchase a new, unused copy of the text.)

Exams

No make-up exams will be given except under extreme circumstances with a valid excuse, in which case you must give me notice well before the exam if at all possible. Valid excuses include grave illness or death in the immediate family, or other similarly dire emergency. They do not include car problems or non-emergency events (weddings, trips, sports meets, etc.). Before proceeding with the course make sure that you can attend all the exams.

Code of Student Academic Responsibility

You are expected to know the Academic Code of Responsibility as it appears in the Carolina Community: Student Policy Manual.

You may not represent other people's work as your own. More specifically, you cannot submit specific answers from other sources without proper attribution. If you copy or otherwise derive materials/answers from other people, books, the web, etc., you must cite your source(s) in a way that adheres to the usual standards for an academic paper. Deriving or copying without proper attribution is plagiarism, which I regard as a serious offense. (Exceptions: You do not need to explicitly cite any material you lift from the course's textbook or from my own lectures or lecture notes. You are also not required to explicitly cite any general background material you use for an answer but which does not specifically relate to the actual question being answered.)

Obtaining answers during an exam other than by the approved means (your own printed material, knowledge, and cleverness) is forbidden. Passing along questions or answers to an exam to anyone else before the exam is given is also forbidden.

Any violation of the rules above constitutes cheating, for which there is no excuse.

THE USUAL PENALTY FOR CHEATING IS FAILURE OF THE COURSE. The offense will also be reported to the USC OFfice of Academic Integrity. The bare minimum penalty you may receive for an instance of cheating is double the points of the assignment off. That means that if an assignment/test is worth 10 points, your ultimate grade would be -20 for the assignment/test. Finally, as noted in the Student Policy Manual, the maximum penalty for cheating on an assignment is expulsion from the University. These penalties apply both to copier and copiee.

Go HERE for more information about the Honor Code and class policies.

Schedule of Lectures

Course topics by chapter are given below. Any topics in brackets "[ ]" do not correspond to current sections in the book. This schedule is flexible and is subject to some revision as the class proceeds. There may not be time to cover all the topics listed. You will be tested only on those topics that could be covered in class, which means that the content of the exams may be adjusted.

Topic(s) Chapter Week(s)
Introduction: mathematical preliminaries, definitions, theorems, proofs, automata concepts: alphabets, strings, and languages 1 1 - 2
Deterministic finite automata 2.1 - 2.2 3
Nondeterministic finite automata, regular expressions 2.3, 2.5 4
Regular expressions (cont.), regular languages, equivalence to automata 3.1 - 3.3 5
Proving languages nonregular: pumping lemma 4.1 - 4.2 6
Minimization of automata 4.4 7
Context-free grammars and languages, parse trees 5.1 - 5.4 8 - 9
Pushdown automata, equivalence to grammars 6.1 - 6.3 10
Normal forms of CFGs, pumping lemma for CFLs 7.1 - 7.2 11
Turing machines, notion of "algorithm" 8 12 - 13
Undecidability and intractability 9 - 10 14
Final Exam (cummulative, but emphasizing material not tested on the midterms) all 12:30pm on 12/14


This page last updated Monday September 11, 2017 at 13:42:33 EDT.