MTH 221 Wk 5 – Final Exam

Complete the final exam. You have one attempt at the exam. So, be sure to review all previous course materials before attempting the exam.

Question 1

Select the correct value for 74mod11.

3

8

-3

-8

Question 2

What is the value of left parenthesis 260 times 5321 plus 42 times 28 right parenthesis mod 13 ?

6

7

9

12

Question 3

x equals 3 to the power of 4 times 5 cubed times 7 times 11 to the power of 4 y equals 3 squared times 5 to the power of 4 times 7 times 13 to the power of 4

What is the prime factorization for gcd(x, y)?

3 squared times 5 cubed

3 squared times 5 cubed times 7

3 squared times 5 cubed times 7 squared

3 squared times 5 cubed times 7 times 11 to the power of 4 times 13 to the power of 4

Question 4

Let straight pi left parenthesis x right parenthesis be the number of prime numbers in the range from 2 to x. Select the pair of inequalities that are both true.

straight pi left parenthesis 1000 right parenthesis less or equal than straight pi left parenthesis 10000 right parenthesis fraction numerator straight pi left parenthesis 1000 right parenthesis over denominator 1000 end fraction less or equal than fraction numerator straight pi left parenthesis 10000 right parenthesis over denominator 10000 end fraction

straight pi left parenthesis 1000 right parenthesis less or equal than straight pi left parenthesis 10000 right parenthesis fraction numerator straight pi left parenthesis 1000 right parenthesis over denominator 1000 end fraction greater or equal than fraction numerator straight pi 10000 right parenthesis over denominator 10000 end fraction

straight pi left parenthesis 1000 right parenthesis greater or equal than straight pi left parenthesis 10000 right parenthesis fraction numerator straight pi left parenthesis 1000 right parenthesis over denominator 1000 end fraction less or equal than fraction numerator straight pi left parenthesis 10000 right parenthesis over denominator 10000 end fraction

straight pi left parenthesis 1000 right parenthesis greater or equal than straight pi left parenthesis 10000 right parenthesis fraction numerator straight pi left parenthesis 1000 right parenthesis over denominator 1000 end fraction greater or equal than fraction numerator straight pi left parenthesis 10000 right parenthesis over denominator 10000 end fraction

Question 5

Use the equation below to determine the multiplicative inverse of 23 mod 96.

1 equals 6 times 96 minus 25 times 23

6

25

-25

71

Question 6

Select the decimal representation for (A07)16 .

261

263

2560

2567

Question 7

Select the correct value for 740mod2399 . The following equalities may be useful:

72mod2399=49

74mod2399=2

78mod2399=4

716mod2399=16

732mod2399=256

764mod2399=512

260

514

1024

2048

Question 8

Alice encrypts a message m to send to Bob by computing:

(m + 51) mod 83.

If the cyphertext that Alice sends is 11, then what was the original message?

62

43

-40

11

Question 9

Bob uses the RSA cryptosystem to allow people to send him encrypted messages. He selects the parameters:

p=3,q=17,e=3,d=11

Alice wants to send the message m = 5 to Bob. Select the cyphertext that she sends.

4

23

24

37

Question 10

To select a stir-fry dish, a restaurant customer must select a type of rice, protein, and sauce. There are two types of rices, three proteins, and seven sauces. How many different kinds of stir-fry dishes are available?

2 plus 3 times 7

2 times 3 times 7

2 plus 3 plus 7

2 cubed times 7

Question 11

A country has two political parties, the Reds and the Blues. The 100-member senate has 44 Reds and 56 Blues. Each party must elect a chair and a vice chair from their party’s members, and one person cannot be elected for both. How many different outcomes are there for the chair and vice chair elections?

100 times 99 times 98 times 97

44 times 43 times 56 times 55

100 to the power of 4

44 squared times 56 squared

Question 12

There is a set of 10 jobs in the printer queue. One of the jobs in the queue is called job A. How many ways are there for the jobs to be ordered in the queue so that job A is the first to finish or the last to finish?

