CMPU 145

Foundations of Computer Science

Fall 2018


Jonathan Gordon

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

Coaching Hours

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


Sep. 3

Labor Day

No class.

Sep. 5

Class information.

Lecture: Introduction, Sets.

Read 1.1–1.4.

Optional reading: Russell’s Paradox.

Sep. 7

Lecture: Review of Scheme

Lab 0 (with solutions)

Reference: Introduction to Computer Science using Scheme, Part 1 (from CMPU 101).


Sep. 10

Lecture: Intersection and Union

Code: Recursive functions

Read 1.5.

Assignment 1 (Solutions)

Sep. 12

Lecture: Power Sets

Code: Lab 0 walk-through

Read 1.6.

Sep. 14

Lab 1 (with solutions)


Sep. 17

Lecture: Binary Relations

Code: Cross product, keep pairs

Read 2.1–2.2.

Sep. 19

Lecture: Relations (cont’d)

Code: Domain, Reflexive?

Read 2.3.1, 2.3.3, and 2.4.

Assignment 2 (Solutions)

Sep. 21

Lab 2 (with solutions)


Sep. 24

Lecture: Equiv. relations & partitions

Read 2.5.

Sep. 26

Lecture: Wrapping up Relations

Handout: One more proof about equivalence relations and partitions

Finish chapter 2.

Assignment 3 (Solutions)

Sep. 28

Lab 3 (with solutions)


Oct. 1

Lecture: Functions

Read 3.1–3.4.

Oct. 3

Lecture: Functions cont’d

Code: Curried functions

Finish chapter 3.

Assignment 4 (Solutions)

Oct. 5

Lab 4 (with solutions)


Oct. 8

Lecture: Induction, recursion, and the natural numbers

Code: Fibonacci

Read 4.1–4.5.2.

Oct. 10

Lecture: Continuing with Numerical Induction

Handout: Numerical Recursion

Oct. 12

No lab

Midterm practice problems (Solutions)


Oct. 15

🍁 October Break

Oct. 17

πŸ‚ October Break

Oct. 19

🐿 October Break


Oct. 22

Lecture: Continuing with induction & recursion: From numbers to lists

Handout: List Recursion

Oct. 24

Midterm review

Handout: Induction Examples

Oct. 26




Oct. 29

Lecture: Induction on Flat Lists, Strong Induction, and Introduction to Combinatorics

Optional reading: Order on Natural Numbers & Strong Induction

Assignment 5 (Solutions)

Oct. 31

πŸŽƒ Spooky Lecture: Counting: Permutation and Combinations

Code: Exponent

Read 5.1–5.4.1.

Nov. 2

Lab 5 (with solutions)


Nov. 5

Lecture: Permutations and Combinations continued

Code: Generate all tuples

Nov. 7

Lecture: Combinations: Validating answers using simulation

Code: n-choose-k; representing cards

Finish chapter 5.

Assignment 6 (Solutions)

Nov. 9

Lab 6 (with solutions)


Nov. 12

Lecture: Probability, part 1

Read 6.1–3.

Nov. 14

Lecture: Probability, part 2

Code: Simulating hands of cards

Nov. 16

Lab 7 (with solutions)


Nov. 19

Lecture: Probability, part 3

Code: Simulating conditional probability (Helper)

Read 6.4, 6.6–7.

Optional: Read 6.5, 6.8.

Assignment 7 (Solutions)

Nov. 21

😒 Cancelled due to lack of a quorum

Nov. 23

πŸ₯§ Thanksgiving


Nov. 26

Lecture: Introduction to Propositional Logic

Read 8.1–8.3.

Nov. 28

Lecture: Propositional logic, continued

Code: Interpreting propositions

Nov. 30

Lab 8 (with solutions)


Dec. 3

Lecture: Wrapping up propositional logic

Handout: Resolution

Assignment 8 (Solutions)

Dec. 5

Lecture: First-order logic

Optional reading: Chapter 9.

Dec. 7

Lab 9 (with solutions)


Dec. 10

Lecture: First-order logic semantics and inference

Dec. 12

Friday teaching day; class is 3:10–5:10 in SP 309

Final exam review

Final practice problems (Solutions)

Dec. 14

πŸ“• Study period


Dec. 18
5 p.m.

Final exam, SP 309



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 hands-on 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 / Prince love symbol) 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.

DrRacket Tips

Programming Tips


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 typed-up 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 in-class exam during the semester, around Fall Break. There will also be a regularly scheduled final exam. All exams will be paper-and-pencil affairs, with open-book/open-notes, but no electronic devices (e.g., no calculators or computers).

Course Grades

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

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.

Title IX

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 on-campus resources:

The SAVP website and the Title IX section of the EOAA website have more information, as well as links to both on- and off-campus resources.