# Fall 2023 (Other Semesters)

Date/SubjectPrepIn ClassAssignments

Tue Aug 29 (#0)
Introduction
slides: presentation pdf

Thu Aug 31 (#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
slides: presentation pdf
>>> Assign Exercise Half & Half Nucleobase Count

Tue Sep 5 (#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 Sep 7 (#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 Sep 12 (#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 Sep 14 (#5)
Call Stack; Backtrack Recursion: N-Queens
video: Call Stack(CS 50)
video: N-Queens Problem
worksheet
slides: presentation pdf
>>> Assign WarmUp Int Tree Sum
>>> Assign WarmUp Sequential N-Queens
>>> Assign Exercise Parallel N-Queens

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

Tue Sep 19 (#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 Sep 21 (#7)
Floodfill; X10
video: Floodfill
video: X10: One Finish To Join Them All
worksheet
slides: presentation pdf
>>> Assign Exercise Floodfill

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

Tue Sep 26 (#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 Sep 28 (#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 Sep 30
<<< Submit Exercise Divide and Conquer Nucleobase Count
<<< Submit Exercise Merge Sort
<<< Submit Exercise Floodfill

Tue Oct 3 (#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 Oct 5 (#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 Oct 7
<<< Submit Exercise Fibonacci
<<< Submit Exercise Higher-Order Functions: Map and Reduce

Tue Oct 10
Fall Break (No Class)

Thu Oct 12 (#12)
MapReduce: Bottlenecked Framework
video: For Each Loop with Index
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

Sat Oct 14
<<< Submit Exercise Mapper<E,K,V>
<<< Submit Exercise AccumulatorCombinerReducer<V,A,R>

Tue Oct 17 (#13)
MapReduce: Matrix Framework
video: Geoffrey Challen: Distributed MapReduce
worksheet
slides: presentation pdf
>>> Assign Exercise Matrix MapReduce Framework

Thu Oct 19 (#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

Sat Oct 21
<<< Submit Exercise MutualFriends MR App
<<< Submit Exercise Bottleneck MapReduce Framework

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

Thu Oct 26 (#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)

Sat Oct 28
<<< Submit Exercise Matrix MapReduce Framework
<<< Submit Exercise Cholera MR App

Tue Oct 31 (#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

Thu Nov 2 (#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

Sat Nov 4
<<< Submit Exercise Windbag MR App
<<< Submit Exercise Powers Of 2 Iterable
<<< Submit Exercise Parallel Scan
<<< Submit Exercise Pack

Tue Nov 7 (#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

Thu Nov 9 (#20)
worksheet
slides: presentation pdf
>>> Assign Exercise ConcurrentHashTable

Sat Nov 11
<<< Submit Exercise Quicksort
<<< Submit Exercise Concurrent Stack

Tue Nov 14 (#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

Thu Nov 16 (#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

Sat Nov 18
<<< Submit Exercise Ordered Locks
<<< Submit Exercise All Or Nothing Locks
<<< Submit Exercise ConcurrentHashTable

Tue Nov 21 (#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

Thu Nov 23
Thanksgiving (No Class)

Sat Nov 25
<<< Submit Exercise Atomicity Races
<<< Submit Exercise Atomic Stack
<<< Submit Exercise K-mer Balance
<<< Submit Exercise K-mer Counting

Tue Nov 28 (#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 Nov 30 (#25)
Pipeline
video: Pipeline Parallelism (Sarkar)
worksheet
slides: presentation pdf
>>> Assign Exercise Iced Cakes Pipeline

Sat Dec 2
<<< Submit Exercise Legged Races

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

Thu Dec 7 (#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 Dec 9
<<< Submit Exercise Iterative Averaging
<<< Submit Exercise Iced Cakes Pipeline

Sat Dec 16
<<< Submit Exercise Thread and Executor Service
<<< Submit Exercise Parallel Raytracer