闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

1. (10ts) True or False

1 For any two sets A and B, A - B ≠ B - A

2 For any sets A, B and C, (A ׫ B) ׫ C = A ׫ (B ׫ C)

3 { ׎} א { ׎}

4 Let P be a program with complexity O(n) and Q be a program with complexity O(n2 ). For any input, P runs faster than Q

5 For any two sets A and B such that A is uncountable and B is countable, A - B must be uncountable

6 The student was asked whether a given function f is one-to-one. He chose two random elements 5 and 6 in the domain and showed that they f(5) and f(6) are same. Student concluded that the function is not one-to-one. Is the student’s reasoning correct?

7 The student was asked whether a given function f is one-to-one. He chose two random elements 5 and 6 in the domain and showed that they f(5) and f(6) are different. Student concluded that the function is one-to-one. Is the student’s reasoning correct?

8 The function f : Z × Z → Z f (m, n) = 2m − n is onto

9 The function f: RxR → R f (x) = (x + 1)/(x + 2) is a bijection

10 There exists a function f such that it is O(x2 ) but not O(x3 )

2. (10pts) Numerical Questions

1 How many multiplications are required for multiplying matrices A and B, if A is 15x20 and B is 20x10 (using the standard algorithm)

2 Let A, B, C be sets with 10, 20 and 30 elements each. How many elements are present in AxBxC?

3 What is the smallest integer value of n such that the function f(x) = x3 (log x)5 is O(xn )

4 What is the largest integer value of n such that the function f(x) = x6 (log x)5 is Ω(xn )

5 Program P takes 2n steps for an input of size n. The CPU can execute 230 steps in one second. What is the largest size of input P could handle if it must finish in 100 seconds? (Note size of the input is an integer. It cannot be a fraction.)

6 What is 59602 mod 97?

7 How many positive integers between 1000 and 9999 inclusive are divisible by 7?

8 How many one-to-one functions are there from R to Z? (You could specify a specific number or you can say infinite)

9 Find the first five terms of the sequence (a0 .. a4) defined by the following recurrence relation and initial condition. an = 6an−1, a0 = 2

10 Let S = {−1, 0, 2, 4, 7}. Find f (S) if f (x) = 2x + 1.

3. (10pts) Short questions

a. True or False?

23n is O(32n): Your answer

Explanation justifying your answer

b. Arrange the functions √n, 1000 log n, n log n, 2n!, 2n, 3n, and n2 /1,000,000 in a list so that each function is big-O of the next function.

c. Find a one-to-one function from R (set of real numbers) to the set [1..5]. (You can consider different cases based on what the input is.)

d. Using the definition of O notation, find the value of c and k to show that