Theory of Computation - Week 0 Quiz Solutions

Question 1

The number of bit strings of length 8 that either start with 1 or end with 00 is?

A.32

B.128

C.160

D.192

Correct Answer: 32

Question 2

Let G be a connected planar graph with 10 vertices. If the number of edges on each face is 3, then the number of edges in G is?

A.20

B.24

C.32

D.36

Correct Answer: 20

Question 3

Which of the following is correct?

A.The number of odd degree vertices in an undirected graph is odd

B.The number of odd degree vertices in an undirected graph is even

C.The number of even degree vertices in an undirected graph is even

D.The number of even degree vertices in an undirected graph is odd

Correct Answer: The number of odd degree vertices in an undirected graph is odd

Question 4

Consider the relation R = {(x, x), (y, y), (x, z), (z, x)}on the set x, y, z. Which one of the following is TRUE?

A.R is reflexive

B.R is symmetric

C.R is anti- symmetric

D.R is anti- reflexive

Correct Answer: R is reflexive

Question 5

How many onto (surjective) functions are there from an n-element set (n ≥ 2) to a 2-element set?

A.2 n − 2

B.2 n − 1

C.2 n

D.2(2 n − 1)

Correct Answer: 2 n − 2

Question 6

What is the total number of possible symmetric relations on a set of 3 elements?

A.2 9

B.2 6

C.2 3

D.2

Correct Answer: 2 9

Question 7

How many even numbers of 2 digits are there which have both digits distinct?

A.41

B.42

C.43

D.44

Correct Answer: 41

Question 8

How many 4-digit numbers can be formed from the digits 1, 2, 3, 4, 5, 6,7 which are divisible by 5 (none of the digits are repeated)?

A.24

B.36

C.120

D.720

Correct Answer: 24

Question 9

Which of the following binary strings is a palindrome?

A.1011001

B.1100011

C.10101010

D.11001101

Correct Answer: 1011001

Q10

Question 10

How many odd numbers of 3 digits are there which have all 3 digits distinct?

A.320

B.360

C.328

D.300

Correct Answer: 320

Practice: Week 0: Assignment 0