CS255 Spring 2022Practice Midterm

Studying for one of my tests does involve some memorization. I believe this is an important skill. Often people waste a lot of time and fail to remember the things they are trying to memorize. Please use a technique that has been shown to work such as the method of loci. Other memorization techniques can be found off the Wiki Page for Moonwalking with Einstein. Given this, to study for the midterm I would suggest you:

• Know how to do (by heart) all the practice problems.
• Go over your notes at least three times. Second and third time try to see how much you can remember from the first time.
• Go over the homework problems.
• Try to create your own problems similar to the ones I have given and solve them.
• Skim the relevant sections from the book.
• If you want to study in groups, at this point you are ready to quiz each other.

The practice midterm is below. Here are some facts about the actual midterm: (a) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (b) You should bring photo ID. (c) There will be more than one version of the test. Each version will be of comparable difficulty. (d) One problem (less typos) on the actual test will be from the practice test.

1. Define the terms: probability distribution, discrete random variable. Define and give an example of pairwise independence.
2. A Venusian year is about 225 Venusian Days. How many Venusians (who are equally likely to be born on any day) need to be in a room before there is a 50% chance that two share a birthday?
3. Prove that any permutation is equally likely to be generated by the Knuth shuffle.
4. Give an example parallel computation in which the inequality `T_P le T_1/P + T_(infty)` is actually within O(1) of an equality.
5. What is a concurrency platform? What is nested parallelism? What is static threading? What is a determinancy race condition?
6. Briefly explain how to simulate spawn and sync parallelism from class using Java Threads.
7. Suppose we are using BoxSort on an array of size 16384. What is the expected number of splittings we would expect before the LogSort subroutine is called on the remaining box? Show your reasoning.
8. Say a triangle independent set in a graph is a set of vertices such that no three vertices in the set share a triangle. Suggest how to modify ParallelMIS so that it computes maximal triangle independent sets.
9. Give an example malicious sequence of coin flips such that the processors in the Synchronous CCP algorithm from class never decide on a register to write to.
10. Suppose 8 good processors were running the Byzantine agreement protocol and there were also 8 faulty processor. Show how the faulty processors could prevent an agreement.