Basic concept

🔴必考theorem：

1. Theorem：
1. Handshaking Lemma: In any simple graph:
2. Euler’s Formula:
corollary：
1. 记不住的话，就记住这个图（特例）：（2个点，1条边，1个面。2 - 1 + 1 = 2）
2. 任何凸多面体（convex polyhedron）也会符合这个公式。
（欧拉公式的全称是Euler’s Polyhedron Formula）
（可以去这么想：将任何一图多面体放入一个球中，在多面体的中心放一个点光源，它的顶点和边会映在球体内壁，将球面向地图那样展开，会得到planar）
图示：

2. 例题：
考试的题一定会跟这些难度差不多，题型差不多。
1. （简单）The graph G has 6 vertices with degrees 2,2,3,4,4,5. How many edges does G have? Could G be planar? If so, how many faces would it have. If not, explain.
answer
💡
We can determine the number of edges using the Handshake lemma.
Degree sum: 2 + 2 + 3 + 4 + 4 + 5 = 20
2e = 20 → e = 10
The graph has 10 edges.
G could be planar if it satisfies Euler’s formula. We know e = 10 and v = 6.
v - e + f = 6 - 10 + f = 2 → f = 6
The graph could be planar. The graph would have to have 6 faces.
2. （中等）I’m thinking of a connected planar containing 12 faces. Seven are triangles and four are quadrilaterals. The planar has 11 vertices including those around the mystery face. How many sides does the last face have?
answer

💡

f = 12, v = 11, e = ?

Seven triangles:

Four Quadrilaterals:

---

Assume the last face has n edges and n vertices. Then

---

We know e must be a whole number so 37 + n must be even. This means n is odd.

This indicates the last face must have an odd number of edges and vertices. Now we can apply Euler’s formula:

Now we solve for n.

Since we know that Euler’s theorem holds for any convex polyhedron, the problem can also be asked this way:

I’m thinking of a convex polyhedron containing 12 faces. Seven are triangles and four are quadrilaterals. The polyhedron has 11 vertices including those around the mystery face. How many sides does the last face have?

3. （有趣）Prove that there are exactly 5 regular polyhedra.
answer
💡
Case 1: Each face is a triangle. Let f be the number of faces. There are then edges. Using Euler’s formula we have . Now each vertex has the same degree, say k. So the number of edges is also . Putting this together gives .
 
Both k and f must be positive integers. Note that is an increasing function for positive f, bounded above by a horizontal asymptote at k = 6. Thus the only possible values for k are 3, 4, and 5. Each of these are possible.
To get k = 3, we need f = 4 (this is the tetrahedron). For k = 4, we take f = 8 (the octahedron). For k = 5, take f = 20 (the icosahedron).
Thus there are exactly three regular polyhedra with triangles for faces.
 
Case 2: Each face is a square. Now we have . Using Euler’s formula we get , and counting edges using the degree k of each vertex gives us .
. Solving for k gives .
 
Case 3: Each face is a pentagon. We perform the same calculation as above, this time getting
.
Then
.
.
---
Now the horizontal asymptote is at
This is less than 4, so we can only hope of making k = 3.
We can do so by using 12 pentagons, getting the dodecahedron.
This is the only regular polyhedron with pentagons as faces.
 
 
 
总结一下：其实就是上文提到的两个定理的应用。无论这道题刚拿到手的时候又没有头绪，先把这两个定理打上去.

正宫给的大纲：

Graph basics

