Description
Question 1: Hair Splitting with Set Expressions
Let us define the successor of the set A to be the set A ∪ {A}. Find the successors of the
following sets:
a) A = {x}
b) B = {x, y}
c) C = Ø
d) D = { Ø, { Ø }}
Question 2: Tautologies and Contradictions
Find out for each of the following propositions whether it is a tautology, a contradiction,
or neither (a contingency). Prove your answer.
a) [(p → q) ∧ (q → r)] → (p → r)
b) (p ∨ q ∨ r) → [(q → r) ∨ (p → q)]
Question 3: Set Operations
Let us take a look at the sets A = {x, y, z}, B = {1, 2}, C = {y, z}. List the elements of
the following sets D, E, F, G, H, and I:
a) D = (B × A) – (B × C)
b) E = 2A – 2C
c) F = 2(2B )
2
d) G = (A × B × C) ∩ (C × B × A)
e) H = {(a, b, c) | a, b, c∈Β ∧ b ≠ c ∧ a = b}.
f) I = {(a, b, c) | a∈A ∧ b∈B ∧ c∈C ∧ a = c}
Question 4: Cardinality
Are the following statements true for all sets A, B and C? Prove your answers.
a) |A ∪ B ∪ C| = |A – B – C|
b) |A ∪ B ∪ C| = |A| + |B| + |C| – |A ∩ B| – |A ∩ C| – |B ∩ C|
Question 5: Functions
Find out whether the following functions from R to R are injective, surjective, and/or
Bijective (no proof necessary).
a) f(z) = -z
b) f(z) = 300z5 + 4
c) f(z) = z⋅sin z
d) f(z) = z2
/(z2 + 1)
Question 6: Big-O Estimates
Give as good a big-O estimate as possible for the following complexity functions:
a) f(n) = (n⋅log n) (n2 + 2n)
b) f(n) = (2n! + 4n3
) + (2n
⋅n3
)
c) f(n) = n4 + 5 log n + n3 (n2 + 2n)
3
Question 7: Algorithms and Their Complexity
a) Write a simple program in pseudocode (or in Python, C, C++, or Java, but only use
basic commands so that comparisons can be counted) that receives a sequence of
integers a1, …, an as its input and determines if the sequence contains two distinct
terms x, y such that x = y2
. Once it finds such terms, it prints them and terminates; it
does not continue searching after the first find. If the program does not find any such
terms, it prints a disappointed comment and also terminates.
b) Describe the kind of input that causes worst-case time complexity for your algorithm
(only count comparisons), and explain why this is the case.
c) Provide an equation for your algorithm that describes the number of required
comparisons as a function of input length n in the worst case. For some algorithms, it
may be a good idea to first use a sum notation, but at the end you should provide a
closed-form equation, i.e., one that no longer uses the sum symbol but only
operations such as multiplication or addition of individual numbers or variables.
d) Use the big-O-notation to describe the worst-case time complexity of your algorithm.
Question 8 (Bonus Question): Venn Diagrams
Draw the Venn diagrams for the following sets:
a) A ∪ B ∪ C
b) A ∪ (B – C)
c) (A ∩ B) ∪ (A ∩ C)
d) (A ∩ B ) ∪ (A ∩ C )
