Core Module 1: Logic

To-Do Date: Jan 16 at 11:59pm

The required reading for the first week/module is Chapter 2: Logic of the AIDMA textbook. This is one of the 3 textbooks that we will use as required reading for the core modules; you may want to download a local copy. Although only Chapter 2 is required, you may want to take a glance at the How to use this book page in the preface as well as Chapter 1: Motivation to get to know this book.

This book has many kinds of practice opportunities (Exercises, Fill in the details, Questions, Evaluates, Reading Comprehension Questions, and Problems – see the How to use this book page for details). Most of them are hyperlinked to their solutions for immediate checking of your comprehension of the material/concepts. We will not be using those officially in our class meetings very often (we sometimes do), but do take advantage of these questions to read actively.

If you already have a background and consider yourself adequately familiar with the module topic, you may find it tedious to read through the chapters sentence by sentence. It is okay for you in this case to skim the reading (or at least skip the practice questions in the book). Frankly, it is up to you how you use the reading. The bottom line is, by the start of each module’s first class meeting, we expect everyone to have a solid understanding of the basic concepts in the scope of the required reading. The prepare quiz is partially there to help you examine this.


To earn a satisfactory completion for CM1:

  • Read this required reading (and mark this post as done afterwards)
  • Get 80% or more questions correct in CM1: Logic Prepare Quiz (note that there’s a 1hr 15min cooldown between consecutive attempts)
  • Get a completion on recitation work by either attending or submitting on Gradescope
  • Get a satisfactory or above on the Gradescope assignment

OR

  • Get an excellent on all Gradescope assignment questions

Core Module 2: Proof Methods

To-Do Date: Jan 23 at 11:59pm

Reading: Chapter 1: What is a Proof? of MCS (our second textbook). Several notes:

  • MCS 1.1-1.2 are just a recap now, and we have already covered in class some basic inference rules such as Modus Ponens and Modus Tollens in MCS 1.4.1. Hopefully this eases you into the land of proofs.
  • Please be aware of the notational and stylistic inconsistencies between different textbooks. For two concrete examples:
    •  and ¬ are simply written as IMPLIES and NOT, respectively, in MCS 1.4.1. Note that this is not only because MCS introduces proofs before logic: the entire book doesn’t use logic operator symbols.
    • We write all premises (antecedents) of an inference rule on separated lines, whereas MCS writes them on a same line, delineated with commas.
      • On the other hand, AIDMA doesn’t even explicitly introduce inference rules. This is why we need multiple textbooks!
  • MCS Chapter 1 gives a nice overview of proof techniques. However, it does not really touch the question of what are proofs? Most of discrete math textbooks written for CS don’t bother. This is covered more in detail in our third textbook, MFADM in its Chapters 1 and 11. The reason that it is not used as our required reading is because it is more formal and (in my point of view) too overwhelming for this class.

To earn a satisfactory completion for CM2:

  • Get 80% or more questions correct in CM2: Proof Methods Prepare Quiz (note that there’s a 1hr 15min cooldown between consecutive attempts)
  • Get a completion on recitation work by either attending or submitting on Gradescope
  • Get a satisfactory or above on the Gradescope assignment
  • Get all 4 questions on the PrairieLearn homework (unlimited tries until LDoC)

OR

  • Get an excellent on all Gradescope assignment questions
  • Get all 4 questions on the PrairieLearn homework (unlimited tries until LDoC)

Core Module 3: Math Tools

To-Do Date: Jan 30 at 11:59pm

Reading: AIDMA Chapter 4.2, Chapter 6, and Chapter 7.1-7.2 (and maybe 7.3 for CS201 co-takers, see below). As a preview, they cover:

  • 4.2: covers division, the mod operator, and congruence.
  • Ch.6: covers sequences, recurrence relations, and evaluating sums and products.
  • 7.1-7.2: covers asymptotic notations (which includes the Big-O notation that will soon be covered in CS201, but also more) and growth rates of common positive functions.
  • 7.3: how to use asymptotic notations to analyze algorithms (useful for those in CS201 right now; may be boring for everyone else).
    • Alternatively, CS201 co-takers can take a look at past CS201 material on sorting/recursive algorithms (slide decks I and II). What we will probably need is how MergeSort works, which unfortunately isn’t covered until March this semester in CS201. So consider this a preview/frontload of later CS201 material and not extra work in CS230.