• Understanding basic graph terminology:
vertex, edge, adjacency, incidence, endpoint;
vertex: 节点
edge：边
adjacency：两个顶点之间有边连接
incidence：顶点与边相连
endpoint：一条边连接的两的顶点
isolated/leaf vertices；
isolated：没有任何边连接的顶点。其度数为 0
Leaf vertices：度为 1 的顶点，也就是只与一个其他顶点相连
simple graphs, weighted/unweighted graphs, directed/undirected graphs;
略。FIT1058中几乎只有简单图，做事没有明确表示，就只考虑简单图。
degree.
其节点相连的边的数量
• Being able to define a graph using set notation.
set notation
🔹 basic definition：
A graph G is defined as a pair of sets:
G = (V, E)
Where:
• V is the set of vertices (also called nodes)
• E is the set of edges, each of which is a pair of vertices
---
🔸例子
Let the set of vertices be:
Let the set of edges be:
Then the graph is written as:
• Being able to work with different graph representations:
edge list;
({a, b}, {a, c}, …)
adjacency matrix;



adjacency list;
a: b, c
b: a, d
…
incidence matrix.



• Understanding what is meant by a subgraph, and how to identify a subgraph of another graph.
definition
A subgraph is a graph that is “part” of another graph.
If is a graph, then a graph is a subgraph of G if:
Additionally, every edge in must have both endpoints in
how to identify
自己想吧
• Being familiar with notation for special graphs such as complete graphs, path graphs, and cycle graphs.
notation
见上文
• Knowing the Handshaking Lemma and its corollaries, and being able to apply it to specific graphs to reason about their vertex degree.
Handshaking Lemma
corollaries
1. For any graph G,
2. Every graph has an even number og vertices of odd degrees
Review: Lesson 11 pre-reading and all of Lesson 11.1
Suggested Applied Exercises: Problems 1, 2, 4

Movement and connectivity in graphs

Being able to define and identify walks, trails, paths, and cycles in graphs.
1. a walk from a vertex v to a vertex w is a sequence of vertices and edges.
2. a trail is a walk in which no edge is used more than once
3. a path is a trail in which no vertices is used more than once
4. a cycle is a closed trail in which no vertices except the firat and last one is repeated
Being able to calculate the distance between two vertices in a graph.
the distance between 2 vertices u and v is the shortest path from u and v
Understanding what it means for a pair of vertices to be connected.
2 vertices are connected if there is a path from v to w in G. This in turn holds if and only if there is a walk from v to w in G
Understanding what it means for a graph to be connected.
The graph G is connected if, for every pair of vertices, there is a path from v to w in G.
Being able to identify the connected components of a graph.
A component of G is a maximum connected subgraph of G, meaning that is not a proper subgraph of any other connected subgraph of G
Review: all of Lesson 11.2
Suggested Applied Exercises: Problems 5, 6, 7

Bipartite graphs and Euler tours

Understanding what is meant by a bipartite graph, and how to identify one
A graph is a Bipartite graph if its vertex set V can be written as a disjoint unit
Knowing how to assign a 2-colouring to a bipartite graph
。。。略了吧还是
Understanding what is meant by an Euler tour, and knowing how to specify one in a graph, if it exists
An Euler tour is a closed trail that uses every edge
1. Since it is a trail, this means each edge gets used exactly once
2. Since it is closed, it finishes at its starting vertex
Understanding what kinds of graphs do and don't have Euler tours
A connected graph G has Euler tour if and only if every vertex has even degree
Review: all of Lesson 11.3
Suggested Applied Exercises: Problems 8, 9, 10

Trees, forests, and spanning trees

• Knowing what a tree is, and the basic properties of trees, including the 3 theorems given in Lesson 12.1.2
what is a tree
A tree is a connected graph without cycles
3 theorems given
1. A graph G = (V, E) is a tree if and only if it is minimal connected graph on G
2. Every tree with at least 2 vertices has a leaf
3. For every , every tree on n vertices has n - 1 edges
• Knowing what a forest is, and that every forest with n vertices and k components has n−k edges
Forest
1. A forest is a graph with no cycles
2. For every , every forest with n vertices and k components has n - k edges
• Knowing what a spanning tree is, how to find a spanning tree of a graph using either the edge deletion or edge addition methods, knowing how to use Kruskal's Greedy Algorithm on weighted graphs to find a minimum cost spanning tree
spanning tree
A spanning tree of G is a subgraph of G witch
1. is a tree
2. include evert vertex of G
find a spanning tree
1. deleting edges: delete an edge in every cycle
2. Adding edges if it does not form a cycle
Kruskal’s Greedy algorithm
1. sort all the edges of the graph by increasing weight.
2. initialise a forest: each edge is its own tree.
3. for each edge (u, v), in order of weight:
if u and v are in different components (no cycle would form)
add the edge to the minimum spanning tree.
union the sets
4. repeat until there are n - 1 edges.
Suggested Applied Exercises: Problems 2, 3, 4, 5, 6, 7, 8

