---

In lieu of a course textbook, assigned readings are the Notes and Examples from lecture. It is a good idea to skim the assigned reading before the lecture for the main ideas, attend lecture, and then to go through the assigned reading again to fill in the details that you missed, both in your initial skim of the reading and in the lecture.

Date	Lecture Topics	Readings	Assigned Work
Week 1
Lectures	Course introduction and goals A brief reintroduction to exceptions in C++ 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	N: Course Introduction N: Contracts and Exceptions N: Templates
Videos	Virtualization: Running more than one operating system simultaneously Quick overview of the ICS 46 VM development environment
Th 3/31			Begin working through Project #0 Aim to have the ICS 46 set up and ready to run today
Week 2
Lectures	The "resource acquisition is initialization" (RAII) technique in C++ Automating the release of resources, even when exceptions are thrown, using RAII Ownership of dynamically-allocated objects 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 Multidimensional arrays (briefly) Options for storing multidimensional data in C++	N: Smart Pointers N: Multidimensional Data
Videos	Randomness Entropy and pseudorandomness Generating sequences of random values in C++	N: Randomness
W 4/6			Project #0 due 11:59pm
Week 3
Lectures	Asymptotic analysis: O-, Ω-, and Θ-notation Best-, worst-, and average-case analysis Variations on linked lists Analyzing linked list variations using O-, Ω-, and Θ-notation Stacks, queues, and deques "Alternative" forms of algorithm analysis Amortized analysis (briefly) Why std::vector's reallocations aren't as bad as you think	N: Asymptotic Analysis N: Linked List Variations N: Stacks, Queues, and Deques N: Amortized Analysis
Videos	Moving, as opposed to copying, in C++ Move semantics in C++ Rvalue references Move constructors Move assignment operators	N: Move Semantics
M 4/11			Exercise Set 1 due 11:59pm
F 4/15			Project #1 due 11:59pm
Week 4
Lectures	Analyzing the performance of recursion Recurrences General trees General tree implementation Breadth-first tree traversals Depth-first tree traversals (preorder and postorder) Comparing the performance (time and memory) of tree traversals N-ary and binary trees Internal vs. external nodes	N: Asymptotic Analysis of Recursion N: General Trees N: Tree Traversals N: N-ary and Binary Trees
M 4/18			Exercise Set 2 due 11:59pm
Week 5
Lectures	Binary search trees The importance of logarithms in computer science The importance of keeping binary search trees balanced What is a "good" balance condition? AVL trees Skip lists Probabilistic analysis (briefly)	N: Binary Search Trees N: AVL Trees N: Skip Lists
M 4/25			Exercise Set 3 due 11:59pm
W 4/27			Project #2 due 11:59pm
Week 6
Lectures	Hashing and hash tables Separate chaining "Good" hash functions Open addressing Linear probing Hashing objects other than numbers 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	N: Hash Tables N: Priority Queues N: Graphs
M 5/2			Exercise Set 4 due 11:59pm
Week 7
Lectures	Graph implementation trade-offs Adjacency lists vs. adjacency matrix implementations Depth-first graph traversal Breadth-first graph traversal Why connectedness is an important factor in a graph Connectedness of a graph Strong connectedness vs. weak connectedness Testing graphs for connectedness Dijkstra's shortest path algorithm Topological ordering of a DAG	N: Graph Traversals N: Graph Connectedness N: Graph Connectedness N: Graphs: Shortest Paths N: Graphs: Topological Ordering
M 5/9			Project #3 due 11:59pm
W 5/11			Exercise Set 5 due 11:59pm
Week 8
Lectures	The sorting problem What can and cannot be sorted Sorting in O(n2) time Insertion sort Selection sort Sorting in O(n log n) time Treesort Heapsort Divide and conquer algorithms (briefly) Quicksort Mergesort	N: Comparison-Based Sorting
W 5/18			Exercise Set 6 due 11:59pm
Week 9
Lectures	A lower bound for comparison-based sorting Modeling comparison-based 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?) Equivalence classes The Union-Find algorithm	N: Linear-Time Sorting N: The Union-Find Algorithm
M 5/23			Project #4 due 11:59pm
W 5/25			Exercise Set 7 due 11:59pm
Week 10
Lectures	Something fun to be announced later (time permitting)
M 5/30	University Holiday: Memorial Day — NO LABS TODAY
W 6/1			Project #5 due 11:59pm
F 6/3			Exercise Set 8 due 11:59pm
Finals Week
Tu 6/7	FINAL EXAM: 7:00pm-9:00pm, EH 1200