fraction numerator 10 factorial over denominator 2 end fraction

2 times 9 factorial

9 factorial

10 factorial

Question 13

A country has two political parties, the Reds and the Blues. The 100-member senate has 44 Reds and 56 Blues. How many ways are there to pick a 10 member committee of senators with the same number of Reds as Blues?

open parentheses table row 44 row 10 end table close parentheses times open parentheses table row 56 row 10 end table close parentheses

open parentheses table row 100 row 10 end table close parentheses

open parentheses table row 44 row 5 end table close parentheses plus open parentheses table row 56 row 5 end table close parentheses

open parentheses table row 44 row 5 end table close parentheses times open parentheses table row 56 row 5 end table close parentheses

Question 14

A class of 30 students with 14 boys and 16 girls must select 4 leaders. How many ways are there to select the 4 leaders so that at least one girl is selected?

16 times open parentheses table row 29 row 3 end table close parentheses

16 times open parentheses table row 30 row 3 end table close parentheses

open parentheses table row 30 row 4 end table close parentheses minus open parentheses table row 16 row 4 end table close parentheses

open parentheses table row 30 row 4 end table close parentheses minus open parentheses table row 14 row 4 end table close parentheses

Question 15

A teacher with 10 students has 30 lesson times available. She will teach exactly one of her students during each lesson time. How many ways are there for her to decide which student she will teach during each lesson time if she must teach each student exactly 3 times?

open parentheses table row 30 row 10 end table close parentheses

P left parenthesis 30 comma 10 right parenthesis

fraction numerator 30 factorial over denominator 10 times 3 factorial end fraction

fraction numerator 30 factorial over denominator left parenthesis 3 factorial right parenthesis to the power of 10 end fraction

Question 16

A store sells 6 varieties of donuts. Chocolate is one of the varieties sold. How many ways are there to select 14 donuts if at most 4 chocolate donuts are selected?

open parentheses table row 19 row 5 end table close parentheses minus open parentheses table row 15 row 5 end table close parentheses

open parentheses table row 19 row 5 end table close parentheses minus open parentheses table row 15 row 4 end table close parentheses

open parentheses table row 19 row 5 end table close parentheses minus open parentheses table row 14 row 5 end table close parentheses

open parentheses table row 19 row 5 end table close parentheses

Question 17

17 different tasks are assigned to 7 different people. Each task is assigned to exactly one person and there are no restrictions on the number of tasks that can be given to any one person. Since the tasks are different, it matters who gets which tasks. How many ways are there to assign the tasks?

open parentheses table row 23 row 6 end table close parentheses

P left parenthesis 17 comma 7 right parenthesis

17 to the power of 7

7 to the power of 17

Question 18

There is a set of 14 jobs in the printer queue. Two of the jobs in the queue are called job A and job B. How many different ways are there for the jobs to be ordered in the queue so that job A is first or job B is last or both?

13 factorial minus 12 factorial

2 times 13 factorial

2 times 13 factorial minus 12 factorial

13 factorial

Question 19

Each person in a group weighs at least 100 pounds and at most 130 pounds. How large must the group be in order to guarantee that there are at least 2 people whose weights differ by at most 9 pounds?

5 people

6 people

30 people

31 people

Question 20

What is the total degree of the graph below?

3

4

6

8

Question 21

Suppose that G is a graph with n vertices such that every vertex has degree 4. If the graph is represented using the matrix representation, then what is the worst-case complexity to find all the neighbors of a particular vertex?

theta left parenthesis 1 right parenthesis

theta left parenthesis log n right parenthesis

theta left parenthesis n right parenthesis

theta left parenthesis n squared right parenthesis

Question 22

Select the graph property that is not preserved under isomorphism. The vertices of the graph are numbered 1 through n, where n is the number of vertices.

The degree of every vertex is 3.

