Foundations of Computer Science
Lecturer:
Prof. Daniel R. Schlegel, 395 Shineman Center, daniel.schlegel@oswego.edu
Office hours: Tuesday 3-4PM, Wednesday 9-10AM, Friday 2-3PM and by appointment.
Section 800: TR 9:35-10:55am, Shineman 175
Section 810: TR 11:10-12:35pm, Shineman 175
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.
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.16.2016 (2016). Available at: http://www.cse.cuhk.edu.hk/~andrejb/engg2440/mcs.pdf
Useful Resources:
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 with a partner of your choosing. If you cannot find a partner, let me know and I will match you up. There will be 6 to 8 assignments, due typically within a week of assignment. Some more significant programming projects will be given more time. Late assignments will not be accepted and will be given a grade of 0 for both students. Submission will be via Blackboard.
Grading:
It is expected that each person (or group if working in pairs for an exercise) 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 | 60% |
| Midterm Exam | 20% |
| Final Exam | 20% |
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 8 topics, with the course generally split into two parts.
Part 1
Discrete Structures
Functions + Relations
Induction + Recursion
Formal Languages
Part 2
Logic
Finite State Machines
Languages + Grammars
Computability
The course schedule as follows is only a draft. It is expected to change, but changes will be announced in class. Lecture slides/notes will be maintained on Blackboard.
| Week | Day | Date | |
|---|---|---|---|
| 1 | Tuesday | 1/24 | First day of class Discrete Structures - Sets Readings: MCS 4.1 |
| Thursday | 1/26 | Discrete Structures - Sets & Lists Java HashSet Example Readings: FC 2.4-2.5 |
|
| 2 | Tuesday | 1/31 | Functions |
| Wednesday | 2/1 | Add deadline |
|
| Thursday | 2/2 | Math vs. Computer Functions Assignment 1 on Blackboard - Due 2/9 11:59PM |
|
| 3 | Tuesday | 2/7 | Functions |
| Thursday | 2/9 | Formal Logic Readings: Suppes Chapter 1 (See Blackboard) |
|
| Friday | 2/10 | Drop deadline |
|
| 4 | Tuesday | 2/14 | Formal Logic Using Truth Tables to Analyze Arguments Readings: Peter Suber's Truth-functional propositional logic translation tips |
| Thursday | 2/16 | Review of Assignment 1; Proof Theory | |
| 5 | Tuesday | 2/21 | Proof Theory Continued Assignment 2 on Blackboard - Due 2/28 at the beginning of class |
| Thursday | 2/23 | Proof Theory Continued | |
| 6 | Tuesday | 2/28 | Predicate Logic |
| Thursday | 3/2 | Review for Midterm Midterm Study Guide |
|
| 7 | Tuesday | 3/7 | Midterm Exam |
| Thursday | 3/9 | ||
| 8 | Tuesday | 3/14 | Spring recess - no class |
| Thursday | 3/16 | Spring recess - no class | |
| 9 | Tuesday | 3/21 | Recursion Assignment 3 on Blackboard - Due 3/28 11:59PM Readings: Recursion, Recursion Examples |
| Thursday | 3/23 | Recursion and Induction Readings: FoC Section 1.9 |
|
| 10 | Tuesday | 3/28 | Recursion and Induction - Tower of Hanoi |
| Thursday | 3/30 | Formal Languages and Regular Expressions Readings: FoC 3.1-3.3 |
|
| 11 | Tuesday | 4/4 | Regular Expressions in Java Assignment 4 on Blackboard - Due 4/11 11:59PM Readings: Regular Expressions Tutorial; FoC 3.4 |
| Thursday | 4/6 | Deterministic Finite Automata | |
| 12 | Tuesday | 4/11 | Non-Deterministic Finite Automata Readings: FoC 3.5 |
| Thursday | 4/13 | Finite-State Transducers Readings: FoC 4.1-4.3 |
|
| 13 | Tuesday | 4/18 | Grammars Assignment 5 on Blackboard - Due 4/25, Beginning of Class Readings:FoC 4.4 |
| Thursday | 4/20 | Class Cancelled (Dan @ ABET) | |
| 14 | Tuesday | 4/25 | Pushdown Automata Readings: FoC Chapter 5; My CSE111 Notes on TMs; Wikipedia article on Automata-based programming |
| Thursday | 4/27 | Turing Machines Assignment 6 on Blackboard - Due 5/4, Beginning of Class Readings Rapaport, William J., Philosophy of Computer Science Chapter 8 - A walkthrough of Turing's original paper |
|
| 15 | Tuesday | 5/2 | TMs / Computability - Walking through Turing's paper |
| Thursday | 5/4 | Last day of class Walking through Turing's paper Computability Final Exam Study Guide |
|
| Finals Week | Tuesday | 5/9 | Section 810 Final Exam 10:30AM-12:30PM - Shineman 175 |
| Finals Week | Thursday | 5/11 | Section 800 Final Exam 8AM-10AM - Shineman 175 |
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.