# Quick Self-test

Should you take CS294-248? Here is a __very simple__ test
for you to help you decide. You should find this test to be very
easy: if you cannot answer more than 2-3 questions below, or feel
unsure about, say, half of the questions, then you probably shouldn't
take this class.
- What are the complexity classes NP, PSpace, PTIME?
- What is the transitive closure of a graph?
- Consider a relation R(A,B,C). What does the functional
dependency A → B mean?
- A relation R(A,B) has 100 tuples, and a relation S(B,C) has 500
tuples. What is the maximum number of tuples that the natural join
R ⨝ S can have? What about the minimum number of
tuples?
- Let R = {a,b,c}, S = {b,c,d}, T = {a,b,e}, K = {f,g}
Compute ((R-S) ∪ T) × K.
- Suppose the relations R(A,B) and S(B,C) have N tuples each.
Write an algorithm to check whether this formula is true:
∀ x (∃ y (R(x,y) → ∃ z S(y,z))). What is
the asymptotic runtime of your algorithm?
- What is the asymptotic complexity of the following algorithms:
- Searching for a value x in an array of N elements.
- Searching for a value x in a sorted array of N elements.
- Merging two sorted arrays of length N.
- Quicksort

- A relation R(A,B) has 1000 tuples. We create a new relation
S(A,B) as follows. With start with S=the emptyset, then we iterate
over all tuples in R, and, for each tuple, we insert it in S with
probability 3%. What is the expected number of tuples in S?
- Continuing the question above, suppose that A is a key in R. Is
A also a key in S?
- Let R(A,B,C) be a relation with 3 attributes, and the following
content: R = {(i mod 2, i mod 3, i mod 6) | i = 0,..,5}. Which
attribute(s) form a key in R?

This is a self-text, for your information only: you don't need to turn
in anything.