# Spring 2023 (Other Semesters)

Date/SubjectPrepIn ClassAssignments
Sun Jan 15

Tue Jan 17 (#0) Introductionslides: presentation pdf

Thu Jan 19 (#1) Fork, Join, Computation Graphsyoutube playlist
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 Jan 24 (#2) Finality; Race Conditions; Abstract Data Type: Stackyoutube playlist
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

Thu Jan 26 (#3) Iterables; ForkLoopsyoutube playlist
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 Exercise Powers Of 2 Iterable
>>> Assign WarmUp Fork Loop
>>> Assign Exercise ForkLoop Images

Tue Jan 31 (#4) Coarsening; Matrix Multiplyyoutube playlist
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 2 (#5) Call Stack; Backtrack Recursion: N-Queensyoutube playlist
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 Stack

Sat Feb 4<<< Submit Exercise Half & Half Nucleobase Count
<<< Submit Exercise Race Condition: Image Batch
<<< Submit Exercise Powers Of 2 Iterable
<<< Submit Exercise ForkLoop Images

Tue Feb 7 (#6) Divide and Conqueryoutube playlist
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
>>> Assign Exercise Parallel N-Queens
>>> Fun Challenge Merge Sort Parallel Combiner
>>> Fun Challenge Matrix Multiply Divide and Conquer

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

Sat Feb 11<<< Submit Exercise Ranges
<<< Submit Exercise Coarsening (N-Way Split) Nucleobase Count
<<< Submit Exercise ForkLoop 2d
<<< Submit Exercise Stack

Tue Feb 14 (#8) Work: Always Do Less; Determinism; Ideal Parallelism; Multiprocessor Scheduling; Parallel Speedup and Amdahl's Lawyoutube playlist
video: Data Races (Sarkar)
video: Functional & Structural Determinism (Sarkar)
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: The Magic of Fibonacci Numbers
worksheet
slides: presentation pdf
>>> Assign WarmUp Big Powers of 2
>>> Assign Exercise Fibonacci

Thu Feb 16 (#9) Abstract Data Type: HashTable; Higher-order Functionsyoutube playlist
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 18<<< Submit Exercise Divide and Conquer Nucleobase Count
<<< Submit Exercise Merge Sort
<<< Submit Exercise Parallel N-Queens
<<< Submit Exercise Floodfill

Tue Feb 21 (#10) MapReduceyoutube playlist
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 23 (#11) java.util.Collectorvideo: AccumulatorCombinerReducer<V,A,R>
worksheet
slides: presentation pdf
>>> Assign WarmUp Card Only Sequential Map Reduce Framework
>>> Assign Exercise AccumulatorCombinerReducer<V,A,R>

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

Tue Feb 28 (#12) MapReduce: Bottlenecked FrameworkShort Reading: Mutual Friends MapReduce
video: For Each Loop with Index
worksheet
slides: presentation pdf
>>> Assign WarmUp Set Intersector
>>> Assign WarmUp Word Count Only Parallel Map Reduce Framework
>>> Assign Exercise MutualFriends MR App
>>> Assign Exercise Bottleneck MapReduce Framework

Thu Mar 2 (#13) MapReduce: Matrix Frameworkyoutube playlist
video: Geoffrey Challen: Distributed MapReduce
worksheet
slides: presentation pdf
>>> Assign Exercise Matrix MapReduce Framework

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

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

Short Reading: Data Reveals That "Occupying" Twitter Trending Topics is Harder Than it Looks!
worksheet
slides: presentation pdf
video lecture
>>> Assign Exercise Windbag MR App

Tue Mar 14 Spring Break (No Class)

Thu Mar 16 Spring Break (No Class)

Tue Mar 21 (#16) Scanyoutube playlist
video: Hillis & Steele Scan
video: Blelloch Scan
worksheet
slides: presentation pdf
>>> Assign WarmUp Sequential Scan
>>> Assign Exercise Parallel Scan
>>> Assign Exercise Pack
>>> Fun Challenge Blelloch Scan (Work Efficient)

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

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

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

Sat Apr 1<<< Submit Exercise MutualFriends MR App
<<< Submit Exercise Bottleneck MapReduce Framework
<<< Submit Exercise Matrix MapReduce Framework
<<< Submit Exercise Cholera MR App
<<< Submit Exercise Windbag MR App
<<< Submit Exercise Parallel Scan
<<< Submit Exercise Pack
<<< Submit Exercise Quicksort

worksheet
slides: presentation pdf
>>> Assign Exercise ConcurrentHashTable

Thu Apr 6 (#21) Concurrent Data Structures; Determinacy Races; Atomicity Races; Atomicsyoutube playlist
video: ConcurrentHashMap Compute Demo
video: Atomic Variables (Sarkar)
worksheet
slides: presentation pdf
>>> Assign Exercise Atomicity Races
>>> Assign Exercise Atomic Stack

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

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

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

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

Tue Apr 18 (#24) Fuzzy Barriers; Point To Point Synchronizationyoutube playlist
video: Phaser Rosetta Stone with Precise Control
video: Fuzzy Barriers (Sarkar)
video: Phasers (Sarkar)
video: Iterative Averaging with Point-to-Point Synchronization (Sarkar)
worksheet
slides: presentation pdf
>>> Assign WarmUp Sequential Legged Race
>>> Assign Exercise Legged Races
>>> Fun Challenge Point To Point Iterative Averaging
>>> Fun Challenge Fuzzy Iterative Averaging
>>> Fun Challenge Fuzzy Point To Point Iterative Averaging

Thu Apr 20 (#25) Pipelinesvideo: Pipeline Parallelism (Sarkar)
worksheet
slides: presentation pdf
>>> Assign Exercise Iced_Cakes_Pipeline

Sat Apr 22<<< Submit Exercise K-mer Balance
<<< Submit Exercise K-mer Counting
<<< Submit Exercise Iterative Averaging

video: ExecutorService submit and Future get
video: ExecutorService invokeAll
worksheet
slides: presentation pdf
>>> Assign Exercise Thread and Executor Service

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

Sat Apr 29<<< Submit Exercise Legged Races
<<< Submit Exercise Iced_Cakes_Pipeline

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