CMSI 282 - (Superset of) Topics
preliminaries
- review of algorithm analysis, recurrences, and the master theorem
- logarithms, square roots, powers, polynomials, and primes
combinatorial objects
- existence vs. counting vs. enumeration vs. optimization
- how to generate:
- permutations
- combinations
- subsets
- set partitions
- integer partitions
- graphs
algorithm paradigms
- algebraic manipulation
- decrease-and-conquer, divide-and-conquer
- greedy programs
- dynamic programming
- randomization
- exhaustive search, sieves, backtracking, branch-and-bound
- heuristic methods:
- A*
- simulated annealing
- genetic (also known as evolution, or population-based) algorithms
- swarm and nature-inspired algorithms
- paradigms for geometric algorithms
characters and strings
- Huffman compression
- fast string matching
- sequence alignment
sorting revisited
- optimal comparative sorts and mergesort
- priority queues, heaps and heapsort
- quicksort
- partition and order statistics
- sorting without comparing
cake-cutting and fair division
- discrete algorithms for n > 2 players
- complexity of cake-cutting
- simple vs. strong vs. envy-free division
- unequal shares and Ramsey partitions
- open questions
graphs
- implementing and generating graphs
- shortest-path problems
- traversals and connectivity problems
- union-find and topological sorting
- minimum spanning trees
- maximum flows and bipartite matchings
computational geometry
- points, lines, and polygons
- convex hulls
- nearest neighbors
- intersecting line segments
approximation algorithms
Return to: CMSI 282 home page
Revised: December 20, 2008