site stats
  • MTH 221 Wk 3 – Midterm Exam

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)^2 + (aj)^2 = (ak)^2) 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^2)


  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^2)


  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 3 – Midterm Exam

  • Product Code: Tutorial
  • Availability: In Stock
  • $40.00


Tags: MTH 221