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.
  1. What are the complexity classes NP, PSpace, PTIME?
  2. What is the transitive closure of a graph?
  3. Consider a relation R(A,B,C). What does the functional dependency A → B mean?
  4. 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?
  5. Let R = {a,b,c}, S = {b,c,d}, T = {a,b,e}, K = {f,g} Compute ((R-S) ∪ T) × K.
  6. 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?
  7. What is the asymptotic complexity of the following algorithms:
    1. Searching for a value x in an array of N elements.
    2. Searching for a value x in a sorted array of N elements.
    3. Merging two sorted arrays of length N.
    4. Quicksort
  8. 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?
  9. Continuing the question above, suppose that A is a key in R. Is A also a key in S?
  10. 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.