MTH 221 All Weeks Homework https://uopcourses.com/category/mth-221/
MTH/221
DISCRETE MATH FOR INFORMATION TECHNOLOGY
The Latest Version A+ Study Guide
**********************************************
MTH 221 Entire Course Link
https://uopcourses.com/category/mth-221/
**********************************************
MTH 221 Wk 1 — Ch. 2 Homework
Complete each section of Ch. 2, “Logic and Sets.” You must use this link to earn points.
MTH 221 Wk 2 — Ch. 3 Homework
Complete each section of Ch. 3, “Functions, Boolean Algebra, and Relations.” You must use this link to earn points.
MTH 221 Wk 3 — Ch. 4 Homework
Complete each section of Ch. 4, “Algorithms, Induction, and Recursion.” You must use this link to earn points.
MTH 221 Wk 3 — Midterm Exam
Complete the midterm exam. You have one attempt at the exam. So, be sure to review all previous course materials before attempting the exam.
Question 1
The propositional variables s and m represent the two propositions:
s: It is sunny today.
m: I will bring my umbrella.
Select the logical expression that represents the statement: “Despite the fact that it is sunny today, I will bring my umbrella.”
s
s logical and m
s logical or m
not m
Question 2
p = F, q = T, and r = T.
Select the expression that evaluates to true.
not left parenthesis q logical or r right parenthesis
left parenthesis not p logical and r right parenthesis logical or q
left parenthesis not q logical or r right parenthesis logical and p
p logical or not q logical or not r
Question 3
Select the statement that is false.
If 3 is a prime number, then 5 is a prime number.
If 4 is a prime number, then 6 is a prime number.
If 4 is a prime number, then 5 is a prime number.
If 3 is a prime number, then 6 is a prime number.
Question 4
Use De Morgan’s law to select the statement that is equivalent to:
“It is not true that the patient has high blood pressure or influenza.”
The patient has high blood pressure or has influenza.
The patient does not have high blood pressure and does not have influenza.
The patient does not have high blood pressure or does not have influenza.
The patient has high blood pressure and has influenza.
Question 5
Select the law which shows that the two propositions are logically equivalent.
left parenthesis not p logical and left parenthesis r logical or not q right parenthesis right parenthesis logical or left parenthesis not left parenthesis not p logical and w right parenthesis not p logical and left parenthesis left parenthesis r logical or not q right parenthesis logical or w right parenthesis
DeMorgan’s law
Distributive law
Associative law
Commutative law
Question 6
The predicate T is defined as:
T left parenthesis x comma y comma z right parenthesis colon space left parenthesis x space plus space y right parenthesis squared space equals space z
Select the proposition that is true.
T(4, 1, 5)
T(4, 1, 25)
T(1, 1, 1)
T(4, 0 2)
Question 7
The domain of discourse are the students in a class. Define the predicates:
S(x): x studied for the test
A(x): x received an A on the test
Select the logical expression that is equivalent to:
“Everyone who studied for the test received an A on the test.”
for all x left parenthesis A left parenthesis x right parenthesis rightwards arrow for blank of left parenthesis S left parenthesis x right parenthesis right parenthesis
for all x left parenthesis S left parenthesis x right parenthesis rightwards arrow for blank of A left parenthesis x right parenthesis right parenthesis
for all x left parenthesis S left parenthesis x right parenthesis logical and for all left parenthesis x right parenthesis right parenthesis
for all x left parenthesis S left parenthesis x right parenthesis stack left right arrow A left parenthesis x right parenthesis right parenthesis with blank below and blank on top
Question 8
Select the logical expression that is equivalent to:
not for all x left parenthesis not P left parenthesis x right parenthesis logical or Q left parenthesis x right parenthesis right parenthesis
there exists x left parenthesis P left parenthesis x right parenthesis logical and not Q left parenthesis x right parenthesis right parenthesis
there exists x left parenthesis not P left parenthesis x right parenthesis logical or Q left parenthesis X right parenthesis right parenthesis
for all x left parenthesis P left parenthesis x right parenthesis logical or not Q left parenthesis x right parenthesis right parenthesis
for all x left parenthesis not P left parenthesis x right parenthesis logical and Q left parenthesis x right parenthesis right parenthesis
Question 9
The domain for x and y is the set of real numbers. Select the statement that is false.
for all x there exists y left parenthesis x plus y greater or equal than 0 right parenthesis
there exists x for all y left parenthesis x plus y greater or equal than 0 right parenthesis
for all x there exists y left parenthesis x y less or equal than 0 right parenthesis
there exists x for all y left parenthesis x y greater or equal than 0 right parenthesis
Question 10
Select the truth assignment that shows that the argument below is not valid:
p logical or q bottom enclose not q space space space space space space space space end enclose therefore p stack left right arrow q with blank below and blank on top
p = T
q = T
p = F
q = T
p = T
q = F
p = F
q = F
Question 11
Select the correct expression for (?) in the proof segment below:
1. space p rightwards arrow for blank of r space space H y p o t h e s i s 2. space p logical and q space space H y p o t h e s i s 3. space left parenthesis ? right parenthesis space space S i m p l i c a t i o n comma space 2 4. space r space space M o d u s space T o l l e n s comma space 1 comma space 3
p
q
p logical or q
p logical and q
Question 12
Which rule is used in the argument below?
Alice is a student in the class.
Alice got an A on the test and did not study.
Therefore, there is a student in the class who got an A on the test and did not study.
Universal instantiation
Universal generalization
Existential instantiation
Existential generalization
Question 13
Use the definitions below to select the statement that is true.
A equals left curly bracket x element of bold italic Z colon space x space i s space e v e n right curly bracket B equals left curly bracket x element of bold italic Z colon space minus 4 less than x less than 17 right curly bracket
A is finite.
B subset of or equal to A
A subset of A
empty set subset of B
Question 14
A = {1, 2, {3, 4}, {5, 6, 7}}
Select the correct value for |A|.
4
5
6
7
Question 15
A equals left curly bracket x element of bold italic Z colon space x space i s space a space p r i m e space n u m b e r right curly bracket B equals left curly bracket 4 comma 7 comma 9 comma 11 comma 13 comma 14 right curly bracket space C equals space left curly bracket x element of bold italic Z colon space 3 less or equal than x less or equal than 10 right curly bracket S e l e c t space t h e space s e t space c o r r e s p o n d i n g space t o space left parenthesis A union B right parenthesis intersection C space. space
{3, 5, 7}
{3, 4, 7, 9}
{3, 4, 5, 7, 9}
{3, 4, 5, 7, 9, 11, 13}
Question 16
A equals left curly bracket x element of bold italic Z colon space x space i s space e v e n right curly bracket C space equals space left curly bracket 3 comma 5 comma 9 comma 12 comma 15 comma 16 right curly bracket D space equals space left curly bracket 5 comma 7 comma 8 comma 12 comma 13 comma 15 right curly bracket T h e space u n i v e r s a l space s e t space U space i s space t h e space s e t space o f space a l l space i n t e g e r s. space S e l e c t space t h e space s e t space c o r r e s p o n d i n g space t o space left parenthesis top enclose A union D end enclose right parenthesis intersection C
{3,9}
{8,12}
{5,12,15}
{5,7,13,15}
Question 17
A={a,b}
B={1,2,3}
Select the the expression that is an element of A x B x B.
(b,2,3)
(a,a,1)
left parenthesis b comma 2 squared right parenthesis
(2,1,1)
Question 18
The space function space f colon left curly bracket 0 comma 1 right curly bracket squared rightwards arrow for blank of left curly bracket 0 comma 1 right curly bracket cubed space is space defined space as colon For space every space x element of left curly bracket 0 comma 1 right curly bracket squared comma space f left parenthesis straight x right parenthesis space equals space 0 straight x space. Select space the space set space corresponding space to space the space range space of space f space.
{01, 00}
{00, 01, 10, 11}
{000, 001, 010, 011}
{000, 001, 010, 011, 100, 101, 110, 111}
Question 19
A donut store sells packages of 12 donuts. The store has made x donuts. How many complete packages does the store have for sale?
open floor 12 x close floor
open ceil 12 x close ceil
open floor x divided by 12 close floor
open ceil x divided by 12 close ceil
Question 20
f colon bold italic Z rightwards arrow bold italic Z. f left parenthesis x right parenthesis equals open ceil x over 3 close ceil
Select the correct description of the function f.
One-to-one and onto
One-to-one but not onto
Onto but not one-to-one
Neither one-to-one nor onto
Question 21
Select the function that does not have a well-defined inverse.
f colon bold Z rightwards arrow bold Z f left parenthesis x right parenthesis equals open ceil x plus 2 close ceil
f colon bold R rightwards arrow bold R f colon left parenthesis x right parenthesis equals negative 2 x plus 5
f colon bold R rightwards arrow bold Z f left parenthesis x right parenthesis equals open ceil x close ceil
f colon bold R rightwards arrow bold R f colon left parenthesis x right parenthesis equals 3 x plus 4
Question 22
Start with the number n = 32844. Divide n by 7 and round the result down to an integer. Keep repeating the division and rounding step until the resulting number is less than 7. How many divisions are performed?
open ceil log subscript 7 32844 close ceil
open floor log subscript 7 32844 close floor
open ceil 32844 divided by 7 close ceil
open floor 32844 divided by 7 close floor
Question 23
The values for variables x, y, and z are:
x = 1, y = 0, z = 1
Select the Boolean expression that evaluates to 0.
z with bar on top y plus x y with bar on top
stack x y z with bar on top
stack x plus y plus z with bar on top
stack left parenthesis y plus z with bar on top right parenthesis with bar on top x
Question 24
Select the Boolean expression that is equivalent to the function defined in the table blow:
x stack y z with bar on top plus x y z
x y with bar on top z with bar on top plus stack x y with bar on top z with bar on top
x y with bar on top z with bar on top plus x y z
x stack y z with bar on top plus stack x y z with bar on top
Question 25
Select the Boolean expression that corresponds to the output of the Boolean circuit below:
left parenthesis stack x plus y with bar on top right parenthesis left parenthesis y with bar on top plus z right parenthesis
left parenthesis x plus y with bar on top right parenthesis left parenthesis y with bar on top plus z right parenthesis
stack x y with bar on top plus y with bar on top z
x y with bar on top plus y with bar on top z
Question 26
Select the set that corresponds to the relation given in the arrow diagram below:
{ (1, 3), (1, 4), (2, 3) }
{ (1, 3), (1, 4), (3, 2) }
{ (1, 3), (1, 4), (2, 3), (2, 2) }
{ (1, 3), (1, 4), (3, 2), (2, 2) }
Question 27
A is a finite non-empty set. The domain for relation R is the power set of A. (Recall that the power set of A is the set of all subsets of A .) For X subset of or equal to A and Y subset of or equal to A, X is related to Y if X and Y have the same cardinality (i.e., open vertical bar X close vertical bar equals open vertical bar Y close vertical bar). Select the description that accurately describes relation R .
Symmetric and Reflexive
Anti-symmetric and Reflexive
Symmetric and Anti-reflexive
Anti-symmetric and Anti-reflexive
Question 28
Graph G is defined by the arrow diagram below.
Select the pair of vertices such that there is no walk of length 4 in G from the first vertex to the second vertex.
1, 3
1, 4
2, 1
4, 3
Question 29
The figure below is a Hasse diagram for a partial order:
What are the minimal elements?
E
E, D
E, D, H
E, D, F, H
Question 30
A person’s birth date consists of the month, day, and year in which that person was born. The domain for a relation R is a set of people. There are at least two people in the group with the same birth date and at least two people with different birth dates. A person x is related to person y under the relation if they have the same birth date or if x’s birth date is earlier than y’s birth date. Which description correctly characterizes the relation?
Neither a partial order nor a strict order
A partial order
A strict order
A strict order and a total order
Question 31
The domain of relation R is the set of all non-negative integers. x is related to y if open floor x divided by 3 close floor equals open floor y divided by 3 close floor . The equivalence class R defines a partition over the set of all non-negative integers. How many elements are in each set in the partition?
0
1
3
Each set in the partition is infinite.
Question 32
Below is a database showing the daily train schedule for a train station.
What series of operations should be performed in order to get the departure times of all the Express trains to Amsterdam?
SELECT[Destination = “Amsterdam”]
PROJECT[Express/Local, Departure Time]
SELECT[Express/Local = “Express”]
PROJECT[Destination, Departure Time]
SELECT[Destination = “Amsterdam” and Express/Local = “Express”]
PROJECT[Departure Time]
SELECT[Destination = “Amsterdam” and Express/Local = “Express”]
PROJECT[Departure Time, Track]
Question 33
Select the correct description for the output of the Algorithm below.
Algorithm
Input: a1, a2,…, an, a sequence of numbers
n, the length of the sequence
x, a number
Output: ??
For i = 1 to n-1
For j = i+1 to n
If (|ai — aj| > 0) Return( “True” )
End-for
End-for
Return( “False” )
“True” if there are any two numbers in the list that are not equal to each other, and “False” otherwise.
“True” if there are any two consecutive numbers in the list that are not equal to each other, and “False” otherwise.
“True” if there are any two numbers in the list that are equal to each other, and “False” otherwise.
“True” if there are any two consecutive numbers in the list that are equal to each other, and “False” otherwise.
Question 34
f left parenthesis n right parenthesis equals 4 n squared plus 5 n plus 6 space. space Which space choices space for space c space and space n subscript o space are space sufficient space to space prove space that space f is italic space italic 0 italic left parenthesis n to the power of italic 2 italic right parenthesis italic space ?
c equals 3 a n d straight n subscript 0 equals 2
c equals 5 and n subscript 0 equals 3
c equals 9 and n subscript italic 0 italic equals italic 1
c equals 15 and n subscript 0 equals 1
Question 35
Select the asymptotic worst-case time complexity of the following algorithm:
Algorithm
Input: a1, a2, …, an, a sequence of numbers
n, the length of the sequence
x, a number
Output: ??
For i = 1 to n-1
For j = i+1 to n
For k = 1 to n
If ((ai)² + (aj)² = (ak)²) Return( “True” )
End-for
End-for
End-for
Return( “False” )
capital theta left parenthesis 1 right parenthesis
capital theta left parenthesis n right parenthesis
capital theta left parenthesis n squared right parenthesis
capital theta left parenthesis n cubed right parenthesis
Question 36
The sequence {f subscript n} starts with an index of 1 and is defined so that f subscript n is the largest integer k such that k squared less or equal than n . Which sequence fits the definition of {f subscript n} ?
1, 4, 9, 16, 25, …
1, 1, 1, 2, 2, …
2, 4, 8, 16, 32, …
1, 2, 3, 4, 5, …
Question 37
A population of mice increases by 10% every year. Define g subscript n to be the number of mice after n years. Select the recurrence relation that describes the sequence left curly bracket g subscript n right curly bracket .
g subscript n equals left parenthesis 1.01 right parenthesis times g subscript n minus 1 end subscript
g subscript n plus left parenthesis 1.1 right parenthesis times g subscript n minus 1 end subscript
g subscript n equals left parenthesis.01 right parenthesis times g subscript n minus 1 end subscript plus g subscript n minus 2 end subscript
g subscript n equals left parenthesis.1 right parenthesis times g subscript n minus 1 end subscript plus g subscript n minus 2 end subscript
Question 38
Select the summation expression whose value is equivalent to the sum 4 cubed plus 6 cubed plus 8 cubed plus times times times plus 28 cubed space.
begin inline style sum from j equals 4 to 28 of end style left parenthesis 2 j right parenthesis cubed
begin inline style sum from j equals 4 to 14 of end style left parenthesis 2 j right parenthesis cubed
begin inline style sum from j equals 4 to 28 of end style left parenthesis 2 j right parenthesis cubed
begin inline style sum from j equals 2 to 14 of end style left parenthesis 2 j right parenthesis cubed
Question 39
The inductive step of an inductive proof shows that for k greater or equal than 4, if 2 to the power of k greater or equal than 3 k, then 2 to the power of k plus 1 end exponent greater or equal than 3 left parenthesis k plus 1 right parenthesis . Which step of the proof uses the fact that k greater or equal than 4 greater or equal than 1 ?
2 to the power of k plus 1 end exponent greater or equal than 2 times 2 to the power of k left parenthesis Step space 1 right parenthesis greater or equal than 2 times 3 k left parenthesis Step space 2 right parenthesis greater or equal than 3 k plus 3 k left parenthesis Step space 3 right parenthesis greater or equal than 3 k plus 3 left parenthesis Step space 4 right parenthesis greater or equal than 3 left parenthesis k plus 1 right parenthesis left parenthesis Step space 5 right parenthesis
Step 2
Step 3
Step 4
Step 5
Question 40
The sequence left curly bracket g subscript n right curly bracket is defined recursively as follows:
g subscript 0 equals 1 space comma space and space g subscript n equals 3 times g subscript n minus 1 end subscript plus 2 subscript n space comma space for space n greater or equal than 1 .
If the theorem below is proven by induction, what must be established in the inductive step?
Theorem: For any non-negative integer n, g subscript n equals 5 over 2 times 2 to the power of n minus n minus 3 over 2 .
For space k greater or equal than 0 space comma space if space g subscript k equals 3 times g subscript k minus 1 end subscript plus 2 k space comma then space g subscript k plus 1 end subscript equals 5 over 2 times 2 to the power of k plus 1 end exponent minus left parenthesis k plus 1 right parenthesis minus 3 over 2.
For space k greater or equal than 0 space comma space if space g subscript k equals 5 over 2 times 2 to the power of k minus k minus 3 over 2 space comma then space g subscript k plus 1 end subscript equals 5 over 2 times 2 to the power of k plus 1 end exponent minus left parenthesis k plus 1 right parenthesis minus 3 over 2 space.
For space k greater or equal than 0 space comma space if space g subscript k equals 3 times g subscript k minus 1 end subscript plus 2 k space comma then space g subscript k plus 1 end subscript equals 3 times g subscript k plus 2 left parenthesis k plus 1 right parenthesis space.
For space k greater or equal than 0 space comma space if space g subscript k equals 5 over 2 times 2 to the power of k minus k minus 3 over 2 space comma then space g subscript k plus 1 end subscript equals 3 times g subscript k plus 2 left parenthesis k plus 1 right parenthesis space.
Question 41
Let S(n) be a statement parameterized by a positive integer n. Consider a proof that uses strong induction to prove that for all n greater or equal than 4 , S(n) is true. The base case proves that S(4), S(5), S(6), S(7), and S(8) are all true.
Select the correct expressions to complete the statement of what is assumed and proven in the inductive step.
Supposed that for k greater or equal than space left parenthesis 1 ? right parenthesis , S(j) is true for every j in the range 4 through k. Then we will show that (2?) is true.
(1): 4
(2): S(k+1)
(1): 4
(2): S(j+1)
(1): 8
(2): S(k+1)
(1): 8
(2): S(j+1)
Question 42
The loop below computes the sum begin inline style sum from k equals 1 to n of end style k squared colon
While space left parenthesis straight j less or equal than straight n right parenthesis space space space sum space colon equals space sum plus straight j to the power of logical and 2 space space space straight j space colon equals space straight j plus 1 End minus while
Pre-condition: m and n are non-negative integers. j = 1 and sum = 0.
Post-condition: s u m equals begin inline style sum from k equals 1 to n of end style k squared space.
Error converting from MathML to accessible text.
What facts are assumed in proving the post-condition?
Error converting from MathML to accessible text.
Error converting from MathML to accessible text.
Error converting from MathML to accessible text.
Error converting from MathML to accessible text.
Question 43
S is a set of strings over the alphabet {a, b} and is defined recursively as follows:
Basis colon space straight lambda element of S and b element of S Recursive space rules colon space if space straight x space is space in space straight S comma space then space b x a element of S and a x b element of S space.
Select the set that corresponds to all the strings in S of length 4.
In
empty set
{bbaa, aabb}
{baba, abab}
{bbaa, aabb, baba, abab}
Question 44
The set of full binary trees is defined as follows:
Basis: A single vertex with no edges is a full binary tree. The root is the only vertex in the tree.
Recursive rule: If T1 and T2 are full binary trees, then a new tree T’ can be constructed by first placing T1 to the left of T2, adding a new vertex v at the top and then adding an edge between v and the root of T1 and an edge between v and the root of T2. The new vertex v is the root of T’.
Suppose that a full binary tree T’ is created using the recursive rule applied to full binary trees T1 and T2. Let v(T) denote the number of vertices in tree T. Which expression correctly describes v(T’)?
v left parenthesis T apostrophe right parenthesis equals 2 times v left parenthesis T 1 right parenthesis plus 2 times v left parenthesis T 2 right parenthesis plus 1 space
v left parenthesis T apostrophe right parenthesis equals 2 times v left parenthesis T 1 right parenthesis plus 2 times v left parenthesis T 2 right parenthesis
v left parenthesis T apostrophe right parenthesis equals v left parenthesis T 1 right parenthesis plus v left parenthesis T 2 right parenthesis plus 1
v left parenthesis T apostrophe right parenthesis equals v left parenthesis T 1 right parenthesis plus v left parenthesis T 2 right parenthesis
Question 45
The function SuperPower given below receives two inputs, x and n, and should return x to the power of 4 n minus 2 end exponent space. x is a real number and n is positive integer.
SuperPower(x, n)
If n = 1, then Return(x²)
y := SuperPower(x, n-1)
Return( ? )
What is the correct value for the algorithm to return?
y to the power of 4
x to the power of 4
y times x to the power of 4
x times y to the power of 4
Question 46
The function SuperPower receives two inputs, x and n, and should return x to the power of 4 n minus 2 end exponent. x is a real number and n is positive integer.
SuperPower(x, n)
If n = 1, then Return(x²)
y := SuperPower(x, n-1)
Return( ? )
The correctness of algorithm SuperPower(r, n) is proven by induction on n. Suppose that the inductive hypothesis is that SuperPower(x, k) returns x to the power of 4 k minus 2 end exponent . What fact must be proven in the inductive step?
Exponent left parenthesis straight x comma space straight k plus 1 right parenthesis space returns space x to the power of 4 k minus 1 end exponent
Exponent left parenthesis straight x comma space straight k plus 1 right parenthesis space returns space x to the power of 4 k plus 2 end exponent
Exponent left parenthesis straight x plus 1 comma space straight k right parenthesis space returns space left parenthesis x plus 1 right parenthesis to the power of 4 k minus 2 end exponent
Exponent left parenthesis straight x plus 1 comma space straight k right parenthesis space returns space left parenthesis x plus 1 right parenthesis to the power of 4 k plus 2 end exponent
Question 47
Which recurrence relation describes a function that has the same asymptotic growth as T(n), defined by the recurrence relation:
T left parenthesis n right parenthesis equals 2 times T left parenthesis n divided by 2 right parenthesis plus capital theta left parenthesis n right parenthesis space
T left parenthesis n right parenthesis equals T left parenthesis left ceiling n divided by 2 right ceiling right parenthesis plus 17
space T left parenthesis n right parenthesis equals T left parenthesis left ceiling n divided by 2 right ceiling right parenthesis plus T left parenthesis left floor n divided by 2 right floor right parenthesis plus 5 squared
T left parenthesis n right parenthesis equals T left parenthesis left ceiling n divided by 2 right ceiling right parenthesis plus 12 n
T left parenthesis n right parenthesis equals T left parenthesis left ceiling n divided by 2 right ceiling right parenthesis plus T left parenthesis left floor n divided by 2 right floor right parenthesis plus left parenthesis 5 n plus 12 right parenthesis
MTH 221 Wk 4 — Ch. 5 Homework
Complete each section of Ch. 5, “Integer Properties and Counting.” You must use this link to earn points.
MTH 221 Wk 5 — Ch. 6 Homework
Complete each section of Ch. 6, “Graphs and Trees.” You must use this link to earn points.
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}
