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 Reading Assignments
1 Mon Aug 21 Introduction, pre-req assessment
Wed Aug 23 Models of parallel computation [BM04, sections 1.1]
[J92, section 1.1-1.3]
2 Mon Aug 28 Models of parallel computation (cont.)
Parallel Summation		 [BM04, sections 1.1-1.3, 2.1]
[J92, section 1.3-1.4]
Wed Aug 30 Brent's scheduling principle [BM04, sections 1.2-1.4]
[J92, section 1.4-1.6] 		Homework 1 out
3 Mon Sep 4 HOLIDAY: Labor Day
Wed Sep 6 Parallel Prefix Sums [HS86]
[J92, section 2.1]
[B93, sections 1.1-1.2]
4 Mon Sep 11 Iterative Prefix Sums, Applications [B93, sections 1.3, 1.5.1]
Wed Sep 13 Segmented Prefix Sums [B93, sections 1.4.1, 1.5] Homework 1 due
Homework 2 out
5 Mon Sep 18 Segmented Prefix Sums (cont.) [B93, sections 1.4.1]
Wed Sep 20 Finding Minimum [J92, section 2.6]
6 Mon Sep 25 Parallel Searching [J92, section 4.1]
Wed Sep 27 Mergesort, parallel merging [J92, sections 2.4, 4.3.1] Homework 2 due
Homework 3 out
7 Mon Oct 2 Work-efficient parallel merging [J92, section 2.4]
Wed Oct 4 Parallel merging analysis [J92, section 2.4]
8 Mon Oct 9 O(log log n) merging [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 [J92, section 4.4]
[0-1 Notes]
[BSN]
10 Mon Oct 23 Bitonic Merge [J92, section 4.4]
[0-1 Notes]
[BSN]
Wed Oct 25 List Ranking, pointer hopping [J92, section 3.1] Homework 4 due
Homework 5 out
11 Mon Oct 30 Randomized List Ranking [J92, section 3.1]
Wed Nov 1 Deterministic symmetry breaking via coloring [J92, section 2.7]
12 Mon Nov 6 O(log n)-time, O(n)-work List Ranking [J92, section 3.1]
Wed Nov 8 Euler Tour Technique [J92, section 3.2] Homework 5 due
13 Mon Nov 13 Tree contraction [J92, section 3.3] Homework 6 out
Wed Nov 15 Expression tree evaluation [J92, section 3.3]
14 Mon Nov 20 Lowest Common Ancestor (LCA) [J92, section 3.4.1-3.4.2]
Wed Nov 22 Range Minima Queries (RMQ) [J92, section 3.4.3]
15 Mon Nov 27 Introduction to Computational Geometry, Parallel Convex Hull [J92, sections 2.3.1, 6.1]
Wed Nov 29 Parallel Convex Hull (cont.) [J92, section 6.1] Homework 6 due
16 Mon Dec 4 Parallel Algorithms Workshop
Wed Dec 6 Parallel Algorithms Workshop

Exam dates

Reading Materials