Syllabus for CSCE 355
Foundations of Computation
Spring 2024

Time and Place

Time: MW 2:20pm to 3:35pm
Place: Davis College, Room 209

Class Homepage

Instructor

Stephen A. Fenner
Email: I use the CSE domain (cse DOT sc DOT edu) and my user name is fenner.
Web: https://cse.sc.edu/~fenner
Office: Storey Innovation Center, Room 2249
Office Hours: MW 1:00pm - 2:00pm or by appointment

Teaching Assistant

Name: Canyu Zhang
E-mail: canyu at email dot sc dot edu
Office hours: MW 10:00am - 12:00pm, Storey Innovation Ctr. Rm. 2242

Prerequisites

CSCE 211, 212, 350

Text

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

The 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 tools 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. (As a side benefit, much of the techniques learned in this course have practical, real-world applications in software.)

Course Outcomes

Students will be able to:

  1. Prove theorems in discrete math by induction, contradiction, or cases
  2. Analyze, design, and manipulate finite state acceptors
  3. Design and manipulate regular expressions
  4. Prove languages not regular or context-free
  5. Design and analyze context-free grammars and push-down automata
  6. Analyze and simulate a Turing machine
  7. Prove problems undecidable via reducibility

Important Note

The course conduct and rules given below may be subject to change on short notice during the semester, at my sole discretion. See "Provisions for Student-to-Instructor, Student-to-Student, and Student-to-Content Interactions," below for information in the case that the course switches to virtual mode during the semester.

Coursework and Grading

There will be regular written homework assignments, in total worth 10% of your grade. There will be two midterm exams, each worth 20% of your grade. Another 15% of your grade will consist of a programming project. The remaining 35% of your grade is a final exam.

Homework and Project

The written homework will be lightly graded; you will get credit if you demonstrate an earnest, reasonably intelligent approach to a problem, even if your answer is incorrect. The homework is meant primarily to prepare you for the exams. Late homework submissions will not be accepted.

Team homework submissions are accepted. You are encouraged to form a team of up to four (4) people for a single joint homework submission. Benefits include sharing ideas with other people, reduced workload, and faster feedback (due to less grading). This is purely optional. If you do form a team, then elect one member of the team to submit the homework, and be sure all your names are on the submission. This applies to all homeworks.

The programming project will be assigned during the second half of the course. You may use any programming language you want, provided it is supported on the machines in the department's Linux lab and can be invoked from the bash shell. These include C, C++, Java, and Python, among others.

Your project code will be run automatically (via a script) on one of the Linux lab machines, and your grade will be based on the outcome of running the script. Depending on the assignment, there may or may not be additional grading based on some combination of correctness, efficiency, and style. The grading criteria will be made clear in the project handout.

This is not a team project. Each student will submit her or his own project code, and no code-sharing is allowed between or among students.

Midterm Exams

Each midterm exam will be taken in person in the normal classroom (see above). All midterm exams will be closed book, closed notes, no electronic devices of any kind, EXCEPT you are allowed a single letter-sized sheet of paper with anything you want written or printed on it (both sides) during the exam. (The only possible exception to the no electronics rule is for legitimate use of e-devices by students with documented special needs and prior notice.) Violating these rules constitutes a violation of the Carolina Honor Code with all its requisite consequences, including a grade of F for the entire course (see "Code of Student Academic Responsibility" below). These exam-related rules may be subject to modification and clarification as the course proceeds.

Each midterm will be a number of questions or problems related to the preceding homework assignments. Answers to frequently asked questions about the exams may be posted on the class homepage.

Here is the schedule of exams. Both midterms will take place during the normal class time.

Exam Date
1st midterm Monday Feb 19 (12th class period)
2nd midterm Wednesday Mar 20 (19th class period)
Final Monday April 29, 12:30pm - 3:00pm

Final Exam

The final exam will be in the normal classroom and will follow the same rules as the midterm exams, except you are allowed 2.5 hours to take the exam and you will be allowed three (3) sheets of letter-size paper instead of one (1). Final exam questions will also be derived from the homework exercises, but more loosely. The final exam is cumulative, with emphasis on topics not adequately covered by the midterm exams.

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.

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

Provisions and Resources for Students with Disabilities

Students with disabilities should contact the Student Disability Resource Center. The contact information is below:

    1705 College Street, Close-Hipp Suite 102,
    Columbia, SC 29208
    Phone:803.777.6142     Fax: 803.777.6741
    Email: sasds@mailbox.sc.edu
    Web: https://sc.edu/about/offices_and_divisions/student_disability_resource_center/index.php


These services provide assistance with accessibility and other issues to help those with disabilities be more successful. Additionally, students should review the information on the Disabilities Services website and communicate with the professor during the first week of class. Other academic support resources may help students be more successful in the course as well.
    Library Services (http://www.sc.edu/study/libraries_and_collections)
    Writing Center (http://www.cas.sc.edu/write)
    Carolina Tech Zone (http://www.sc.edu/technology/techstudents.html)

Provisions for Student-to-Instructor, Student-to-Student, and Student-to-Content Interactions

These rules will apply in the event that, for any reason, the course modality switches to virtual instruction.

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

Nota bene: Some versions of the textbook, especially those sold internationally, have occasional discrepancies with the version sold in the bookstore here. This may include added or omitted exercises, changing the numbering of subsequent exercises. All exercise numbers in the homework are with respect to the bookstore version.

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, University-required quarantining or isolation due to COVID infection or exposure, 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 University's Honor Code and its Student Code of Conduct. (You can also see these and more at the Student Conduct and Academic Integrity website.)

You may not represent other people's work as your own. More specifically, you cannot submit specific answers or program code from other sources without proper attribution. If you copy or otherwise derive materials/answers/code 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. In the case of computer code, you are still in violation even if you modify the code after copying it without citation. It is also a violation of class policy to allow or otherwise make it possible for someone else copy your code, even if the copying does not occur in the semester in which you took the course.

(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 Honor Code, 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 general 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 (Time and date mentioned above.)


This page last updated Monday January 8, 2024 at 13:55:41 EST.