CSCI054 is a combined course on functional programming and formal proof. The course both exposes students to a new programming paradigm and introduces discrete structures and proof techniques that will be needed in later computer science classes. In addition a few practical applications will be discussed.
The prerequisite for the class is any flavor of CSCI051, a 5 on the CS A AP exam, or permission of the instructor/department. Send me (Prof. Osborn) an email if you have questions about these requirements.
The professor for this class is Prof. Osborn. If you want to talk about the class or chat about general advising things, please stop by my office hours (Thursday 2:45--3:45pm and Friday 1:30pm--3:30pm), which are typically in person but might be on Zoom (I'll announce if they're on Zoom). I can also meet with you at other times by appointment (in person or on zoom): send me an email with some times that are good for you and a sense of what you want to talk about.
The mentors/TAs for the class are Landen Isacson, Keyron Linarez, Tara Mukund, Lenny Raybukh, Lawrence Stampino-Strain, and Emily Zhu. In general the mentor hours will be on the 1st or 2nd floor of Edmunds; check the pinned post on Slack for up-to-date info. There may be occasional changes and cancellations, however, so please also check Slack for updates.
We'll be using this course website for distributing course materials and Slack for making announcements and answering questions. We'll be using Gradescope for submitting and returning assignments. Let me know if you have problems accessing either.
The textbooks for the class are:
You are encouraged to look for and to use other resources. Some others that people have found useful are:
If you find anything particularly helpful you are strongly encouraged to share it with the class on Slack.
If you might need accommodations please contact the Disability Coordinator on your home campus. The process for Pomona students is available here .
More generally, life happens to all of us and I know there may be times when staying on top of the workload in this class is going to feel like too much on top of everything else that you're managing. If that happens, please come talk to me so that I'm aware and so that we can work together to try to figure out a plan. Please keep in touch!
The basic flow each week will be as follows:
The lectures will be in Edmunds 101.
You will be assigned to a small group of approximately 4-6 students during the first week of classes. Your group will work together for the entire semester; your first task will be to find an hour when all of you can meet either Thursday or Friday. The plan is for each group to have an assigned TA who will attend the meetings to answer questions, talk through concepts, etc. Each week there will be a low-stakes assignment to work on during your group meeting; this should be turned in by 10pm Friday evening on Gradescope. There will also be two anonymous surveys during the semester for you to give feedback on how your group is working.
In addition, there will be a weekly problem set. The assignments will mostly be done and submitted in pairs and will also be submitted on Gradescope. The pairs will be by assignment for the first few weeks and then at your discretion after that. Problems on the assignment will ask you to apply concepts in new ways. As with the practice problems you may discuss the problems with anyone else currently taking cs54 (or with the TAs or myself), but each pair must write up their own solution. Unless stated otherwise, these are due by 10pm on the due date.
Each lecture will begin with a brief self-graded review quiz. One lecture per week (typically a Thursday) will end with a short topic test. It is possible to regain points lost on a topic test during office hours.
To make good use of class time, it is essential to do readings, prepare for class, and attend lecture; besides the daily assessment, each class session is divided between a brief lecture and group work on example problems.
The course will conclude with a cumulative in-class final exam in week 15, with an option of retakes during the final exam slot (Wednesday 12/11, 2:00pm--5:00pm, in the usual classroom).
The breakdown of grades will be as follows:
This is a high-level outline of the planned schedule. Note that the calendar is subject to change . For the readings "CDMCS" refers to the book "Connecting Discrete Mathematics and Computer Science" by David Liben-Nowell and "LYAH" refers to the book "Learn You a Haskell for Great Good!" by Miran Lipovača and others. The chapter numbers for LYAH refer to the online version of the book; note that the section numbers are not explicit.
Unless stated otherwise, all deadlines are at 10pm on the given date.
| Week | Day | Date | Topic | Reading | Due |
|---|---|---|---|---|---|
| 1 | T | 08/27 | admin, groups, intro to Haskell, code, worksheet | LYAH: Ch 1, 2.1-2 | Quiz: Class logistics |
| R | 08/29 | lists and tuples, code, worksheet | LYAH: Ch 2.3-6 | Quiz & test: Class logistics, defining functions, conditionals, cons syntax, cons vs append, list comprehensions | |
| Fr | 08/30 | week01-group | |||
| Su | 09/01 | week01-ps, template | |||
| 2 | T | 09/03 | types, intro to pattern matching, code, worksheet | LYAH: Ch 3, 4.1 | Quiz: Conditionals, lists vs tuples, cons syntax |
| R | 09/05 | pattern matching, guards, where, code, worksheet | LYAH: Ch 4 | Quiz & test: List comprehensions, typeclasses and function type syntax, pattern matching, cons vs append, recursion on lists | |
| F | 09/06 | week02-group | |||
| Su | 09/08 | week02-ps, template | |||
| 3 | T | 09/10 | where, let, higher-order functions, code, worksheet | LYAH: Ch 4, 6 | Quiz: Types, guards, let/where |
| R | 09/12 | higher-order functions continued, code, worksheet | LYAH: Ch 4, 6 | Quiz & test: List comprehensions, let/where, map/filter, types of higher order functions, currying, lambdas | |
| F | 09/13 | week03-group | |||
| Su | 09/15 | week03-ps, template | |||
| 4 | T | 09/17 | folds, code, worksheet | LYAH: Ch 6 | Quiz: Cons syntax, higher order functions, lambdas |
| R | 09/19 | discrete math data types: sets, functions, worksheet | CDMCS: Ch 2.1-3, 2.5 | Quiz & Test: Higher order functions, currying, lambdas, pattern matching, fold, sets | |
| F | 09/20 | week04-group, sample tex file | |||
| Su | 09/22 | week04-ps, week04-ps-coding, cs54header.tex, coursetemplate54.sty | |||
| 5 | T | 09/24 | propositional logic, worksheet | CDMCS: Ch 3.1-3 | Quiz: Fold, domain/codomain/range, one-to-one/onto |
| R | 09/26 | predicate logic, worksheet | CDMCS: Ch 3.4-5 | Quiz & Test: Bijections, set operations, propositional logic, truth tables, predicate logic | |
| F | 09/27 | week05-group | |||
| Su | 09/29 | week05-ps | |||
| 6 | T | 10/01 | predicate logic, writing proofs, worksheet | CDMCS: Ch 3.5, 4.3-5 | Quiz: Lambdas, partial application, fold, one-to-one/onto |
| R | 10/03 | proof strategy: direct, contrapositive, worksheet | CDMCS: Ch 4.3-5 | Quiz & Test: Set operations, contrapositive, truth tables, predicate logic | |
| F | 10/04 | week06-group | |||
| Su | 10/06 | week06-ps | |||
| 7 | T | 10/08 | proofs: contradiction, worksheet | CDMCS: Ch 4.3-5 | Quiz: Direct proof, contrapositive proof |
| R | 10/10 | proofs: induction, sum notation, worksheet | CDMCS: Ch 5.2-3 | Quiz & Test: Proof by contradiction, contrapositive, truth tables, pattern matching and recursion, number theory | |
| F | 10/11 | week07-group--this is due before fall break! | |||
| Su | 10/13 | fall break begins; week07 topics are in week08's problem set, so get started early! | |||
| 8 | T | 10/15 | fall break | ||
| R | 10/17 | proofs: strong induction, worksheet | CDMCS: Ch 5.2-3 | Quiz & Test: Induction, number theory, truth tables, proof strategy | |
| F | 10/18 | week08-groups | |||
| Su | 10/20 | week08-ps, cs54header.tex, coursetemplate54.sty | |||
| 9 | T | 10/22 | functions, worksheet | CDMCS: Ch 2.5 | Quiz: Strong induction, sum notation, one-to-one/onto |
| R | 10/24 | relations | CDMCS: Ch 8.2-4 | Quiz & Test: Set operations, contrapositive, induction, proving one-to-one/onto | |
| F | 10/25 | week09-group | |||
| Su | 10/27 | week09-ps | |||
| 10 | T | 10/29 | relations continued, countability, worksheet | CDMCS: Ch 9.3 | Quiz: Relations (transitivity/symmetry/reflexivity), induction |
| R | 10/31 | uncountability | CDMCS: Ch 9.3 | Quiz: Countability | |
| F | 11/01 | week10-groups | |||
| Su | 11/03 | week10-ps | |||
| 11 | T | 11/05 | encryption, worksheet | CDMCS: Ch 8.3-4 | Test & Quiz: relation properties, closures; countability, uncountability, pattern matching and recursion |
| R | 11/07 | RSA, worksheet | CDMCS: Ch 7.5 | Quiz & Test: Encryption, higher order functions, number theory, relations, countability | |
| F | 11/08 | week11-groups | |||
| Su | 11/10 | week11-ps, week11-ps-coding | |||
| 12 | T | 11/12 | combinatorics | CDMCS: Ch 9.2 | Quiz: Encryption, countability, set operations |
| R | 11/14 | binomial theorem | CDMCS: Ch 9.2 | Quiz & Test: Sum notation, induction, combinatorics, predicate logic | |
| F | 11/15 | week12-group | |||
| Su | 11/17 | week12-ps, week12-ps-coding | |||
| 13 | T | 11/19 | probability, worksheet | CDMCS: Ch 10.2 | Quiz: Combinatorics, set operations |
| R | 11/21 | more probability, worksheet | CDMCS: Ch 10.2 | Quiz & Test: Probability, combinatorics, induction, countability, uncountability | |
| F | 11/22 | week13-group | |||
| Su | 11/24 | week13-ps | |||
| 14 | T | 11/26 | review | Quiz: Combinatorics, probability, uncountability | |
| R | 11/29 | Thanksgiving break | |||
| 15 | T | 12/03 | *** final exam in class *** | Topics: Haskell, proof techniques (direct, induction), functions and relations, countability, combinatorics | |
| R | 12/05 | *** Reading Days, no class *** | |||
| W | 12/11 | In-class exam retakes/regrading | 2:00pm--5:00pm, during final exam slot |