Dan Grossman Teaching Materials
This document is for students and instructors. It covers the same material as the slides and homeworks in more detail. It is something between lecture notes and a draft of textbook chapters.
The materials on this page offer a 2-3 week unit introducing parallelism and concurrency in a lower-level data structures course. They have been used since Spring 2010 as part of this full data-structures course and have also been adapted for CS2 courses and for introductions in more advanced courses (see "Other Users"). All materials are free and questions/feedback/suggestions are encouraged.
For motivation on incorporating this material in lower-level data structures and a short overview of the approach, see:
All the materials on this page use Java, including Java's ForkJoin Framework, when a particular language or code example is needed. Some of the materials, including the reading notes, have been ported to C++.
In PowerPoint 2007 and pdf
The breakdown into "lectures" does not exactly map to 1-hour segments; overall there is about 7-8 hours of material divided into 6 lectures.
These instructions are essential for writing and running real parallel programs using the ForkJoin library, as in the project and some of the homework exercises.
Please do not post solutions to these exercises
Java parallel-programming project:
Compute U.S. population densities with real data. Includes a simple, optional, fun GUI.
Exam problems used in Spring 2010 or Spring 2012. By design, some of the questions were fairly difficult. Note solutions are posted. The full exams (2010, 2012) also had questions on sorting and graphs, with a 110-minute time limit.
I ran a 3-hour workshop at SIGCSE 2011. The workshop materials are below. They are self-contained with some original content (e.g., new lab exercises) but also substantial overlap with other materials.
Workshop abstract: Multithreading (Pretty) Early for
Everyone: Parallelism and Concurrency in Second-Year Data-Structures
There is wide interest in introducing students to threads earlier, but how? This workshop gives an answer: a 3-week unit in data structures. It should appeal to data-structure instructors and those tasked with curriculum revision. The presenter wrote/used the course materials and advised later instructors. A key approach is to distinguish parallelism (using more resources to solve problems faster) and concurrency (managing shared access to resources). The material is taught via core data-structure topics (asymptotic complexity, sorting, queues, etc.) and using Java and its ForkJoin Framework. Participants will write parallel programs, find concurrency errors, and discuss how the material can fit their needs. Those with or without knowledge of threads and fork-join programming are welcome.
Installation instructions (to be completed in advance)
Please let me know how you are using these materials and how they can be improved. Even typos are helpful.
spac at cs.washington.edu is a low-traffic mailing list for announcing updates and occasional discussions among users. You can subscribe here or just ask me to subscribe you.
We gratefully acknowledge gifts from Intel Labs University Collaborations and grants from the U.S. National Science Foundation that provided financial resources to develop these materials.
Last updated: May 2014