|
Textbook: Michael Sipser
"Introduction to the Theory of Computation" 3rd Edition
Cengage, 2013
Other books of interest:
Harel, "Algorithmics", Addison Wesley,
--- for a broad overview of the abstract concepts of computer science with little mathematics
Garey and Johnson, "Computers and Intractability, a Guide to the Theory of NP-Completeness", Freeman
& Company
--- an excellent reference to NP-completeness and its practical ramifications
|
|
Read this document very carefully, as it defines what is required
to perform effectively in this class. You will be assumed
to have read and understood this syllabus: ignorance is not an excuse.
If later in the semester you realize for example, that you can't attend the final exam, this will be your fault
and no makeup exam will be supplied. Endeavor not to attempt
make yourself an exception.
Course content very approximately in temporal order: However some subjects may be approached non-linearly because
of natural cross connections in the material.
|
Mathematics from chapter zero of the text will be assumed
where necessary (via the prerequisite).
Sections of the book listed below should be read in conjunction with the class. As the class proceeds
it should be clear which sections have just been covered in order, and therefore which are about to be covered.
The course content is defined by the sections listed below.
Chapter 1
Finite automata and regular languages.
Chapter 2 excluding p.115-122
Context-free languages, grammars, pushdown automata.
Chapter 3
Turing machines and the formal definition of an algorithm.
Chapter 4
Decidability, and the Halting Problem.
Chapter 5
Reductions and unsolvable problems.
§6.1 The Recursion Theorem
§6.2
Decidability of Logical Theories.
Chapter 7
Time complexity and NP-completeness.
Chapter 8
Space complexity
§9.3 Circuit Complexity
§10.5
Parallel Computation
§10.6
Cryptography
|
|
Evaluation: The following
rules will be strictly enforced.
Evaluation will consist of assignments (7), a Midterm exam, and a Final
exam. Assignments are a vital part of the learning process:
persons who do not submit reasonable attempts at all seven assignments will receive an F for the course. Examinations are open
book and open notes.
Due dates for all assignments are strict: all homeworks must be received
by gradescope during the day they are due in order to receive
credit.
Grading is absolute (i.e. not on a curve). The overall grade will be based
upon: 8% for each homework, 6% for the midterm, and 30% for the final. In addition 8% of the course will
be recorded for scholastic conduct. Students who do not violate the scholastic conduct rules (see below) will receive
the full 8%. A minimum of 60% is necessary for an S or C- grade.
Grading will be as follows: 95.0% or above yields an A, 90.0% an A-, 85% = B+, 80% = B, 75% = B-, 70% =: C+, 65%
= C, 60% = C-, 55% = D+, 50% = D, and less than 50% yields an F. Percentages are not
rounded when using this scheme, because this would be tantamount to moving
all of the grade boundaries down by 0.5%.
If you have a question about grading, address it to the TAs
via Gradescope. Only if something wholely unreasonable has occurred will the
instructor intervene.
Furthermore, there is a
limit of 10 days from when an assignment's grade is posted online for grading problems to be dealt with. So check your grades online frequently.
Incompletes will in general not be given. An incomplete will be considered
only when a provably serious family or personal emergency arises during the end part of the course, proof is presented,
and the student has already completed all but a small portion of the work.
Make-up Exams will in general
not be given. Verify at the start of the semester that you can attend all exams at the stated dates and
times, and if you cannot do so, then withdraw from the course.
A make up exam will be considered only when a provably serious family or personal
emergency arises during the relevant part of the course, and proof is presented.
Scholastic conduct
must be acceptable.
Specifically, you must do your homeworks, and examinations yourself, on your
own. Read
these linked documents as a part of the syllabus. Do not search
for homework related information on the World Wide Web; we do this and will recognize any logical idiosyncrasies
from such answers that occur in your homework. Plagiarism in the widest
sense is forbidden. Generate your own solutions.
In the event of academic misconduct on your part the Office for Student Conduct & Academic Integrity
will be consulted to see if there's a record of a prior instance of academic misconduct. In all cases, OSCAI will be notified of the present misconduct, so
that future misconduct can be appropriately penalized.
Also the instructor will decide privately
if the misconduct in the present class is egregious
or not. Included in the egregious category of misconduct is any sort of plagiarism where the student does not understand
completely the material plagiarized.
However, any academic misconduct
is open to being decided to be egregious by the instructor.
If there was a prior instance of academic misconduct or if the present misconduct is egregious, the penalty given for academic misconduct by the
instructor is an F for the entire course. Note that OSCAI may independently decide in some cases to award an additional penalty, such as suspension
or even expulsion from the University.
Only in the case that there is no prior instance of academic misconduct and the instructor decides that the academic misconduct is not egregious will a lesser penalty
be possible. OSCAI will still be notified.
|
The instructor may at his discretion at any time give any student
a short oral quiz on a student's submitted answer to any homework question to determine whether the student understands
the text they have supplied. Failure to supply an adequate response will be deemed evidence for academic dishonesty
(plagiarism), which may lead to failing the course and disciplinary action from the university.
|
|