Date 
Lecture Topics 
Readings 
Project Work 
Week 1 
Tu 4/4 
 Course introduction
 Some necessary, additional C++ background
 Function templates
 Why templates are generally written in header files



Th 4/6 
 Class templates
 Separating interface from implementation, even in header files
 Member function templates
 Randomness
 Entropy and pseudorandomness
 Generating sequences of random values in C++



Week 2 
Tu 4/11 
 The "resource acquisition is initialization" (RAII) technique in C++
 Automating the release of resources, even when exceptions are thrown, using RAII
 Ownership of dynamicallyallocated objects
 Smart pointers (as an RAII technique for memory management)
 Unique ownership and std::unique_ptr



Th 4/13 
 Shared ownership and std::shared_ptr
 Why not all pointers can be smart pointers
 Asymptotic analysis: O, Ω, and Θnotation
 Best, worst, and averagecase analysis



F 4/14 


Project #0 due 11:59pm 
Week 3 
Tu 4/18 
 An indepth look at Project #1
 Multidimensional arrays (briefly)
 Options for storing multidimensional data in C++



Th 4/20 
 Variations on linked lists
 Analyzing linked list variations using O, Ω, and Θnotation
 Stacks, queues, and deques
 "Alternative" forms of algorithm analysis



Week 4 
M 4/24 


Project #1 due 11:59pm 
Tu 4/25 
 Amortized analysis (briefly)
 Why std::vector's reallocations aren't as bad as you might think
 Analyzing the performance of recursion
 Recurrences
 General trees



Th 4/27 
 An indepth look at Project #2
 General trees (continued)
 General tree implementation
 Breadthfirst tree traversals
 Depthfirst tree traversals (preorder and postorder)
 Comparing the performance (time and memory) of tree traversals



Week 5 
Tu 5/2 
 Nary and binary trees
 Internal vs. external nodes
 The importance of logarithms in computer science
 Binary search trees



Th 5/4 
 The importance of keeping binary search trees balanced
 What is a "good" balance condition?
 AVL trees



F 5/5 


Project #2 due 11:59pm 
Week 6 
Tu 5/9 
 Skip lists
 Probabilistic analysis (briefly)
 Hashing and hash tables
 Separate chaining
 "Good" hash functions



Th 5/11 
 MIDTERM — regular lecture time and location



Week 7 
Tu 5/16 
 Open addressing
 Linear probing
 Hashing objects other than numbers
 Moving, as opposed to copying, in C++
 Move semantics in C++
 Rvalue references
 Move constructors
 Move assignment operators



Th 5/18 
 Priority queues
 Implementing a priority queue using a min heap or max heap



Week 8 
Tu 5/23 
 Graphs: definition and terminology
 Directed graphs
 Directed acyclic graphs (DAGs)
 Undirected graphs
 Graph implementation tradeoffs
 Adjacency lists vs. adjacency matrix implementations



Th 5/25 
 Depthfirst graph traversal
 Breadthfirst graph traversal
 Why connectedness is an important factor in a graph
 Connectedness of a graph
 Strong connectedness vs. weak connectedness



F 5/26 


Project #3 due 11:59pm 
Week 9 
M 5/29 
University Holiday: Memorial Day — NO LABS TODAY 


Tu 5/30 
 Testing graphs for connectedness
 An overview of Project #4
 Dijkstra's shortest path algorithm
 Topological ordering of a DAG



Th 6/1 
 The sorting problem
 What can and cannot be sorted
 Sorting in O(n^{2}) time
 Insertion sort
 Selection sort
 Sorting in O(n log n) time
 Treesort
 Heapsort



Week 10 
Tu 6/6 
 Divide and conquer algorithms (briefly)
 Quicksort
 Mergesort
 A lower bound for comparisonbased sorting
 Modeling comparisonbased sorts using decision trees



Th 6/8 
 How to sort in linear time by using techniques other than comparisons
 Counting sort
 Radix sort
 Why radix sort can run in linear time (i.e., linear with respect to what?)
 Conclusion



F 6/9 


Project #4 due 11:59pm 
Finals Week 
Th 6/15 
 FINAL EXAM: 4:00pm6:00pm, HSLH 100A


