The schedule below shows the tentative dates for all class topics, readings, and assignments. You should complete all assigned reading before class on the day it is listed. Labs will be available shortly before the assigned lab day. There may be some revisions to the schedule during the semester, but I will make sure to announce these changes in class.
If you view this page with JavaScript enabled you can jump to the current week on the schedule, and you should see the next day of class highlighted in the schedule below.
We begin to consider the core ideas of the course.
Topics: Course goals. Course format.
We continue our introduction to the course.
Topics: Approaching algorithms. Testing priority queues. Heaps, continued. Problem: Getting from here to there. Problem: Optimal soldering plans. Problem: Scheduling overlapping tasks.
We begin to consider ways to analyze the running times of algorithms.
Topics: Review of complexity analysis from 301. Big-Oh, formalized. Characteristics of Big-Oh and associated proofs.
We continue to explore running time
Topics: Other characteristics of Big-Oh. Other notations (theta, little-oh). Casual and careful loop counting.
We explore one of the important algorithm design techniques, divide and conquer. Divide and conquer algorithms and structures achieve some efficiency by splitting the input in half.
Topics: Divide and conquer, in theory. Review of divide-and-conquer algorithms and structures. Finding the median value in an array. Exponentiation with integer exponents.
We pause to discuss a variety of outstanding issues.
Topics: Nearest Neighbor, revisited. Other Roughgarden examples.
We explore ways to think about the running time of divide-and-conquer algorithms.
Topics: Analyzing recursive algorithms with recurrence relations. Solving recurrence relations. Looking ahead to the master theorem.
We delve more deeply into the nearest neighbor algorithm.
We continue ideas from the prior class.
Topics: Nearest neighbor example. More practice solving recurrence relations. The recurrence formula theorem.
We continue trees in general and binary search trees in particular.
Topics: A bit more about the recurrence formula theorem. Trees, formalized. Terminology. Binary trees. Traversing trees. Binary search trees. Building balanced BSTs.. Balancing BSTs..
We start to consider red-black trees, one of the approaches for keeping search trees relatively balanced.
Topics: Red-black tree basics. Red-black tree examples. Insertion in red-black trees.
We continue our exploration of red-black trees.
Topics: Deletion in binary-search trees. Deletion in red-black trees.
We pause to catch up on balanced trees and other issues.
Topics: Red-black trees. Other balanced trees.
We begin our consideration of one of the most common algorithmic problems, that of putting a collection of values in order.
Topics: Characteristics of sorting algorithms. Common sorting algorithms.
We consider lower bounds on comparison-based sorting algorithms.
Topics: Recap from prior class. Some followup questions on algorithms. A theorem about lower bounds. Proving that theorem.
We consider some algorithms that achieve O(n) running time, often by limiting the input in certain ways.
Topics: A sorting exercise. Other strategies for sorting. Bucket sort. Radix sort.
We consier issues of sorting in preparation for assignment 6.
We consier issues of sorting in preparation for assignment 6.
We explore the trie data structure.
Topics: Review of dictionaries. Costs of dictionary implementations. Tries.
We begin to explore why and how we we use formal techniques to verify our algorithms.
Topics: Goals for this unit. Verifying imperative code. Loop invariants. Example - binary search.
We consider the details of common verification mechanisms.
Topics: Example - binary search, revised. Example - DNF. Example - Efficient exponentiation with recursion. Example - Efficient exponentiation with iteration.
We conclude our exploration of program verification and loop invariants.
Topics: About HW7. Example - Efficient exponentiation with iteration. Other invariants.
We watch “Coded Bias” in preparation for a discussion.
We consider the implications of Coded Bias on our own practices as computer scientists and algorithm designers.
We start our exploration of graphs by considering algorithms for computing the shortest path between nodes in a graph.
Topics: Graphs. The shortest-path problem. Dijkstra’s shortest-path algorithm. Analyzing Dijkstra’s shortest-path algorithm. All-pairs shortest-path algorithms.
We consider an important class of graph algorithm, that of computing the minimum spanning tree of a graph.
Topics: Minimum spanning trees. Examples. Designing an MST algorithm.
We explore the details and proofs of correctness of some MST algorithms.
Topics: Prim’s algorithm and Kruskal’s algorithm. Efficiency. Proofs of correctness.
We consider an algorithm and structure that are useful in a variety of situations.
Topics: A set ADT. Data structure design, revisited. The union-find structure. Analyzing union find. Improving union-find.
We consider how we might implement MSTs
We explore netflork flow algorithms and their applications.
Topics: Looking back to graph algorithms. Network flows.
We continue to explore netflork flow algorithms and their applications.
Topics: The Ford-Fulkerson algorithm. Bipartite matching. Further applications of network flow.
We consider another important algorithm design technique.
Topics: Fibonacci numbers. The stamps problem. The value of caching. Dynamic programming, generalized.
Motivated by the stamps problem, we return to greedy solutions for coins and other objects.
Topics: Greedy coins. The activity selection problem. Why prove. Proofs of correctness.
We further continue our consideration of dynamic programming
Topics: Generalizing the technique. Other problems.
We consider an algorithm from the literature
Topics: Introduction to skip lists. Knapsack, concluded. Edit distance.
We conclude our initial exploration of dynamic programming.
Topics: Edit distance, continued. Variations of edit distance.
We return to an algorithm from the literature
We catch up on a missed topic
We consider some basic issues in string matching algorithms
Topics: Approximate substring matching. Exact substring matching. The brute-force approach. The hash-code approach.
We continue to explore string-matching algorithms
Topics: The hash-code approach. Keeping track of look-ahead. Building the table.