This schedule is tentative and subject to change during the semester. Changes will be reflected on this page as well as announced during lecture. Students should consult this schedule regularly for the most uptodate information.
Lecture  Date  Topic  Reading/homework 

1  W 8/24  Introduction Profile and assessment quiz 
1.1, 1.2 (skim) 3.1 (O and Θ) 
2  M 8/29  Recursion: simplifyanddelegate  Ch 2 
3  W 8/31  Recursion: Towers of Hanoi, mergesort Review: summation notation, induction 
4.1 
M 9/5  Labor day  Homework 1 due Friday 9/9 at 11:59 pm 

4  W 9/7  Recursion: recurrence equations Review: logarithms, Onotation 
4.3 
5  M 9/12  Recursion: divideandconquer Review: worse case time complexity 
33.4 
6  W 9/14  Recursion: backtracking  Erickson notes (just 3.1, 3.3, 3.6) 
F 9/16  Homework 2 due Fri 9/16 11:59pm  
7  M 9/19  Recursion: dynamic programming  15.1 
8  W 9/21  Recursion: dynamic programming  
9  M 9/26  Data structures: roadmap Data structures: stacks, space complexity of recursive algorithms, find the convex hull 
10.1, 10.2 (skim) 33.3 (Graham scan) 
10  W 9/28  Data structures: priority queues, heaps, selection and heapsort Heapsort code 
Ch 6 and/or Binary heaps (videos 14)  Prof Taylor 
F 9/30  Homework 3 due Fri 9/30 11:59pm Homework 4 due Fri 9/30 11:59pm 

11  M 10/3  Exam 1  
12  W 10/5  Data structures: dictionaries, BSTs BST starter code 
12 
13  M 10/10  Data structures: redblack trees  13 
14  W 10/12  Randomization: hashing 1: hash tables, hash chaining, hash functions  11.111.3 
F 10/14  Homework 5  
15  M 10/17  Randomization: hashing 2: table resizing (section 8 only), open addressing  11.4 
16  W 10/19  Problem solving session  
F 10/21  Homework 6  
17  M 10/24  Randomization: deterministic and randomized quicksort Review of basic probability, expectation, indicator variables 
7.17.3 
18  W 10/26  Randomization: analysis of randomized quicksort Proof using indicator variables 
7.4 
Su 10/30  Homework 7  
19  M 10/31  Graphs: representation, DFS, strongly connected components  22.1, 22.3 
20  W 11/2  Exam 2  
21  M 11/7  Graphs: Tarjan’s algorithm for strongly connected components  22.5 
22  W 11/9  Graphs: BFS, singlesource shortest path problem, Dijkstra  22.2, 24.3 
Su 11/13  Homework 8  
23  M 11/14  Graphs: relaxation  
24  W 11/16  Graphs: BellmanFord algorithm  24.124.2 
Su 11/20  Homework 9  
25  M 11/21  Graphs: minimum spanning trees  23.123.2 
W 11/23  Noninstructional day  
26  M 11/28  Hardness: sorting and search lower bounds  8.1 
27  W 11/30  Exam 3  
Su 12/4  Homework 10  
28  M 12/5  Hardness: radix sort, NPcompleteness  8.3, Ch 34 (skim chapter) 
29  W 12/7  Hardness: approximation algorithms  Ch 35 (skim chapter) 
Su 12/11  Homework 11 Bonus assignment 

30  M 12/12  Review  
Section 7 final exam F 12/16 2:45PM–5:00PM, MH 422 

Section 8 final exam W 12/14 9:45AM–12:00PM, MH 422 
abstract data type (ADT)  interface (API)  implementations 

stack  push() pop() 
linked list contiguous array dynamic array 
queue  queue() dequeue() 
linked list contiguous array dynamic array 
priority queue  insert(priority, obj) get_min() 
binary heap dary heap (d=2,4,8,…) fibonacci heaps 
dictionary aka map aka associative array 
set(key, value) get(key)=value is key in dictionary? 
hash table binary search tree 
set  add(key) is key in set? 
dictionary bit vector 
graph  add(node) add_edge(n1, n2) neighbors(node) is n1 a neighbor of n2? 
dictionary adjacency matrix adjacency list 
Various remarks:
previous()
and next()
. Binary search trees can also be viewed as a generalization of dynamic arrays in that the data is sorted (by key) but it also strikes a balance between fast insertion and fast lookup.