1-2 | Quiz I

Question 1

13 in binary system?

Answer 1

1101

Question 2

174 in binary system?

Answer 2

10101110

Question 3

Size of an instance
What is the size of a positive integer 𝑛?

eg 13, 174

algorithm to determine this?

Answer 3

13 is represented by 4 bits
174 is represented by 8 bits

procedure size(𝑛)
s ← 0
while (𝑛 > 0) do
𝑛 ← ⌊𝑛/2⌋
𝑠 ← 𝑠 + 1
return 𝑠

Question 4

1.

Suppose that a is a positive integer. To prove the claim “If a<sup<2</sup> is even, then a is even”, by contradiction, we assume:

• a<sup<2</sup> is even and a is even
• a<sup<2</sup> is odd and a is odd
• a<sup<2</sup> is odd and a is even
• a<sup<2</sup> is even and a is odd

Answer 4

a<sup<2</sup> is even and a is odd

Question 5

2.

Suppose that a is positive integer. If a is divisible by 5 and a is divisible by 3, then:

• a = 3k, where k is an integer divisible by 2
• a = 15k, where k is an integer
• a = 3k, where k is an integer that is not divisible by 5
• a = 5k, where k is an integer that is not divisible by 3

Answer 5

a = 15k, where k is an integer

Question 6

3.

The summation Σ_1≤k≤nk(k+1) equals

• n(n+1)
• n²
• n(n+1)/2
• n(n+1)(n+2)/3

Answer 6

n(n+1)(n+2)/3

Question 7

4.

The summation Σ1≤s≤n(2-s)2 equals

• 4n + 6Σ_1≤s≤ns + Σ_1≤s≤ns²
• 2n + 6Σ_1≤s≤ns
• 4n -4Σ_1≤s≤ns -Σ_1≤s≤ns²
• 4n -4Σ_1≤s≤ns + Σ_1≤s≤ns²

Answer 7

4n -4Σ_1≤s≤ns + Σ_1≤s≤ns²

Question 8

5.

TRUE or FALSE:

Let log_ax denote logarithm with base a of x. Then, x = b^log_ax, where a ≠ b.

Answer 8

FALSE

Question 9

6.

TRUE or FALSE:

If a is rational and a*b is irrational, then b is irrational.

Answer 9

TRUE

Question 10

7.

TRUE or FALSE:

Σ_2≤i≤n-2k(k-1)(n-k) = Σ_0≤i≤nk(k-1)(n-k).

Answer 10

FALSE

Question 11

8.

TRUE or FALSE:

Σ_1≤i≤nln(a_i*b_i/c_i) = Σ_1≤i≤nln(a_i) + Σ_1≤i≤nln(b_i) - Σ_1≤i≤nln(c_i)

Answer 11

TRUE

Question 12

9.

TRUE or FALSE

Σ_1≤i≤nb + Σ_1≤j≤ma = nb+(m+1)a

Answer 12

FALSE

Question 13

10.

The summation Σ_2≤i≤n(i+1) equals:

• (n²+3n-4)/2
• (n+1)²
• (n-1)(i+1)
• n(n+1)/2

Answer 13

(n²+3n-4)/2