Algorithms and Data Structures
Fall 2012
Lectures:
Tu 8:30-10:30 + reading
Book:
Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms
Topics
Introduction, recurrences, big O, Omega
Dynamical programming
Sorting (bubble, insertion, merge-sort, quicksort,
lower bound; counting and radix sort)
Selection: minimum, maximum, median; heap
Binary search tree, red-black tree
Graphs, basic notions, BFS, DFS
Trees, Prufer's code, Cayley's theorem
Minimum spanning trees
Shortest paths
Flows
Geometric algorithms
Approximation algorithms