Skip to main content

Schedule

Week 0
Date Topic Work Due
8/25 An introduction to the course
We begin to consider the core ideas of the course.
Week 1
Date Topic Work Due
8/28 Shortest path
We continue our exploration of the shortest path problem from the prior class.
8/30 Asymptotic analysis
We begin to consider ways to analyze the running times of algorithms.
9/1 Reflective activities
We reflect on the learning goals of the first few days of class and ground our understanding in a variety of exercises.
Week 2
Date Topic Work Due
9/4 Divide-and-conquer algorithms and structures
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.
9/6 Asymptotic analysis and recurrence relations
We explore ways to think about the running time of divide-and-conquer algorithms.
9/8 The Master Theorem
We consider proofs related to recurrence relations, and therefore to divide-and-conquer algorithms.
Week 3
Date Topic Work Due
9/11 Roles of data structures and abstract data types
We begin to consider the ADTs and data structures that underlie many of the algorithms we write.
9/13 Hash Tables
We consider hash tables, one of the more popular implementations of the dictionary ADT.
9/15 More on dictionaries
We consider some basic issues of the tree ADT / data structure.
Week 4
Date Topic Work Due
9/18 Binary search trees
We continue trees in general and binary search trees in particular.
9/20 Red-black trees
We start to consider red-black trees, one of the approaches for keeping search trees relatively balanced.
9/22 Red-black trees, continued
We continue our exploration of red-black trees.
Week 5
Date Topic Work Due
9/25 2-3 trees
We continue to explore balanced trees by considering another approach to balancing trees.
9/27 Pause for breath
We pause to catch up on balanced trees and other issues.
9/29 Sorting
We begin our consideration of one of the most common algorithmic problems, that of putting a collection of values in order.
Week 6
Date Topic Work Due
10/2 Lower bounds on sorting algorithms
We consider lower bounds on comparison-based sorting algorithms.
10/4 O(n) sorting algorithms
We consider some algorithms that achieve O(n) running time, often by limiting the input in certain ways.
10/6 Radix sort
We continue our exploration of O(n) algorithms, focusing primarily on bucket sort and radix sort
Week 7
Date Topic Work Due
10/9 Discussion of exam 1
We consider exam 1
10/11 Tries
We explore the trie data structure.
10/13 Pause for breath
We wrap up a variety of topics
Fall Break
Week 8
Date Topic Work Due
10/23 Detour - Skip lists
We consider some details of skip lists.
10/25 Program verification (1)
We begin to explore why and how we we use formal techniques to verify our algorithms.
10/27 Program verification (2)
We consider the details of common verification mechanisms.
Week 9
Date Topic Work Due
10/30 Program verification (3)
We continue our exploration of program verification.
11/1 Program verification (4)
We conclude our exploration of program verification with a traditional example.
11/3 Shortest paths
We start our exploration of graphs by considering algorithms for computing the shortest path between nodes in a graph.
Week 10
Date Topic Work Due
11/6 Minimum spanning trees
We consider an important class of graph algorithm, that of computing the minimum spanning tree of a graph.
11/8 Minimum spanning trees, continued
We explore the details and proofs of correctness of some MST algorithms.
11/10 Implementing graphs
We consider how we might implement/represent graphs in the computer.
Week 11
Date Topic Work Due
11/13 Sets and union-find
We consider an algorithm and structure that are useful in a variety of situations.
11/15 Network flows
We explore network flow algorithms and their applications.
11/17 Dynamic programming (1)
We consider another important algorithm design technique.
Week 12
Date Topic Work Due
11/20 Dynamic programming (2)
We continue our consideration of dynamic programming
11/22 Discussion of exam 2
We consider common issues on exam 2
Thanksgiving Break
Week 13
Date Topic Work Due
11/27 Dynamic programming (3)
We conclude our initial exploration of dynamic programming by visiting a common dynamic programming algorithm, approximate string matching.
11/29 Basics of string matching
We consider some basic issues in string matching algorithms
12/1 Improved string-matching algorithms
We continue to explore string-matching algorithms
Week 14
Date Topic Work Due
12/4 Knuth-Morris-Pratt, concluded
We conclude our exploration of string matching with the Knuth-Morris-Pratt algorithm
12/6 Wrapup
We start to conclude the class
12/8 Evaluate and debrief
We conclude the class
Finals Week
Date Topic Work Due
12/13 Final Examination

Accessibility statement. Check accessibility with WAVE.

Copyright © Samuel A. Rebelsky. Selected materials are design elements are due to other members of the Grinnell CS department and are used with permission.

This work is licensed under a Creative Commons Attribution 3.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc/3.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.

This website was built using Jekyll, Twitter Bootstrap, and the Bootswatch Cosmo Theme.