Foundations of Computer Science
Lecturer:
Prof. Daniel R. Schlegel, 395 Shineman Center, daniel.schlegel@oswego.edu
Office/Lab hours: M 4-5pm; W 7-8am; Th 11:30-12:30; or by appointment
Section 800: MWF 12:40-1:35pm, Shineman 174
Course Description:
This course will provide students with a broad perspective of computer science and will acquaint them with various formal systems on which modern computer science is based. Students will be instructed in the basics of theoretical computer science, with an emphasis on application of the theory in various subdomains of computer science. The course will cover fundamental topics such as finite state machines, regular and context-free languages, Turing machines, and computational complexity.
Course Objectives:
To convert logical statements from informal language to propositional and predicate logic expressions
To apply formal logic to model and analyze the correctness of software constructions
To inductively prove properties of recursively defined functions
To use sets, functions, and relations to model software problems and solutions
To design a finite state machine to accept a specified language
To transform a non-deterministic machine to a deterministic one
To design a regular expression to represent a specified language
To design a context-free grammar to represent a small expression language
To recognize uncomputable problems that have no algorithmic solution
Textbooks:
Critchlow, Carol, and David Eck. “Foundations of Computation.”, v.2.3.1 (2011). Available at: http://math.hws.edu/FoundationsOfComputation/
Lehman, Eric, F Thomson Leighton, and Albert R Meyer. “Mathematics for Computer Science”, v.6.6.2018 (2018). Available at: https://courses.csail.mit.edu/6.042/spring18/mcs.pdf
Useful Resources:
Useful symbols to know
Be-Fitched (Fitch-style proof strategies) @ Stanford
Attendance Policy and Classroom Etiquette:
As per college policy, attendance in all sessions is obligatory. If you cannot attend a class meeting due to religious, athletic, health related circumstance, or circumstance of particular hardship, please notify me in advance via email. Please be ready to present proof, if necessary. Cell phones shouldn’t be used during lecture, and laptops should only be used for taking notes (I don’t recommend this). If use of any electronics becomes districting to other students I reserve the right to discontinue the allowance of their use.
Assignments:
All assignments will be completed alone, though discussion of general approaches with classmates is encouraged. During the semester there will be roughly 8 assignments. Submission will be via Blackboard or hard copy in class, depending on the assignment.
You will have 7 days to use throughout the semester to submit late work. A maximum of 3 days may be used on any one assignment. We will say that a span of days where the university is closed will count only as one day. Therefore if an assignment is due on a Friday, it may be submitted Saturday or Sunday using only one late day. A submission on Monday will use two, and so on. Outside of this late policy, no late assignments will be accepted.
Grading:
It is expected that each person participate during each class. As discussed before, attendance is required. Each assignment task will be assigned a point value (generally some multiple of 3 depending on difficulty), where the following scheme will be used in grading it:
0 – Did not attempt / No serious attempt
1 – Mostly incorrect solution
2 – Somewhat incorrect solution
3 – Perfect solution
If the problem is a multiple of 3, then intermediate scores will be given as appropriate. The total points received on all assignments will then be summed and divided by the points possible and scaled as appropriate according to the percentages given below. Exams will be graded in the same way as the assignments.
| Assignments | 50% |
| Midterm Exam | 20% |
| Final Exam | 30% |
The default grading for the course will be along the university’s standard grading curve:
| A: 93-100 | C+: 77-79 |
| A-: 90-92 | C: 73-76 |
| B+: 87-89 | C-: 70-72 |
| B: 83-86 | D+: 67-69 |
| B-: 80-82 | D: 60-66 |
| E: 0-59 |
A more generous curve may be used, but should not be expected.
Schedule/Outline:
During the semester we will aim to cover the following topics, with the course generally split into two parts.
Part 1
Formal Logic
Mathematical Structures (Sets, Sequences, Functions, Relations…)
Induction and Recursion
Part 2
Formal Languages and Grammars
Finite State Machines
Computability
This syllabus and the course schedule are subject to change by the instructor. All changes and related justification will be announced in class, and updates will be reflected in this web version. Lecture slides/notes will be maintained on Blackboard.
| Week | Day | Date | |
|---|---|---|---|
| 1 | Monday | 8/27 | First day of class Syllabus, Overview Readings: Suppes, Introduction to Logic Chapter 1 (on Blackboard) Be sure to answer office hours survey! |
| Wednesday | 8/29 | Introduction to Formal Logic Syntax of Propositional Logic |
|
| Friday | 8/31 | Propositional Logic Semantics Reading: Peter Suber's Translation Tips (propositional logic section) |
|
| 2 | Monday | 9/3 | No Class - Labor Day |
| Wednesday | 9/5 | Brief presentation by Women in Computing Truth Tables Assignment 1 due 9/14 in class |
|
| Thursday | 9/6 | Add Deadline | |
| Friday | 9/7 | Boolean Arithmetic, Circuits |
|
| 3 | Monday | 9/10 | No Class - Rosh Hashanah |
| Wednesday | 9/12 | Truth Table Arguments Natural Deduction |
|
| Friday | 9/14 | Natural Deduction continued Propositional Logic Reference Sheet added to Blackboard Assignment 2 due 9/24 in class, submit .java file on Blackboard |
|
| 4 | Monday | 9/17 | Proof by Contradiction |
| Wednesday | 9/19 | No Class - Yom Kippur | |
| Thursday | 9/20 | Drop Deadline | |
| Friday | 9/21 | Proof by Contradiction, concluded Predicate logic Reading: Peter Suber's Translation Tips (predicate logic section) |
|
| 5 | Monday | 9/24 | Predicate Logic Reading: MCS Section 4.1 |
| Wednesday | 9/26 | Sets Introduction Assignment 3 due 10/5 in class |
|
| Friday | 9/28 | Sets, continued HashSets in Java |
|
| 6 | Monday | 10/1 | Lists; Relations Reading: FoC 2.4-2.8 |
| Wednesday | 10/3 | Relational Databases Functions |
|
| Friday | 10/5 | Functions / Functions in programming languages Assignment 4 due 10/15 in class, submit .java file on Blackboard |
|
| 7 | Monday | 10/8 | Function Composition |
| Wednesday | 10/10 | Function Inverses | |
| Friday | 10/12 | No Class - Dan sick | |
| 8 | Monday | 10/15 | Induction and Recursion Intro |
| Wednesday | 10/17 | Exam 1 | |
| Friday | 10/19 | No Class - Fall Break Mid Term Grades Posted |
|
| 9 | Monday | 10/22 | Go over exam |
| Wednesday | 10/24 | Recursion | |
| Friday | 10/26 | Towers of Hanoi problem Reading: FoC Chapter 3 through 3.3. Assignment 5 due 11/12 in class, submit .java files on Blackboard Withdraw Deadline |
|
| 10 | Monday | 10/29 | Induction |
| Wednesday | 10/31 | Induction, concluded. A look ahead to the final third of the course Explanation of the Online Portion of the Course |
|
| Friday | 11/2 | Formal Languages (Panopto on Blackboard) Dan at AMIA Annual Symposium |
|
| 11 | Monday | 11/5 | Regular Expressions, Formally (Panopto on Blackboard) Dan at AMIA Annual Symposium |
| Wednesday | 11/7 | Regular Expressions in Java (Panopto on Blackboard) Dan at AMIA Annual Symposium |
|
| Friday | 11/9 | Work through the Java Regular Expression Tutorial, then complete the small problem on Blackboard. Dan at AMIA Annual Symposium |
|
| 12 | Monday | 11/12 | Introduction to Finite Automata |
| Wednesday | 11/14 | Deterministic Finite Automata Reading: FoC 3.4-3.7 |
|
| Friday | 11/16 | Non-Deterministic Finite Automata | |
| 13 | Monday | 11/19 | NFA wrap up, Finite State Transducers Assignment 6 due 11/30 in class |
| Wednesday | 11/21 | No Class - Thanksgiving Break | |
| Friday | 11/23 | No Class - Thanksgiving Break | |
| 14 | Monday | 11/26 | FSTs, concluded Grammars, BNF |
| Wednesday | 11/28 | Grammars, concluded | |
| Friday | 11/30 | Introduction to Turing Machines Assignment 7 due 12/7 in class Reading: FoC 4.4 on Pushdown Automata, FoC Chapter 5 |
|
| 15 | Monday | 12/3 | Turing Machines, Continued Readings Rapaport, William J., Philosophy of Computer Science Chapter 8 - A walkthrough of Turing's original paper |
| Wednesday | 12/5 | Walking through Turing's paper Final Exam Study Guide |
|
| Friday | 12/7 | Last Day of Class Walking through Turing's paper |
|
| Finals Week | Friday | 12/14 | Final Exam 10:30am-12:30pm |
Academic Integrity:
While it is acceptable to discuss general approaches with your fellow students, the work you turn in must be your own. If you have any problems doing the assignments, consult the instructor. Please be sure to read the webpage, “Academic Integrity“, which spells out all the details of this, and related policies. See my page on plagiarism for an explanation of what I consider cheating.
Disability Statement:
If you have a disabling condition, which may interfere with your ability to successfully complete this course, please contact the Office of Disability Services at dss@oswego.edu and x3358.