Time: MW 2:20pm to 3:35pm
Place: Horizon Parking Garage (519 N. Main St.), Room 210
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
Name: Meysam Shirdel Bilehsavar
E-mail: meysam at email dot sc dot edu
Office hours:
CSCE 211, 212, 350
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.
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.)
Students will be able to:
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.
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. Homework submissions are due by 11:30pm on the due date. Late homework submissions will not be accepted.
Team submissions of written homework 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 and reduced workload, but discipline is required to make sure you understand those answers submitted by other members of your team. This is purely optional. If you do form a team, then elect one member of the team to submit the homework, who must include all team member names on the submission. This applies to all written homeworks, but not the programming project, which must be done individually (see below).
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 some 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 direct code-sharing is allowed between or among students or anyone else except the instructor or the TA. You may, however, discuss issues and general approaches with others at a high level. Violations of this rule are considered violations of the Carolina Honor Code forbidding plagiarism (see "Code of Student Academic Responsibility" below).
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 24 (12th class period) |
2nd midterm | Wednesday Mar 26 (19th class period) |
Final | Monday May 5, 12:30pm - 3:00pm |
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:
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 |
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)
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.
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.
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.
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 Tuesday January 28, 2025 at 14:56:58 EST.