ICS 46 Spring 2018
Schedule


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/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 dynamically-allocated 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 in-depth 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 average-case 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
  • Breadth-first tree traversals
Th 5/3
  • 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
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 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
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(n2) 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 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?)
  • Conclusion
F 6/8 Project #5 due 11:59pm
Finals Week
Tu 6/12
  • FINAL EXAM: 7:00pm-9:00pm, HSLH 100A