MACM 201 – D100 AND D200 ASSIGNMENT #3
离散数学hw代写 Instructions Answer all questions on paper or a tablet using your own handwriting. Please number each page. Include a cover page with your name,
Instructions 离散数学hw代写
Answer all questions on paper or a tablet using your own handwriting. Please number each page. Include a cover page with your name, student ID number and a list of the questions you answered. If you use paper make a photo of each page and upload your solutions to crowdmark. If you use a tablet, export your assignment to .pdf and upload the .pdf to crowdmark.
Definitions, Concepts & Keywords
- Random variables, expected value, the bins and balls problem.
- Construct and solve first order recurrence relations.
- Construct and solve second order recurrence relations.
Exercises 离散数学hw代写
1.
Suppose John tosses a coin 5 times. Let X be the number of heads.
Calculate P r(X = x) for x = 0, 1, 2, 3, 4, 5 and find E(X).
2.
(a) Let X be a random variable and a be a constant. Show that E(aX) = aE(X).
Follow the proof that E(X + Y ) = E(X) + E(Y ) given in class.
(b) Let X and Y be two random variables. Suppose we know E(X) = 7 and E(Y ) = 3.
Let Z = X − Y be a random variable. What is E(Z)? Justify your answer.
3. 离散数学hw代写
Suppose we toss 5 balls into 5 bins randomly. Let X be the number of balls in a bin.
(a) Determine the probability X is 0, 1, 2, 3, 4, 5 balls.
(b) Calculate E(X). You should get 1.
4.
Suppose we toss m balls into n bins randomly.
Let X be the expected number of empty bins.
In class we showed that E(X) = n(1 − 1/n)m. For n = 10 and m = 5, 10, 20 calculate E(X).
For the case n = 10 and m = 20, interpret the result for E(X) (write one sentence in English to explain what the result means).
5. 离散数学hw代写
Suppose we toss m balls into n bins randomly. Let X be the number of bins with exactly one ball in them. Determine a formula for the probability p that a bin has one ball in it and then calculate E(X), the expected number of bins with one ball. For m = n = 10 calculate p and E(X). You should get p = 0.38742.
6.
Consider the recurrence an+1= 3an− an−1 with a1 = 1, a2 = 1. Calculate a0, a3, a4.
7.
Give an example of a first order non-homogenous recurrence relation and a second order homogeneous recurrence relation.
8.
As I write this the number of people in India with the corona virus is 2.5 million. It is estimated that each person who has the virus will, on average, infect 3 people in a week before recovering or dying. Let inbe the number of people infected after n weeks where i0= 2.5 million. Give a recurrence relation for in. How long will it take before 100 million are infected?
9. 离散数学hw代写
Below is C code, and Python code, for the Selectionsort algorithm. The input is an array A of n decimal numbers. Line 10 sorts the first n − 1 numbers in A recursively.
C Code:
1: void Selectionsort( double A[], int n ) {
2: // sort A[0],A[1],...,A[n-1] into ascending order
3: int i,m; double t;
4: if( n<=1 ) return; // A is already sorted
5: m = 0;
6: for( i=1; i<n; i++ )
7: if( A[i]>A[m] ) m = i;
8: // interchange A[i] and A[m]
9: t = A[i]; A[i] = A[m]; A[m] = t;
10: Selectionsort(A,n-1);
11: return;
12: }
Python Code:
1: def Selectionsort(A,n): 2: # sort A[0], A[1], ..., A[n-1] into ascending order 3: if n<=1: 4: return # A is already sorted 5: m=0 6: for i in range(1,n): 7: if A[i]>A[m]: m=i 8: # interchange A[i] and A[m] 9: A[i], A[m] = A[m], A[i] 10: Selectionsort(A,n-1)
Let cn be the number of comparisons between elements of A made in line 7. Give a recurrence equation and an initial value for cn and solve it. Does Selectionsort do fewer or more comparisons than Bubblesort?
Note: you do not need to know how an algorithm works in order to count the number of times it executes a particular operation.
10. 离散数学hw代写
In a resort in Mexico guests may have dinner at three restaurants, the Italian restaurant, the French restaurant or the Brazilian restaurant. Each evening you must eat at one of the restaurants but you may not eat at the French restaurant two nights in a row. Let dn be the number of ways you may eat at the three restaurants over n evenings.
(a) How many eating choices are there for 1, 2 and 3 nights?
(b) Find a recurrence for dn .
(c) Using the recurrence relation, calculate d3, d4 and d5.
11.
Consider the recurrence relation an= an−1+ An + B where A and B are constants. Solve the recurrence with a1 = 1.
12.
Solve the recurrence xn = xn−1+ 20xn−2for n ≥ 2 with x0 = 5, x1 = −2.
更多代写：racket编程代写 考试代考 英国理工科网课代修 critical essay怎么写 英文简历模板 代写总结思路
