Schedule

This is an approximate schedule. Expect dates and topics to change. (I will try to keep due dates the same.)

Monday	Wednesday	Friday
Week 00: Approaching the Course
		(01) 28 August 2015 An Introduction to the Course Course Goals. Course Format. Approaching Algorithms. Problem: Getting From Here to There. Problem: Optimal Soldering Plans. Problem: Scheduling Overlapping Tasks.
Week 01: Getting Started
(02) 31 August 2015 Asymptotic Analysis	(03) 2 September 2015 Reflective Activities Dijsktra's Shortest-Path Algorithm. Algorithm design principles. Greedy algorithms. Quick review of asymptotic analysis. Additional characteristics of Big-Oh.	(04) 4 September 2015 Asymptotic Algorithm Analysis, Continued Asymptotic analysis, revisited. Other properties of Big-Oh notation. Careful loop counting.
Week 02: Formal Approaches
(05) 7 September 2015 Divide and Conquer Approaches Divide and Conquer Algorithms. Analyzing Divide-and-Conquer Algorithms. Estimating Recurrence Relations. Solving Recurrence Relations with Recursion Trees. Proving Recurrence Relations with the Substitution Method. Solving Recurrence Relations with the Master Theorem.	(06) 9 September 2015 Asyptotic Analysis and Recurrence Relations Recursion trees, revisited. Proving asymptotic bounds of recursive functions. The master theorem. The kth-largest problem.	(07) 11 September 2015 Pause for Breath Proving closed forms of recurrence relations. Finding the kth-largest element of an unsorted array/list.
Week 03: ADTs and Data Structures
(08) 14 September 2015 Roles of Data Structures and Abstract Data Types Abstract data types. Data structures. The Dictionary ADT.	(09) 16 September 2015 Hash Tables Review of hash tables. Hash functions, revisited. Other uses of hash tables and hash functions.	(10) 18 September 2015 An Introduction to Trees Hash Tables: Semi-Formal Analysis. Hash Functions and Hash Tables: Other Applications. Trees: The Basics. Balancing Trees.
Week 04: Binary Search Trees
(11) 21 September 2015 Binary Search Trees Trees, Formalized. Terminology. Binary Trees. Traversing Trees. Binary Search Trees. Balancing Binary Search Trees.	(12) 23 September 2015 Red-Black Trees Balancing (or at least rearranging) balanced trees. Red-black tree basics. Red-black tree examples. Insertion in red-black trees.	(13) 25 September 2015 Red-Black Trees, Continued Review. Your questions. Insertion in red-black trees. Deletion in binary-search trees. Deletion in red-black trees.
Week 05: Sorting
(14) 28 September 2015 Red-Black Trees, Concluded Key ideas from insertion. Deletion in binary search trees. Deletion in red-black trees.	(15) 30 September 2015 2-3 Trees 2-3 Trees. Insertion in 2-3 Trees. Deletion in 2-3 Trees. B-Trees.	(16) 2 October 2015 Sorting Comparing sorting algorithms. O(nlogn) sorting algorithms. Lower bounds on sorting algorithms.
Week 06: Sorting, Continued
(17) 5 October 2015 Heap Sort Background. Heaps. Inserting into Heaps. Removing from Heaps. Heap Sort.	(18) 7 October 2015 Lower Bounds Compare-and-swap algorithms. Decision trees. Analyzing the size of these decision trees. Estimating n!.	(19) 9 October 2015 O(n) Sorting Algorithms Other strategies for sorting. Bucket sort. Radix sort.
Week 07: Miscellaneous
(20) 12 October 2015 Radix Sort A Demo. Thinking About Radix Sort. Radix Sort and Strings. Re-Costing Radix Sort.	(21) 14 October 2015 Tries	(22) 16 October 2015 No Class
Fall Break
Week 08: An Introduction to Graphs
(23) 26 October 2015 Graphs Tries, Revisited. Graphs. A Graph ADT. Graph Traversal.	(24) 28 October 2015 Graph ADTs Designing a graph ADT. Different perspectives on graph ADTs. Building graphs. Accessing values. Implementing graphs (if time).	(25) 30 October 2015 Implementing the Graph ADT Traversal algorithms. Marking vertices and edges. Three graph implementations and their costs.
Week 09: Graph Algorithms
(26) 2 November 2015 Minimum Spanning Trees Minimum spanning trees. Two algorithms: Prim's algorithm and Kruskal's algorithm. Examples. Proofs of correctness.	(27) 4 November 2015 Minimum Spanning Trees, Continued Three approaches. Examples. Proofs of correctness. Running times.	(28) 6 November 2015 Sets and Union-Find Kruskal's algorithm, revisited. A Set ADT. The Union-Find algorithm.
Week 10: More Graph Algorithms
(29) 9 November 2015 Shortest Paths The Shortest-Path Problem. Dijkstra's Shortest-Path Algorithm. Analyzing Dijkstra's Shortest Path Algorithm. All Pairs Shortest Path Algorithms. The Floyd-Warshall Algorithm.	(30) 11 November 2015 Pause for Breath All-pairs shortest path, continued. The Floyd-Warshall algorithm. Looking ahead: The max-flow problem / Augmenting paths.	(31) 13 November 2015 Network Flows The max-flow problem. Augmenting paths. The Ford-Fulkerson algorithm. Bipartite matching.
Week 11: Dynamic Programming
(32) 16 November 2015 Pause for Breath	(33) 18 November 2015 Dynamic Programming (1) The Stamps problem. Dynamic programming. The Knapsack problem.	(34) 20 November 2015 Dynamic Programming (2) A DP Solution to the Stamps Problem. The Knapsack Problem. The String Matching Problem.
Week 12: Miscellaneous
(35) 23 November 2015 Dynamic Programming (3) Dynamic programming, reviewed. The Edit Distance problem. The Knapsack problem, revisited.	(36) 25 November 2015 Pause for Breath

Week 13: String Matching
(37) 30 November 2015 String Matching Basics	(38) 2 December 2015 Improved String-Matching Algorithms	(39) 4 December 2015 Pause for Breath
Week 14: Wrapup
(40) 7 December 2015 Looking Ahead: P vs. NP	(41) 9 December 2015 Wrapup	(42) 11 December 2015 Evaluate and Debief