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 set theory, number theory, and combinatorics.

• Solve problems using recursion and induction.

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

Resources

Disco

Disco language reference

Lecture notes

Optional Resources

Discrete Mathematics
and its Applications

How to Prove It

Calendar

Below is a unified calendar for the semester showing the topic for each class meeting, as well as assignment due dates. Some specifics may change as the semester progresses, but the calendar will be kept up-to-date.

Module	Date	Activity / Lecture	LGs	Assignments & Resources
Introduction to Disco + MATH 240	W 22 Jan	MATH 240 syllabus		HW: CSCI student survey, install Disco
	F 24 Jan	Introduction to Disco		HW (due 2/3): hw0.disco ( solution )
Logic and Proof	M 27 Jan	Propositional logic	L1
	W 29 Jan	Implication & logical equivalence	L1	HW: L1, L4 problems (due Monday 2/3)
				HW 1 (L1, L4) solutions
				Challenge HW (1 engagement point): hwc1.disco
	F 31 Jan	Algebraic laws for propositional logic	L2, L3
	M 3 Feb	Predicates & quantifiers	L4
	W 5 Feb	More quantifiers	L4, L5	HW 2: L2-L5 problems (due Monday 2/10)
				HW 2 (L2-L5) solutions
	F 7 Feb	Restricted quantifiers	L4, L5
	M 10 Feb	Introduction to proofs	P1	How to Prove Things
	W 12 Feb	Proofs & propositional logic	P1	HW 3: P1 problems (due Tuesday 2/18)
				HW 3 solutions
				Challenge HW 2 (1 pt)
				Challenge HW 3 (2 pts)
	F 14 Feb	More proof examples (contrapositive)	P1
Set Theory	M 17 Feb	No class (Mid-winter break)
	W 19 Feb	No class (snow)
	F 21 Feb	Introduction to set theory	S1, S2
	M 24 Feb	Set operations	S2, P2
	W 26 Feb	More set operations	S2, S3
	F 28 Feb	Product and sum types in Disco	S4
Relations + Functions	M 3 Mar	Relations	F1
	W 5 Mar	Equivalence relations	F1
	F 7 Mar	Functions	F2
	M 10 Mar	1-1 and onto functions	F3, P3
	W 12 Mar	Bijections and countable sets	F4
	F 14 Mar	Countable and uncountable sets	F4
Recursion + Induction	M 17 Mar	Sequences and recurrences	R1, R2
	W 19 Mar	Sums	R3
	F 21 Mar	Solving recurrences	R4
	M 24 Mar	No class (Spring break)
	W 26 Mar	No class (Spring break)
	F 28 Mar	No class (Spring break)
	M 31 Mar	Induction	R4, P4
	W 2 Apr	Strong induction	P4
	F 4 Apr	More induction examples	P4
Number Theory	M 7 Apr	Divisibility	N1
	W 9 Apr	Modular equivalence	N4
	F 11 Apr	More modular equivalence	N4
	M 14 Apr	Primes
	W 16 Apr	GCD and the Euclidean Algorithm	N2, N4
	F 18 Apr	Bézout’s Theorem and Modular Inverses	N3, N4
	M 21 Apr	Fermat’s Little Theorem	N5
	W 23 Apr	RSA
Combinatorics	F 25 Apr	Intro to combinatorics, product rule	C1
	M 28 Apr	Addition and subtraction rules	C1
	W 30 Apr	Division rule and binomial coefficients	C2
	F 2 May	Binomial coefficients	C2
	M 12 May	Final exam

Coursework

Your work in the course will consist of two main elements: homework and quizzes.

Homework

• Homework problems will be assigned every day, with all homework for each week typically due the following Monday by 5pm. Model solutions to homework problems will be posted a day or two after they are due.

• Homework will be graded only for completion/effort on a credit/no credit basis, and earns engagement points.

• Homework assignments may be completed individually or with a partner. Groups larger than 2 are not allowed.

• 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.

• There may be occasional Challenge homework assignments posted, which cover slightly more in-depth topics and/or ask you to synthesize multiple learning goals. Such Challenge assignments are optional but provide extra engagement points.

  • Challenge HW 1 (1 point)
  • Challenge HW 2 (1 point)
  • Challenge HW 3 (2 points)

Quizzes

There will be a quiz every Friday in class. Each quiz will cover certain specific learning goals, and will have one question per (clearly marked) learning goal.

• The quiz problems will be similar to homework problems assigned previously.

• You may complete as many or as few of the problems on a quiz as you wish.

• Each question is graded individually, on a two-level scale of (S)atisfactory/(N)ot Yet, along with written feedback.

  • A grade of (S)atisfactory means you have demonstrated a proficient understanding of the learning goal. Satisfactory does not necessarily mean “perfect”; there can be one or two mistakes as long as they are not central to the learning goal.

  • A grade of (N)ot Yet means you have not yet demonstrated proficient understanding of the learning goal. However, along with the Not Yet grade, I will provide written feedback which you can use to revise your understanding, and take the opportunity to try again on the next week’s quiz.

• Normally, make-up quizzes will not be offered. If you miss a quiz, you will have an opportunity to demonstrate proficiency on the same learning goals on a subsequent quiz.

• In exceptional circumstances, however (e.g. missing multiple consecutive quizzes due to illness or sports), let me know and we can work out an alternative.

Final Quiz

The final quiz will take place during the final exam slot, on Monday, May 12, from 8:30-11:30am. It will consist of one question per learning goal from the entire course, providing you with one last opportunity to demonstrate proficiency on any learning goals you missed. If you have already demonstrated proficiency on enough learning goals to earn your desired final grade in the course, you do not have to take the final quiz.

