Algo2 Topics

To gain access to the course resources, including notes, videos and links, please email me.

Topics

Note that the classification of topics into categories such as Graphs, Algorithms and Data structures is sometimes fuzzy. Some problems on graphs are algorithmic, data structures are built using algorithms and in turn are used to speed up algorithms, etc.

Don't worry about items that are [under construction]. They mainly represent an ongoing to-do list. There are already enough topics that are ready, and more will be added. The list will eventually have more topics than can fit in a semester-long course.

• Graphs:
  • Edge coloring and vertex coloring
    • What does coloring edges have to do with scheduling a round-robin tournament?
      What does coloring vertices have to do with designing the final exam block schedule?
  • Cliques, independent sets, Ramsey numbers
    • See how some structures must exist if a graph has enough vertices.
  • Planarity and crossing number
    • What graphs are planar? How many edges do planar graphs have? Can we bound the minimum number of edge crossings for a given graph?
  • Spanners and path approximation
    • Construct paths with few links that approximate paths with many links, while preserving certain properties.
      Reduce the cost of building a connected network without sacrificing the efficiency of traversing it.
  • Matching
    • Given two sets of objects, and a set of possible matches between them, how can you maximize the number of objects that get matched, assuming each object can only match to one other?
  • Network flow
    • See how capacity constraints in wires / pipes / networks will limit output supply in a complicated network.
  • All-pairs shortest paths
    • The next step after having studied single-source shortest paths.
• Algorithms:
  • Linear programming (definition, geometric interpretation, 2D algorithm)
    • Brief intro to a huge field of computer science / optimization.
  • Examples of the Probabilistic Method
    • Discover how to use probability to obtain bounds for certain problems that don't actually involve probability.
  • Exact string matching (e.g., Z algorithm)
    • A classic problem: does a particular word occur in a given text?
  • String matching with errors (e.g., edit distance) [under construction]
    • Define and find the distance between two strings.
  • Lower bounds (algebraic decision trees, and reductions) [under construction]
    • How to obtain lower bounds for problems from scratch, or by knowing existing bounds for other problems.
• Data structures:
  • WAVL trees (and AVL)
    • In between AVL and Red-Black trees, and better in some ways.
  • Optimal BST
    • How does knowing the frequencies of searches help us build a better BST? How close can we get if we don't know anything in advance? What difference does it make if the tree is static or dynamic?
  • Splay trees
    • A self-adjusting BST, and an opportunity to polish your amortization skills.
  • Geometry of BST
    • How to interpret BST algorithms as 2D point sets.
  • Expected depth for random BST
    • Why are randomly built BSTs expected to be balanced, and what is the best bound on expected depth?
  • Binomial heaps, Fibonacci heaps, Quake heaps
    • Fancier versions of heaps, and how they apply to topics you learned in intro to algorithms.
  • Fractional cascading
    • A data structure that allows a cool way of searching for an element in several sorted lists, and speeds up other applications.
  • High dimensional range counting
    • Fast ways of determining how many points are in a box (with pre-processing).
  • Weight-balanced trees and Scapegoat trees
    • Balancing by subtree size instead of height.
  • Huffman coding
    • Data compression
  • Suffix trees [partially done, but still under construction]
    • Pre-process a huge text, using only a constant (multiple) factor more space, so that you can search for any pattern in time proportional just to the pattern length, not the text length.
  • Skip lists [under construction]
    • See how to search in a structure that resembles a subway.
  • Treaps, Queaps and Quacks [under construction]
    • Combining properties of trees, queues, heaps and stacks.
  • Cuckoo hashing [under construction]
    • Learn about a hashing method that resembles the behavior of a not-so-nice bird.
  • Point location
    • How to find where you clicked on a map. More surprising and elegant than you might think.

Besides the topics listed, I might also cover some cool algorithms from the field of Computational Geometry, as long as not too many students have already taken that course. For example, we could cover the convex hull problem, Voronoi diagrams, high-dimensional kd trees, the closest pair problem, minimum enclosing circle, sweepline algorithms, detecting intersections among line segments, data depth, etc.