The degree of every vertex is at least n/2.

Every even numbered vertex has degree 3.

The graph has at least n/2 vertices of degree 1.

Question 23

In the graph below, which pair of vertices have a path of length 6 between them?

B and C

B and G

C and D

D and G

Question 24

Which set is a connected component of the graph below?

{A, H}

{B, D, F}

{C, E, G, J}

{A, B, D, F, H, J}

Question 25

The degree sequence of a graph is a list of the degrees of all of the vertices in non-increasing order. The degree sequence for four different graphs are given below. Each graph is guaranteed to be connected. Select the degree sequence corresponding to the graph that has an Euler circuit.

1, 2, 3, 3, 4, 4, 4, 5

2, 2, 2, 4, 4, 4, 4

2, 2, 3, 4, 4, 4, 5

2, 3, 3, 4, 4, 4, 6

Question 26

Select the sequence that is a Hamiltonian cycle for the graph shown below:

open angle brackets d comma e comma f comma b comma a comma c close angle brackets

open angle brackets d comma e comma f comma b comma a comma c comma d close angle brackets

open angle brackets d comma f comma e comma c comma a comma b comma d close angle brackets

open angle brackets d comma f comma e comma c comma b comma a comma d close angle brackets

Question 27

A planar graph G has 7 vertices. One of the vertices has degree 4, two vertices have degree 3, and four vertices have degree 2. How many regions does G have?

4

5

6

7

Question 28

The greedy algorithm is used to color the graph shown below. The vertices are colored in order: A through G. The colors are ordered as:

1 – Red

2 – Blue

3 – Green

4 – Yellow

5 – Purple

What is the coloring assigned to each vertex?

A – red, B – red, C – blue, D – green, E – yellow, F – yellow, G – purple

A – red, B – blue, C – red, D – red, E – red, F – blue, G – blue

A – red, B – red, C – blue, D – green, E – green, F – yellow, G – yellow

A – red, B – blue, C – green, D – red, E – red, F – blue, G – blue

Question 29

Which choice corresponds to the level 2 vertices?

j, f, and i

g, b, and c

j, d, k, and i

e, d, m, a, and l

Question 30

Use the prefix tree below to encode the word “piece”.

11101000011110

11110100011110

1110100011110

1110100001110

Question 31

Select the set of properties such that it is impossible to have a graph that satisfies all the properties in the set.

Connected, 7 vertices, 7 edges

Tree, 10 vertices, 9 leaves

8 vertices, 10 edges, not a tree

Acyclic, 7 vertices, 7 edges

Question 32

Select the sentence that correctly describes the value returned by Post-order(r), where r is the root of a tree.

Post-order(v)

Count = 0

For every child w of v:

Count = Count +1

End-for

For every child w of v:

x := Post-order(w)

If (x > Count) Count := x

End-for

Return( Count )

The height of the tree

The number of leaves in the tree

The number of internal vertices in the tree

The largest number of children belonging to any vertex in the tree

Question 33

The graph below is traversed using depth first search. The search starts at vertex A and ends with vertex F. The vertices are considered in alphabetical order. What are the edges in the depth first search tree?

{A, B}, {B, D}, {A, C}, {C, E}, {E, F}

{A, B}, {B, D}, {B, E}, {E, C}, {E, F}

{A, B}, {A, C}, {C, E}, {E, B}, {B, F}

{A, B}, {B, D}, {B, F}, {F, E}, {F, C}

Question 34

What are the edges in the minimum spanning tree of the graph shown below?

{d, f}, {f, c}, {c, h}, {c, e}, {e, g}, {f, a}, {a, b}

{d, f}, {f, c}, {c, h}, {c, e}, {e, g}, {c, a}, {a, b}

{d, f}, {d, g}, {g, e}, {e, c}, {c, h}, {f, a}, {a, b}

{d, f}, {d, g}, {g, e}, {e, c}, {c, h}, {c, a}, {a, b}