Discrete Structures (Fall 2024)
Overview
What are the mathematical foundations of computer science? How does mathematical formalism relate to the pragmatics of computer science? In this course, we study discrete mathematics, broadly the branches of mathematics that study discrete objects, and their applications towards computer science.
By understanding discrete mathematics deeply, we, in turn, gain an understanding of how mathematics informs our studies as computer scientists, namely:
- We solve problems in computer science by modeling domains of problems, a process that is, at its core, mathematical.
- The interpretation of the syntax and semantics of mathematics is identical to the interpretation of a programming language, so we can leverage our understanding of programming to learn mathematics rapidly.
- There is a spectrum of reasoning between absolute mathematical formalism and informal reasoning, a spectrum that we must move across at will as competent programmers.
Finally, by studying discrete mathematics in depth and relating it to our experiences as computer programmers, we also gain expertise and comfort in studying mathematics as a discipline of modeling and problem-solving.
Course Learning Outcomes
- Mathematical Literacy
- Reading: read and comprehend mathematical text involving both symbols and prose.
- Writing: author arguments of varying mathematical rigor with fundamental proof techniques (i.e., constructive, inductive, contradictory, and equivalence-based arguments).
- Analyzing: critically analyze rigorous mathematical arguments for latent assumptions and missing detail.
- Problem-solving: employ the concrete-to-abstract method to efficiently solve mathematical problems.
- Mathematical Modeling
- Objects: model real-world phenomena using relevant objects drawn from discrete mathematics (i.e., sets, relations, random variables, and graphs).
- Properties: formally state and prove relevant properties of mathematical models using propositional and first-order logic.
- Mathematical Computation
- Combinatorics: count the number of elements in a finite algebraic structure using combinatorial principles.
- Probability: compute the probability of an event using combinatorial principles.
- Graphs: carry out the execution of fundamental graph algorithms by hand, e.g., traversals, spanning trees, and paths.
- Program Reasoning
- Operational correctness: state and reason about formal properties of programs using operational semantics.
- Complexity: count the number of relevant operations a (potentially recursive) program performs.
- Algorithmic correctness: state and reason about formal properties of algorithms (specified in pseudocode) using tools drawn from discrete mathematics.
- Constructive design: translate between a (constructive) proof of a property and a program that enjoys that property by design.
- Mathematical Soft Skills
- Collaboration: employ appropriate collaborative strategies to productively solve problems with peers.
- Practice: habitualize learning mathematics through self-driven, hands-on exploration and problem-solving practice.
Core Outcomes
Core learning outcomes are the fundamental skills that you should be able to confidentially perform quickly and efficiently by the end of the course. They are asssessed via the core exams we conduct throughout the semester:
- Weeks 1–4
- Author a formal proof of a property of a pure program.
- Author a formal proof by structural induction.
- Author a formal proof by mathematical induction.
- Read a formal and proof and identify latent assumptions.
- Author a formal proof of a property of impure program.
- Weeks 5–9
- Author a rigorous proof of the equality of two sets.
- Author a rigorous proof utilizing classical reasoning (“proof by contradiction”).
- Model real-world phenomena using the fundamental definitions of relations.
- Model real-world phenomena using the formal definitions of graphs and trees.
- Author rigorous proofs of properties of graphs and their associated algorithms.
- Week 10–13
- Count the number of elements in an algebraic structure using combinatorial principles.
- Accurately count the number of relevant operations that a (recursive) program performs.
- Interpret a combinatorial formula as an algorithm for constructing an object when choice is involved.
- Compute the probability of an event using fundamental combinatorial principles.
- Apply random variables and expectation to model a probabilistic phenomena.
Textbook, Software, and Connectivity
There is no required textbook for this course. Required readings for the course will be distributed electronically as a work-in-progress textbook. The course webpage and readings contain suggestions for supplementary texts that give alternative takes on topics or go into more depth.
In this course, we will use the following software packages and services:
- Python: a general-purpose scripting programming language.
- Overleaf: online editing and collaboration of LaTeX documents.
- Gradescope: deliverable submission and feedback reporting.
- Microsoft Teams: communication and Q&A.
You will receive invitations to Gradescope and Teams at the beginning of the semester. Please let me know if you do not receive access to this site. The course webpage also contains additional software resources, e.g., Python and LaTeX tutorials and other utilities, that you might find useful in this course.
Diversity, Inclusion, and Accommodations
I am committed to fostering an inclusive classroom environment that allows you try, fail, and succeed, all in the service of mastering the learning outcomes of the course. In turn, I expect you to fully engage with the course through class attendance and timely submissions of work. If anything precludes you from doing so, e.g., illness, sports event, or religious observance, the golden rule is to let me know as early as possible. I will do what I can to help you succeed in the course. However, this requires that I have advanced notice, at least a week in advances, when appropriate and possible, so that we have an appropriate time frame to develop and implement a plan of action based on your needs.
I particularly encourage students with disabilities to meet with me and discuss how our classroom and course activities could impact their work and what accommodations would be essential. As part of this process, you should contact the Office of Disability Resources for further guidance and instructions.
Title IX
Grinnell College is committed to compliance with Title IX and to supporting the academic success of pregnant and parenting students and students with pregnancy related conditions. If you are a pregnant student, have pregnancy related conditions, or are a parenting student (child under one-year needs documented medical care) who wishes to request reasonable related supportive measures from the College under Title IX, please email the Title IX Coordinator at titleix@grinnell.edu. The Title IX Coordinator will work with Disability Resources and your professors to provide reasonable supportive measures in support of your education while pregnant or as a parent under Title IX.
Course Work and Evaluation
My grading philosophy comes from the grading for growth movement described in such texts as Nilson’s Specifications Grading, Feldman’s Grading for Equity, and Blum’s Ungrading. I believe that:
- The stated learning outcomes are achievable by anyone that enrolls in this course.
- Mastery of the learning outcomes is obtained via exploration, experimentation, and failure.
- Eventual mastery should be valued as highly as “getting it right” the first time.
- Your final course grade should reflect your mastery of the course’s learning goals at the end of the term.
To this end, the course is structured around several deliverables that, when taken together, indicate your mastery of the course’s learning outcomes outlined in the Overview section of the syllabus.
Deliverables
The main activities of our course are centered around four kinds of deliverables:
- Daily drills: introductory practice problems tied to each reading due the day before each class period.
- Lab exercises: collaborative practice and exploration-style problems worked on during class.
- Demonstration exercises: individually completed weekly homework sets that apply the weekly concepts to substantial tasks aligned with the themes of the course.
- Core exams: in-class exams that directly assess mastery of the core skills of the course.
Daily Drills
In each course reading, you will find a small number of practice problems that reinforce the concepts introduced in the reading. As the old saying goes, “Mathematics is not a spectator sport,” so these drills are designed to help you begin putting the day’s topics into practice.
- Each class period’s daily drill is due at 10 PM the day before class.
- Daily drills are graded on a binary satisfactory (S)/non-satisfactory (N) scale. If it is clear that you have put effort into your responses by completing the drill with mostly positive results, you can expect to receive a satisfactory grade.
- There is a 24 hour grace period for turning in daily drills, e.g., if you forget to press the submit button. Otherwise, late daily drills will not be accepted! Note that you can miss several daily drills without penalty to your final grade; see how your overall letter grade is calculated for details.
- You are expected to bring your completed daily drills to class every day. We will frequently use the daily drills to begin our class discussion.
Lab Exercises
The bulk of your practice and exploration of the course learning goals come through lab exercises. These lab exercises will allow you to gain familiarity and eventual fluency with the course concepts by exploring and working through problems. Lab exercises are completed in small groups so that you can take advantage of the benefits of collaborative learning.
- Each set of labs is due the Saturday of the week that the lab is assigned. For example, if labs are assigned on Monday, Wednesday, and Friday, they are due the same week on Saturday.
- Like daily drills, labs are graded on a binary satisfactory (S)/non-satisfactory (N) scale.
- There is a 48 hour grace period to turn in labs, e.g., if you need more time to coordinate with your partner. Like daily drills, late labs will not be accepted, and you can miss several labs without penalty to your final grade; see how your overall letter grade is calculated for details.
- While labs are graded on a binary scale, you are expected to read the detailed feedback given by the course staff. This feedback will help you self-assess your mastery of the course content.
Demonstration Exercises
The demonstration exercises, i.e., weekly homework, allows you to demonstrate mastery of the course’s learning outcomes through problems that put the course concepts into more practical, real-world contexts.
Demo responses will be graded in more depth than the other deliverables, specifically along two dimensions:
- Is the response correct? Does the response correctly answer the question(s) posed? Does it meet the specification outlined in the problem description?
- Is the response well-designed? Does it follow the design requirements and conventions appropriate to the medium? Is the deliverable clear, and does it communicate a proper understanding of both the problem and its solution?
Rather than using a point-based system that obscures these two dimensions, we codify these requirements with an EMRN rubric (an adaption of the “EMRF” rubric designed by Stutzman and Race). Demonstration responses are graded on a four-point scale:
- Excellent (E)
- Complete understanding of the material is evident.
- Exhibits, at worst, a few minor design errors and can serve as an exemplary solution for the course.
- Meets Expectations (M)
- Complete understanding of the material is evident without the need for further revision.
- Exhibits minor correctness or design errors that can improve the submission significantly if revised.
- Needs Revision (R)
- One or more misunderstandings of the material are evident from the work.
- Exhibits many minor errors or one or more major errors that necessitate revision.
- Not Completed (N)
- Not completed to a degree where understanding is evident.
Note that excellent ratings represent work that reflects mastery of the material and mindfulness towards producing quality work. To obtain excellent ratings, you should dedicate ample time to review and revise your work—just like writing a paper—before the deadline.
Each week, normally on Mondays, you are allowed turn in up to two demonstration exercises for grading, whether they are new submissions or revisions. This includes the Monday of finals week. Additionally, you may turn in a final two demos for grading by final deadline for all work.
If you are turning in a revision of a demonstration exercise, you must fill out the revision request form in addition to turning your work in to Gradescope to notify the course staff. If you do not fill out the revision request form, the course staff will be unable to grade your revision for that week.
Core Exams
Some of the course’s learning outcomes are core outcomes, demonstrable skills that you should be confident performing by the end of the semester. To directly assess your mastery of these skills, we will conduct a series of core exams during the semester. Core exams are in-class exams inspired by mastery-based testing practices found in mathematics.
Core exams consist of one problem for each core learning outcome of the course covered so far at the time of the exam. This includes all learning outcomes covered in previous core exams, allowing you reattempt problems if you missed them on previous exams!
Core problems are graded on a binary satisfactory (S)/non-satisfactory (N) scale where a satisfactory answer is completely correct (modulo minor flaws that are understandable given the timed, in-class nature of the exam). Note that, unlikely the demos, core problems more closely resemble the daily drills in terms of their scope and complexity.
Once you receive an S on a problem tied to a particular core outcome, you do not need to attempt additional problems connected to that outcome in subsequent exams, i.e., you have demonstrated mastery of that outcome, so you are done with it!
The final core exam period of the course, held during finals week, is a revision core exam. No new learning outcomes are introduced so that you have a final opportunity to demonstrate mastery of any core outcomes you have missed throughout the semester.
Final Deadline for All Work
Note that all work must be submitted by Friday, December 20, 5:00 PM CST . This is College policy and cannot be waived for any reason. If you find yourself needing to turn in work past this deadline, you must consult with me as soon as possible beforehand to submit an incomplete request for the course. Regarding incompletes:
- Incomplete requests are not automatically granted; make sure you have a backup plan in case your incomplete request is denied.
- The only work we will allow during the incomplete period are demonstration exercises.
Overall Letter Grades
Major letter grades for the course are determined by tiers, a collection of required grades from your demonstration exercises and core exams. You will receive the grade corresponding to the tier for which you meet all of the requirements. For example, if you qualify for the A tier in one category and the C tier in another category, then you qualify for the C tier overall as you only meet the requirements for a C among all the categories.
Note that I reserve the right to update the requirements for grades as circumstances dictate during the semester, e.g., if a deliverable is cut. However, I will always update the requirements so that they are no stricter than they were previously.
| Tier | Demonstration Exercises (11) | Core (15) |
|---|---|---|
| C |
|
At least 9 Ss |
| B |
|
At least 11 Ss |
| A |
|
At least 13 Ss |
- D: exactly one of the requirements of a C are met.
- F: no requirements for a C are met.
Plus/minus grades
To earn a plus/minus grade, you must have completed one tier’s requirements and partially meet the next tier’s requirements. This will arise in two situations: C/B and B/A. For example, you may completely meet the requirements of a C and meet the requirements of a B for demos, but not for core exams. In these situations, you will earn a minus grade for the higher tier, i.e., a B- if you are between a C and B and an A- if you are between a B and an A.
Be aware that if you are at an A tier for one deliverable category but at a C tier for another, then you fully qualify for the C tier and partially meet the requirements of the B tier and thus would earn a B-.
Daily drill and lab grades
You may miss turning in at most three daily drills and at most three lab exercises without penalty. After the first three missing drill or lab exercises, your overall letter grade will lower by one-third of a letter grade (i.e., A becomes A-, B- becomes a C+, C becomes a D) for every two additional deliverables you miss from that category. The following table summarizes this policy for concrete numbers of missed daily drills and labs through 9 although the policy extends to any number of missing assignments.
| Missed x/y daily/labs | 0–3 labs | 4 lab | 5 labs | 6 labs | 7 labs | 8 labs | 9 labs |
|---|---|---|---|---|---|---|---|
| 0–3 dailies | -0 | -1/3 | -1/3 | -2/3 | -2/3 | -1 | -1 |
| 4 dailies | -1/3 | -2/3 | -2/3 | -1 | -1 | -4/3 | -4/3 |
| 5 dailies | -1/3 | -2/3 | -2/3 | -1 | -1 | -4/3 | -4/3 |
| 6 dailies | -2/3 | -1 | -1 | -4/3 | -4/3 | -5/3 | -5/3 |
| 7 dailies | -2/3 | -1 | -1 | -4/3 | -4/3 | -5/3 | -5/3 |
| 8 dailies | -1 | -4/3 | -4/3 | -5/3 | -5/3 | -2 | -2 |
| 9 dailies | -1 | -4/3 | -4/3 | -5/3 | -5/3 | -2 | -2 |
Course Breakpoints
Our grading system offers flexibility, but at the cost of giving the illusion that if you fall behind in your work, there is always an opportunity to catch up. While this is true in theory, in practice, it is difficult to do so in many situations because of personal issues, competing courses, extracurricular obligations, etc. This flexibility also makes it difficult—for both you and myself—to determine when you have fallen behind in the course and need external help such as the course staff, tutors, or academic advising.
I encourage you to preemptively come to me for help and guidance if you feel like you are falling behind. However, to be more clear about when you might be falling behind in the course, I am tracking the following course breakpoints in your progress. When one of the following situations occurs:
- You have missed more than two classes in a row.
- You have used up either your “free” daily drill or lab assignments.
- You receive an N on a demo.
- You do not turn in any demos during a revision window in which you have outstanding demos that need revision.
- After a core examination, your total completed outcomes among all outstanding core outcomes is below 60%.
- You are otherwise at substantial risk of earning below a C in the course.
I will follow up with you and academic advising (via an academic alert) to check in, provide guidance, and develop a plan for getting back on track.
Help, Collaboration, and Academic Honesty
There are several resources—course staff, your peers, and external sources—that you can use to expedite your learning in the course. However, you must balance your use of external resources with the need to produce original work, so that we can assess your learning appropriately. To this end, we have several policies that describeou resources are permissible to use depending on the deliverable you are using them on.
The Instructor and Course Staff
Please use each course staff member’s preferred means of communication, e.g., email or Microsoft Teams DM, to communicate with them about individual issues concerning logistics, grades, demos, or core exam questions. Regardless of the medium, note that the course staff will generally not respond immediately to messages. However, we will check our messages at fixed times throught the day.
Peer Learning and Outside Resources
Utilizing discussion with peers and outside learning to facilitate your learning is a critical skill for success in computer science. However, at the same time, you must be aware that getting stuck and pushing through challenging problems is essential for robust learning. To this end, we allow the following forms of collaboration.
- You are encouraged to collaborate with your peers on daily drills and the labs. You may also consult the course staff, other people, and external resources, including AI-based completion tools. In all cases, you (or your group in the case of group work) should independently write up your solutions and cite all the resources you used in authoring your work.
- You may only discuss the demonstration exercises and core exam questions with the course staff. When completing these, you may only consult the course website and book when developing your solutions. You may not collaborate with peers, consult external resources, or share information about assignments with others.
Keep in mind that adaptation of pre-existing code or solutions whether it comes from a peer, myself, or the Internet, requires a citation in the cases where it is allowed.
In all cases, the work that you produce should be your own. The golden rule is that you should be capable of reproducing your deliverable on the spot with minimal effort if it was accidentally deleted.
If you feel that the stress and pressure of the course are compelling you to violate the academic honesty policies of the course and the college as explained in the student handbook, please talk to me as soon as possible. The course’s grading policies are designed to help you manage your time in light of the different stressors in your life. I will do my best to work with you to figure out how to help you better manage your time relative to your learning goals and desired achievement level for the course.
Sharing of Course Materials
While you retain copyright of the work you produce, we must still uphold the academic integrity of this course. To this end, you may not share copies of your assignments with others (unless otherwise allowed by the course policies) or upload your assignments to third-party websites unless substantial changes are made to the assignment (e.g., significant extensions and improvements to your code). Ultimately, it must be clear that the end product is significantly different from what was asked in the original assignment. I do recognize that there are times when you want to do this, e.g., uploading projects to Github for your resume, and so I encourage you to talk to me in advance so that we can ensure that you upload a meaningful project that does not run afoul of this policy.