﻿ 离散数学hw代写 MACM 201代写 – 天才代写

# 离散数学hw代写 MACM 201代写

2022-08-13 11:11 星期六 所属： 作业代写,留学生作业代写-北美、澳洲、英国等靠谱代写 浏览：421

## MACM 201 – D100 AND D200 ASSIGNMENT #3

### 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= 3anan1 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 dbe 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 d.

(c) Using the recurrence relation, calculate d3, d4 and d5.

#### 11.

Consider the recurrence relation an= an1+ An + B where A and B are constants. Solve the recurrence with a1 = 1.

#### 12.

Solve the recurrence xn = xn1+ 20xn2for n 2 with x0 = 5, x1 = 2.