ICS 46 Spring 2017

Assigned readings are a combination of pages from this web site (presented as links to those pages) and notes and examples from lecture (presented as links preceded by N:). 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 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 dynamically-allocated 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 average-case analysis
F 4/14 Project #0 due 11:59pm
Week 3
Tu 4/18
  • An in-depth 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 in-depth look at Project #2
  • General trees (continued)
  • General tree implementation
  • Breadth-first tree traversals
  • Depth-first tree traversals (preorder and postorder)
  • Comparing the performance (time and memory) of tree traversals
Week 5
Tu 5/2
  • N-ary 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 trade-offs
  • Adjacency lists vs. adjacency matrix implementations
Th 5/25
  • 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
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(n2) 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 comparison-based sorting
  • Modeling comparison-based 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:00pm-6:00pm, HSLH 100A