Discrete 2021: Topics

1 Use Statements and Propositions.

1.1 Analyze Propositions and Boolean Expressions Description This subsection should introduce all 5 Boolean connectors (\( \neg \), \( \wedge \), \( \vee \), \( \rightarrow \), \( \leftrightarrow \)), their truth tables.
(Rosen2019, p.1-13)Propositional Logic   (Brehm2018_1_1)Propositional Logic
1.1.1. Define what is a proposition
Mention non-proposition sentences, include trickier situations (contradictory self-referential statements)
1.1.2. Define Boolean operations (\( \neg, \wedge, \vee, \rightarrow, \leftrightarrow \))
Define Boolean operations through its natural language equivalent and its truth table.
1.1.3. Create truth tables for expressions
Show how to evaluate expressions starting from subexpressions by plugging in the True/False values.
1.1.4. Introduce the formal concepts of precedence and associativity.
Explain that power operation (\( 2^{3^4} \)) as well as the logical implication (\( A \rightarrow B \rightarrow C \)) are right-associative - they group from the right to the left.
1.1.5. Restore parentheses in a Boolean expression using precedence (e.g. negation has the highest priority, conjunction is done before disjunction). Draw syntax trees showing evaluation order.
Show that Boolean expressions is one specific case of expressions (along with arithmetic, polynomials, etc.) May also illustrate precedence (arithmetic, comparisons, Booleans) in some programming language.
1.2 Create propositional statements Description Solve some word problems with propositional logic. We should pay special attention to cases where the connectors can be misunderstood or their everyday meaning differs from the formal one.
(Rosen2019, p.17-22)Applications of Propositional Logic   (Brehm2018_1_2)Applications of Propositional Logic
1.2.1. Translate English into Propositional logic.
Given a statement in English and atomic propositions, write its Boolean expression.
1.2.2. Recognize situations when natural language uses logical connectives in a different sense.
Analyze phrases expressing inclusive and exclusive OR; various ways to express implications (“sufficient”, “necessary”, “whenever”, “if”, “only if”, “if and only if”)
1.2.3. Solve Logic Puzzles and Word Problems based on propositional logic
Use case analysis and other simple methods to establish truth values of propositions, if some incomplete information about the situation is given.
1.2.4. Use Boolean expressions in programming.
Apply short-circuit Boolean evaluation in some programming language such as Python. Lazy and eager evaluation (and distinguishing them by side-effects). Explain how "if” statements differ from implications in propositional calculus.
1.3 Identify tautologies, contradictions and satisfiable expressions Description Perform equivalent transformations of Boolean expressions (here we use equivalences not as Boolean connectors that may sometimes return “False”, but as a way to write Boolean identities that are universaly true). Also solve satisfiablility of Boolean problems in a more general sense - even when they are not equivalences.
(Rosen2019, p.26-33)Propositional Equivalences   (Brehm2018_1_3)Propositional Equivalences
1.3.1. Check tautologies using truth tables
Tasks may include other manipulations on truth tables (building jus the "interesting" parts of tables; finding which values must take certain values)
1.3.2. Rewrite propositions using equivalences
Simplify Boolean statements using Boolean identities (double negation; De Morgan's laws; Contrapositive for an Implication; distributive laws and so on)
1.3.3. Identify tautologies, satisfiable statements and contradictions
Describe tautologies, satisfiable expressions and contradictions in terms of truth tables. Prove or disprove Boolean tautologies; check satisfiability of Boolean expressions. In all these situations try to pare down the truth tables to find "interesting" subcases to check (get used to avoid mechanistical approach to verify all 2^n rows in a truth table as this would be error-prone and slow).
1.3.4. Create new tautologies from existing ones using inference rules.
Use syllogisms like Modus Ponens and other inference rules to derive logical formulas.
1.3.5. Convert every Boolean expression to its CNF and DNF
Use truth table to construct CNF or DNF; make it shorter by combining similar terms.
1.3.6. Draw a Boolean circuit, try to use limited number of elements.
Draw Boolean circuits where you are allowed to reuse the same subexpression output in multiple inputs.
1.4 Use Predicates and Quantifiers Description This subsection introduces predicates as expressions depending on variables and "naive" concept of quantifiers (universal quantifier is just a long conjunction; existential quantifier is just a long disjunction)
(Rosen2019, p.40-55)Predicates and Quantifiers   (Brehm2018_1_4)Predicates and Quantifiers
1.4.1. Define a predicate as a function to booleans.
Interpret commonly known math concepts (inequalities, relations in geometry) as predicates.
1.4.2. Analyze syntax and restore parentheses in quantifier expressions.
Draw syntax trees, define scopes of variables, recognize free and bound variables.
1.4.3. Interpret quantifiers over finite domains as long conjunction (\( \forall \)) or long disjunction (\( \exists \))
Given value table for some predicate on a finite domain, evaluate quantifier expressions.
1.4.4. Check the syntax in quantifier expressions
Use precedence rules, restore parentheses, avoid ambiguities with set domains.
1.4.5. Apply simple manipulations to predicate/quantifier expressions (apply negations, rename variables, apply other tautologies).
Negate predicates applying De Morgan's laws.

1.5 Use Nested Quantifiers Description This section does not cover much new material; it is useful as a reminder - how to use the first order logic to explain everyday situations.
(Rosen2019, p.60-68)Nested Quantifiers   (Brehm2018_1_5_2)Translating with Nested Quantifiers
1.5.1. Rewrite English sentences and mathematical statements with nested quantifiers.
Formalize English sentences and some mathematical statements into propositional logic and simple (1st order; no more than 2 nesting levels) predicate calculus.
1.5.2. Interpret quantifier expressions in human language (Show the difference between "For every person there exists a father" vs. "There exists a father for everyone")
1.5.3. Negate multiple quantifiers using De Morgan's laws and other equivalence rules.Evaluate Boolean expressions (and also predicate/quantifier expressions over simple or finite sets). May need to introduce simple relations (square tables with True/False) to illustrate how predicates/quantifiers operate.
1.5.4. Rewrite popular mathematical concepts (divisibility, being a prime number, monotonicity, boundedness, continuity, existence of a limit, existence of a derivative) with predicates and quantifiers
1.6 Use Rules of Inference Description This section is meant to introduce some Aristotelian and other traditional logic reasoning (modus ponens, substitution, etc.) and other rules of inference. Only simple cases are shown; we do not show the tricky cases of inference; do not differentiate between constructive and non-constructive logic at this point.
(Rosen2019, p.73-82)Rules of Inference (Knepley2020, p.12-20)SUNY Buffalo, CSE191 Notes.   (Brehm2020_1_6_1)Rules of Inference for Propositional Logic (Brehm2020_1_6_2)Rules of Inference for Quantified Statements
1.6.1. Recognize hypotheses and goals in a proof.
1.6.2. Apply modus ponens: \( A \rightarrow B,\, A \;\vdash\; B \)
1.6.3. Apply modus tollens: \( A \rightarrow B,\, (\neg B) \;\vdash\; (\neg A) \)
1.6.4. Apply transitivity: \( A \rightarrow B,\, B \rightarrow C \;\vdash\; A \rightarrow C \)
1.6.5. Apply disjunctive syllogism: \( A \vee B,\, \neg A \;\vdash\; B \)
1.6.6. Apply "addition": \( A \;\vdash\; A \vee B \)
1.6.7. Apply "simplification": \( (A \wedge B) \;\vdash\; A \)
1.6.8. Apply "conjunction": \( A,\, B \;\vdash\; (A \wedge B) \)
1.6.9. Apply "resolution": \( (A \vee B),\, (\neg A \vee C) \;\vdash\; (B \vee C) \)
1.7 Use Common Proof Strategies Description This subsection should introduce the basics of human-readable proofs with simple logical structure (and without overly complicated mathematics). We illustrate IF-THEN and IF-AND-ONLY-IF types of statements with results from elementary geometry, algebra, number theory or real analysis. (It is highly desirable to choose examples that may be familiar to the participants.)
(Rosen2019, p.84-93)Introduction to Proofs   (Brehm2018_1_7_1)Direct Proof (Brehm2018_1_7_2)Proof by Contraposition (Brehm2018_1_7_3)Proof by Contradiction
1.7.1. Explain direct proofs for IF-THEN statements
1.7.2. Explain proofs by contraposition for IF-THEN statements
1.7.3. Explain constructive proofs by contradiction (e.g. non-existence). Simple examples that show how proofs by contradiction do not need to rely on the classical logic (such as the Law of Excluded Middle)
1.8 Use More Proof Strategies Description Introduce proof techniques that reflect simple logical structure of the statement (for example analyzing cases would mean a generalization/universal quantifier over some finite set of cases;
(Rosen2019, p.96-113)Proof Methods and Strategy (Nahas2019)Nahas Tutorial   (Brehm2020_1_8_1)Proof by Cases (Brehm2020_1_8_2)Proofs of Existence And Uniqueness
1.8.1. Explain proofs by analyzing cases.
1.8.2. Explain proofs by counterexamples.
1.8.3. Introduce "without loss of generality" clauses.
1.8.4. Explain nonconstructive proofs by contradiction (e.g. existence). Game analysis by "mirroring strategy" and other proofs that look somewhat like cheating, but are actually correct. Why the Law of Excluded Middle is necessary in such cases.

2 Define Sets, Functions, their Set-Level Properties

2.1 Manipulate Sets and Functions Description This subsection only cares about set notation, defining new sets via subset and tuple (pair, tripple, etc.) constructions.
(Rosen2019, p.121-131)Sets   (Brehm2018_2_1_2)More about Sets
2.1.1. Define set by listing elements or intervals.
2.1.2. Define set by defining a predicate.
2.1.3. Define subsets, proper subsets.
2.1.4. Define pairs and other n-tuples.
2.1.5. Define power sets.
2.1.6. Reproduce Russel's paradox and retell it in some situations.
2.1.7. Demonstrate how predicate logic statements depend on the set used as the domain for quantifiers.
2.2 Manipulate sets over some universe Description This subsection is a refresher of the Boolean operations, since set operations for a given universe closely resemble Boolean operations (set intersection is same as conjunction, etc.)
(Rosen2019, p.133-144)Set Operations   (Brehm2020_2_2_1)Operations on Sets (Brehm2020_2_2_2)Set Identities (Brehm2020_2_2_3)Proving Set Identities
2.2.1. Define the union of two or more sets.
2.2.2. Define the intersection of two or more sets.
2.2.3. Define the complement of a set.
2.2.4. Define the difference of two sets.
2.2.5. Define the symmetric difference of sets.
2.2.6. Draw Venn diagrams for 2, 3, 4 sets.
2.2.7. Draw Euler diagrams (where some subset relations are known - so you do not show all the \( 2^n \) theoretically possible regions as in a Venn diagram).
2.3 Define functions and their set-related properties Description Nearly every topic in mathematics is somehow related to functions; here we only explain some set-theoretical properties of functions - defining domain, range, some properties (one-to-one, onto, bijection), also inverse and composition of two or more functions.
(Rosen2019, p.147-161)Functions   (Brehm2020_2_3_1)Introduction to Functions (Brehm2020_2_3_2)One to One and Onto Functions (Brehm2020_2_3_3)Inverse Functions and Composition of Functions (Brehm2020_2_3_4)Useful Functions to Know
2.3.1. Describe the domain and the range (codomain) of a function.
2.3.2. Describe the one-to-one, onto and bijective (i.e. one-to-one AND onto) properties of a function.
2.3.3. Find inverse functions for some known function examples
2.3.4. Find composition of multiple functions.

2.4 Define and use sequences Description This subsection introduces simple sequences and also notation (long sums, products, Boolean operations, set unions/intersections) to manipulate them.
(Rosen2019, p.179-186)Sequences and Summations   (Brehm2020_2_4_1)Introduction to Sequences (Brehm2020_2_4_2)Recurrence Relations (Brehm2020_2_4_3)Summations and Sigma Notation (Brehm2020_2_4_4)Summation Properties and Formulas
2.4.1. Define sequences as functions from natural numbers to something
2.4.2. Define recurrent sequences
2.4.3. Define long sums and similar looping constructs
2.5 Compare Set Cardinalities Description This subsection discusses comparing sizes of two sets; it is essential to develop intuition on which problems can be formalized and which ones are algorithmically solvable.
(Rosen2019, p.179-186)Cardinality of Sets   (Bazett2018)Integers and Rationals are both infinite but is it the SAME infinity?
2.5.1. Define injective functions between 2 sets.
2.5.2. Define surjective functions between 2 sets.
2.5.3. Prove that adding finitely many elements to a countable set is countable
2.5.4. Prove that the union of two countable sets is countable
2.5.5. Prove that the union of countably many countable sets is countable
2.5.6. Prove that the powerset of any set is larger than the original set
2.5.7. Prove statements about subsets, functions, sequences in the set of integers
2.5.8. Set cardinality results in geometry (2D space has the same number of points as a 1D space). Continuum hypothesis.
2.5.9. Apply Schroder-Bernstein theorem to show that bijection must exist.
2.6 Perform actions on matrices with discrete objects Description Matrices are rectangular tables of objects of some kind (usually numbers or truth values); this subsection shows how they can be used to describe functional dependencies between elements in two sets - e.g. linear transformations; directed graphs; relations on a given set - all these situations will need them. At this point it is just an introduction for the matrix notation and some simple manipulations on them.
(Rosen2019, p.188-193)Matrices   (Brehm2020_2_6_1)Matrices and Matrix Operations (Brehm2020_2_6_3)Zero-One Matrices
2.6.1. Perform sum, difference, product of numeric matrices
2.6.2. Define join (memberwise disjunction), meet (entry-by-entry conjunction) and the Boolean product of two matrices.
2.6.3. Define transposed matrices, symmetric matrices.

3 Identify algorithms and estimate their time complexity

3.1 Describe algorithms for lists/arrays and their paradigms Description In the subsection we introduce various concepts related to algorithms: input, output, pseudocode, execution time, underlying variables and data, proofs of correctness.
(Rosen2019, p.201-213)Algorithms   (Brehm2020_3_1_1)Introduction to Algorithms and Pseudo Code (Brehm2018_3_1_2)Searching Algorithms (Brehm2018_3_1_3)Sorting Algorithms (Brehm2018_3_1_4)Optimization Algorithms
3.1.1. Describe common characteristics of algorithms (mass problem, input, output, strictly defined steps, finite time)
3.1.2. Describe an algorithm to find maximum in a list of n with pseudocode.
3.1.3. Describe linear search algorithm
3.1.4. Describe binary search algorithm
3.1.5. Describe bubble sort algorithm
3.1.6. Describe the naive string matching algorithm
3.1.7. Describe the greedy algorithm to pay the change with minimum coins.
3.1.8. Prove that for the eurocent coins (1,2,5,10,20,50,100,200) greedy algorithm is optimal
3.1.9. Describe the greedy scheduling algorithm
3.1.10. Define the halting problem; prove that it is unsolvable
3.2 Define and use the big-O notation and related complexity measures Description This subsection is preoccupied by the growth asymtotics, it introduces various growth rates (Big-O-Notation) and also the related Omega and Theta notations.
(Rosen2019, p.216-228)The Growth of Functions (Tepper2016)Total Noobs Guide to Big O
3.2.1. Define the big-O notation
3.2.2. Compare various elementary functions by their growth speed
3.2.3. Compute the big-O for sums and products of functions.
3.2.4. Define big-Omega and big-Theta notations
3.2.5. Produce graphs (in xOy plane) or tables for some functions to compare their growth
3.3 Define and determine some algorithm complexity measures Description This subsection combines two previous ones – we analyze the pseudocode of an algorithm and come up with an estimate of how many operations it takes (up to a constant factor and addition with terms of smaller growth order).
(Rosen2019, pp.231-235)Complexity of Algorithms
3.3.1. Define time and space complexity for the given run of a program
3.3.2. Define worst-case and average time complexity
3.3.3. Describe the number of steps for binary search in a list of n elements
3.3.4. Compute the number of steps for bubble sort
3.3.5. Compute the lower bound for any sorting algorithm
3.3.6. Compute the number of steps for naive string matching
3.3.7. Develop an intuition about function growth rates
3.3.8. Analyze some Fibonacci computation algorithms (avoid cases where recursive calls multiply exponentially)

4 Use modular arithmetic

4.1 Operate with modular arithmetic Description This subtopic only focuses on modular arithmetic (properties that are preserved when finding remainders during division by a fixed positive integer \( m \)).
(Rosen2019, p.251-258)Divisibility and Modular Arithmetic (Knepley2020, p.132-182)CSE191, Integer Arithmetic   (Brehm2018_4_1_1)Divisibility (Brehm2018_4_1_2)Modular Arithmetic
4.1.1. Add, subtract and multiply congruences (ring operations)
4.1.2. Transform congurences equivalently
4.2 Convert integer representations Description In this subsection we convert decimal to binary and similar numbering systems.
(Rosen2019, p.260-268)Integer Representation and Algorithms   (Brehm2018_4_2_1)Decimal Expansions (Brehm2018_4_2_2)Binary, Octal and Hexadecimal Expansions (Brehm2018_4_2_3)Conversion Between Binary, Octal and Hexadecimal Expansions (Brehm2018_4_2_4)Algorithms for Integer Operations
4.2.1. Convert a representation of a number into a number by Horner’s scheme
4.2.2. Obtain a representation of a number by Horner’s scheme backwards
4.2.3. Perform arithmetic operations on number representations
4.2.4. Make computations on binary fractions (including infinite periodic fractions)
4.2.5. Perform efficient modular exponentiation
4.3 Prove properties of primes, GCD, LCM and related algorithms Description This subtopic introduces algorithms related to primality, divisibility and finding GCD or LCM.
(Rosen2019, p.271-288)Primes and Greatest Common Divisors   (Brehm2018_4_3_1)Prime Numbers and Their Properties (Brehm2018_4_3_2)GCD's and LCM's (Brehm2018_4_3_3)The Euclidean Algorithm
4.3.1. Analyze the full search primality testing algorithm (divide up to \( \sqrt{n} \))
4.3.2. Prove that there are infinitely many primes
4.3.3. State known facts about prime “gaps”
4.3.4. State properties of LCD and GCD
4.3.5. Apply Euclid algorithm to compute LCD
4.4 Find Bezout coefficients and solve linear congruences Description Show how to solve linear congruences (or systems of linear congruences as in the Chinese Remainder theorem)
(Rosen2019, p.290-300)Solving Congruences   (Brehm2018_4_3_4)GCD's as Linear Combinations (Brehm2018_4_4_1)Solving Congruences
4.4.1. Use Blankinship algorithm to compute Bezout coefficients
4.4.2. Find inverse of a number w.r.t. some module
4.4.3. Solve arbitrary linear congruences
4.4.4. Prove and use Chinese remainder theorem
4.4.5. Prove and use Little Fermat theorem
4.4.6. Formulate and use Euler's theorem
4.4.7. Solve problems with primitive roots and discrete logarithms
4.5 Define hashing and checksums in terms of modular arithmetic Description The only subsection on the applications of number theory focuses on algorithms to compute hash functions and also the checksums designed to ensure the integrity of data. (There are other major applications, say, in cryptography, but we do not care, since the course has sufficiently large scope already.)
(Rosen2019, p.303-308)Applications of Congruences
4.5.1. Define a simple hashing function using modular arithmetic
4.5.2. Define some popular checksums using modular arithmetic
4.5.3. Check the integrity of credit cards, personal identity numbers ("personas kods", Latvia) and ISBN.

5 Prove statements by mathematical induction

5.1 Prove general statements using the simplest scheme of mathematical induction (\( n \rightarrow n+1 \)) Description This subsection explains the very basic scheme of induction (prove the statement for \( n=0 \) or \( n=1 \), then prove it by advancing one step at a time).
(Rosen2019, p.331-350)Mathematical Induction   (Brehm2018_5_1_1)Mathematical Induction - Summation Formulae and Inequalities (Brehm_2018_5_1_2)Mathematical Induction - Divisibility and Set Theory
5.1.1. Prove summation formulas and other algebraic identities by induction
5.1.2. Prove inequalities by induction
5.1.3. Use the method of invariants to prove impossibility results
5.2 Prove statements by variants of mathematical induction Description Define and prove statements by induction, where it is essential to look back more than one step.
(Rosen2019, p.354-362)Strong Induction and Well-Ordering   (Brehm2018_5_2_1)The Well Ordering Principle and Strong Induction
5.2.1. Introduce hot and cold states in combinatorial games.
5.2.2. Analyze winning strategies in some games using strong induction
5.2.3. Prove formulas for recurrent sequences (such as Fibonacci) by using modified scheme of induction.
5.3 Use recursive definitions and structural induction Description Define and prove inductive statements that can be defined on expressions and/or tree-like structures.
(Rosen2019, p.365-378)Recursive Definitions and Structural Induction   (Brehm_5_3_1)Recursive Definitions
5.3.1. Define sequences recursively (Fibonacci, Catalan, etc.) and illustrate them in word problems.
5.3.2. Define tree-like structures recursively (next level in a tree is created from multiple subtrees)
5.3.3. Define syntax trees (for expressions, statements) in programming language
5.3.4. Introduce attributes that are calculated as we move up the tree
5.3.5. Define simple fractals using Lindenmayer systems

9 Introduce relations, their properties and possible representations.

9.1 Define and analyze binary relations Description This subsection only discusses binary relations at a general level.
(Rosen2019, p.599-608)Relations and their properties   (Brehm2020_9_1_1)Introduction to Relations (Brehm2020_9_1_2)Properties of Relations (Brehm2020_9_1_3)Combining Relations
9.1.1. Define general binary relations on \( A \times B \) and on \( A \times A \).
9.1.2. Identify properties for relations; check them in examples.
9.1.3. Combine relations into new ones.
9.2 Operate with relational operations Description The subsection adresses somewhat marginal topic of n-ary relations, but it is still important, since it forms the basis of relational databases (RDBMS) such as MySQL or Oracle. We try to illustrate it with in-memory databases (such as Pandas library).
(Rosen2019, p.611-619)n-ary Relations   (CS186Berkeley2018)Binary vs Ternary Relationships
9.2.1. Define an n-ary relation
9.2.2. Identify relational concepts in databases (tables, primary keys, foreign keys, composite keys)
9.2.3. Do simple selects and joins
9.2.4. Define support and confidence in association rules (such as item purchases)
9.3 Represent binary relations as matrices and directed graphs Description This subsection discusses advantages for each representation and what things can be computed for each one.
(Rosen2019, p.621-626)Representing Relations   (Brehm2020_9_3_1)Matrix Representations of Relations and Properties (Brehm2020_9_3_1)Representing Relations Using Digraphs
9.3.1. Manipulate relations with their matrix representation
9.3.2. Manipulate relations with their directed graph representation

9.4 Find and use relation closures Description The subsection introduces the concept of closure (as the “smallest” of all possible subsets with the given property). One particularly useful subtype of closure is the transitive closure.
(Rosen2019, p.599-608)Relations and their properties   (GeorgiaTech2015)Transitive Closure
9.4.1. Define transitive closure and some other closures.
9.4.2. Use and analyze Warshall Algorithm
9.5 Use equivalence relations for set partitions Description This subsection discusses a very useful subspecies of relations – equivalence relations; and how they can be used to structure the set where they are defined.
(Rosen2019, p.599-608)Relations and their properties   (Brehm2020_9_5_1)Equivalence Relations
9.5.1. Verify that a relation is an equivalence relation
9.5.2. Show the equivalence classes created by an equivalence relation
9.6 Prove and use statements about partially ordered sets Description This subsection addresses a set with a common relation – that of a partial order (which is also reflexive, antisymmetric and transitive, but two elements may also be incomparable).
(Rosen2019, p.599-608)Relations and their properties   (Lambert2019)What is a Partial Order Relation?
9.6.1. Introduce partially ordered set and related concepts (well ordered, totally ordered sets).
9.6.2. Introduce various types of lexicographic orderings (also reverse ordering, shortlist ordering)
9.6.3. Manipulate Hasse diagrams and transitive closures on them
9.6.4. Define lattices and the concepts of least upper bound and greatest lower bound.
9.6.5. Describe topological sorting

6 Use combinatorics

6.1 Count the number of elements in ordered or unordered selections with or without repetition. Description The subsection shows easy principles to evaluate the number of various selections (and they generalize lots of specialized formulas)
(Rosen2019, p.405-416)The Basics of Counting   (Brehm2020_6_1_1)Counting Rules
6.1.1. Use the product rule and the sum rule
6.1.2. Use the subtraction rule and the division rule
6.1.3. Use the principle of inclusion-exclusion
6.2 Use the Pigeonhole principle Description Subsection discusses a simple idea of a proof by contradiction also known as the Dirichlet principle (if there are n+1 objects and n boxes, then at least one box should have at least 2 objects) and some variants of this.
(Rosen2019, p.420-426)The Pigeonhole Principle
6.2.1. Use the simplest form of Pigeonhole principle
6.2.2. Use the generalizations of the Pigeonhole principle
6.2.3. Use Pigeonhole principle in number theory
6.3 Count permutations and combinations Description This is similar to 6.1, but we revisit the material and show how to compute some well-known selections (permutations and combinations with or without repetition).
(Rosen2019, p.428-434)Permutations and Combinations   (Brehm2020_6_3_1)Permutations and Combinations (Brehm2020_6_3_2)Counting Rules Practice
6.3.1. Count permutations without repetitions
6.3.2. Count combinations without repetitions
6.4 Define binomial coefficients Description This is similar to 6.1, but we revisit the material and show how to compute some well-known selections (permutations and combinations with or without repetition).
(Rosen2019, p.437-443)Binomial Coefficients   (Brehm2020_6_4_1)The Binomial Theorem
6.4.1. Build pascal’s triangle and use it to view various sums of binomial coefficients
6.4.2. Use Newton’s binomial formula
6.4.3. Use multinomial formula
6.4.4. Prove various identities with binomial coefficients.
6.5 Compute and use generalized permutations and combinations Description This subsection is a summary that discusses how the symmetry in a problem (distinguishable or indistinguishable objects, their order, their repetitions) affect the total count.
(Rosen2019, p.445-454)Binomial Coefficients
6.5.1. Count permutations with repetitions
6.5.2. Count combinations with repetitions
6.5.3. Count other selections with symmetry (distinguishable order, circular direction, etc.)

7 Compute and manipulate discrete probabilities

7.1 Use the classical definition of probability Description This subsection introduces the simplest notion of probability for discrete (i.e. countable) events. Use assumptions that all elementary events have equal probabilities.
(Rosen2019, p.469-475)Introduction to Discrete Probability   (Brehm2020_7_1_1)An Intro to Discrete Probability (Brehm2020_7_1_2)Discrete Probability Practice
7.1.1. Define the classical definition of probability and event
7.1.2. Define union, intersection and comlement of events
7.1.3. Compute probability for some events and combinations of events
7.1.4. Analyze probabilistic “paradoxes” and surprises
7.2 Introduce the basic concepts of the probability theory Description This chapter introduces all the fundamental concepts of discrete probabilities once they have been defined.
(Rosen2019, p.477-491)Probability Theory   (Brehm2020_7_2_1)Probability Theory (Brehm2020_7_2_2)Random Variables and the Binomial Distribution
7.2.1. Add probabilities of elementary events in various combinations
7.2.2. Use the sum for pairwise disjoint events
7.2.3. Use the inclusion/exclusion principle for probabilities
7.2.4. Define and use conditional probabilities
7.2.5. Define and use independent events
7.2.6. Define Bernoulli distribution
7.2.7. Define Binomial distribution
7.2.8. Define and use the concept of random variable
7.2.9. Introduce and solve the Birthday problem (1st kind of waiting time)
7.2.10. Introduce other types of waiting times
7.2.11. Define probabilistic algorithms and probabilistic simulations
7.3 Apply Bayes’ theorem Description The subsection shows a very practical way to express unknown conditional probabilities using directly observable ones (which show the “opposite” conditional probabilities).
(Rosen2019, p.494-501)Bayes’ Theorem
7.3.1. Formulate and prove Bayes’ Theorem
7.3.2. Formulate some variants and generalizations of Bayes’ Theorem
7.3.3. Show the applications of Bayes’ Theorem in text clusterization, spam filters and Data Leak Prevention
7.4 Summarise data with expected value and variance Description There are many ways to summarize larger amounts of numeric data (including median, inter-quartile range, mode, etc.), but here we only deal with the two simplest measures. Expected value (also mean and expectation) is defined for a random variable and it expresses the location. Variance (dispersija) and its square root – standard deviation (standartnovirze) measure the variability of data – how far it goes from the mean value.
(Rosen2019, p.503-517)Expected Value and Variance
7.4.1. Define and compute the expected value of a random variable
7.4.2. Use the linearity of expected value and other properties
7.4.3. Apply the expected value to find average-case computational complexity.
7.4.4. Define the uniform distribution; find its expected value and variance
7.4.5. Define the Poisson distribution with parameters; find its expected value and variance
7.4.6. Define the geometric distribution and find its expected value (the 2nd type of waiting time)
7.4.7. Define Multinomial distributions and their parameters; find its expected value and variance
7.4.8. Define Hypergeometric distrubtions and their parameters; find its expected value and variance
7.4.9. Define independent set of random variables
7.4.10. Define the variance of a random variable and its standard deviation.
7.4.11. Formulate and prove Bienayame’s Formula
7.4.12. Formulate and prove Markov’s Inequality
7.4.13. Formulate and prove Chebyshev’s Inequality

8 Obtain convenient expressions for various useful sequences and counting problems

8.1 Build recurrent relations for word problems Description The subsection shows how real-life problems can be converted into recurrent sequences; their definitions and closed formulas for these sequences (a closed formula is an explicit expression to compute the n-th member of a sequence without going through all the recurrent members preceding it.
(Rosen2019, p.527-536)Applications of Recurrence Relations   (Brehm2020_8_1_1)Modeling with Recurrence Relations
8.1.1. Write recurrent relations for Hanoi tower and similar recursive processes
8.1.2. Write recurrent relations to count strings with certain properties
8.1.3. Define Catalan numbers and use their correspondence with counting hierarchy-like structures
8.2 Solve linear recurrence relations Description Homogeneous and nonhomogeneous linear recurrences have some general methods to solve them (characteristic equations that allow to determine, what part of the sequence grows like a geometric progression). Fibonacci series is the best known linear recurrence, but there are many others.
(Rosen2019, p.540-550)Solving Linear Recurrence Relations   (Brehm2018_8_2_1)Second Order Linear Homogeneous Recurrence Relations
8.2.1. Use the characteristic equation for the case when all the roots are different.
8.2.2. Use the characteristic equation for the case when some roots are equal.
8.2.3. Use the characteristic equation for the case when there are complex roots
8.2.4. Solve linear nonhomogeneous relations
8.3 Solve recurrences expressing divide-and-conquer algorithms Description Some practically important recurrences (and related algorithms) are based on subdividing task into parts (and then reassembling their solutions with some additional cost). There is a famous theorem that solves this recurrence (and has three subcases) – it is called Master’s Theorem.
(Rosen2019, p.553-561)Divide-and-Conquer Algorithms and Recurrence Relations   (Rman2018)What is the Master Theorem?
8.3.1. Define and analyze the fast multiplication algorithm by Karatsuba
8.3.2. Define and analyze the fast matrix multiplication by Strassen
8.3.3. Define and analyze the merge-sort algorithm
8.3.4. Generalize the recurrence relations into Master theorem
8.5 Apply inclusion-exclusion principle Description Some counting tasks are more easily solved for the intersections (not unions) of multiple sets. If we need to solve them for unions, it is possible to count the union by adding the counts for individual sets, then subracting (and/or subsequently adding) for those cases where something has been counted twice, three times, etc.
(Rosen2019, p.579-583)Inclusion-Exclusion   (Brehm2020_8_5_1)The Principle of Inclusion Exclusion
8.5.1. Explain inclusion-exclusion principle on a Venn diagram
8.5.2. Use inclusion-exclusion principle in word problems when intersection counts are known
8.5.3. Use inclusion-exclusion principle for number divisibility and Euler’s function

10 Solve graph problems and use graphs to model other tasks

10.1 Represnt word problem situations as graphs; define vertices and nodes for each case Description This subsection explains obvious and less obvious situations where graphs may provide an answer to combinatorial questions.
(Rosen2019, p.673-682)Graphs and Graph Models   (Brehm2020_10_1_1)Introduction to Graphs
10.1.1. Explain graph concepts to communication and transport networks
10.1.2. Explain graph concepts in social networks, quotations, Web links, set intersections
10.1.3. Explain graph concepts in semantic Web
10.1.4. Explain graph concepts in tournaments
10.1.5. Explain directed graph concepts in precedence and dependency problems
10.2 Understand graph-related concepts and recognise them in concrete graphs Description The subsection focuses on identifying specific phenomena in graphs and also introduces additional restrictions on graphs (connected, bipartite, directed, planar, acyclic and so on) which lead to different parts of the theory.
(Rosen2019, p.685-694)Graph Terminology and Special Tpes of Graphs   (Brehm2020_10_2_1)Graph Terminology (Brehm2020_10_2_2)Special Types of Graphs (Brehm2020_10_2_3)Applications of Graphs
10.2.1. Define adjacency, neighborhood, the degree of a vertex, the Handshake theorem (the sum of all degrees in a graph)
10.2.2. Explain the differences for the same concepts in a directed graph
10.2.3. Introduce some special graphs – complete graphs \( K_n \), cycles \( C_n \), wheels \( W_n \) and \( n \)-dimensional cubes \( Q_n \).
10.2.4. Define bipartite graphs and matching concepts.
10.2.5. Prove and use Hall’s Marriage theorem.
10.3 Use adjacency list and matrix representations of graphs. Description The subsection compares two approaches to store graphs (such as using them as input for programs), and when to use each one. It also discusses the “invariant” properties of graphs that do not depend on their representations - isomorphic graphs may be considered equivalent – regardless of how they are represented and how their vertices are labeled.
(Rosen2019, p.703-710)Representing Graphs and Graph Isomorphism
10.3.1. Describe a graph using adjacency lists
10.3.2. Describe a graph using adjacency matrices
10.3.3. Define graph isomorphism problem and solve it in some particular cases
10.4 Use the concepts of paths and connectivity Description The subsection defines connectivity for undirected and also directed graphs (included strong connectivity). It also shows how this is related to finding path or paths between given vertices.
(Rosen2019, p.714-724)Connectivity
10.4.1. Define paths in undirected graphs
10.4.2. Define connected components in an undirected graph
10.4.3. Define some other vertex and edge connectedness measures
10.4.4. Prove that two graphs are not isomorphic by looking at their paths or similar properties
10.4.5. Show how the concepts apply to directed graphs
10.5 Solve problems related to cycles in graphs. Description This subsection introduces computationally easy problem (Euler’s cycles) and computationally hard problem (Hamilton’s cycles) – and how each one of them may be used.
(Rosen2019, p.728-739)Euler and Hamilton Paths
10.5.1. Define an Euler path in a graph
10.5.2. Define and prove the necessary and sufficient coefficient for an Euler path
10.5.3. Define the concept of a Hamiltonian path in a graph

11 Identify tree concepts, traverse trees with DFS and BFS for simple applications

11.1 Identify, list and count various objects in trees. Description The root, inner nodes, leaves, ancestors and successors, paths, traversals – all these tree-related concepts are often needed when using hierarchies of various kinds. This subsection defines the concepts and also counts all such objects efficiently.
(Rosen2019, p.781-791)Introduction to Trees   (Brehm2020_11_1_1)Introduction to Trees (Brehm2018_11_1_2)Rooted Trees
11.1.1. Define trees, inner nodes, leaves and related concepts
11.1.2. Rooted trees, parents, children, siblings, ascendants, descendants, height and depth.
11.1.3. Define full n-ary trees
11.1.4. Count (or prove bounds) for various elements in trees
11.1.5. Prove the logarithmic estimate for the depth of a full n-ary tree
11.3 Define and use preorder, inorder and postorder traversals in a rooted tree Description There are a few standard orders how to visit nodes in a tree (DFS is somewhat similar to visiting a labyrinth – and it also has three separate flavors). All these orders are important as they serve as building blocks to various algorithms.
(Rosen2019, p.808-819)Tree Traversal
11.3.1. Define BFS traversal in a tree
11.3.2. Define DFS preorder traversal
11.3.3. Define DFS inorder traversal
11.3.4. Define DFS post-order traversal
11.3.5. Use abstract syntax trees to get infix, prefix and postfix expressions
11.4 Define and construct MSTs (Minimum Spanning Trees) Description This section deals with MSTs – a concept applicable to an arbitrary connected graph with a tree (basically, which edges do we select from a given graph, so that it is a spanning tree (still connected graph, but does not contain any redundant edges – there are no loops).
(Rosen2019, p.821-832)Spanning Trees
11.4.1. Define Minimum Spanning Trees
11.4.2. Construct the Spanning Trees obtained from the BFS or DFS traversals
11.4.3. Define the backtracking problem to search for a solution in a hierarchy