Office hours: Tuesday and Thursday, 3:00β5:00 and by appointment, Sanders Physics 305
Monday & Wednesday, 1:30–2:45 p.m., Sanders Physics 105
Friday, 3:10–5:10 p.m., Sanders Physics 309
In Sanders Physics 307:
The calendar on this page will be updated throughout the semester with readings, assignments, and exams. Schedule a reminder to check it after each class.
Week  Monday  Wednesday  Friday 

0 
Sep. 3Labor Day No class. 
Sep. 5Class information. Lecture: Introduction, Sets. Read 1.1–1.4. Optional reading: Russell’s Paradox. 
Sep. 7Lecture: Review of Scheme Lab 0 (with solutions) Reference: Introduction to Computer Science using Scheme, Part 1 (from CMPU 101). 
1 
Sep. 10Lecture: Intersection and Union Code: Recursive functions Read 1.5. 
Sep. 12Lecture: Power Sets Code: Lab 0 walkthrough Read 1.6. 
Sep. 14Lab 1 (with solutions) 
2 
Sep. 17Lecture: Binary Relations Code: Cross product, keep pairs Read 2.1–2.2. 
Sep. 19Lecture: Relations (cont’d) Code: Domain, Reflexive? Read 2.3.1, 2.3.3, and 2.4. 
Sep. 21Lab 2 (with solutions) 
3 
Sep. 24Lecture: Equiv. relations & partitions Read 2.5. 
Sep. 26Lecture: Wrapping up Relations Handout: One more proof about equivalence relations and partitions Finish chapter 2. 
Sep. 28Lab 3 (with solutions) 
4 
Oct. 1Lecture: Functions Read 3.1–3.4. 
Oct. 3Lecture: Functions cont’d Code: Curried functions Finish chapter 3. 
Oct. 5Lab 4 (with solutions) 
5 
Oct. 8Lecture: Induction, recursion, and the natural numbers Code: Fibonacci Read 4.1–4.5.2. 
Oct. 10Lecture: Continuing with Numerical Induction Handout: Numerical Recursion 
Oct. 12No lab 
6 
Oct. 15π October Break 
Oct. 17π October Break 
Oct. 19πΏ October Break 
7 
Oct. 22Lecture: Continuing with induction & recursion: From numbers to lists Handout: List Recursion 
Oct. 24Midterm review Handout: Induction Examples 
Oct. 26Midterm 
8 
Oct. 29Lecture: Induction on Flat Lists, Strong Induction, and Introduction to Combinatorics Optional reading: Order on Natural Numbers & Strong Induction 
Oct. 31π Spooky Lecture: Counting: Permutation and Combinations Code: Exponent Read 5.1–5.4.1. 
Nov. 2Lab 5 (with solutions) 
9 
Nov. 5Lecture: Permutations and Combinations continued Code: Generate all tuples 
Nov. 7Lecture: Combinations: Validating answers using simulation Code: nchoosek; representing cards Finish chapter 5. 
Nov. 9Lab 6 (with solutions) 
10 
Nov. 12Lecture: Probability, part 1 Read 6.1–3. 
Nov. 14Lecture: Probability, part 2 
Nov. 16Lab 7 (with solutions) 
11 
Nov. 19Lecture: Probability, part 3 Code: Simulating conditional probability (Helper) Read 6.4, 6.6–7. Optional: Read 6.5, 6.8. 
Nov. 21π’ Cancelled due to lack of a quorum 
Nov. 23π₯§ Thanksgiving 
12 
Nov. 26Lecture: Introduction to Propositional Logic Read 8.1–8.3. 
Nov. 28Lecture: Propositional logic, continued 
Nov. 30Lab 8 (with solutions) 
13 
Dec. 3Lecture: Wrapping up propositional logic Handout: Resolution 
Dec. 5Lecture: Firstorder logic Optional reading: Chapter 9. 
Dec. 7Lab 9 (with solutions) 
14 
Dec. 10 
Dec. 12Friday teaching day; class is 3:10–5:10 in SP 309 Final exam review 
Dec. 14π Study period 
15 
Dec. 18

