Schedule for weeks 1 through 16

Wk	Day	Date	Topic	Resources	Events

1	Mon	Jan 07	Course Introduction	Algoraph

	Wed	Jan 09	Graph Algorithms	Skim ALG 3.1-3.4, 4.1-4.7

	Fri	Jan 11	Divide-and-conquer Graph algorithms	Skim ALG 2.1-2.5

2	Mon	Jan 14	Greedy Algorithms Horn Formulas Set Cover	ALG 5.3-5.4	HW 1 due

	Wed	Jan 16	Graph Algorithms

	Fri	Jan 18	Algoraph Stuff

3	Mon	Jan 21	Dynamic Programming Shortest Paths Travelling Saleseman	ALG 6.6 Warshall's Algorithm Notes (Read) Floyd's Algorithm Demo	HW 2 due

	Wed	Jan 23	Divide-and-conquer	Read Mergesort notes Read Quicksort notes Answer Mergesort Reading Questions Answer Quicksort Reading Questions

	Fri	Jan 25	Prim's algorithm discussion

4	Mon	Jan 28	Snow Day!		No Class

	Wed	Jan 30	Snow Day! (Really?! Another one?)		No Class

	Fri	Feb 01	Optimizing Algorithms: Practice!		HW 3 due (No lates!)

5	Mon	Feb 04	Linear Programming	ALG 7.1

	Wed	Feb 06	Network Flow Bipartite Matching	ALG 7.2-7.3 Ford-Fulkerson Demo (Does not seem to fully work in Chrome. Try Firefox.) Network Flow Demo Bipartite Matching Demo

	Fri	Feb 08	Duality Zero-sum games	ALG 7.4-7.5	HW 4 due

6	Mon	Feb 11	Winter Recess		No Class

	Wed	Feb 13	Simplex Algorithm Circuit Evaluation	ALG 7.6-7.7 (Skip 7.6.3)	HW 5 due

	Fri	Feb 15	Parallel Programming	Read Introduction to Parallel Programming SRQ → Answer IPP Questions

7	Mon	Feb 18	Open MP	Watch videos 1-7 from Intro to OpenMP OpenMP.org Open MP Slides (from videos, for reference) Open MP Introduction (for reference) Open MP Exercises (code from videos) Patternlets (in class) OpenMP Patternlets code SRQ, important note → OMP Videos 1-7 Question

	Wed	Feb 20	Open MP	Watch videos 8-15 from Intro to OpenMP OpenMP Reference Sheets SRQ → OMP Videos 8-15 Question	HW 6 due Submit pi2.c (using reduction as suggested in video 11) as 385-SRQ

	Fri	Feb 22	Open MP	Watch videos 16-18 from Intro to OpenMP SRQ → OMP Video 16-18 Question

8	Mon	Feb 25	Everything	Brain Writing utensil Paper	Midterm Exam

	Wed	Feb 27	Open MP	Watch videos 19-22 from Intro to OpenMP SRQ → OMP Video 19-22 Question

	Fri	Mar 01	Open MP

9	Mon	Mar 04	Open MP	QuickSortProject.zip	HW 7 due (program)

	Wed	Mar 06	Open MP	Watch videos 23-27 from Intro to OpenMP	HW 7 due (write-up)

	Fri	Mar 08	Search problems	ALG 8.1

10	Mon	Mar 11	NP-Complete Problems	ALG 8.2 ALG 8.3 through top of page 249 A Few Sample Reduction	HW 8 due (code)

	Wed	Mar 13	Problem Reductions	ALG 8.3 NP-Completeness Notes	HW 8 due (write-up)

	Fri	Mar 15	Spring Break		No Class

Spring Break Week

11	Mon	Mar 25	Backtracking Branch-and-Bound	ALG 9.1 Backtracking and Branch-and-bound links

	Wed	Mar 27	Approximation Algorithms	ALG 9.2	HW 9 due

	Fri	Mar 29	Parallel Programming	Read Ch 2-3.3 of SIPC Sophomoric Parallelism and Concurrency (SIPC)

12	Mon	Apr 01	Java's ForkJoin	Read Ch 3.4-3.6 of SIPC Read Grossman notes 1 Java ForkJoin Framework Java ForkJoin Framework Guide Java ForkJoin Javadoc

	Wed	Apr 03	Local Search Heuristics	ALG 9.3 Read Grossman notes 1	Work day

	Fri	Apr 05	Java's ForkJoin Divide-and-conquer in parallel	Read Ch 4-5.2 of SIPC Grossman notes 2

13	Mon	Apr 08	Analyzing Parallel Algorithms	Grossman notes 2	HW 10 due

	Wed	Apr 10	Parallel Prefix Pack	Read Ch 5 of SIPC (Re-read 5-5.2, finish chapter) Grossman Notes 3

	Fri	Apr 12	Parallel Quicksort and Mergesort

14	Mon	Apr 15	Parallel Sorting Concurrency	Read Ch 6 of SIPC Grossman Notes 4

	Wed	Apr 17	Race conditions	Read Ch 7 of SIPC Grossman Notes 5	HW 11 due

	Fri	Apr 19	Easter Break		No Class

15	Mon	Apr 22	Easter Break		No Class

	Wed	Apr 24	Programming Pack and Partition

	Fri	Apr 26	Review		HW 12 due

Ex	Fri	May 03	Final Exam, 9:00 - 11:00 am