ICS 443: Parallel Algorithms (Fall 2017)


Contents

Topics

The following topics will be covered in class during the semester:

Schedule

Specific topics will be filled in the schedule as they are covered during the semester.

This semester's scribe notes will be posted in Laulima.

Week Day Date Topic Old Scribe Notes Notes
1 Mon Aug 21 Introduction, pre-req assessment
Wed Aug 23 Models of parallel computation Scribe Notes Reading: [BM04, sections 1.1], [J92, section 1.1-1.3]
2 Mon Aug 28 Models of parallel computation (cont.)
Parallel Summation
Scribe Notes Reading: [BM04, sections 1.1-1.3, 2.1], [J92, section 1.3-1.4]
DROP DATE (without W)
Wed Aug 30 Brent's scheduling principle Scribe Notes Reading: [BM04, sections 1.2-1.4], [J92, section 1.4-1.6]
Homework 1 out
ADD DATE
3 Mon Sep 4 HOLIDAY: Labor Day
Wed Sep 6 Parallel Prefix Sums Scribe Notes 1
Scribe Notes 2
Slides
Reading: [HS86][J92, section 2.1][B93, sections 1.1-1.2]
4 Mon Sep 11 Iterative Prefix Sums, Applications Slides Reading: [B93, sections 1.3, 1.5.1]
Wed Sep 13 Segmented Prefix Sums Scribe Notes Reading: [B93, sections 1.4.1, 1.5]
Homework 1 due
Homework 2 out
5 Mon Sep 18 Segmented Prefix Sums (cont.)
Homework 1 solutions
Reading: [B93, sections 1.4.1]
Wed Sep 20 Finding Minimum Reading: [J92, section 2.6]
6 Mon Sep 25 Parallel Searching Reading: [J92, section 4.1]
Wed Sep 27 Mergesort, parallel merging Reading: [J92, sections 2.4, 4.3.1]
Homework 2 due
Homework 3 out
7 Mon Oct 2 Work-efficient parallel merging Reading: [J92, section 2.4]
Wed Oct 4 Parallel merging analysis Reading: [J92, section 2.4]
8 Mon Oct 9 O(log log n) merging Reading: [J92, sections 4.2, 4.3.1]
Wed Oct 11 Homework 2 review. Pre-midterm review Homework 3 due
Homework 4 out
9 Mon Oct 16 Midterm Exam
Wed Oct 18 Sorting networks Reading: [J92, section 4.4] [0-1 Notes] [BSN]
Fri Oct 20 DROP DATE (with W)
10 Mon Oct 23 Bitonic Merge Reading: [J92, section 4.4] [0-1 Notes] [BSN]
Wed Oct 25 List Ranking, pointer hopping Reading: [J92, section 3.1]
Homework 4 due
Homework 5 out
11 Mon Oct 30 Randomized List Ranking Reading: [J92, section 3.1]
Wed Nov 1 Deterministic symmetry breaking via coloring Reading: [J92, section 2.7]
12 Mon Nov 6 O(log n)-time, O(n)-work List Ranking Reading: [J92, section 3.1]
Wed Nov 8 Euler Tour Technique Reading: [J92, section 3.2]
Homework 5 due
13 Mon Nov 13 Tree contraction Reading: [J92, section 3.3]
Homework 6 out
Wed Nov 15 Expression tree evaluation Reading: [J92, section 3.3]
14 Mon Nov 20
Wed Nov 22
15 Mon Nov 27
Wed Nov 29 Homework 6 due
16 Mon Dec 4 Parallel Algorithms Workshop
Wed Dec 6 Parallel Algorithms Workshop

Exam dates

Reading Materials