当前位置:天才代写 > 作业代写,留学生作业代写-北美、澳洲、英国等靠谱代写 > 离散数学代写 CS 70代写 概率论代写

离散数学代写 CS 70代写 概率论代写

2021-08-27 17:08 星期五 所属: 作业代写,留学生作业代写-北美、澳洲、英国等靠谱代写 浏览:1047

CS 70代写

CS 70 Discrete Mathematics and Probability Theory

离散数学代写 You can (if you choose) use latex. It is fairly easy and satisfying. Surround an expression by “$$ … $$” on gradescope and you will be in latex.

 

Some Latex Commands for Gradescope.

You can (if you choose) use latex. It is fairly easy and satisfying. Surround an expression by “$$ … $$” on gradescope and you will be in latex. Examples: “$$ A+B*D $$” will give: A+BD. There are useful commands:

 

离散数学代写
离散数学代写

1.Long Ago. 

1.A∨ ¬(BC) A∨ (¬B∨ ¬C)

True

False

2.¬∀x,y,Q(x, y) ≡ ∃x,y,¬Q(x, y)

True

False

3.P ⇒ Q is logically equivalent to ¬QP.

True

False

4.Consider a stable matching instance where S is the job optimal stable pairing. Consider a run of the job-propose matching algorithm, where one candidate c rejects a job j that they should not have in one step. That is, c recieves an offer from and jand chooses jinstead of j, when j was ahead of jin their preference list.

Let P be the resulting pairing.

(a) For every instance, job j cannot do better in P than in S. (Better means get a partner who they prefer more.)

True

False

(b) Every candidate other than c does as well or better in P than in S.

True

False

(c) Every job other than j does as well or better in P than in S.

True

False

 

2. Graphs  离散数学代写

1.Consider a graph on n vertices with exactly one cycle and m edges. What is the number of connected components? (Hint: m n.)

2.For a tree on n vertices, what is the expected number of connected components if each edge is deleted with probability 1/3?

3.If we delete every edge with probability 1/2 from an Eulerian graph on n vertices, what is the expected number of odd degree vertices in the remaining graph?

4.Every simple cycle is 2-colorable.

True

False

 

3.Mostly Modular.  离散数学代写

1.∀ nonzero x, y N gcd(x, y mod x) = gcd(x, y).

True

False

2.∀ nonzero x, y N, gcd(x, mod y) = gcd(x, y).

True

False

3.Give an example of positive integers for a and n where

(1 · 2···(n1))an-1 ≠ (1 · 2···(n1)) (mod n).

a:______________

n:______________

4.Let S = {x : x ∈ {1,…,34} and gcd(x,35) = 1}?

(a) What is the size of the set S?

(b) What is a|S|+1 (mod 35) for a S?

(c)What is a|S|+1 (mod 35) for a 6∈ S?

5.What is 18-1 (mod 13)?

6.If x = 1 (mod 13) and x = 0 (mod 18) then what is x (mod 234)? (Note: 234 = 18×13)

7.For primes, p and q, where e = d-1 (mod (p1)(q1))?

(a) What is aed (mod q)? (Answer cannot use e or d, but may use numbers, a,p or q.)

(b) Find an x pq, where p|(aed x). (Answer is an expression that may use a, p, and q.)

 

4.Polynomials.  离散数学代写

1.Given a polynomial,  +a2 +a1x+a0 modulo 7 with roots at 3, 1, and 6. What is a0? (Notice that the coeffificient of  is 1.)

2.Working (mod 5), fifind a polynomial modulo 5 of degree 2 that has roots at 0 and 3, and goes through point (2,3)

3.Consider that one encodes a message of n numbers (mod m), by forming a degree n1 polynomial using the numbers as coeffificients, and sending 2n1 points. If each point is erased with probability 1/2, what is the probability that the original message can be reconstructed? (Hint: each pattern of erasures is equally probable.)

 

5.Countability/Computability.  离散数学代写

1.For every pair of distinct rational numbers there is a rational number in between them.

True

False

2.The rational numbers are uncountable.

True

False

3.There is a program that takes a program P, an input x, and a number n and determines whether P run on input x ever writes to memory location n.

True

False

4.There is a program that takes a program P, an input x, and a number n and determines whether P run on input x ever writes to any memory location i n.

True

False

5.A program “knows” a real number if it takes an integer n and outputs the nth bit of the real number. (Note: positive values of n signify to the left of the decimal point, and negative ones to the right.)

(a)There is a program that knows π.

True

False

(b)For every real number x, there is a program that knows x.

True

