Overview

An introduction to the discrete paradigm in mathematics and computer science. Topics include logic, set theory, number theory, induction, recursion, counting techniques, and graph theory.

Learning Goals

Upon completing this course, you will be able to:

• Translate natural language statements to and from formal propositional logic.

• Apply the rules of propositional logic to derive correct mathematical arguments.

• Recall and apply basic definitions, together with logical reasoning, to solve problems involving naive set theory, number theory, combinatorics, and graph theory.

• Solve problems using recursion and induction.

• Write coherent mathematical proofs using proper mathematical notation and reasoning.

Resources

Optional Resources

---

Calendar

Date	Topic	Notes
	= video     = PDF     = disco code
W 1/18	Introduction to Disco
F 1/20	Syllabus and more Disco	CSCI student info survey due
		Module 0 assigned
M 1/23	Propositional logic	Grading contract due
W 1/25	Implication & logical equivalences
F 1/27	Logical equivalences	Module 0 due, Module 1 assigned
M 1/30	Predicates & Quantifiers
W 2/1	No class (ice)
F 2/3	Nested & restricted quantifiers	Module 1 due, Module 2 assigned
M 2/6	More quantifiers, intro to proofs
W 2/8	Proofs	How to Prove Things
F 2/10	Proof examples	Module 2 due, Module 3 assigned
M 2/13	Proof by contradiction
	Introduction to set theory
W 2/15	Sets in Disco, subsets, empty set
F 2/17	Set operations	Module 3 due, Module 4 assigned
M 2/20	No class (midwinter break)
W 2/22	Functions	Grading contract evaluation due
F 2/24	1-1 and onto functions	Module 4 due, Exam 1 take-home problems posted
M 2/27	Bijections and countable sets
W 3/1	Countable and uncountable sets
F 3/3	Midterm exam 1	Module 5 assigned
M 3/6	LaTeX	Writing project 1 assigned
W 3/8	Divisibility
F 3/10	Modular equivalence	Module 5 due, Module 6 assigned
M 3/13	More modular equivalence
W 3/15	Primes
F 3/17	GCD and the Euclidean Algorithm	Module 6 due
M 3/20	No class (spring break)
W 3/22	No class (spring break)
F 3/24	No class (spring break)
M 3/27	Bézout’s Theorem and Modular Inverses
W 3/29	Fermat’s Little Theorem
F 3/31	RSA	Grading contract evaluation due
		Writing project 1 due
		Module 7 assigned
M 4/3	Sequences
T 4/4		Exam 2 take-home problems posted
W 4/5	Induction
	Additional induction examples:
F 4/7	Strong induction	Module 7 due, Module 8 assigned
		Writing project 2 assigned
M 4/10	Midterm exam 2
W 4/12	Intro to combinatorics, product rule
	Product rule examples
F 4/14	Addition and subtraction rules, PIE
M 4/17	Division rule and binomial coefficients	Module 8 due
W 4/19	Binomial coefficients	Module 9 assigned
F 4/21	No class	Writing project 2 due
M 4/24	Introduction to graphs
W 4/26	Vertex degrees, Eulerian paths
F 4/28	Hierholzer’s Algorithm	Module 9 due
M 5/8	Final exam, 8:30-11:30am
	Practice problems

---

Grading

Grading contracts

In this course, you determine your own final grade: you will prepare and submit for my approval a grading contract explaining your chosen final grade and what you will do to achieve it. You will then earn your chosen final grade by fulfilling the agreed-upon contract.

This may be different than what you are used to. Professor Cathy Davidson of CUNY perfectly sums up the reasons for doing things this way:

The advantage of contract grading is that you, the student, decide how much work you wish to do this semester; if you complete that work on time and satisfactorily, you will receive the grade for which you contracted. This means planning ahead, thinking about all of your obligations and responsibilities this semester and also determining what grade you want or need in this course. The advantage of contract grading to the professor is no whining, no special pleading, on the student’s part. If you complete the work you contracted for, you get the grade. Done. I respect the student who only needs a C, who has other obligations that preclude doing all of the requirements to earn an A in the course, and who contracts for the C and carries out the contract perfectly.

Required components of a grading contract

There is no specific format required for a grading contract, but it must have the following components:

