Exam 1 topics

This is intended to give you a sense of what I think is important from the course so far, and what I will be thinking of when creating the exam.

I hate disclaimers, but here are some anyway. This is not a contract. I may have inadvertently left something off this list that ends up in an exam question. I make no guarantees that the exam will be 100% limited to items listed below. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.

You are permitted one 8.5 x 11 sheet of paper with notes (both sides) for use as a reference during the exam.

Students should be able to…

• Write code, debug code, predict output, or otherwise demonstrate fluency with threaded programming in Java.
• Formulate a problem as a fork/join problem, both in the abstract as well as in Java using both regular threads as well as the ForkJoin library.
• Discuss and consider how one chooses how many threads to use in solving a problem.
• Use, justify, and evaluate tradeoffs involved regarding a sequential cutoff.
• Define and measure work, span, speedup, and parallelism in general as well as for specific problems.
• Analyze in a big-O sense the above metrics for ForkJoin, or for other sorts of situations as specified.
• State, interpret, derive, and/or evaluate Brent's Theorem, Amdahl's Law, and Gustafson's Law in general or for specific problems.
• Code, trace, and/or interpret parallel prefix sum. Be able to demonstrate how it works. Derive, justify, or analyze big-O complexity for it.
• Code, trace, and/or interpret parallel pack. Be able to demonstrate how it works. Derive, justify, or analyze big-O complexity for it.
• Code, trace, and/or interpret parallel quicksort and mergesort. Be able to demonstrate how they work. Derive, justify, or analyze big-O complexity for it, at least at a high level.
• Define mutual exclusion, critical section. Interpret an interleaving schedule, or produce one to demonstrate a particular issue with provided code.
• Use locks in Java via synchronized blocks. Demonstrate fluency with how they work.
• Define and distinguish data races and bad interleavings.
• Demonstrate and justify how data races can lead to buggy code.