Date 
Lecture Topics 
Readings 
Project Work 
Week 1 
Tu 4/3 
 Course introduction and goals
 Virtualization: Running more than one operating system simultaneously
 Quick overview of the ICS 46 VM development environment
 Exceptions
 Throwing and catching exceptions
 Why exceptions profoundly affect design in C++



Th 4/5 
 Contracts
 Preconditions and postconditions
 Class invariants
 Writing classes more carefully
 Exception safety
 The noexcept keyword
 Class templates
 Separating interface from implementation, even in header files
 Member function templates



Week 2 
Tu 4/10 
 Randomness
 Entropy and pseudorandomness
 Generating sequences of random values in C++
 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



W 4/11 


Project #0 due 11:59pm 
Th 4/12 
 Smart pointers (as an RAII technique for memory management)
 Unique ownership and std::unique_ptr
 Shared ownership and std::shared_ptr
 Why not all pointers can be smart pointers



Week 3 
Tu 4/17 
 An indepth look at Project #1
 Multidimensional arrays (briefly)
 Options for storing multidimensional data in C++



Th 4/19 
 Moving, as opposed to copying, in C++
 Move semantics in C++
 Rvalue references
 Move constructors
 Move assignment operators



Week 4 
M 4/23 


Project #1 due 11:59pm 
Tu 4/24 
 Asymptotic analysis: O, Ω, and Θnotation
 Best, worst, and averagecase analysis
 Variations on linked lists
 Analyzing linked list variations using O, Ω, and Θnotation
 Stacks, queues, and deques



Th 4/26 
 "Alternative" forms of algorithm analysis
 Amortized analysis (briefly)
 Why std::vector's reallocations aren't as bad as you think
 Analyzing the performance of recursion
 Recurrences



Week 5 
Tu 5/1 
 General trees
 General tree implementation

 Breadthfirst tree traversals



Th 5/3 
 Depthfirst tree traversals (preorder and postorder)
 Comparing the performance (time and memory) of tree traversals
 Nary and binary trees
 Internal vs. external nodes



F 5/4 


Project #2 due 11:59pm 
Week 6 
Tu 5/8 
 Background on Project #3
 Binary search trees
 The importance of logarithms in computer science



Th 5/10 
 MIDTERM — regular lecture time and location



Week 7 
Tu 5/15 
 The importance of keeping binary search trees balanced
 What is a "good" balance condition?
 AVL trees
 Skip lists
 Probabilistic analysis (briefly)



Th 5/17 
 Hashing and hash tables
 Separate chaining
 "Good" hash functions
 Open addressing
 Linear probing
 Hashing objects other than numbers



F 5/18 


Project #3 due 11:59pm 
Week 8 
Tu 5/22 
 Priority queues
 Implementing a priority queue using a min heap or max heap
 Graphs: definition and terminology
 Directed graphs
 Directed acyclic graphs (DAGs)
 Undirected graphs



Th 5/24 
 Graph implementation tradeoffs
 Adjacency lists vs. adjacency matrix implementations
 Depthfirst graph traversal
 Breadthfirst graph traversal
 Why connectedness is an important factor in a graph
 Connectedness of a graph
 Strong connectedness vs. weak connectedness



Week 9 
M 5/28 
 University Holiday: Presidents' Day — NO LABS TODAY



Tu 5/29 
 Testing graphs for connectedness
 Dijkstra's shortest path algorithm
 Topological ordering of a DAG



W 5/30 


Project #4 due 11:59pm 
Th 5/31 
 The sorting problem
 What can and cannot be sorted
 Sorting in O(n^{2}) time
 Insertion sort
 Selection sort



Week 10 
Tu 6/5 
 Sorting in O(n log n) time
 Treesort
 Heapsort
 Divide and conquer algorithms (briefly)
 Quicksort
 Mergesort



Th 6/7 
 A lower bound for comparisonbased sorting
 Modeling comparisonbased sorts using decision trees
 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/8 


Project #5 due 11:59pm 
Finals Week 
Tu 6/12 
 FINAL EXAM: 7:00pm9:00pm, HSLH 100A