• Your desired course grade. You may choose to contract for an A, B, or C (if you’re wondering about D’s and F’s, see below). Note that your grading contract should not explain the reasons for your choice. I will not judge you because of your choice, and you do not need to justify it: there are as many different valid reasons for choosing to work toward a particular final grade as there are students. If you do wish to explain to me the reasons for your choice—which you are in no way required to do—you may do so in an email, a personal conversation, etc., but it should not go in your contract.

• A description of the work and requirements you will complete, in checklist format. It doesn’t have to be super detailed, but you do have to explicitly include everything. For example, you can’t just say “I will complete all the assignments listed in the syllabus”; you must actually list them. This is so that you and I both know that you are explicitly aware of the requirements, and to help you keep track of what you have completed and what you have yet to complete. You also have some choice in terms of which assignments you complete, so you must record your choice in the contract.

  Note that at the beginning of the semester you may not have a very good idea about this. For example, if you need to complete eight modules, it’s not reasonable to insist that you know which specific modules you plan to complete. However, you can refine your contract over the course of the semester. You just have to put something to start; for example, a reasonable default would be to plan to complete the first eight modules assigned.

Example grading contract

For example, a grading contract might look like this:

My desired course grade in Discrete Math is a C. To achieve this grade, I will complete the following:

• CSCI student info survey
• Grading contract
  • Submit grading contract
  • Grading contract evaluation 1
  • Grading contract evaluation 2
• Modules (8)
  • Module 0
  • Module 1
  • Module 2
  • Module 3
  • Module 4
  • Module 6
  • Module 9
  • Module 10
• Writing project 1
• Exams (2)
  • Midterm 1
  • Midterm 2

Grading contract submission

You must turn in an initial proposed grading contract by the start of class on Monday, January 23rd. After the initial submission, I may require some revisions before I approve your contract.

Contract evaluation and adjustment

Two times during the semester (Wednesday, February 22 and Friday, March 31) you are required to reflect on your progress in the course and complete an evaluation of your work, comparing it against what you agreed to in your grading contract. Your evaluation should:

1. Contain a copy of your original grading contract, with items you have completed checked off.

2. Revise your grading contract with more specific details as appropriate, for example, regarding which modules and writing projects you intend to complete.

3. Include a 1-2 paragraph reflection, which answers questions such as the following:

   • What have you done well?
   • What have you learned?
   • What could you do to improve your learning?
   • What could I (the instructor) do to improve your learning?
   • Are there ways in which you have not lived up to the requirements of your contract, and if so, what steps are you taking, or will you take, to rectify that?

Your evaluation is also an opportunity to request an adjustment to your contract in either direction. If you find that you will be unable to meet the obligations of your contract, you may request to move to the next lowest grade and its requirements. Contrariwise, if you find that you’ve been performing above the obligations of your contract, you may request to fulfill the requirements for the next higher grade.

Note, however, that you don’t have to wait for an evaluation to adjust your contract. If your life has really gone off the rails (or if, say, you are finding the class easier and more enjoyable than you thought!) just come and talk to me about adjusting your contract.

A, B, and C grades

• To earn an A in the course, you must:
  • Complete the CSCI student information survey.
  • Submit and agree on a grading contract with the instructor.
  • Complete two grading contract evaluations.
  • Complete all but one assigned modules.
  • Complete two writing projects.
  • Complete all three exams.
• Or, to earn a B in the course, you must:
  • Complete the CSCI student information survey.
  • Submit and agree on a grading contract with the instructor.
  • Complete two grading contract evaluations.
  • Complete all but two assigned modules.
  • Complete two writing projects.
  • Complete two exams.
• Or, to earn a C in the course, you must:
  • Complete the CSCI student information survey.
  • Submit and agree on a grading contract with the instructor.
  • Complete two grading contract evaluations.
  • Complete all but four assigned modules.
  • Complete one writing project.
  • Complete two exams.

D and F grades

[Adapted from Cathy Davidson.] You cannot intentionally contract for a grade of D (and certainly not for an F). However, I reserve the right to award a grade of D or F to anyone who fails to meet their contractual obligations in a systematic way. A “D” grade denotes some minimal fulfilling of the contract; an “F” denotes absence of enough satisfactory work, as contracted, to warrant passing of the course. Both a “D” and “F” denote a breakdown of the contractual relationship.

