Chapter 6
Sections 32, 33, 34
Conditional Probability, Independence, Random Variables, Expectation
Definitions
• Conditional Probability
• Independent Events
• Random Variable
• Independent Random Variable
• Expectation or Expected Value
• Variance
Key Points
• Make sure you know how to calculate probabilities when flipping coins, rolling
dice, drawing a card from a deck.
• Remember that Random Variables are functions.
• There are usually two ways to solve a probability problem:
1. With the formulas directly
2. With intuition
• Make sure you know how to calculate the expected value of a situation.
• Knowing that Linearity of the Expectation might help with this
• Make sure you know how to calculate the variance (but also know that a long,
painful problem probably won’t show up on the test).
• It’s helpful to know that 𝑉𝑉𝑉𝑉𝑉𝑉 𝑋𝑋 = 𝐸𝐸 𝑋𝑋2 − 𝐸𝐸 𝑋𝑋 2
Examples
Chapter 7
Sections 35 & 36
Division and GCD
Definitions
• The Division Theorem
• Quotient
• Remainder
• The operations of div and mod
• Common Divisor
• Greatest Common Divisor
• Relatively Prime
• Fundamental Theorem of Arithmetic
Key Points
• Make sure you know the definition of quotient and remainder that come with
the Division Theorem
• Make sure you know how to use the division algorithm to create a
multiplication problem
• It can be tricky with negative numbers. Make sure you’re clear on how it works in this
case.
• Be able to calculate the GCD of any two integers using the Euclidean
Algorithm.
• Be able to use the Euclidean Algorithm to find the Bezout coefficients
Examples
For each pair of integers 𝑉𝑉 and 𝑏𝑏, find integers 𝑥𝑥 and 𝑦𝑦 such that
𝑉𝑉𝑥𝑥 + 𝑏𝑏𝑦𝑦 = gcd(𝑉𝑉, 𝑏𝑏)
1. 𝑉𝑉 = 207, 𝑏𝑏 = 413
2. 𝑉𝑉 = 54321, 𝑏𝑏 = 50
3. 𝑉𝑉 = 1739, 𝑏𝑏 = 29343
Chapter 9
Sections 47, 48, 49, 50
Graphs, Subgraphs, Connection, Trees
Definitions
• Graph
• Adjacent
• Degree
• Subgraph
• Spanning and Induced Subgraphs
• Clique and Clique Number
• Independent Set and Independence
Number
• Compliment
• Walk
• Path
• Concatenation
• Path Graph
• Connected to
• Component
• Connected
• Cut Vertex and Cut Edge
• Cycle
• Forest
• Tree
• Leaf
• Spanning Tree
Key Points
• A graph is defined with sets. A drawing is only a visual representation of that graph,
but can be drawn in an infinite number of ways
• Be able to make a drawing of a graph from a set, and vice versa.
• Use what you know about the degrees of vertices to help you with difficult
problems
• There are a lot of definitions in graph theory, but the names of things are fairly
intuitive.
• Chances are, if you “get to know” as many of the graphs with ~10 vertices and
fewer, you’ll be prepared to see any graph that comes up on the exam.
• Know what it means for a graph to induce/span another graph and how these are
related to cut edges/vertices.
• Group compliments/cliques/independence together in your head.
• Make sure you know the difference between a walk and a path, and where each one
is valuable.
• Drawing a graph in a situation that is confusing is the best way out.
Examples
1. Draw all of the graphs with one vertex.
a. How many are connected vs. disconnected?
b. How many are trees vs. forests?
c. What are their clique and independence numbers?
d. How many components/cut vertices/edges does each one have?
2. Repeat #1 with all of the graphs with 2 vertices.
3. Repeat #1 with all of the graphs with 3 vertices.
4. Repeat #1 with all of the graphs with 𝑛𝑛 vertices.
See you at the final