Important Reminder:

• There is a Quiz every Friday that there isn't otherwise an exam.

Week 1

• Welcome and Assessment
• Hashing: Bucket Sorting and Hashing; also procedurals
• Independence Day (July 4) -- No class
• Hashing: Collision resolution techniques

Week 2

• Complexity of algorithms
• DP: Dynamic Programming and Memoization -- Introduction
• DP: Classic problems: Knapsack, chain multiplication, LCS, string reconstruction
• DP: Continued
• DP: Continued

Week 3

• Sorting: Quadratic sorts, Quicksort
• Sorting: Binary Heaps and Heap sort, Binomial Heaps
• Sorting: Radix sort, Search Trees
• Sorting: AVL and Splay Trees
• Sorting: B-Trees, Tries, Extensible Hashing

Week 4

• Slack/Spare/Review
• Midterm Exam
• Compression: Huffman coding
• Compression: String compression, LZW compression
• Finite Automaton

Week 5

• String Matching: Knuth-Morris-Prat
• String Matching: Aho-Corasick, Rabin-Karp
• Graphs: Representation and Traversals
• Graphs: Greedy Algorithms and Shortest Path
• Graphs: Spanning Trees, Minimum Spanning Trees

Week 6

• Graphs: Cycle Detection with Union-Find, more Minimum Spanning Trees
• Graphs: Bellman-Ford, Floyd-Warshall
• Computability
• Slack/Review/Spare
• Final Exam