Planar graphs

• Knowing what is meant by a planar graph, and a planar drawing of a graph, and the difference between the two
a planar graph
A graph that can be drawn in the plane without any edges crossing (except at its endpoints)
a planar drawing of a graph
A planar drawing of a graph is a specific layout or representation of a graph on the 2D plane without any edge crossings.
• It’s an actual picture or embedding of the graph.
• A graph may have multiple drawings — only one needs to be planar to classify the graph as planar.
• Knowing and being able to use Euler's Theorem n−m+f=2, and its corollary m≤3n−6
Euler’s Theorem: n - m + f = 2
NULL
corollary
1. For any planar graph G with v > 3 vertices and e edges
1. For any triangle-free planar G with v ≥ 3 vertices and e edges
1. and are nonplanars.
Review: Lesson 12.2.2
Suggested Self-Study Exercises: Problems 9, 10, 11, 12, 13
 
Other modules
module 1: set
Basic notation and terms
Defining a set, using set notation
idk wut this sh*t is
Familiarity with notation relating to sets of numbers
Just mind that N represent the set of positive integers in this unit. Different from high school.
Familiarity with notation relating to sets of strings over some alphabet
If A is an alphabet and , then denotes all the strings of exactly k characters in which each character belongs to A.
For example, A = {0, 1}, then
 
Mind that is the set containing the empty string , This is not to be confused with empty set
 
Also mind that we write for the set of all finite strings.
for example, A = {0, 1},
Review Lesson 1 pre-reading
Basic set relations and operations:
Subsets, supersets
Subset:
Proper subset:
superset:
Set complement, understanding what the universal set is and how it relates to complementation
Set complement:
How universal set relates to complementation:
Set difference, union, intersection, symmetric difference
Set difference:
union:
intersection:
symmetric difference:
De Morgan’s Laws for sets, and other basic equivalences between set operations
1. De Morgan’s Laws for sets:
Working with the Cartesian product of two or more sets
This is not to be confused with the set of strings over some alphabet
Review Lesson 1.1.1, all of Lesson 1.2, and Lesson 1.3.1
Suggested Applied Exercises: Problems 1, 3, 6, 9-17, 19
Counting and partitioning sets
Calculating the power set of a set
The power set is a set of all subsets of A, including: empty set and the set itself
cardinality:
Counting all subsets of a given size
subsets:
proper subset:
Partitioning a set
A partition of a set A is a set disjoint nonempty subsets of A whose union is A. These subsets are called parts of the partition
coarsest partition: { A }
finest partition:
Review Lesson 1.1.2, Lesson 1.1.3, and Lesson 1.3.2
Suggested Applied Exercises: Problems 5, 7, 8, 20, 21, 22
module 2: functions and relations
Basic notation and terms
• Understanding the definition of a function as a rule which maps elements in some domain to elements in some codomain
• Being able to define a function by specifying its domain, codomain, and rule
Understanding the difference between a function's codomain and its image
The codomain: declared target set of input, not exactly the set of the actual output.
image: actual output produced by the input
• Understanding how functions can be represented as sets of ordered pairs
• Defining and understanding functions that have more than one argument
Review Lesson 2 pre-reading, Lesson 2.1.1, Lesson 2.1.2 (first and last sections)
Suggested Applied Exercises: Problems 5, 6
Special kinds of functions
Knowing what is meant by the terms empty function, identity function, constant function, and indicator function, understanding how to identify any of these special functions, and the notation that is used to represent them
Empty Function:
Definition:
A function with an empty domain. That is, there are no inputs, and hence no outputs.
Notation:
• Since there are no elements in the domain, there are no pairs (x, f(x)).
• It’s a valid function, but it doesn’t do anything — it’s vacuously defined.
Example
---
Identity Function
Definition:
A function that returns exactly what was input.
Notation:
• Also written as: f(x) = x
• It’s the function that leaves all elements unchanged.
Example:
---
Constant Function
Definition:
A function that always returns the same value, no matter what the input is.
Notation:
• For some fixed
• Graphically: it’s a horizontal line (if real-valued)
Example:
---
Indicator Function
Definition:
A function that indicates membership in a subset:
• Returns 1 if the input belongs to a set
• Returns 0 otherwise
Notation:
Where:
Example:
Let , then:
Knowing what is meant by the terms injection, surjection, and bijection, and being able to identify or define these three different kinds of functions.
injection: 一对一，画一条平行于x轴的直线，与图像最多只有一个交点
surjection: image == codomain 图像在y轴上的投影覆盖整个codomain
bijection: injection + surjection
Review Lesson 2.1.2 ('Some Special Functions' section), Lesson 2.1.3, Lesson 2.2.1
Suggested Applied Exercises: Problems 1, 2, 4, 7, 8, 11
Function inversion and composition
Knowing what an inverse function is, the circumstances under which it does or doesn't exist, and being familiar with the notation used.
inverse function exists ↔ bijection
Understanding function composition, the circumstances under which it can and can't be done, being familiar with the notation used, knowing what iterated composition of a function is.
define the composition of two functions and by:
 