---

Modules

There will be a number of modules corresponding to topics in the course. Each module consists of things like problems to solve, programming assignments to complete, and/or readings. Each item on a module will be graded on a 0-4 scale:

• 4: the solution is complete and correct.
• 3: the solution has all the right big ideas, but may be somewhat incomplete and/or get a few details wrong.
• 2: the solution has some correct ideas, but has some big holes or conceptual errors.
• 1: the problem was attempted, but the solution is substantially incorrect or incomplete.
• 0: the problem is missing.

To get credit for a module, the average score on the items must be at least 3.25.

If you do not get credit for a module, you may revise it; see the resubmission policy below.

#	Module	Resources	Assigned	Due
0	Introduction to Disco		F 20 Jan	F 27 Jan
1	Propositional logic		F 27 Jan	F 3 Feb
2	Quantifiers		F 3 Feb	F 10 Feb
3	Proofs	How to Prove Things	F 10 Feb	F 17 Feb
4	Sets		F 17 Feb	F 24 Feb
5	Functions		F 3 Mar	F 10 Mar
6	Divisibility		F 10 Mar	F 17 Mar
7	Number theory		F 31 Mar	F 7 Apr
8	Sequences & Induction		F 7 Apr	M 17 Apr
9	Combinatorics		W 19 Apr	F 28 Apr

Module submission policy

• I encourage you to work together on problems; however, problem solutions must be your own work, and academic integrity will be taken seriously.

• Problem solutions should be written or typed neatly, and turned in electronically via this Google form. Submissions must be in PDF format (Word, Pages, etc. can export a PDF, typically as an option under the “File” menu).

  • You may also write your problem solutions on physical paper and scan them using an app such as Genius Scan which can export your document as a PDF.

Writing projects

You will complete two writing projects during the semester, either individually or in groups of two. The projects will give you an opportunity to tackle some bigger problems, and focus on putting details together into a coherent written exposition. You are required to write up your projects using the LaTeX typesetting system.

You will have two weeks to complete each project:

• Project 1 will be assigned Friday, March 3 and due Friday, March 31.
• Project 2 will be assigned Friday, April 7 and due Friday, April 21.

More details about each project will be made available when it is assigned.

Exams

There will be three in-class exams in the course, two midterm exams and a cumulative final exam. Exams will typically have two types of questions:

• Long-answer questions, such as proofs. You will be told these questions at least one week in advance and will be able to prepare your solution; however, you will not be able to bring any notes with you into the exam.

• Short-answer questions. You will not be given these questions ahead of time. However, Dr. Yorgey will provide resources such as information about what type of questions to expect and/or practice problems.

Exam grading

Exam problems will be graded in the same manner as homework problems. To receive credit for an exam, you must score an average of 3.0 or better on the exam problems.

Exam revision

If you do not receive credit for an exam, you may revise it; see the resubmission policy below.

However, if you score 2 or lower on an exam problem, Dr. Yorgey may also require you to complete an additional, similar problem. This additional problem must be completed under similar conditions as the original exam (that is, you may prepare a solution ahead of time using any resources you wish, but then you must write out your solution without referring to any resources, at an agreed-upon time). To receive credit for the exam you must score an average of 3.0 or better on all the exam problems, including any newly assigned problems.

---

Tokens, late submissions, and resubmissions

Each student starts the semester with three virtual tokens which they can spend however they wish. Tokens are non-transferable.

• One token may be spent to turn in any assignment late.
  • All assignments must be submitted at the latest by the last day of final exams, Tuesday, May 9.
• 1/2 token may be spent to submit a revised homework assignment or project at any time.
• Note that group members must spend one token each to turn in a late project, or 1/2 token each to turn in a revised project.
  • If one group member does not have enough tokens, don’t let it stop you from submitting a late or revised module: that group member will simply not be eligible to get credit for the module until they obtain sufficient tokens.

Conversely, additional tokens may be earned in the following ways:

