CS 3212: Algorithms

Class material


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.
    • Self-adjusting binary search trees.

  • Module 4: Equality Search, Hashing, Tries
    • Key signatures and addressing.
    • Open-chain hashing.
    • 2D hashing.
    • Digital search trees.
    • Tries

  • Module 5: Pattern Search
    • The string search problem.
    • The Rabin-Karp algorithm.
    • The Knuth-Pratt-Morris algorithm
    • Finite-automaton search.
    • Wildcards, regular expressions and non-deterministic finite automata.
    • Web search engines.

  • Module 6: Performance testing
    • Performance testing and profiling.
    • Code tuning in Java.
    • Stepwise refinement in problem-solving.

  • Module 7: Graphs, part I
    • Definitions, key ideas, applications.
    • Data structures for graphs.
    • Breadth-first search.
    • Depth-first search.
    • Applications of depth-first search.
    • Topological sort in DAG's.

  • Module 8: Graphs, part II
    • On-line vs. off-line problems.
    • On-line equivalence-class problem and union-find.
    • Minimum spanning trees: Kruskal's algorithm with union-find.
    • Priority queues.
    • Prim's spanning tree algorithm.
    • Dijkstra's shortest-path algorithm.

  • Module 9: Shortest Paths and Dynamic Programming
    • Assorted topics in Shortest-Paths: negative weights, DAG's.
    • All-pairs shortest paths: Floyd-Warshall algorithm.
    • Distributed routing: RIP, OSPF.
    • Dynamic programming: Load balancing problem.
    • Dynamic programming: Floyd-Warshall 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 NP-Completeness
    • Problem complexity.
    • Some well-known combinatorial problems.
    • Problem transformations.
    • NP-complete problems, reducibility.
    • Approximations.
    • Exhaustive Enumeration

  • Module 12: Bio-inspired 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 average-case complexity of algorithms.

  • Appendix (Occasionally useful stuff)