ICS 46 Spring 2022
Schedule


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
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++
Videos
  • Randomness
  • Entropy and pseudorandomness
  • Generating sequences of random values in C++
W 4/6
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
Videos
  • Moving, as opposed to copying, in C++
  • Move semantics in C++
  • Rvalue references
  • Move constructors
  • Move assignment operators
M 4/11
F 4/15
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
M 4/18
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)
M 4/25
W 4/27
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
M 5/2
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
M 5/9
W 5/11
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
W 5/18
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
M 5/23
W 5/25
Week 10
Lectures
  • Something fun to be announced later (time permitting)
M 5/30
  • University Holiday: Memorial Day — NO LABS TODAY
W 6/1
F 6/3
Finals Week
Tu 6/7
  • FINAL EXAM: 7:00pm-9:00pm, EH 1200