Discrete Math

Question 1

1.        

Given an unordered list of n numbers, what algorithm would you use to sort it, and what is the worst-case runtime of the algorithm?

Answer


a.
Tournament sort, O(n log n).

b.
Tournament sort, O(n).

c.
Prim's Algorithm, O(n log n).

d.
Prim's Algorithm, O(n * n).
4 points   

Question 2

1.        

Given a graph with n vertices, what is the minimum number of edges needed such that the graph is connected?

Answer


a.
n.

b.
n – 1.

c.
n * n.

d.
n log n.
4 points   

Question 3

1.        

Which is a minimal spanning tree of the following graph:



[D]

 

Answer


a.
A-B-D-E-C.

b.
A-D-E-C-B.

c.
A-B-D.

d.
There is no minimal spanning tree.
4 points   

Question 4

1.        

How many six-bit strings begin with 100?

Answer


a.
4.

b.
8.

c.
32.

d.
16.
4 points   

Question 5

1.        

If you select 5 microprocessors from 100 microprocessors, where 30 of the 100 are defective, what is the probability that you select no defective processors?

Answer


a.
C(100, 10)/C(30, 5).

b.
C(70, 5)/C(100, 5).

c.
C(100, 5).

d.
C(100, 5)/C(70, 5).
4 points   

4 points   

Question 7

1.        

Which of the following is not a proof method?

Answer


a.
Existence proof.

b.
Proof by contradiction.

c.
Proof by converse.

d.
Direct Proof.
4 points   

Question 8

1.        

What is the cardinality of the set X = {1,5,3,8,10}?

Answer


a.
5.

b.
1.

c.
10.

d.
27.
4 points   

Question 9

1.        

Given a hash function h(n) = n mod 5, what would a computer s memory cells look like if we were to input values 2, 9, and 13:



 [D]

 

Answer


a.
2
10
14
 
 
0
1
2
3
4

b.
 
 
2
13
9
0
1
2
3
4

c.
 
2
10
 
14
0
1
2
3
4

d.
 
 
10
 
2,14
0
1
2
3
4
4 points   

Question 10

1.        

Represent the following database as n-ary tuples:



[D]

 

Answer


a.
{(Joe Smith, Smith21,1), (Jane Doe, Jdoe1, 1), (Tim Thomas, TimT, 5)}.

b.
{(Joe Smith, Jane Doe, Tim Thomas), (Smith21, Jdoe1, TimT), (1, 1, 5)}.

c.
{(Joe, Smith, Smith21,1), (Jane, Doe, Jdoe1, 1), (Tim, Thomas, TimT, 5)}.

d.
{(Joe, Smith, Jane, Doe, Tim, Thomas), (Smith21, Jdoe1, TimT), (1, 1, 5)}.
4 points   

Question 11

1.        

Assume A is the universal quantifier, E is the existential quantifier and ~ is the symbol for NOT. Let P(x) = 2 x3x. Assume that x can be any real number. Which of the following statements is true?

Answer


a.
Ex P(x).

b.
Ax P(x).

c.
Ax ~P(x).

d.
None of the above.
4 points   

Question 12

1.        

How many strings of length 3 are possible (without repetition) given a set X = {a, b, c, d}.

Answer


a.
6.

b.
8.

c.
24

d.
1,248.
4 points   

Question 13

1.        

Given the graph below, what is (A, D, C, D, B)?



[D]

 

Answer


a.
Simple path.

b.
Cycle.

c.
Simple cycle.

d.
None of the above.
4 points   

Question 14

1.        

Given the graph below, which of the following is a Hamiltonian cycle? 



[D]

 

Answer


a.
(C, E, D, A, B, C)

b.
(A, D, B, C, E, D, A).

c.
(B, C, E, D, B, C, B).

d.
(C, E, D, A, C).
4 points   

Question 15

1.        

Given the graph below, what is the total weight of the shortest weighted path from A to E?



[D]

 

Answer


a.
8.

b.
5.

c.
4.

d.
3.
4 points   

Question 16

1.        

Given a graph with n vertices, what is the minimum number of edges needed to make the graph connected?

Answer


a.
n.

b.
n – 1.

c.
n * n.

d.
n log n.
4 points   

Question 17

1.        

How many times does the computer print the string "Good bye"?
i = 2
while (i < 7) {

print ("Good bye")

i = i + 1}

Answer


a.
4.

b.
5.

c.
3.

d.
6.
4 points   

Question 18

1.        

Which of the following algorithm computation times is O(n)?

Answer


a.
2n – 5.

b.
n * log(n).

c.
n * n + n.

d.
None of the above.
4 points   

Question 19

1.        

If each of the following describes the run time of an algorithm, which of the following has the longest worst-case run time?

Answer


a.
O(nlog(n)).

b.
O(n).

c.
O(n/2).

d.
O(n * n).
4 points   

Question 20

1.        

What does the following algorithm return?

f(n){
if (n< 2)

return 1

else

return f(n – 1) + n

Answer


a.
n!

b.
The maximum divisor of n.

c.
n + (n – 1) + (n – 2) + . . . + 1.

d.
n – 2.
4 points   

Question 21

1.        

In terms of n, what is the closest-fit worst-case time complexity of the following algorithm?

f(n){
if (n< 2)

return 1

else

return f(n – 1) * n

Answer


a.
O(n).

b.
O(log(n)).

c.
O(n!).

d.
None of the above.
4 points   

Question 22

1.        

Note that in analysis of algorithms, time complexity is typically measured in terms of the size of the input and not the input values. If n is a single number, then its binary string representation can be represented using approximately m bits (the size of the input), where m = log_2(n). Therefore, the maximum value that can be expressed in m bits is n = O(exp(m)). In terms of m, what is the closest-fit worst-case time complexity of following algorithm?

 
f(n){
if (n< 2)

return 1

else

return f(n – 1) * n

 

Answer


a.
O(m).

b.
O(log(m)).

c.
O(exp(m)).

d.
None of the above.
4 points   

Question 23

1.        

Given the graph below, which algorithm is best used to find a shortest path from A to E?



[D]

 

Answer


a.
Dijkstra's.

b.
Tournament sort.

c.
Prim's.

d.
Bubble sort.
4 points   

Question 24

1.        

Which of the following problems cannot be solved using graphs and graph-based algorithms?

Answer


a.
Matching problem.

b.
Sorting of a list of numbers.

c.
Traveling salesman problem.

d.
None of the above.
4 points   

Question 25

1.        

Which of the following problems can always be solved using trees and tree-based algorithms?

Answer


a.
Maximum flow problem.

b.
Minimum cut problem.

c.
Sorting of a list of numbers.

d.
All of the above.