CS计算机代考程序代写 algorithm Chapter 6

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