2018 Fall - 304 - Foundations of Computer Science - Syllabus
This class is taught by Jay McCarthy. Call him Jay. Email him at first-name DOT last-name AT gmail DOT com.
We meet in Olsen 104 at TR 0930-1045.
Jay’s office hours are TR 1230-1400 in DAN 341.
There is a mailing list hosted at Google Groups.
Use it to ask non-revealing questions and receive answers, as well as
general course announcements. You are responsible for reading the
content of this mailing list.
1 Important Course Details
Description. A survey of the mathematical foundations of Computer
Science. Finite automata and regular languages. Stack Acceptors and
Context-Free Languages. Turing Machines, recursive and recursively
enumerable sets. Decidability. Complexity. This course involves no
computer programming.
Readings. (ITC) We’ll be using the book
Introduction to the
Theory of Computation (3rd Edition), by Michael
Sipser (Amazon
link). (If you need to use a different edition, there will be minor
differences, but the main content will be the same. You are
responsible for the differences.)
Policy. We do not allow electronic devices, such as
laptops, phones, and tablets, to be used during class, without an
explicit accomodation exception. I will first ask you to put it away
and then I will ask you to leave.
2 Lectures, Assignments, and Exercises
Day |
| Date |
| Topic |
| Notes | ||
1 |
| Thu |
| 09/06 |
| Preliminaries |
|
|
2 |
| Tue |
| 09/11 |
| Regular Languages: Finite Automata |
|
|
3 |
| Thu |
| 09/13 |
| (cont.) |
|
|
4 |
| Tue |
| 09/18 |
| Regular Languages: Nondeterminism |
|
|
5 |
| Thu |
| 09/20 |
| (cont.) |
|
|
6 |
| Tue |
| 09/25 |
| Regular Languages: Regular Expressions |
|
|
7 |
| Thu |
| 09/27 |
| (cont.) |
|
|
8 |
| Tue |
| 10/02 |
| Regular Languages: Nonregular Languages |
|
|
9 |
| Thu |
| 10/04 |
| (cont.) |
|
|
10 |
| Tue |
| 10/09 |
| Context-Free Languages: Context-Free Grammars |
|
|
| Thu |
| 10/11 |
| No class | |||
11 |
| Tue |
| 10/16 |
| Context-Free Languages: Pushdown Automata |
|
|
12 |
| Thu |
| 10/18 |
| (cont.) |
|
|
13 |
| Tue |
| 10/23 |
| Midterm Review |
| |
14 |
| Thu |
| 10/25 |
|
| ||
15 |
| Tue |
| 10/30 |
| Context-Free Languages: Non-Context-Free Languages |
|
|
16 |
| Thu |
| 11/01 |
| (cont.) |
|
|
17 |
| Tue |
| 11/06 |
| Church-Turing Thesis: Turing Machines |
|
|
18 |
| Thu |
| 11/08 |
| (cont.) |
|
|
19 |
| Tue |
| 11/13 |
| Church-Turing Thesis: Variants of Turing Machines |
|
|
20 |
| Thu |
| 11/15 |
| (cont.) |
|
|
21 |
| Tue |
| 11/20 |
| Church-Turing Thesis: Algorithm Definition |
|
|
| Thu |
| 11/22 |
| No class | |||
22 |
| Tue |
| 11/27 |
| Decidability: Decidable Languages |
|
|
23 |
| Thu |
| 11/29 |
| (cont.) |
|
|
24 |
| Tue |
| 12/04 |
| Decidability: Halting Problems |
|
|
25 |
| Thu |
| 12/06 |
| (cont.) |
|
|
26 |
| Tue |
| 12/11 |
| Reducibility: Undecidable Problems from Language Theory & Mapping Reducibility |
|
|
27 |
| Thu |
| 12/13 |
| Final Review |
|
|
Final |
| Wed |
| 12/19 |
|
|
| |
3 Work in this Course
If you do a little work for this course every day, including
reading the textbook and doing the exercises, you will find the exams
and papers easy to write. If you just search for answers in course
material as you try to complete work, you will not do well.
I highly recommend that you read
this
article about grading. I also recommend you read
this
article about the stress that you may experience in a computer
science program. Please try to make healthy productive choices in your
life. I would love the opportunity to help you in any ways I can.
3.1 Exercises
In the Lectures, Assignments, and Exercises table above, a number of exercises are referenced. You are not required to do each of them, but I highly recommend that you complete some of them. It is extremely difficult to do them all and I am intentionally vague on details, so you will maximize your learning rather than just satisfy an assignment spec. Required work (such as exams, papers, and presentations) may reference material from class, from the reading, or from these exercises. If you do not do the exercises, then, for example, there will be exam questions which will be unintelligible and nigh impossible for you to answer successfully. If you would like to discuss your solution to them, please meet me in my office. I will not review solutions via email, but I will answer clarifying questions.
3.2 Paper
Consult the paper details for details about
the content of the paper. This class may not actually have a paper
project.
I will not pre-grade your paper through email, but I can try to
discuss it with you, although it is most effective to discuss it with
you in my office.
You hand in your paper by putting them on the lectern at the
start of class on the day they are due. No papers will be accepted at
any other time, for any reason. No papers will be acceped
electronically. If you cannot turn in your work personally, you may
have a friend do it.
Your turn-in must clearly have your name on it and indicate
which option you chose.
Your turn-in must be prepared electronically. I recommend using
LaTeX. You must use 0.5"
margins, the font Times New Roman at 11pt, and single-spacing. Each
page must be numbered in the footer. You must print with black
ink (color may be used in diagrams, but not in the text) on white
paper. If your printer is low on ink or toner, find another one rather
than giving me something that is faded. I recommend using only mild
formatting. You should not include long quotes, code samples, or large
diagrams. You should reference sources using the BibTeX
alpha
style.
Your turn-in must be stapled together. It is your responsible to
ensure this is the case.
You may not turn in more than five pieces of paper. You probably
want to turn in exactly five pieces of paper. This means ten "pages"
of content, although since references count it may be more like nine.
Work that is incorrectly formatted will be returned ungraded and
I will consider it as though you never turned it in.
Your paper will receive a grade from the closed interval between
0 and 1. I will evaluate your paper based on the
veracity of its content, its logical structure, as well as its
grammar, style, and form.
3.3 Presentation
Consult the presentation details for details
about the content of the presentation. This class may not actually
have a presentation project.
I will not pre-grade your presentation through email, but I can
try to discuss it with you, although it is most effective to discuss
it with you in my office.
You must record yourself for fifteen minutes and email me a link
to the video. I highly recommend that you upload it as an unlisted
YouTube video and send me that link. It is the most convenient for
everyone. You must send this link to me before 5pm on the listed due
date. No presentations will be accepted at any other time, for any
reason. In extenuating circumstances, we can arrange an in-person
presentation.
Your email must have the subject: [CS304] Presentation turn-in. If it does not have this
subject, it will not be graded and I will treat it as though you did
not turn it in.
Your email must include a written list of the exercises you did,
with an annotation for which ones you are presenting about. This list
should not just include the names on the syllabus, but the particular
options for each exercise you choose.
I highly recommend that you use your operating
system’s screen-recording capability and use a simple presentation
mechanism, like a digital whiteboard. If you don’t how to get your OS
to record the screen, a cross-platform option is Google Hangsout on
Air. You can use it to record yourself, and your screen, and it can
automatically archive to YouTube. If you are presenting code, it makes
sense to present from within your editor and show the code working. In
any case, remember: the most important part of your presentation is
the words you say.
Your presentation should be designed like you are teaching a
class or having a conversation about something you deeply understand
with a friend. You should not use a script or have any substantial
notes. If you need notes, then write down ten (10) words that will
help prompt you and keep you on track.
It is possible to get extra-credit if you go above and beyond
the expectations and impress me. When you turn it in, clearly state
that you think you have done this so I can evaluate what you believe
is extra-credit-worthy.
Your presentation will receive a grade from the closed interval
between 0 and 1.25. I will evaluate your
presentation based on the veracity of its content, its logical
structure, as well as its style and form.
3.4 Exams
Exams must be taken in person, at the scheduled time.
Exams must be completed without any notes, books, or resources
of any kind.
You must use 8.5" by 11" College Ruled paper without
frill and write using a black pen. You are responsible for my ability
to read and understand your writing and diagrams.
Your exams must clearly have your name on it.
You may not hand in more than five pieces of paper and
individual answers must not use more than a single piece of
paper (front and back.) These pages must be stapled together, which
you are responsible for. I recommend pre-stapling your paper before
the exam.
Exams that are incorrectly formatted will be returned ungraded
and I will consider it as though you never turned it in.
Your exams will receive a grade from the closed interval between
0 and 1.25. I will evaluate your exam based on the
veracity of its content and the logical structure of your answers.
In your exam, you will be provided four groups of two
questions. You can answer one question from each group. After you
answer one question from each group, you may answer a single other
question (i.e. answering two questions for one group.) If you provide
answers for more than five questions or two for more than one group,
then I will return your exam ungraded as though you never turned it
in. Each question will be equally weighted at 0.25.
Nearly all exam questions are best answered using all of the
available space. If you can’t write more than a paragraph, then you
probably don’t really understand the question well enough to answer it
correctly.
3.5 Class Numeric Grade
This function takes your turn-ins and combines them into a numeric grade:
> (define (combine proj1 midterm proj2 final) (+ (* 0.2 proj1) (* 0.2 midterm) (* 0.3 proj2) (* 0.3 final)))
Examples:
> (combine 0.0 0.0 0.0 0.0) 0.0
> (combine 0.5 0.5 0.5 0.5) 0.5
> (combine 0.0 0.0 1.0 1.0) 0.6
> (combine 0.0 0.0 1.0 1.25) 0.675
> (combine 0.0 1.25 0.0 1.25) 0.625
> (combine 1.0 1.0 1.0 1.0) 1.0
> (combine 1.0 1.25 1.0 1.25) 1.125
This function is designed to allow you to perform poorly at the
beginning of the course, but still recover and end with a good grade.
3.6 Course Letter Grade
The following function to converts your numeric grade into a letter grade:
> (define (convert-to-letter ng) (cond [(> ng 0.93) "A"] [(> ng 0.9) "A-"] [(> ng 0.86) "B+"] [(> ng 0.83) "B"] [(> ng 0.8) "B-"] [(> ng 0.76) "C+"] [(> ng 0.73) "C"] [(> ng 0.7) "C-"] [(> ng 0.66) "D+"] [(> ng 0.6) "D"] [else "F"]))
Examples:
> (convert-to-letter 1) "A"
> (convert-to-letter 0.94) "A"
> (convert-to-letter 0.899999) "B+"
> (convert-to-letter 0.81) "B-"
> (convert-to-letter 0.74) "C"
> (convert-to-letter 0.6999999) "D+"
> (convert-to-letter 0.62) "D"
> (convert-to-letter 0.57) "F"
3.7 Graduate Student Option
If you are taking the class as a graduate class,
then you must do two projects between the midterm and final—
4 Help
My job is to help you.
One of the best ways for me to help you is to teach you how to
help yourself. The main way I will put this idea into practice is that
I will not answer your question until you have shown that you’ve read
the relevant part of the textbook and have a concrete question or
point of confusion about it.
If you need a "shallow" amount of help, then look at the
Google Group. First, see if I have already
answered your question. Then, send your own email.
Only send me personal email if you need to talk about something
private, such as your grades. Anything else is best discussed in
public, so others can benefit. If you do send personal email, put
[CS304] as a prefix in the subject.
If you need a "deep" amount of help, please come to my office or
call me (801-361-0732) and we’ll talk and try to resolve whatever ails
you.
5 Fine Print
In this course, all work is to be each
student’s own. Students should therefore be familiar with the
University’s rules on academic dishonesty, which can be found in the
Bulletin of Undergraduate Studies and in the Schedule of Classes. In
particular, plagiarism will not be tolerated! Any student caught
plagiarizing another’s work will automatically receive a grade of F
for the course. If you are unsure as to what constitutes plagiarism,
it is your responsibility to check with the instructor. Other forms of
dishonesty will result in similar actions. You may collaborate with
your classmates on the design and results of the programs you will
write in this course, but each student must implement these programs
alone. Submission of shared student code is not permissible, and will
result in a grade of F for the course. Help files are typically
provided for each programming assignment, and students are encouraged
to cut and paste useful code from these help files into their
assignment submissions, but all other code must be the specific work
of each student.
You are not allowed to post solution code
to problem sets assigned in this class in public places
(e.g. Github). This includes your own solutions as well as solutions
that may be provided by the instructors.
This policy is a courtesy to future
students, who — to the fullest extent possible — should have the
opportunity to struggle with the problems in the same way that you
do.
Non-compliance will be pursued rigorously per UMass
Lowell’s academic integrity policy.