• Scheduling and attending an office hours meeting with Dr. Yorgey earns 1/2 token.
• Creating a practice problem for some topic covered in the course, along with a correct solution, earns 1/2 token.
• Creating some sort of educational material for the course earns 2 tokens.
  • Examples of the sorts of things you might create include (but are not limited to):
    • A video or animation explaining a concept from the course
    • A document with explanation or examples of concepts from the course
  • To earn a token the educational material must, in my judgment, be potentially helpful to other Discrete Math students, present or future. If your educational material does not meet this criterion, I will work with you to revise it until it does.
  • With your permission, and appropriate attribution, materials you create will be posted to the course website.
• Opening a github issue with a good bug report or suggestion for Disco earns 1 token.

---

Expectations

Although you and I play different roles in the course, we both have your learning as a common goal. There are things I expect from you as a student in the course, but there are also things you can expect of me as the course instructor and facilitator.

If I am not fulfilling my responsibilities outlined below, you are welcome (and encouraged!) to call me out, perhaps via the anonymous feedback form. I will also initiate a conversation if you are not fulfilling yours. However, none of us will meet all of the expectations perfectly—me included!—so it’s also important that we have grace and patience with one another.

	What I expect from you	What you can expect from me
Communication	Check your email and Teams for occasional course announcements. Let me know via email or Teams message if you will need to miss class for some reason. Let me know as soon as possible if you feel you are struggling, would like extra help, or have something going on that will affect your engagement in the course or your ability to fulfill your responsibilities.	Clearly communicate expectations, assignment details and dates, and grading standards. Return grades and feedback on submitted work within two business days of submission. Respond to emails within 24 hours.
Preparation	Come prepared to fully engage in class meetings, with distractions minimized, to the best of your ability. Spend time outside of class actively practicing unfamiliar or shaky concepts or skills (not just reading over notes).	Have a concrete plan for how we will spend each class meeting, prepared to lead you through the plan. Complete all modules and projects myself, to help ensure they are reasonable and don't hold any unintended surprises.
Engagement	Actively engage in lectures by taking notes and asking questions. Abide by the College's Academic Integrity Policy and the Computer Science-specific Academic Integrity Policy.	Make myself available to meet outside of class, and give you my full attention during a meeting. Be committed to your learning, open to feedback and willing to respond in substantive ways to your suggestions or concerns.

Attendance

Attendance in this class is expected, though not required as part of your grade. I appreciate you letting me know when you will need to miss class.

Academic integrity

Hendrix College is committed to high standards of honesty and fairness in academic pursuits. Such standards are central to the process of intellectual inquiry, the development of character, and the preservation of the integrity of the community. Please familiarize yourself with the statement of Academic Integrity.

You should also familiarize yourself with the Computer Science-specific Academic Integrity Policy.

Disabilities

If you have a documented disability or some other reason that you cannot meet the above expectations, and/or your learning would be best served by a modification to the usual course policies, I would be happy to work with you—please get in touch (via Teams or email)! The course policies are just a means to an end; I don’t care about the policies per se but I do care about you and your learning.

It is the policy of Hendrix College to accommodate students with disabilities, pursuant to federal and state law. Students should contact Julie Brown in the Office of Academic Success (505.2954; brownj@hendrix.edu) to begin the accommodation process. Any student seeking accommodation in relation to a recognized disability should inform the instructor at the beginning of the course.

Diversity and Inclusion

Hendrix College values a diverse learning environment as outlined in the College’s Statement on Diversity. All members of this community are expected to contribute to a respectful, welcoming, and inclusive environment for every other member of the community. If you believe you have been the subject of discrimination please contact the Dean of Students Office (Mike Leblanc, leblanc@hendrix.edu, 501-450-1222) or the Title IX Coordinator (Jennifer Fulbright, fulbright@hendrix.edu, 501-505-2901). If you have ideas for improving the inclusivity of the classroom experience please feel free to contact me. For more information on Hendrix non-discrimination policies, visit hendrix.edu/nondiscrimination.

Mental and Physical Health

Hendrix recognizes that many students face mental and/or physical health challenges. If your health status will impact attendance or assignments, please communicate with me as soon as possible. If you would like to implement academic accommodations, contact Julie Brown in the office of Academic Success (brownj@hendrix.edu). To maintain optimal health, please make use of free campus resources like the Hendrix Medical Clinic or Counseling Services (501.450.1448). Your health is important, and I care more about your health and well-being than I do about this class!