Several notes:

  • Your miles on these chapters may vary depending on how much background you already have with the topics. Depending on how much of the material is new to you, this week’s reading may feel rather long. Start early, especially if you need to read 7.3! You can reap your reward later in the semester. By the time CS201 covers the topic, you will be coasting.
  • You can safely skip the following parts:
    • Since AIDMA introduces set theory before these chapters, the text immediately following Thm 7.36, Fill-in-the-details 7.37, and Example 7.38 may not make sense yet for you. It is okay to skip those.
    • As long as limits are not totally foreign to you, you can safely skip the entire 7.1.4 (or do a casual skim to gloss over it.)

To earn a satisfactory completion for CM3:

  • Get 80% or more questions correct in CM3: Math Tools Prepare Quiz (note that there’s a 15min cooldown between consecutive attempts)
  • Get a completion on recitation work by either attending or submitting on Gradescope
  • Get a satisfactory or above on the Gradescope assignment

OR

  • Get an excellent on all Gradescope assignment questions

Core Module 4: Sets, Functions, and Relations

To-Do Date: Feb 6 at 11:59pm

This is a two-week module with 3 class meetings. Exam 1 will happen in class on 2/14 (Wednesday of the second week). This module is not part of Exam 1. 

There are two parts of required readings for this module, both covered in this post, each corresponding to a prepare quiz. We expect these materials to roughly correspond to the first two class meetings of this module (i.e., 2/7 and 2/9).

The third class meeting, 2/16, is after the exam. There is no required reading for the 2/16 class meeting. This is because:

  • Making you read new material between 2/9 and the exam on 2/14 distracts you from preparing for the exam.
  • You deserve a break after taking the exam.

Therefore, for the 2/16 class meeting, just show up in class with a fresh mind and learn everything from scratch in the lecture. This is also how we will run all of the EMs, but the 2/16 class is NOT part of an EM; it is part of Core Module 4: Sets, Functions, and Relations.


  • Reading Part 1: AIDMA Chapter 4.1 – corresponding to CM4: Prepare Quiz I (Sets) and the 2/7 class.
    • In Example 4.10 the textbook says “If it seems strange to talk about whether or not two infinite sets have the same number of elements, don’t worry too much about it. We probably won’t bring it up again.” That might be true for the AIDMA textbook, but we do plan to learn more about infinite sets and their cardinalities in the 2/16 class (so you can safely ignore that topic before Exam 1).
  • Reading Part 2: AIDMA Chapter 4.3-4.4 – corresponding to CM4: Prepare Quiz II (Functions and Relations) and the 2/9 class. Some important notes about definition inconsistencies between AIDMA, MCS, and this imperfect world:
    • Definition of functions.
      • In AIDMA and MFADM, functions are defined first, and relations are defined as a separate concept. It’s (hopefully) clear that some relations are functions and some are not.
      • In MCS, relations are defined first, and functions are defined as functional relations. (You can read MCS Chapter 4 if you’re curious, but I don’t recommend.)
      • How MCS defines functions is not how the rest of the world defines it. For the rest of the world to call a relation a function, it must be both functional and total. (This includes AIDMA and MFADM, although they do not explicitly use the words functional and total in how they introduce functions.)
      • Bottom line: it is usual for a math concept to be not uniformly agreed upon. We should be thankful when it is and accept it (and stay vigilant) when it is not.
    • Definition of partial relations. 
      • In both AIDMA/MFADM, partial orders are defined as reflexiveanti-symmetric, and transitive.
      • In MCS, the same concept is explicitly called a weak partial order, which implies there is also a concept known as a strict partial order.
      • Elsewhere in the world, people sometimes define partial orders in other ways (e.g., just anti-symmetric and transitive).
    • We will sort these all out in class, so you do not need to worry too much about these discrepancies. 

To earn a satisfactory completion for CM4:

  • Get 80% or more questions correct in both CM4: Prepare Quiz I (Sets) and CM4: Prepare Quiz II (Functions and Relations)
  • Get a completion on recitation work by either attending or submitting on Gradescope
  • Get a satisfactory or above on the Gradescope assignment
  • Get all questions on the PrairieLearn homework (unlimited tries until LDoC)OR
  • Get an excellent on all Gradescope assignment questions
  • Get all questions on the PrairieLearn homework (unlimited tries until LDoC)

Core Module 5: Inductions

To-Do Date: Feb 20 at 11:59pm

