About
Announcements
Modules
Coursework
FAQ
Java API

The modules below mostly, but not always, correspond to lectures.

Module 1: Introduction

Module 2: Sorting
 Quicksort
 Mergesort
 Heaps and heapsort.
 Lower bound, bucketsort.

Module 3: Ordered Search
 Review of binary search trees.
 Deletion from a binary search tree.
 AVL trees.
 Multiway trees.
 Selfadjusting binary search trees.

Module 4: Equality Search, Hashing, Tries
 Key signatures and addressing.
 Openchain hashing.
 2D hashing.
 Digital search trees.
 Tries

Module 5: Pattern Search
 The string search problem.
 The RabinKarp algorithm.
 The KnuthPrattMorris algorithm
 Finiteautomaton search.
 Wildcards, regular expressions and nondeterministic finite automata.
 Web search engines.

Module 6: Performance testing
 Performance testing and profiling.
 Code tuning in Java.
 Stepwise refinement in problemsolving.

Module 7: Graphs, part I
 Definitions, key ideas, applications.
 Data structures for graphs.
 Breadthfirst search.
 Depthfirst search.
 Applications of depthfirst search.
 Topological sort in DAG's.

Module 8: Graphs, part II
 Online vs. offline problems.
 Online equivalenceclass problem and unionfind.
 Minimum spanning trees: Kruskal's algorithm with unionfind.
 Priority queues.
 Prim's spanning tree algorithm.
 Dijkstra's shortestpath algorithm.

Module 9: Shortest Paths and Dynamic Programming
 Assorted topics in ShortestPaths: negative weights, DAG's.
 Allpairs shortest paths: FloydWarshall algorithm.
 Distributed routing: RIP, OSPF.
 Dynamic programming: Load balancing problem.
 Dynamic programming: FloydWarshall algorithm.
 Dynamic programming: Optimal binary search trees.

Module 10: Problems,
solution spaces and local search
 Combinatorial optimization problems.
 Solution spaces, local neighborhood, walking around solution space.
 Greedy local search.
 Simulated annealing.

Module 11: Problem complexity and NPCompleteness
 Problem complexity.
 Some wellknown combinatorial problems.
 Problem transformations.
 NPcomplete problems, reducibility.
 Approximations.
 Exhaustive Enumeration

Module 12: Bioinspired problems and algorithms
 Molecular biology primer.
 DNA sequencing problems.
 Cellular automata and Von Neumann's Quandary.
 Computing with DNA.
 Genetic algorithms.

Module 13: The Discrete Fourier Transform
 Sound and audio signals.
 Digitized sound and sampling.
 The Discrete Fourier Transform.
 DFT application to audio.
 The Fast Fourier Transform.
 2D DFT.

Module 14: Probability and Algorithms
 Simple Estimation.
 Estimation accuracy: confidence intervals.
 Histograms.
 Monte Carlo estimation.
 Evaluating averagecase complexity of algorithms.
 Appendix
(Occasionally useful stuff)