Grading

Standards-Based Grading

This course uses standards-based grading. There are a number of standards or learning goals for the course (listed below), and your final grade in the course is determined primarily by the number of standards in which you have demonstrated proficiency. You do not get a grade for quizzes; rather, quizzes are just a means for you to demonstrate proficiency in one or more learning goals.

Learning Goals

Core learning goals are highlighted.

• Module 1: Propositional Logic + Proofs
  • L1: I can make truth tables for propositional logic expressions involving TRUE, FALSE, AND, OR, NOT, IMPLIES, IFF, and variables.
  • L2: I can use algebraic laws to rewrite and simplify, or prove the equivalence of, formulas of propositional logic.
  • L3: I can use De Morgan laws to simplify negations of propositions with quantifiers, AND, and OR.
  • L4: I can formalize English statements as propositional logic formulas, making appropriate use of logical connectives and nested quantifiers.
  • L5: I can express quantified statements in equivalent ways with different domains.
  • P1: I can write an appropriate proof outline for a given propositional logic formula.
• Module 2: Set Theory
  • S1: I can state the definitions, and determine membership, of standard sets such as N, Z, Q, and R.
  • S2: I can evaluate and construct sets using union, intersection, difference, and complement of sets, and sets defined via set comprehension notation.
  • S3: I can list all the elements in a power set, Cartesian product, or disjoint union of sets, or count them without listing them all.
  • S4: I can use pattern-matching to write Disco functions using product and sum types.
  • P2: I can write proofs about sets, set operations, and the subset relation.
• Module 3: Relations + Functions
  • F1: I can determine whether a relation is reflexive, transitive, symmetric, antisymmetric, an equivalence, or a congruence with respect to some operation, and give examples of relations with these properties.
  • F2: I can draw pictures to model the behavior of a function.
  • F3: I can determine whether a given function is 1-1 and/or onto.
  • F4: I can show that two sets have the same cardinality by constructing a bijection between them.
  • P3: I can write proofs about 1-1, onto, and bijective functions.
• Module 4: Recursion + Induction
  • R1: I can compute the terms of a sequence defined via a recurrence.
  • R2: I can implement recurrences as recursive Disco functions.
  • R3: I can evaluate sums involving arithmetic and geometric series.
  • R4: I can come up with closed forms for recurrences and prove them via induction.
  • P4: I can write the outline of a proof by (weak) induction or strong induction.
• Module 5: Number Theory
  • N1: I can determine whether one integer is divisible by another, and calculate quotients and remainders according to the Division Algorithm.
  • N2: I can compute the greatest common divisor of two natural numbers using the Euclidean Algorithm.
  • N3: I can compute Bézout coefficients and modular inverses using the Extended Euclidean Algorithm.
  • N4: I can solve modular equivalences in one variable involving addition, subtraction, and multiplication by a constant.
  • N5: I can apply Fermat’s Little Theorem to test for primality.
• Module 6: Combinatorics
  • C1: I can use the product, addition, and subtraction rules to count things.
  • C2: I can use the division rule and binomial coefficients to count things.

Learning goal cycle

The below is an illustration of the cycle for a hypothetical learning goal “LG8”, introduced in week n:

• Week n: Learning goal LG8 is introduced in class + homework problems are assigned.
• Week (n+1) (Monday): Homework problems for LG8 are due.
• Week (n+1) (Friday): The first quiz including a problem on LG8. This is your first opportunity to demonstrate proficiency with LG8.
• Week (n+2) (Friday): LG8 appears on the weekly quiz again.
• Week (n+3) (Friday): LG8 appears on the weekly quiz for the third and final time.
• Final quiz: LG8 appears one last time (along with all learning goals) on the final quiz at the end of the semester.

That is, each learning goal will be covered in class at some point, with homework problems assigned. The homework is due Monday of the next week, and the quiz on Friday of the next week will include a question on that learning goal. The learning goal will stay on the weekly quizzes for a total of three weeks until it drops off again. If you do not manage to demonstrate proficient understanding of a learning goal within those three quizzes, you will have to wait until the final quiz for another chance. This is partly to motivate you to stay on top of the material, and partly to keep quizzes from becoming completely unwieldy.

Engagement

There are a number of ways you can be engaged with the course that contribute to, but do not directly demonstrate, learning. These activities will earn you engagement points; to get a given final grade you must meet a certain required threshold of engagement points.

• Filling out CSCI survey: 1 pt
• Attendance: 1 pt per class
  • An excused absence is also worth 1 pt, if you let me know ahead of time that you will miss class (or as soon as possible afterwards in case of illness or emergency).
• Homework: 3 pts per assignment
  • 3 points for a complete, on-time HW submission
  • 1 point off for a late submission
  • 1 point off for an incomplete submission
• Challenge homework: 1-3 pts per assignment
• Office hours: 1 pt per office hour meeting, up to a max of 15
• Review/practice problems: 1 pt each, up to a max of 15
  • Review/practice problems you create can be submitted via the HW submission form. You must list the relevant learning goal and include a correct solution. Practice problems meeting these criteria will be posted for the class to use.

There will be about 120-130 total engagement points available over the entire semester. Perfect attendance + homework submission with no challenge HW, office hours, or practice problem submissions would earn 80 points.

Final Grades

Your final grade will be determined according to the below table. To get a particular grade, you must meet or exceed all the criteria in that row.

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.

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 (Donna Eddleman, eddleman@hendrix.edu, 501-450-1230 ) 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!