Reading: AIDMA Chapter 8 (many parts can be skipped if you’ve taken CS201, see below). As a preview, they cover:

  • 8.1: covers mathematical induction.
    • Induction is a hard topic to grasp at the first glance. If you find yourself confused by the first few pages of AIDMA 8.1, you may consider reading MCSLinks to an external site. 5.1 first before going back to AIDMA 8.1 again. This is because:
      • MCS 5.1 mainly discusses an easier variant of induction: it assumes there is only one base case P(0), while the theorem is to be proved for all nonnegative integers (so n≥0), which makes the concept marginally easier to understand.
      • On the other hand, AIDMA (more generally) defines the base case as P(a), which enables the theorem to be proved for all n≥a.
      • AIDMA also explicitly discusses more topics like the approach in doing induction proofs, which is why it is chosen as the official required reading.
    • In AIDMA Example 8.19, you will find the proof for the generalized form of De Morgan’s law, which we took for granted in the first few recitations.
  • 8.2: covers recursive algorithms. Can be skipped or a quick skim if taken CS201.
  • 8.3.1-8.3.3: covers solving recurrence relations… which we already discussed in module 3! So this should be a quick recap. Skip 8.3.4 (linear recurrence relations).
  • 8.4: analyzing recursive algorithms using recurrence relations; can be skipped or a quick skim if taken CS201.

There is no Canvas prepare quiz for CM5. Instead, please complete PL practice 5.


To earn a satisfactory completion for CM5:

Core Module 6: Graph Fundamentals Part I

This is a two-week module with 3 class meetings (2/28, 3/1, and 3/6). The 3/8 class meeting is for the EM (Graph Applications). 

CS201, CS230, and CS330 ALL cover graphs and trees. This is probably the most-overlapped topic within these 3 classes. However, the timing does not work out well for those who are taking CS201/230 at the same time: graphs and trees are usually the last part of CS201, and we cannot schedule our graph module after it. Instead, we will use a parallel approach: apart from the absolutely necessary (basic terminologies of graphs and trees), we try to minimize overlap in content. This implies we will put less emphasis on the following topics in CM6:

  • Binary search trees and its traversal
  • Depth-first search (DFS) and Breadth-first search (BFS) on general graphs
  • Shortest path algorithms (but we will discuss shortest paths as a mathematical concept)

It is hard to completely avoid discussing these topics altogether, but when we do, we will focus on graph theory concepts/high-level ideas. CS201/330 is/was/will be where you learn the details of graph algorithms. The graph applications EM will also cover some of them.


There are two parts of required readings for this module, each corresponding to a prepare quiz. This post covers the first part. The second part is covered in CM6: Required Reading Part II.

  • Reading Part I: AIDMA Chapter 10 – corresponding to CM6: Graph Fundamentals Prepare Quiz I.
    • If you have taken CS201, the first few subsections should be a quick brush up, and Section 10.5 can be safely skipped or glossed over – that section really just talks about adjacency lists and matrices, the two common ways to represent graphs.
    • Folks in CS201 will find the material to be a longer read (due to concept being new) but not necessarily a harder read.
    • Pay attention to the conceptual difference between (unrooted, undirected) trees in graph theory and the (usually rooted and directed) trees in CS201/data structures, especially for those who are in both classes at the same time.
  • Several notes:
    • In Definition 10.16, it is better to use the subset notation with equality () for both parts. We do want a graph to be a subgraph of itself, and AIDMA does not make that clear.
    • Section 10.6 (Problem Solving with Graphs) is part of the reading and should NOT be skipped. It is easy to miss it because the subsection title starts with the word “Problem”.

Core Module 6: Graph Fundamentals Part II

This is a two-week module with 3 class meetings (2/28, 3/1, and 3/6). The 3/8 class meeting is for the Elective Module (Graph Applications). 

There are two parts of required readings for this module, each corresponding to a prepare quiz. This post covers the second part. 

 

  • Reading Part II: MCS Chapter 10 (broadly) – corresponding to CM6: Graph Fundamentals Prepare Quiz II. We are now at the point where we start to see the ideas connecting with each other. This chapter is long, but a lot of it is old material in disguise. Read the following guide before the textbookEmphasized parts are bolded and optional parts are italicized.
    • 10.1 (re-)introduces the basic terms of graph theory again but strictly for digraphs. You may skip if you are confident that you now have a solid grasp on the terminologies. Beware of notational inconsistencies; for example, AIDMA uses G=(V,E) to describe a graph, while MCS goes with G=(V(G), E(G)). They also have slightly different notations for things such as in-degrees and out-degrees.
    • 10.2 and 10.3 are some known ideas (adjacency matrices) plus some newer ideas (shortest path, path counting from matrices). You may skip as long as you have a solid idea of what a shortest path mean.
    • 10.4, 10.5, and 10.6 connect directed acyclic graphs (DAGs) with partial orders. You should focus on the interconnection between these two concepts (why can we represent one with the other) more than the tedious details. Most of 10.6 can be skipped because we have already learned partial orders in Core Module 4: Sets, Functions, and RelationsBeware of the discrepancy in the definition of partial orders (see CM4: Overview and Required Reading (Important) and the class notes for CM4 for details).
    • 10.7 connects partial orders with subset relations. This part is optional.
    • 10.8 introduces linear orders as a special case of partial orders.
    • 10.9 introduces product orders. This part is optional.
    • 10.10 (re-)introduces equivalence relations again. You probably don’t need to read it once more.
    • 10.11 is a summary/review of all relational properties in both set theory and graph theory terms. It is a great resource to examine your comprehension of these two topics!

 

  • If you are also taking CS201 right now, you might want to read about Depth-First Search (DFS) and Breadth-First Search (BFS) on general graphs.
    • For 230 purposes, you do NOT need to know the implementation (recursive or iterative) in Java. What is important for CS230 is you know how conceptually these two search algorithms differ, and that they can be performed on general graphs instead of only trees.