False

 

6.A little counting. 

1.What is the number of ways to have k strictly positive numbers that add up to n?

2.What is the number of ways to produce a sequence of numbers 0 < x1 < x2 < ··· < xk < n?

3.What is the number of ways to produce a sequence of numbers 0 xx2 ≤ ··· ≤ xk < n?

4.What is the number of poker hands that have at least 1 ace? (Recall that a poker hand is 5 cards from a 52 card deck.)

 

7.Probability. 离散数学代写

1.Consider rolling two six sided fair dice.

(a) What is the probability that exactly one die is 6?

(b) What is the probability that the sum of the two dice is 6?

(c) What is the probability that the sum is 6 given that at least one die is at least 3?

(d) The event of rolling a 6 on the fifirst die is independent of the event that the dice sum to 7.

True

False

(e) The event of rolling at least one 6 is independent of the event that the dice sum to 7.

True

False

2.Flip a coin until you repeat either heads or tails 2020 times. We will derive the probability that the fifirst coin is the same as the last coin in the entire sequence of flflips.

(a)If the process stops after 2020 tosses, what is the probability that the fifirst and last coin are the same?

(b)If the process stops after 2021 tosses, what it the probability that the fifirst and last coin are the same?

(c) What is the probability that the fifirst coin is the same as the last coin in the entire sequence of flflips?

3.Which of the following are always true.

(a)E[10X] = 10E[X]

True

False

(b)E[ ] = E[X]²

True

False

(c)E[(X Y)² ] = E[ ] +E[]2E[X]E[Y]

True

False

(d)Var(X +Y) = Var(X) +Var(Y)

True

False

 

8.Marbles.  离散数学代写

Consider two bags of marbles, the “majority red” bag has 6 red marbles and 4 blue marbles, and the “majority blue” bag has 3 red marbles and 7 blue marble, and each bag is chosen with probability 1/2.

1.If you draw a blue marble where each marble in the bag is equally likely, what is the probability that the bag is the “majority blue” bag.

2.What is the probability that the next marble is blue?

 

9.Variance, covariance, tail bounds.

1.If E[X] = 4, and E[Y] = 5, and E[XY] = E[X]E[Y], what is cov(X,Y)?

2.A student earns one standard deviation above the mean on both exam 1 and exam 2. We defifine random variables X and Y as the score of a randomly chosen student on exam 1 and exam 2 respectively. If Var(X) = 1, Var(Y) = 1 and Cov(X,Y) = .5, how many standard deviations above the mean did the student get on the sum of her two scores? (Recall, Var(X +Y) = Var(X) +Var(Y) +2Cov(X,Y). )

3.For a random variable, X, where X ≥ −1, E[X] = 5, and E[ ] = 26. Give an upper bound Pr[X 6]. (It should be tight with respect to the appropriate inequality.)

4.For a random variable, X, where E[X] = 5, and E[ ] = 26, give an upper bound Pr[X 9]. (It should be tight with respect to the appropriate inequality.)

 

10.Markov Chain. 

Consider the following Markov chain.

 

离散数学代写
离散数学代写

 

1.For what value of a does the chain have a unique invariant distribution but does not always converge to it.

2.For a = 1/2, what is the stationary distribution?

π(1):__________

π(2):__________

π(3):__________

 

 

11.Balls and Bins.  离散数学代写

Consider placing 5n balls into 3n bins uniformly at random. (Careful, the constants in front of the n’s are important.)

1.What is the expected number of empty bins?

2.What is the variance of the number of empty bins?

3.What is the expected number of non-empty bins?

4.What is the variance of the number of non-empty bins (in terms of the answer for part (1),(2) and/or (3).)

 

12.Sequential Dice.

Consider rolling a dice repeatedly and until one gets two 6’s in a row.

1.Draw a three state Markov chain where the states are labelled A,B, and C. Your chain should have a state C which is the “goal”; the previous two rolls were a 6. State A should indicate that one has not rolled any die or that the previous die is not 6.

2.What is the expected number of rolls to roll two 6’s in a row?

3.What is the probability of rolling two 6’s in a row prior to rolling a 5? (Hint: add a state to your previous Markov Chain and do a computation.)

 

离散数学代写
离散数学代写

 

其他代写:加拿大代写 作业代写 作业加急 英国代写 北美作业代写 homework代写 java代写 matlab代写 program代写 project代写 essay作业代写 finance代写 python代写 report代写 paper代写 assignment代写

合作平台:essay代写 论文代写 写手招聘 英国留学生代写

 

天才代写-代写联系方式