we can say that if is a bijection, then
 
If f and g are bijections, then
Review Lesson 2.2.2
Suggested Applied Exercises: Problems 12, 13, 14, 16, 17
Relations
Understanding what a binary relation is, how to define one or interpret the definition of one, and the difference between a binary relation and a function
1. A binary relation on sets A and B id just a set of ordered pairs: R A X B
2. define: 1. listing ordered pairs, or 2. by condition
3. a function is a type of binary relation
Properties of binary relations: reflexivity, symmetry, and transitivity
reflexivity: We say R is reflexive if , for all , we have . In other words, everything is related to itself.
symmetric: We say R is symmetric if, for all , implies
transitivity: We say R is transitive if, for all , and together imply
Knowing how to compose more than one binary relation together, and understanding the transitive closure of a binary relation
compose more than one binary relation together: if R is a binary relation from A to B, and S is a binary relation from B to C, then the composition is the binary relation from A to C whose ordered pairs is:
transitive closure: The transitive closure of a binary relation R is the smallest relation that: contain R and is transitive.
For example A = {1, 2, 3}, and relation R = {(1, 2), (1, 3)} is not transitive, because . So the transitive closure is
Understanding what an equivalence relation is, how to recognise whether or not a relation is an equivalence relation, and how to identify the equivalence classes of such a relation
equivalence relation: A relation R on a set A is called an equivalence relation if it satisfies: reflective, symmetric, transitive.
equivalence class: An equivalence class of an element , written [a], is
, that is, all elements that are equivalent to a.
Understanding how to define and interpret the definitions of higher order (e.g., ternary, n-ary) relations
ternary: lve(\)
n-ary: an n-ary relation on sets consists of n-tuples
( where for all . In other words, it is a subset of . The set is called the i-th domain.
Review all of Lesson 2.3
Suggested Applied Exercises: Problems 18, 20, 21
Counting functions and relations
Knowing how to count the number of functions on finite sets
Suppose f: A → B, where |A| = m and |B| = n, there are functions
1. if we know that f is an injection: n(n - 1)(n - 2)(n - m + 1)
2. if we know that f is a surjection:
3. if we know that f is a bijection: n!
Knowing how to count the number of relations on finite sets
How many binary relations from A to B are there, where A and B are finite set:
|A| = m, |B| = n,
Review Lesson 2.2.3, Lesson 2.3.4
Suggested Applied Exercises: Problems 23, 24
module 4: propositional logic
Basic notation and terms
Knowing what a proposition is
A proposition is a declarative sentence that is either true or false, but not both.
Knowing the basic logic operations: ∧,∨,¬,⇒,⇔,⊕ and memorising their truth tables
: implication
: Bi-implication/ equavalence
: exclusive-or.
Knowing how to form logical statements by combining Boolean variables with basic logic operations
Knowing how to write Boolean expressions to model simple real-world problems
Review: Lesson 4 pre-reading, Lesson 4.1.2 – 4.1.4
Suggested Applied Exercises: 1, 2
Laws of Boolean algebra
Knowing basic equivalences between logic operations, e.g.:
• P⇒Q is logically equivalent to ¬P∨Q
• P⇔Q is logically equivalent to (P⇒Q)∧(P⇐Q) and to (¬P∨Q)∧(P∨¬Q)
Knowing what a tautology is
A proposition that is always true
Knowing and being able to apply: De Morgan's Laws, Distributive Laws, and all other laws of Boolean algebra (as listed in Lesson 4.2.1)
1. De Morgan’s Laws:
2. Distributive Laws:
• Being able to prove two logical statements are equivalent either using truth tables, or by applying laws of Boolean algebra to show equivalence
Review: Lesson 4.1.1, Lesson 4.2.1
Suggested Applied Exercises: Problems 3, 4, 5, 6, 7, 9, 10, 11, 12
Conjunctive Normal Form (CNF) and Disjunctive Normal Form (DNF)
Knowing how to recognise and write expressions in CNF or DNF
CNF (conjunction normal form):
DNF (disjunction normal form):
Knowing how to convert expressions to CNF or DNF using truth table methods
DNF: 把为‘真’的行写成‘或’的形式
CNF: 把为‘假’的行写成‘与’的形式。（取反）
Knowing how to use De Morgan's Laws to convert a negated DNF expression to CNF (or vice versa)
DNF → CNF:
1. apply NOT to the entire expression
1. Use De Morgan’s law (outmost OR becomes AND of negated parts)
2. Apply De Morgan’s Law again (on each part)
CNF → DNF: same as DNF → CNF
Knowing how to use a CNF expression to model the conditions of a real-world problem, with clauses to specify the requirements that "at least k variables are true" and "at most k variables are true"
at least k variables are true:
logic: at least k true → at most n - k false → for every n - k + 1 variables, at least one true →
at most k variables are true:
logic: at most k true → for every k + 1 variables, at least one false → form a disjunction of the negation of every k + 1 variables →
exactly k variables are true:
at most k vars are true at least k vars are true
Knowing what is meant by a universal set of operations
Review: Lesson 4.2.2, Lesson 4.2.3, all of Lesson 4.3
Review: some of the common errors when writing Boolean expressions in CNF, in the Mid-Semester Test General Feedback post (Q8 feedback).
Suggested Applied Exercises: Problems 14, 15, 16, 22
module 5: predicate logic
Basics of predicate logic
• Using variables in logic statements
Knowing what a predicate is, and being able to use different kinds of predicates in logic statements
A predicate is a statement with variables such that, for any values of the variables, the predicate is either true or false
Knowing the meaning of and difference between these terms: predicate, proposition, function, relation, variable, constant
predicate: A logic expression with variables, not yet a full truth value. (e.g., P(x))
proposition: A statement that is either true or false
function: a mapping from input to output
relation: A logical connection between variables
Knowing how to interpret and use existential and universal quantifiers in simple predicate logic statements
Universal quantifiers:
existential quantifiers:
Review: Lesson 5 pre-reading, all of Lesson 5.1
Suggested Applied Exercises: 1, 7, 8
Working with quantifiers
• Being able to use multiple quantifiers in an expression to model more complex constraints involving existential and universal statements
• Understanding basic logical equivalences involving quantifiers
• Understanding the relationship between the quantifiers where negation is involved
Review: all of Lesson 5.2, all of Lesson 5.3
Suggested Applied Exercises: Problems 2, 3, 4, 6, 9, 10, 11, 12, 14
module 6: sequence and series
Common types of sequences
Knowing what a sequence is, and the notation used for defining both infinite and finite sequences
Sequence: a function whose domain is the set of positive integer or some finite initial portion of it
Knowing how to identify arithmetic, geometric, and harmonic sequences
arithmetic: 等差数列
geometric：等比数列
harmonic：倒数是等差数列
Review: Lesson 6 pre-reading
Finding formulas for sequences
• Knowing the difference between a recursive definition (recurrence relation) and a closed form (non-recursive) definition of a sequence, and the benefits of each
• Knowing how to give recursive definitions of arithmetic and geometric sequences, and how to use the appropriate formula to convert to a closed form definition in either case
• Knowing the general "explore, formulate, prove" approach to finding a closed form formula for a sequence, and being able to give a proof by induction to prove that a given formula works for all n.
Review: Lesson 6.1.1, Lesson 6.1.2
Suggested Applied Exercises: Problems 1–6, 8
Limits, Big-O notation, and Series
Understanding how to use limit notation to describe the behaviour of sequences over time
Understanding how to use big-O notation to describe the long-term growth of a sequence, and being able to find the big-O complexity of a given formula
Let and be nonnegative real sequences. We write f(n)=O(g(n))f(n)=O(g(n)) if there exist constants cc and N such that, for all n>N, we have
Knowing what a series is, and how to use the summation sign to describe the sum of the first n terms in a sequence
Knowing how to compute the value of a finite arithmetic series, using the relevant formula
Knowing how to compute the value of a finite geometric series, using the relevant formula
Knowing how to compute the sum of an infinite geometric series, as n→∞
condition:
formular:
Review: Lesson 6.1.3 and all of Lesson 6.2
Suggested Applied Exercises: Problems 12, 13
module 7: number theory
Basic terminology
• Multiples, divisors, primes, composites, remainders, mod, gcd
Review: Lesson 7 pre-reading
Suggested Applied Exercises: Problems 1, 2, 4
Euclidean Algorithm, Extended Euclidean Algorithm, coprimality
• Computing the gcd (greatest common divisor) of two integers using the Euclidean algorithm
• Knowing what is meant by an integer linear combination of two integers
• Using the Extended Euclidean Algorithm to express the gcd of two integers as a linear combination
• Knowing what is meant by the term coprime, and how to determine if two integers are coprime
Review: all of Lesson 7.1, Lesson 7.2.1
Suggested Applied Exercises: Problems 12, 13
Modular arithmetic, inverses
• Knowing what is meant by the terms congruence, equivalence class, multiplicative inverse
• Performing modular arithmetic with equivalence classes
• Knowing how to determine if an integer has an inverse in a particular equivalence class
• Using the Extended Euclidean Algorithm to find inverses
Review: Lesson 7.2.2 and Lesson 7.2.3
Suggested Applied Exercises: Problems 3, 7, 9, 10, 11
Euler totient function, exponentiation, primitive roots, cryptography applications
Knowing what is meant by the Euler totient function ϕ(n) of some integer n
Knowing the Euler totient function of a prime number, of prime powers, and of the product of two integers that are coprime
For prime numbers:
Performing fast and modular exponentiation, using Euler's Theorem and Fermat's Little Theorem
fast and modular exponentiation just means doing exponentiation in
Euler's Theorem:
Fermat’s Little Theorem: when n is prime p,
• Knowing what a primitive root of an integer is, and which integers do and don't have primitive roots
• Knowing what a one-way function is, and understanding its applications in cryptography
• Understanding how the Diffie Hellmann key agreement scheme uses modular exponentiation and primitive roots to securely agree on a shared secret over a public channel, then relies on the difficulty of the Discrete Log Problem for its security
Review: Lesson 7.2.4, all of Lesson 7.3
Suggested Applied Exercises: Problem 14, 16, 17, 18, 19, 20
module 8: counting and combinatorics
Basics of counting, inclusion-exclusion
• Understanding when to use counting by addition, and the correlation with the set union operation
• Understanding when to use counting by multiplication, and the correlation with the set intersection operation
• Knowing the principle of inclusion-exclusion, and how to apply it
Review: Lesson 8 pre-reading, all of Lesson 8.1
Suggested Applied Exercises: Problems 1, 5, 6, 7
Ordered selection
• Ordered selection with replacement
• Ordered selection without replacement
Review: all of Lesson 8.2
Suggested Applied Exercises: Problems 2, 3, 10
Unordered selection
• Unordered selection without replacement
• Unordered selection with replacement
Review: all of Lesson 8.3
Suggested Applied Exercises: Problems 4, 8, 9, 10
module 9: discrete probability
Probability basics
• Understanding what is meant by an event in probability, and how to describe it
• Understanding what is meant by the sample space, and how to choose a suitable sample space for a given problem
• Knowing and being able to apply the definition of probability where all outcomes are equally likely:
• Knowing and being able to apply the more general definition of probability of any event A⊆U:
Review: Lesson 9 pre-reading and Lesson 9.1.1
Suggested Applied Exercises: Problems 1(a), 2, 3
Set operations on events, combining events
Understanding what it means for two events to be mutually exclusive or disjoint, and being able to calculate the probability of two or more disjoint sets
mutually exclusive == disjoint
Being able to perform set operations on events to form other events:
• set complement:
• set difference: B \ A
• set union:
• set intersection:
Applying the inclusion-exclusion principle to probabilities where the union or intersection of three or more events is considered
inclusive-exclusive principle:
 
Understanding what it means for events to be independent, and being able to calculate the probabilities of independent events
A and B are independent if:
Review: Lesson 9.1.2, Lesson 9.1.3, Lesson 9.2.1
Suggested Applied Exercises: Problems 4, 6, 8, 9, 10, 11, 15
Conditional probability and Bayes' Theorem
Knowing how to calculate conditional probabilities
Understanding Bayes' Theorem, and how to apply it
Bayes’ Theorem:
Review: Lesson 9.2.2, Lesson 9.3.1, Lesson 9.3.2
Suggested Applied Exercises: Problems 13, 14, 16, 17, 18
Random variables
• Understanding what a random variable is, and how to work with random variables
• Knowing what is meant by the expectation of a random variable E(X), and being able to compute it for random variables where the distribution is known
Knowing and being able to use the property of linearity of expectation
E(aX + bY) = aE(X) + bE(Y)
• Knowing and being able to use the property that for two independent random variables, the expectation of their product is the product of their expectations
Knowing what is meant by median, mode, variance, and standard deviation, and how to compute these values for random variables where the distribution is known, and knowing the following:
1. median: 中位数
mode：众数
variance：方差
standard deviation：标准差
2. For two independent random variables, the variance of their sum is the sum of their variances:
3. Chebyshev's Inequality:
For any random variable X with the expectation E(X) and variance , and any :
Review: all of Lesson 10.1, all of Lesson 10.2
Suggested Applied Exercises: Problems 1, 2, 3, 5, 6
Probability distributions
For each of the following probability distributions, being able to identify examples, calculate probabilities of given events, and calculate expectation and variance:
1. Uniform distribution: 均匀分布
notation: means that the random variable X is uniform;y distributed over
2. Binomial distribution: 二项分布
notation:
3. Poisson distribution: 泊松分布
module the number of events occurring in a fix interval of time/space when events happen at a constant rate
4. Geometric distribution
notation: 注意Pr(X = k) 是第k次试验成功
• Being able to identify and solve problems that take the form of the coupon collector's problem
Review: all of Lesson 10.3
Suggested Applied Exercises: Problems 7, 8, 9, 10, 11