To earn a satisfactory completion for CM6:

Core Module 7: Combinatorics

To-Do Date: Mar 21 at 11:59pm

Reading: AIDMA Chapter 9. 

  • Tired of long required reading instructions? Good news. There are no specific reading instructions this module – just read the entire chapter.

To earn a satisfactory completion for CM7:

  • Get 80% or more questions correct in CM7: Combinatorics Prepare Quiz
  • Get a completion on recitation work by either attending or submitting on Gradescope
  • Get a satisfactory or above on the Gradescope assignment
  • Get all 5 questions in the PL homework (unlimited tries until LDoC)OR
  • Get an excellent on all Gradescope assignment questions
  • Get all 5 questions in the PL homework (unlimited tries until LDoC)

Core Module 8: Graph Fundamentals Part I-II

CM8: Required Reading Part I-II

This is a two-week module (the last CM!) with 3 class meetings (4/3, 4/5, and 4/10). The 4/12 class meeting is for the Elective Module (Probability Applications). 

There are three parts of required readings for this module, each (roughly) corresponding to a prepare quiz and a class meeting’s worth of material. This post covers the first two parts that are due 4/2. The last part is covered in CM8: Required Reading Part III.

One general rule of the required reading this week is that you can safely skip all remarks about continuous probability in the textbook. In fact, it is recommended that you skip them if this is your first exposure to formal probability theory (so that you can focus on the discrete part). These are the parts “highlighted” in yellow in the provided PDF.


  • Reading Part I: MFADM Ch. 8.1-8.2 – corresponding to CM8: Probability Prepare Quiz I (Probability Basics and Conditional Probability)
    • I do not like Example 8.6 because it implies gender/sex is binary and a dichotomy. However, there are not that many free and available textbooks to choose from, and I am not sure any one of them is really identity-inclusive. If this example makes you uncomfortable, think about just throwing two fair coins, and the probability that both are heads given at least one is a head.
    • We will revisit the Monty Hall problem (Example 8.7) thoroughly in class; it is okay if you still feel somewhat confused after finishing reading it. This does not mean you can skip it in the reading.
    • There are four “theorems/rules” in Proposition 8.3. If you have some previous exposure to probability before (e.g., having done CS216), the so-called “Bayes’ Theorem” usually refers to the first one. Our textbook is more comprehensive and (rightfully) does not make it look like the first one is any more important than the other three.

Core Module 8: Graph Fundamentals Part III

CM8: Required Reading Part III

This is a two-week module (the last CM!) with 3 class meetings (4/3, 4/5, and 4/10). The 4/12 class meeting is for the Elective Module (Probability Applications). 

There are three parts of required readings for this module, each (roughly) corresponding to a prepare quiz and a class meeting’s worth of material. This post covers the last part that is due 4/9. The first two parts are covered in CM8: Required Reading Part I-II.

One general rule of the required reading this week is that you can safely skip all remarks about continuous probability in the textbook. In fact, it is recommended that you skip them if this is your first exposure to formal probability theory (so that you can focus on the discrete part). These are the parts “highlighted” in yellow in the provided PDF.


  • Reading Part III: MFADM Ch. 8.5-8.6+ a small part of 8.9 – corresponding to CM8: Probability Prepare Quiz III (Expectations and Deviations)
    • Ch. 8.6 has a lot of stuff that are deemed slightly too advanced and not part of this core module (they are all highlighted in yellow). However, towards the end of it is the Chebyshev’s inequality, which is part of the module (it is highlighted in green, so that you don’t accidentally skip it along with the skippable parts). Its proof in the textbook is optional; we will prove it in class again using Markov’s inequality.
    • Speaking of which Markov’s inequality is curiously put in Ch. 8.9 by the authors; please take a read there. It is also highlighted in green for you.

To earn a satisfactory completion for CM8: