Old PBM763 (2020): Topics

1.1 Analyze Propositions and Boolean Expressions
(Rosen2019, pp.1-13). Video1.1.
1.1.a. Define what is a proposition
1.1.b. Define Boolean operations (\( \neg, \wedge, \vee, \rightarrow, \leftrightarrow \))
1.1.c. Restore parentheses using precedence
1.1.d. Create truth tables for expressions
1.2 Create propositional statements
(Rosen2019, pp.17-22). Video1.2.
1.2.a. Translate English into Propositional logic.
1.2.b. Recognize situations when natural language uses logical connectives in a different sense.
1.2.c. Solve Logic Puzzles and Word Problems.
1.3 Recognize Boolean tautologies and satisfiability.
(Rosen2019, pp.26-33). Video1.3.
1.3.a. Rewrite propositions using equivalences (Use double negation; Use De Morgan's laws; Write Contrapositive for an Implication
1.3.b. Define a tautology if a truth table exists.
1.3.c. Create new tautologies using inference rules.
1.3.d. Define Satisfiable and Contradictory Boolean Expressions.
1.X Use expressions in programming (optional)
1.X.a. Apply operation precedence to a Python expression.
1.X.b. Apply operation associativity to a Python expression.
1.X.c. Apply short-circuit Boolean evaluation.

1.7 Use Common Proof Strategies
(Rosen2019, pp.84-93). Video1.7.a. Video1.7.b. Video1.7.c.
1.7.a. Explain direct proofs for IF-THEN statements
1.7.b. Explain proofs by contraposition for IF-THEN statements
1.7.c. Explain constructive proofs using contradiction.
1.4 Use Predicates and Quantifiers
(Rosen2019, pp.40-55). Video1.4.
1.4.a. Define a predicate as a function to booleans.
1.4.b. Recognize free and bound variables.
1.4.c. Interpret quantifiers over finite domains.
1.4.d. Use precedence for quantifier statements.
1.4.e. Negate predicates, apply De Morgan's laws.
2.1 Manipulate Sets and Functions
(Rosen2019, pp.121-131). Video2.1.
2.1.a. Define set by listing elements or intervals.
2.1.b. Define set by defining a predicate.
2.1.c. Define subsets, proper subsets.
2.1.d. Define pairs and other n-tuples.
2.1.e. Define power sets.
2.1.f. Reproduce Russel's paradox.
2.5 Compare Set Cardinalities
(Rosen2019, pp.179-186). Video2.5.
2.5.a. Define injective functions between 2 sets.
2.5.b. Define surjective functions between 2 sets.
2.5.c. Prove that adding a finite set to a countable is countable.
2.5.d. Union two positive integer sets.
2.5.e. Union infinitely many integer sets.

1.5 Use Nested Quantifiers
(Rosen2019, pp.60-68). Video1.5.
1.5.a. Rewrite mathematical statements with nested quantifiers.
1.5.b. Interpret quantifier expressions in human language.
1.5.c. Negate multiple quantifiers.
1.8 Use Some More Proof Strategies
1.8.a. Explain proofs by analyzing cases.
1.8.b. Explain proofs by counterexamples.
1.8.c. Introduce "without loss of generality" clauses.
1.8.d. Explain nonconstructive proofs of existence.
1.6 Use Rules of Inference
1.6.a. Recognize hypotheses and goals in a proof.
1.6.b. Apply modus ponens: \( A \rightarrow B,\, A \;\vdash\; B \)
1.6.c. Apply modus tollens: \( A \rightarrow B,\, (\neg B) \;\vdash\; (\neg A) \)
1.6.d. Apply transitivity: \( A \rightarrow B,\, B \rightarrow C \;\vdash\; A \rightarrow C \)
1.6.e. Apply disjunctive syllogism: \( A \vee B,\, \neg A \;\vdash\; B \)
1.6.f. Apply "addition": \( A \;\vdash\; A \vee B \)
1.6.g. Apply "simplification": \( (A \wedge B) \;\vdash\; A \)
1.6.h. Apply "conjunction": \( A,\, B \;\vdash\; (A \wedge B) \)
1.6.i. Apply "resolution": \( (A \vee B),\, (\neg A \vee C) \;\vdash\; (B \vee C) \)

2.2 Manipulate sets over some universe
2.2.a. Define the union of two or more sets.
2.2.b. Define the intersection of two or more sets.
2.2.c. Define the complement of a set.
2.2.d. Define the difference of two sets.
2.2.e. Define the symmetric difference of sets.
2.2.f. Draw Venn diagrams for 2, 3, 4 or 5 sets.
2.X Use Proof Strategies for Sets and Functions
2.X.a. Explain proofs for 2 sets being different (conterexample).
2.X.b. Explain proofs for a function being bijective [Define bijections from monotonous continuous functions; Define bijections as variants of 1D Hilbert hotel. Define bijections as variants of 2D Hilbert hotel.]
2.X.c. Explain constructions by selecting minimum in a nonempty set.
2.X.d. Explain proofs using invariants
3.1 Describe algorithms for lists/arrays and their paradigms
(Rosen2019, pp.201-213). Video3.1.a. Video3.1.b. Video3.1.c. Video3.1.d.
3.1.a. Describe common characteristics of algorithms (mass problem, input, output, strictly defined steps, finite time)
3.1.b. Describe an algorithm to find maximum in a list of n with pseudocode.
3.1.c. Describe linear search algorithm
3.1.d. Describe binary search algorithm
3.1.e. Describe the number of steps for binary search in a list of n elements
3.1.f. Describe bubble sort algorithm
3.1.g. Compute the number of steps for bubble sort
3.1.h. Describe the naive string matching algorithm
3.1.i. Compute the number of steps for string matching
3.1.j. Describe the greedy algorithm to pay the change with minimum coins.
3.1.k. Prove that for the eurocent coins (1,2,5,10,20,50,100,200) greedy algorithm is optimal
3.1.l. Describe the greedy scheduling algorithm
3.1.m. Define the halting problem
3.1.n. Prove that the halting problem is algorithmically unsolvable

3.2 Define and use the big-O notation and related complexity measures
(Rosen2019, pp.216-228). Video3.2.
3.2.a. Define the big-O notation
3.2.b. Compare various elementary functions by their growth speed
3.2.c. Compute the big-O for sums and products of functions.
3.2.d. Define big-Omega and big-Theta notations
3.3 Define and determine some algorithm complexity measures
(Rosen2019, pp.231-235). 3.3.a. Define time and space complexity for the given run of a program
3.3.b. Define worst-case and average time complexity
4.1 Use modular arithmetic
(Rosen2019, pp.251-258). Video4.1.a. Video4.1.b.
4.1.a. Add, subtract and multiply congruences (ring operations)
4.1.b. Transform congurences equivalently

4.2 Manipulate integer representations
(Rosen2019, pp.260-268). Video4.2.a. Video4.2.b. Video4.2.c. Video4.2.d.
4.2.a. Convert a representation of a number into a number by Horner’s scheme
4.2.b. Obtain a representation of a number by Horner’s scheme backwards
4.2.c. Perform arithmetic operations on number representations
4.2.d. Perform modular exponentiation
4.3 Prove properties of primes, GCD, LCM and related algorithms
(Rosen2019, pp.271-278). Video4.3.a. Video4.3.b. Video4.3.c.
4.3.a. Analyze the full search primality testing algorithm (divide up to \( \sqrt{n} \))
4.3.b. Prove that there are infinitely many primes
4.3.c. State facts about prime “gaps” and their distribution
4.3.d. State properties of LCD and GCD
4.3.e. Apply Euclid algorithm to compute LCD
4.4 Find Bezout coefficients and solve linear congruences
(Rosen2019, pp.285-293). Video4.4.a. Video4.4.b.
4.4.a. Use Blankinship algorithm to compute Bezout coefficients
4.4.b. Find inverse of a number w.r.t. some module
4.4.c. Solve arbitrary linear congruences

5.1 Prove statements by mathematical induction
(Rosen2019, pp.331-350). Video5.1.a. Video5.1.b.
5.1.a. Prove summation formulas by induction
5.1.b. Prove inequalities and various invariants by induction
5.2 Prove statements by variants of mathematical induction
(Rosen2019, pp.354-362). Video5.2.
5.2.a. Analyze some games with strong induction
5.3 Use recursive definitions and structural induction
(Rosen2019, pp.365-378). Video5.3.
5.4 Use recursive algorithms
(Rosen2019, pp.381-398). 5.4.a. Write and analyze tail-recursive number theory algorithms
5.4.b. Write and analyze tail-recursive linear, binary, ternary search algorithms
5.4.c. Write Fibonacci and related algorithms using iterations or memoization (storing intermediate results)
5.4.d. Write and analyze merge-sort algorithm
5.4.e. Use Master’s theorem to analyze complexity of recursive algorithms
5.4.f. Write assertions for conditionals and loops for program verification