联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> Java编程Java编程

日期:2021-04-21 11:16

COMP1805ABC (Winter 2021) ? "Discrete Structures I"

Practice Questions for the Final Exam

This semester, the final exam for COMP1805ABC will be completed online as a multiple-choice activity in

cuLearn. The exam will be 2 hours long. It will open up at 7:00 pm. You can start your exam between 7:00 pm

and 7:30 pm. Once you begin the exam you will have 2.0 hours to complete and submit it. Please follow this

link for the exact dates and times. https://carleton.ca/ses/exam-schedule/. The exam will be open-book (in that

you may refer to the lecture slides, the textbook, the discrete math study center website, or your handwritten

notes) and basic, non-graphing calculators will be permitted. Any other electronic devices or unauthorized web

sites will be prohibited.

This collection of questions is presented here to help prepare for your final exam. Solutions will not be provided

but you may email your instructors and/or teaching assistants with any questions you might have. Best of luck

with your preparations!

Is a logical expression like (? ( ? (((?? → ??) ∨ ??) ∨ ??))) a tautology, a contradiction, or a contingency?

Justify your answer using only truth tables and then again using only the logical equivalences.

Is ( ? ((?? ∨ (?? ∧ ??)) ∨ (?? → ??))) logically equivalent to (? ((( ? (???)) ∨ ??) ∨ ??))?

How would you justify your answer if the answer was yes? What if the answer was no?

What are the dimensions required for a truth table of (? (? (?? ∨ ((? ??) → ??))))?

Complete the truth table and use it to construct the full disjunctive normal form of this expression.

COMP1805ABC (Winter 2021) ? "Discrete Structures I"

Practice Questions for the Final Exam

Using only the rules of inference and the logical equivalences from class and the notes, show that the

following argument is valid. You may assume that all the premises given are true. Make sure that you include

both the rule and the line number(s) to which that rule is applied.

1. ???(??(??) ∨ ??(??))

2. ???(???(??) ∨ ???(??))

3. ???(???(??) ∧ ??(??))

Conclude: ???(???(??) ∧ ??(??))

Note this is an example of Question 3 from Quiz 2

For this question about predicate logic, please note that, even though the 'nonsense' words are only nouns

and verbs, you do not need to know the meaning of the words being used in order to answer this question.

Consider a universe of discourse that contains (among other things) all farthings. If the predicates S(x), Q(x),

and T(x) represented the assertions x jilled, x quinzeed, and x scrims, respectively, then construct an accurate

translation, using quantified predicates, of the following:

If any farthings jilled then that farthing quinzeed or that farthing did not scrim.

Can you determine if ((((?? ∪ ??) ∪ ??) ∪ (??

??

))) and ((?? ∩ (?? ? (?? ∪ ??)))

??

) are equivalent?

n.b., ?? ? ?? and ??

?? denote the set difference between A and B and the complement of A, respectively.

COMP1805ABC (Winter 2021) ? "Discrete Structures I"

Practice Questions for the Final Exam

Which of the following sets is equivalent to the Universe? Justify your answer.

What type of sequence is 102, 569, 1036, 1503, 1970, 2437?

What about 79, 312, 545, 1011, 1244, 1477?

How can you justify your answers?

What expression, using Sigma notation, represents the sum of the integers from 37 to 211, inclusive?

What is the closed form of this expression?

Consider these adjacency matrices and answer the questions below (for each graph being represented):

How would you perform a breadth-first search starting from a random vertex? A depth-first search?

How would you represent the resultant search trees using an adjacency matrix? An adjacency list?

How many of the vertices in the search trees are cut vertices? Cut edges?

What is the chromatic number of each graph? How can you prove it?

COMP1805ABC (Winter 2021) ? "Discrete Structures I"

Practice Questions for the Final Exam

Consider the collection of functions plg(), bar(), foo(), adv(), and wcr(), each of each is associated with an

unspecified operation that has a worst-case time complexity specified below.

The function call "plg()" is an operation with a worst-case time complexity of Θ(??)

The function call "bar()" is an operation with a worst-case time complexity of Θ(??

2

)

The function call "foo()" is an operation with a worst-case time complexity of Θ(??

2

)

The function call "adv()" is an operation with a worst-case time complexity of Θ(??)

The function call "wcr()" is an operation with a worst-case time complexity of Θ(?????? ??)

g = n

while ( g > 1 ):

k = n

while ( k > 1 ):

i = n

while ( i > 1 ):

q = n

while ( q > 1 ):

plg()

q = 1

bar()

i = i – 1

foo()

k = k / 2

c = n^2

while ( c > 1):

adv()

c = c – 1

wcr()

g = g - 1

What is the time complexity of this algorithm? (Note this example is taken from Tutorial 6 Quiz)

COMP1805ABC (Winter 2021) ? "Discrete Structures I"

Practice Questions for the Final Exam

Consider the following functions:

For what functions ??(??) would each of these functions be O(??(??))? Ω(??(??))? Θ(??(??))?

What witnesses c and k could you use to justify your answers?

For a domain of {′??′, ′?′, ′??′, ′??′, ′??′, ′??′, ′??′, ′??′} and a codomain of {3, 4, 5, 6, 8}, consider the following function:

??(′??′) = 3 ??(′?′) = 4 ??(′??′) = 8 ??(′??′) = 6

??(′??′) = 6 ??(′??′) = 3 ??(′??′) = 3 ??(′??′) = 5

Is this function injective? Surjective? Bijective?

If your answer to any of these is no, what you would need to change to grant it this property?

Consider the following binary relation on the set {0, 1, 2, 3, 4, 5, 6}:

{ (0, 1), (0, 3), (1, 2), (1, 4), (2, 1), (2, 4), (2, 6), (3, 1), (3, 2), (3, 5), (4, 0), (4, 4), (4, 6), (5, 0), (5, 2), (5, 6), (6, 1), (6, 6)}

Is this relation reflexive? Symmetric? Transitive?

If your answer to any of these is no, then complete the closure required for a relation with that property.


版权所有:留学生编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp