Schedule for weeks 1 through 16

Wk	Day	Date	Topic	Resources	Events

1	Mon	Jan 06	Introduction Prerequisite Review

	Wed	Jan 08	Brute Force Closest-Pair Convex Hull	IDAA 3.3

	Fri	Jan 10	Decrease-and-conquer Generating Permutations Generating Subsets	IDAA 4 intro (pages 131-134) IDAA 4.3 Flip-a-switch

2	Mon	Jan 13	More: Permutations and Combinations	Bring Computer!

	Wed	Jan 15	Divide-and-conquer Closest-Pair Convex Hull	IDAA 5 intro (pages 169-171) IDAA 5.5

	Fri	Jan 17	More: Convex Hull	Before class, do Getting Started w/BRIDGES In class start BRIDGES: Convex Hull	HW 1 due

3	Mon	Jan 20	Matrices	Read AIDMA Ch 5.3 Do AIDMA 5.3 RQs

	Wed	Jan 22	Cold Day!	Blankets Heater	No Class!

	Fri	Jan 24	Transform-and-Conquer Gaussian Elimination LU Decomposition	IDAA 6.2 (to top of page 214)	HW 2 due

4	Mon	Jan 27	Transform-and-Conquer Problem Reduction	IDAA 6.6 Linear Programming Exploration (Geogebra) Linear Programming Example (Desmos)

	Wed	Jan 29	Space-time Tradeoffs String Matching	IDAA 7.2 Boyer-Moore Demo Boyer-Moore Demo #2	HW 3 due

	Fri	Jan 31	Space-time Tradeoffs Hashing	IDAA 7.3 Open Hashing Demo Closed Hashing Demo

5	Mon	Feb 03	Transform-and-conquer Balanced search trees Space and Time Trade-Offs B-Trees	IDAA 6.3 (2-3 trees, pgs 223-225; RQs 8-11) IDAA 7.4 B-Tree Demo

	Wed	Feb 05	Dynamic Programming Knapsack Problem	IDAA 8.2

	Fri	Feb 07	Dynamic Programming Optimal Binary Search Tree	IDAA 8.3	HW 4 due

6	Mon	Feb 10	Winter Recess		No Class

	Wed	Feb 12	Greedy Technique Prim's Algorithm Dijkstra's Algorithm	IDAA 9.1 (review) IDAA 9.3 AIDMA Ch 9.6.4 (Do RQs) Minimum Spanning Trees Notes Algoraph

	Fri	Feb 14	Greedy Techniques Kruskal's Algorithm Union-Find	IDAA 9.2 Union-Find Demo	HW 5 due

7	Mon	Feb 17	Greedy Techniques Huffman Encoding	IDAA 9.4 (review) Huffman Encoding Demo BRIDGES: Huffman Encoding

	Wed	Feb 19	Review		HW 6 due

	Fri	Feb 21	Through Chapter 9		Midterm Exam

8	Mon	Feb 24	More: Greedy and Dynamic Programming	Read over BRIDGES: Mountain Path Be ready to program!	HW 7 due

	Wed	Feb 26	Iterative Improvement: Maximum Flow	IDAA 10.2 Ford-Fulkeron Demo Max Flow Demo Network Flow Solver

	Fri	Feb 28	Iterative Improvement: Maximum Matching	IDAA 10.3

9	Mon	Mar 03	Iterative Improvement: Stable Marriage	IDAA 10.4

	Wed	Mar 05	More: Iterative Improvement		HW 8 due

	Fri	Mar 07	Limitations of Algorithm Power Lower-Bound Arguments	IDAA 11.1 Sorting Lower Bound notes Kelvin predictions

10	Mon	Mar 10	Limitations of Algorithm Power Decision Trees	IDAA 11.2	HW 9 due

	Wed	Mar 12	Limitations of Algorithm Power P, NP, and NP-Complete	IDAA 11.3 Halting Problem Notes Turing and the Halting Problem	HW 10 due

	Fri	Mar 14	Spring Break		No Class

Spring Break Week

11	Mon	Mar 24	Limitations of Algorithm Power Challenges of Numerical Algorithms	IDAA 11.4 IEEE 754 Roundoff Error

	Wed	Mar 26	Parallel Programming	Read Ch 2-3.3 of SIPC Sophomoric Parallelism and Concurrency (SIPC) Grossman notes 1

	Fri	Mar 28	Java's ForkJoin Divide-and-conquer in parallel	Read Ch 3.4-3.6 of SIPC Grossman notes 1 Grossman notes 2 Java ForkJoin Framework Guide ThreadExamples

12	Mon	Mar 31	Java's ForkJoin Analyzing Parallel Algorithms	Read Ch 4-5.2 of SIPC Grossman notes 2 ForkJoinExamples	HW 11 due

	Wed	Apr 02	(Naïve) Parallel Quicksort	Loki

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

13	Mon	Apr 07	Parallel Quicksort and Mergesort		HW 12 due (part 1)

	Wed	Apr 09	Implementing Parallel Quicksort and/or Mergesort

	Fri	Apr 11	Parallel Partition with Cutoff		Working session

14	Mon	Apr 14	Coping with Limitations Backtracking	IDAA 12.1 Knight Tour (Java) n-Queens (C++)	HW 13 due

	Wed	Apr 16	Coping with Limitations Branch-and-Bound	IDAA 12.2 Branch-and-Bound Example

	Fri	Apr 18	Good Friday		No Class

15	Mon	Apr 21	Easter		No Class

	Wed	Apr 23	Something fun	ParellelSorts code Subset Sum Demo	HW 12 due (part 2)

	Fri	Apr 25	Review		HW 12 due (part 3)

Ex	Thu	May 01			Final Exam 12:30-2:30pm