CS420 is about learning and practicing principles for organizing your thinking when solving programming problems, and not about memorizing details and facts. You must practice ways of establishing that an algorithm is correct and analyzing its time bound. Getting good at these skills will allow you to come up with efficient algorithms of your own, by figuring out what steps are needed in the pseudocode or program code to get the proof of correctness to go through, or to reduce the running time. You will also learn to recognize what kinds of optimizations on a program are a waste of time, as they will have little or no impact on the running time of the program as a whole.

The following are techniques for algorithm design that we will study in the class:

  • Advanced big-O analysis
  • Reduction of one problem to another
  • Advanced implementation and use of abstract data types
  • Use of mathematical induction in designing algorithms
  • Analysis and design of parallel algorithms
  • Amortized analysis
  • Randomized algorithms
  • Advanced examples of applications of techniques from a first-semester algorithms class: greedy strategies and proofs, dynamic programming, divide-and-conquer strategies
  • NP-completeness

Some of these techniques are covered in CS320; we will cover them at a more advanced level. The following are some illustrations of these topics that we may study, time permitting, together with the techniques they illustrate:

  • Strassen's algorithm -- divide-and-conquer strategy
  • Sorting networks -- divide-and-conquer; parallel algorithms
  • Fast Fourier Transform -- divide-and-conquer; parallel algorithms and architectures
  • Currency arbitraging -- reduction as an algorithm-design technique
  • Floyd-Warshall -- dynamic programming
  • Johnson's algorithm -- problem reduction as a design technique
  • Max flows, min cuts -- reduction as a design technique; use of invariants
  • Sorting, convex hull, Euclidean minimum spanning tree -- use of reduction to obtain lower bounds
  • SAT, 3-SAT, CLIQUE, VERTEX-COVER, SUBSET-SUM -- use of reduction to show NP-completeness and NP-hardness
  • VERTEX-COVER, EUCLIEAN-TRAVELING-SALESMAN, SUBSET-SUM: approximation algorithms for NP-hard problems
  • Maximum global separator in graphs -- randomized algorithms
  • MAX-3-SAT -- randomized algorithms; approximation algorithms
  • Median finding and Quicksort -- randomized algorithms
  • Hash tables -- randomized algorithms; amortized analysis
  • Splay trees -- amortized analysis; designing new ADT's

News: newest on top (it's a stack :)

  • The course books (CLRS and Kleinberg-Tardos) are on reserve in the Morgan Library.
  • Welcome to CS420