## 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 )