βοΈ 
βοΈ 
A computer is not dependent so much on technology as on ideas.
– W. Daniel Hillis
This course introduces the theoretical, structural, and algorithmic foundations of computer science. Topics include: sets, relations, functions, recursive data structures, recursive functions, induction, structural induction, probability, logic, boolean algebra, and proving program correctness. The course will emphasize the exploration of these topics through computer exercises, but it will also focus on developing proof techniques in handwritten exercises. A weekly laboratory period provides guided handson experience.
Prerequisites: CMPU 101.
The primary textbook for this course is Sets, Logic and Maths for Computing, second ed., by David Makinson (Springer, 2012).
This textbook is available for sale at the bookstore, but it is also available for free online through SpringerLink. To access from outside the Vassar network, you may need to search for the book on the library website, which will prompt you to log in.
We will be following the chapters in the textbook quite closely. There will be occasional supplemental readings made available on this website or distributed in class. The material in the textbook will be complemented by regular programming assignments.
We will use Racket (The Language Formerly Known as Scheme / ) in the DrRacket programming environment. DrRacket is installed on the Linux workstations in the department. If you want to work from your own computer, see these instructions.
The lab sessions will initially be devoted to getting familiar with the DrRacket programming environment and how it lets us implement some of the ideas we see in class. Some lab sessions may also include lectures.
There will be regular assignments, usually about one every two weeks. Most of the problems on these assignments will require you to write, test, and run programs; however, some of the problems, particularly in the first part of the semester, will require you to write proofs using techniques discussed in class.
You are strongly encouraged to use pencil when writing proofs since you’ll want to erase. It’s not necessary to typeset your proofs, though you can. Whether involving handwritten proofs or typedup programs, all assignments must be clearly composed and laid out neatly on the page. Your programs must include concise comments that make it clear what you are doing; and your proofs must be legible. In general, at least one blank line should separate consecutive problems/programs.
All assignments are due at the start of class and should be turned in directly to me. Assignments received after the beginning of class will be considered late. Assignments turned in one day late lose 15%. Assignments turned in two days late lose 25%. Assignments turned in more than two days late will be a 0, but you should still turn them in so you get the practice and you get feedback on your work.
When computing your final grade for the course, your lowest homework score from among the homeworks that were turned in – on time or late – will be dropped.
As with all policies, homework policies are intended to be fair to everyone involved in the course, so I will do my best to enforce them fairly. Please feel free to ask me any questions about specific cases that may emerge over the semester.
All assignments must be done individually. No collaboration of any kind is allowed. Any cases of inappropriate collaboration (cheating) have to be reported, and will be dealt with promptly. Any sharing of code – even if it’s just pointing out something on the screen that you’ve written – will be considered cheating. In addition, you may not use code from other sources, including online sources, unless explicitly authorized. In general, receiving and copying solutions (code, pseudocode, proofs, etc.) from any source (a classmate, a friend, a published text, an online source, etc.) is disallowed. Note that using code or other material from sources (other than those explicitly given as course resources) as “inspiration” and submitting highly derivative solutions is viewed as copying. (Please read Going to the Source: A Guide to Academic Integrity and Attribution at Vassar College, available from the Dean of the College website.) Furthermore, on each submitted assignment, you should always cite and acknowledge sources from which you receive assistance, including your textbook, your coaches, or your classmates.
There will be one inclass exam during the semester, around Fall Break. There will also be a regularly scheduled final exam. All exams will be paperandpencil affairs, with openbook/opennotes, but no electronic devices (e.g., no calculators or computers).
The elements of the course will be weighted as follows when determining your overall grade:
Assignments  45% 
Exams  35% (midterm: 15%; final: 20%) 
Labs  20% 
Academic accommodations are available for students registered with the Office for Accessibility and Educational Opportunity (AEO). Students in need of disability (ADA/504) accommodations should schedule an appointment with me early in the semester to discuss any accommodations for this course that have been approved by the Office for Accessibility and Educational Opportunity, as indicated in your AEO accommodation letter.
Vassar College is committed to providing a safe learning environment for all students that is free of all forms of discrimination and sexual harassment, including sexual assault, relationship abuse, and stalking. If you (or someone you know) has experienced or experiences any of these incidents, know that you are not alone. Vassar College has staff members trained to support you in navigating campus life, accessing health and counseling services, providing academic and housing accommodations, helping with legal protective orders, and more.
Please be aware all Vassar faculty members are “responsible employees,” which means that if you tell me about a situation involving sexual harassment, sexual assault, relationship abuse, or stalking, I must share that information with the Title IX Coordinator. Although I have to make that notification, the Title IX office will only provide outreach by email. You will control how your case will be handled – you donβt have to read or respond to the email, and it is completely up to you whether to pursue a formal complaint. Our goal is to make sure you are aware of the range of options available to you and have access to the resources you need.
If you wish to speak to someone privately, you can contact any of the following oncampus resources:
The SAVP website and the Title IX section of the EOAA website have more information, as well as links to both on and offcampus resources.