# Spring 2024 (Other Semesters)

Date/SubjectPrepIn ClassAssignments

Tue Jan 16 (#0)
Introduction
slides: presentation pdf

Thu Jan 18 (#1)
Fork, Join, Computation Graphs
Initial Setup Instructions
Initial Setup Results Form
Prior Experience Survey
video: Fork Join Hypotenuse
video: Work, Span, & Ideal Parallelism
video: Synthesizing Information
worksheet
bonus worksheet
slides: presentation pdf
>>> Assign Exercise Half & Half Nucleobase Count

Tue Jan 23 (#2)
Finality; Race Conditions; Abstract Data Type: Stack
video: Java Keyword final
video: Finality and Lambdas
video: Finality, Closures, and the For Index Loop
video: Data Race: 2+ Tasks Access, At Least 1 Write.
video: ++Data Race
video: Mutable Transcontinental Railroad Data Race
video: Data Structures: Stacks and Queues (Hacker Rank)
video: Making Sense of JUnit Output for Exception with Causes
worksheet
slides: presentation pdf
>>> Assign WarmUp Race Condition: Translation
>>> Assign Exercise Race Condition: Image Batch
>>> Assign Exercise Stack

Thu Jan 25 (#3)
Iterables; ForkLoops
video: For Each Loop
video: Array Initialization with the For Index Loop
video: DOM Iterable<NodeList>
video: Using an Iteratable
video: Iterable<E>.iterator() Mistake to Avoid
video: Join Fork Loop
video: Join Fork Loop Iterable and With Index
video: Fork Loop: Work, Span, & Ideal Parallelism
video: Choosing the Right Tool for the Job: which join_fork_loop
worksheet
slides: presentation pdf
>>> Assign WarmUp DoubleDeltaRange
>>> Assign WarmUp Fork Loop
>>> Assign Exercise ForkLoop Images

Tue Jan 30 (#4)
Range; Coarsening; Matrix Multiply
video: Using Range and Ranges.slice()
video: Join Fork Loop Coarsening
video: Coarsening: N-Way Split
video: Matrix Multiply (on Khan Academy)
video: Matrix Multiply Demo
worksheet
slides: presentation pdf
>>> Assign Exercise Ranges
>>> Assign Exercise Coarsening (N-Way Split) Nucleobase Count
>>> Assign Exercise ForkLoop 2d

Thu Feb 1 (#5)
Call Stack; Backtrack Recursion: N-Queens
video: Call Stack(CS 50)
video: N-Queens Problem
learn: How The Queen Moves
worksheet
slides: presentation pdf
>>> Assign WarmUp Int Tree Sum
>>> Assign WarmUp Sequential N-Queens
>>> Assign Exercise Parallel N-Queens

Sat Feb 3
<<< Submit Exercise Half & Half Nucleobase Count
<<< Submit Exercise Race Condition: Image Batch
<<< Submit Exercise Stack
<<< Submit Exercise ForkLoop Images

Tue Feb 6 (#6)
Divide and Conquer
video: Divide and Conquer: Work, Span, & Ideal Parallelism
video: Merge Sort(CS 50)
video: Merge Sort (HackerRank)
video: Merge Sort Combine
worksheet
slides: presentation pdf
>>> Assign Exercise Divide and Conquer Nucleobase Count
>>> Assign WarmUp Comparator
>>> Assign WarmUp Insertion Sort
>>> Assign Exercise Merge Sort
>>> Challenge Merge Sort Parallel Combiner
>>> Challenge Matrix Multiply Divide and Conquer

Thu Feb 8 (#7)
Floodfill; X10
video: Floodfill
video: X10: One Finish To Join Them All
worksheet
slides: presentation pdf
>>> Assign Exercise Floodfill

Sat Feb 10
<<< Submit Exercise Ranges
<<< Submit Exercise Coarsening (N-Way Split) Nucleobase Count
<<< Submit Exercise ForkLoop 2d
<<< Submit Exercise Parallel N-Queens

Tue Feb 13 (#8)
Sarkar; Ideal Parallelism; Multiprocessor Scheduling; Parallel Speedup and Amdahl's Law; Future Tasks & Functional Parallelism; Memoization; Data Races; Functional & Structural Determinism; Always Do Less Work; Fibonacci
video: Ideal Parallelism (Sarkar)
video: Multiprocessor Scheduling (Sarkar)
video: Parallel Speedup and Amdahl's Law (Sarkar)
video: Future Tasks & Functional Parallelism (Sarkar)
video: Memoization (Sarkar)
video: Data Races (Sarkar)
video: Functional & Structural Determinism (Sarkar)
video: The Magic of Fibonacci Numbers
worksheet
slides: presentation pdf
>>> Assign WarmUp Big Powers of 2
>>> Assign Exercise Fibonacci

Thu Feb 15 (#9)
Abstract Data Type: HashTable; Higher-order Functions
video: Data Structure: Hash Table (Hacker Rank)
video: Predicate<T>
video: Higher-order Function: Filter
video: Filter Higher-order Function Registrar Demo
worksheet
slides: presentation pdf
>>> Assign WarmUp Higher-Order Function: Filter
>>> Assign Exercise Higher-Order Functions: Map and Reduce

Sat Feb 17
<<< Submit Exercise Divide and Conquer Nucleobase Count
<<< Submit Exercise Merge Sort
<<< Submit Exercise Floodfill

Tue Feb 20 (#10)
MapReduce Mapper
video: MapReduceFramework<E,K,V,A,R>
video: Mapper<E,K,V>
video: Learn MapReduce with Playing Cards
worksheet
slides: presentation pdf
>>> Assign Exercise Mapper<E,K,V>

Thu Feb 22 (#11)
AccumulatorCombinerReducer
video: AccumulatorCombinerReducer<V,A,R>
worksheet
slides: presentation pdf
>>> Assign WarmUp Card Only Sequential Map Reduce Framework
>>> Assign Exercise AccumulatorCombinerReducer<V,A,R>

Sat Feb 24
<<< Submit Exercise Fibonacci
<<< Submit Exercise Higher-Order Functions: Map and Reduce

Tue Feb 27 (#12)
MapReduce: Bottlenecked Framework
video: For Each Loop with Index
video: How to Play Poker for Beginners
skim: Texas Holdem Rankings for All 169 Starting Hands
worksheet
slides: presentation pdf
>>> Assign WarmUp Set Intersector
>>> Assign Exercise MutualFriends MR App
>>> Assign WarmUp Word Count Only Parallel Map Reduce Framework
>>> Assign Exercise Bottleneck MapReduce Framework

Thu Feb 29 (#13)
MapReduce: Matrix Framework
video: Geoffrey Challen: Distributed MapReduce
worksheet
slides: presentation pdf
>>> Assign Exercise Matrix MapReduce Framework (Part A)
>>> Assign Exercise Matrix MapReduce Framework (Part B)

Sat Mar 2
<<< Submit Exercise Mapper<E,K,V>
<<< Submit Exercise AccumulatorCombinerReducer<V,A,R>

Tue Mar 5 (#14)
John Snow and the Cholera Outbreak of 1854
video: John Snow 1
video: John Snow 2
video: John Snow 3
worksheet
slides: presentation pdf
>>> Assign Exercise Cholera MR App

Thu Mar 7 (#15)
Short Reading: Data Reveals That "Occupying" Twitter Trending Topics is Harder Than it Looks!
worksheet
slides: presentation pdf
>>> Assign Exercise Chess MR App
>>> Assign Exercise Windbag MR App

Sat Mar 9
<<< Submit Exercise MutualFriends MR App
<<< Submit Exercise Bottleneck MapReduce Framework
<<< Submit Exercise Matrix MapReduce Framework (Part A)
<<< Submit Exercise Matrix MapReduce Framework (Part B)

Tue Mar 12
Spring Break (No Class)

Thu Mar 14
Spring Break (No Class)

Sat Mar 16
<<< Submit Exercise Cholera MR App
<<< Submit Exercise Chess MR App
<<< Submit Exercise Windbag MR App

Tue Mar 19 (#16)
Scan
video: Hillis & Steele Scan
video: Blelloch Scan
worksheet
slides: presentation pdf
>>> Assign Exercise Powers Of 2 Iterable
>>> Assign WarmUp Sequential Scan
>>> Assign Exercise Parallel Scan
>>> Assign Exercise Pack
>>> Challenge Blelloch Scan (Work Efficient)

Thu Mar 21 (#17)
Concurrent Data Structures; Quicksort
video: Quicksort
video: Parallel Quicksort (Sarkar)
worksheet
slides: presentation pdf
>>> Assign WarmUp Join All
>>> Assign Exercise Quicksort
>>> Challenge Parallel Partition

Sat Mar 23

Tue Mar 26 (#18)
Intrinsic Locks via Synchronized
video: Family Bank Account Race
video: Mutual Exclusion, Critical Sections, Explicit and Implicit Locks
worksheet
slides: presentation pdf
>>> Assign Exercise Concurrent Stack

Thu Mar 28 (#19)
Explicit Lock
video: Deadlock and the Dining Philosophers
video: tryLock()
worksheet
slides: presentation pdf
>>> Assign Exercise Ordered Locks
>>> Assign Exercise All Or Nothing Locks

Sat Mar 30
<<< Submit Exercise Powers Of 2 Iterable
<<< Submit Exercise Parallel Scan
<<< Submit Exercise Pack
<<< Submit Exercise Quicksort

Tue Apr 2 (#20)
worksheet
slides: presentation pdf
>>> Assign Exercise ConcurrentHashTable

Thu Apr 4 (#21)
Atomicity Race; Atomics; Atomic Variables
video: ConcurrentHashMap Compute Demo
video: Atomic Variables (Sarkar)
worksheet
slides: presentation pdf
>>> Assign Exercise Atomicity Races
>>> Assign Exercise Atomic Stack

Sat Apr 6
<<< Submit Exercise Concurrent Stack
<<< Submit Exercise Ordered Locks
<<< Submit Exercise All Or Nothing Locks

Tue Apr 9 (#22)
K-mer Counting
video: Intro To K-Mer Counting
worksheet
slides: presentation pdf
>>> Assign WarmUp String K-Mer Counting
>>> Assign Exercise K-mer Balance
>>> Assign WarmUp Balanced String K-Mer Counting
>>> Assign Exercise K-mer Counting

Thu Apr 11 (#23)
Phaser
video: java.util.concurrent.Phaser
video: Phaser Rosetta Stone
video: One-Dimensional Iterative Averaging (Sarkar)
video: Single Program Multiple Data (SPMD) pattern (Sarkar)
video: Phasers (Sarkar)
worksheet
slides: presentation pdf
>>> Assign WarmUp Phased Fork Loop Evening Plan Scenario
>>> Assign WarmUp Sequential Legged Race
>>> Assign Exercise Legged Races

Sat Apr 13
<<< Submit Exercise ConcurrentHashTable
<<< Submit Exercise Atomicity Races
<<< Submit Exercise Atomic Stack

Tue Apr 16 (#24)
Fuzzy Phaser
video: Phaser Rosetta Stone with Precise Control
video: Fuzzy Barriers (Sarkar)
video: Iterative Averaging with Point-to-Point Synchronization (Sarkar)
worksheet
slides: presentation pdf
>>> Assign WarmUp Sequential Iterative Averager
>>> Assign Exercise Iterative Averaging

Thu Apr 18 (#25)
Pipeline
video: Pipeline Parallelism (Sarkar)
worksheet
slides: presentation pdf
>>> Assign Exercise Iced Cakes Pipeline

Sat Apr 20
<<< Submit Exercise K-mer Balance
<<< Submit Exercise K-mer Counting
<<< Submit Exercise Legged Races

Tue Apr 23 (#26)
video: ExecutorService submit and Future get
video: ExecutorService invokeAll
worksheet
slides: presentation pdf
>>> Assign Exercise Thread and Executor Service

Thu Apr 25 (#27)
Work Stealing Scheduler
video: Work Stealing
worksheet
slides: presentation pdf
>>> Assign WarmUp Sequential Raytracer
>>> Assign WarmUp Scheduler Client
>>> Assign Exercise Parallel Raytracer
>>> Challenge Centralized Work Queue

Sat Apr 27
<<< Submit Exercise Iterative Averaging
<<< Submit Exercise Iced Cakes Pipeline

Sat May 4
<<< Submit Exercise Thread and Executor Service
<<< Submit Exercise Parallel Raytracer