<aside> 💡 As you go through, make sure you’re understanding what formulas are used for which types of problems. The tests don’t specifically mention the question type.

I recommend having Zybooks open and completing the practice exercises for each module (one box per module below) as you go along to lock everything in. This walkthrough follows the order of the book.

Also, open the formula sheet (from the bottom of the course page) while studying. It will be available during testing.

</aside>

assumed competency: basic understanding of the structure and logic of for, where, and if/else loops | | Computational Complexity | Intro to Big O and Time Complexity (CS Dojo) The Ultimate Big O Tutorial Best and Worst Case Analysis (Abdul Bari) Big O Cheat Sheet | | Asymptotic Growth | Asymptotic Notation Mini-Course (Khan) What is Asymptotic Analysis? Introducing Asymptotic Notations Asymptotic Notations 101 Asymptotic Summary (MIT) (7:07) |

| Divisibility (Brehm) or Divisibility (Trev) Modular Arithmetic (Brehm) or Trev Modular Multiplication Modular Multiplication Practice (Khan) | | Prime Factorization, GCD, and Euclid’s Algorithm

• read Lesson 2.9 from Zybooks

** the way Zybooks teaches inverses and asks the question is a bit different, review in lesson 2.12 after the “Solving Linear….Inverse” video

*** Z(sub #) notation just means mod #. Ex: inverse of 14 in Zₙ = inverse of 14 in mod n. | Prime Factorization Primes and GCD GCD and LCM Prime Number Theorem Euclidean Alg. *** Extended Euclidean Algorithm *** Extended Euclid Example (more examples) *** Finding GCD Using Euclidian Algorithm (more examples) Solving Linear Congruencies Using Inverse | | Number Representation in Other Bases

• skip octal sections

** read lesson 2.16 from Zybooks | Decimal Expansions Expansions from Decimal Non-Decimal Conversions | | Fast Exponentiation Algorithms

• first 5 mins of Fast Exponentiation give a preview on how to solve but you’ll have to read Zybooks 2.18.

** Click “Need Help” on exercise 2.19.1 for an amazing video on modular exponentiation!! | Fast Exponentiation Modular Exponentiation (26:00) Successive Squaring (for Mod.Ex.) + Fast Exponentiation Units Digits of an Exponential | | Mathematical Foundations of Encryption

• read 2.22 for encryption/decryption practice using given formulas - or skip, it’s basic math/pattern recognition

** formulas given on formula sheet | Cryptography Crash Course Public Keys Practice - RSA RSAKey Generation |

• the summation formula information is mostly review, transferring concepts, and plugging into the formulas, use Zybooks as needed

** the proofs aren’t all explicitly reviewed in the videos but they all have the same structure, just make sure you understand the induction steps. The first video on the right explains all of the basic concepts that translate to each different proof if you listen closely.

*** the proof videos linked in Zybooks for the first few proof lessons were also very helpful and concise | Summations and Sigma Notation Summation Properties and Formulas Mathematical Induction Logic Proof by Induction Proof Using Summation Proof Using Inequalities Proof Using Divisibility Strong Induction The Well-Ordered Principle | | Recursive Structures | Recursive Definitions Recursively Defined Functions and Sets Structural Induction Recursive Algorithms *** | | Simple Recurrence Relations

• read 3.20 and 3.21 in Zybooks | Zybooks and the practice questions are the best resource for this section. |

• review k to 1 in Zybooks but don’t stress if it doesn’t make sense in this lesson. it’s explained a bit better in 4.8.2. | Rule of Sum and Rule of Product (Trev) Sum and Product Rules (MIT) Counting Rules Function Relations + Practice Importance of Bijective Functions K to 1 Correspondence | | Counting with Permutations and Combinations

• combination = subsets | Permutations and Combinations (Brehm) Factorials and Permutations (Trev) Combinations (Trev) Counting Practice (Brehm) Permutations with Restrictions Permutations with Other Restrictions | | Counting with Multisets | At Least / Exactly (Trev) Complex Counting Problems (Brehm) Combinations with Repetition Counting Stars and Bars | | Generating Permutations and Combinations

• Lessons 4.15 and 4.16 in Zybooks | | | Advanced Counting Techniques | The Principle of Inclusion-Exclusion (Brehm) Inclusion-Exclusion Principle (Trev) Inclusion-Exclusion (MIT) Binomial Theorem (Brehm) Binomial Theorem and Pascal’s Triangle (Trev) Finding Binomial Coefficients Pascal’s Identity and Triangle (Brehm) The Pigeonhole Principle (Brehm) and Proof Pigeonhole Principle (Trev) and Examples |

use the class worksheets in course search to gauge for OA readiness |