Intro to algorithms

Kragen Javier Sitaker, 2016-09-06 (4 minutes)

If I want my paper-oriented algorithm notation to be useful, one avenue is to express algorithms that people are interested in in it. Perhaps introduction-to-algorithms classes would be a good place to find them. So here is a summary of some intro-to-algorithms classes, covering mostly only the algorithms, although in a few cases I’ve also included the problems because it wasn’t clear which algorithm was being taught. I’ve probably missed a lot.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2008/calendar/ is an intro-to-algorithms syllabus. Algorithms it covers:

http://www.cs.rpi.edu/~goldsd/spring2013-csci2300.php is another, in some sense much less comprehensive. It covers:

http://www.cs.rit.edu/~anh/alg_resources.html is another. Unfortunately it doesn’t give any significant detail on what is covered.

http://www.fas.harvard.edu/~libcs124/E124/syllabus.html is another, with rather nice lecture notes. It covers:

http://www.cse.msstate.edu/~swan/teaching/2008-3_CSE-4833-6833_Algs/schedule.htm is another, far less comprehensive:

http://cs.smith.edu/~streinu/Teaching/Courses/252.html is another:

Finally, http://courses.cs.washington.edu/courses/cse421/14su/ covers:

Here are the items that appear in more than 2 of those lists:

  6 shortest paths
  5 minimum spanning tree
  5 dynamic programming
  5 depth-first search
  5 breadth-first search
  4 vertex cover
  4 traveling salesman
  4 satisfiability
  4 mergesort
  4 dijkstra’s algorithm
  3 topological sort
  3 strassen’s algorithm
  3 memoized fibonacci
  3 matrix multiplication
  3 integer multiplication

That’s 15 algorithms or problems, which seems like a reasonably short list of things to cover; some of them are even redundant, like Strassen’s algorithm to solve matrix multiplication.

It seems sort of bizarre to me that graph algorithms are given such great prominence in these introductory courses, since they seem, to me at least, to have relatively little importance in practical day-to-day programming. Certainly we work with graphs all the time, and we even occasionally topologically sort them. But shortest-path algorithms and minimum spanning trees almost never occur in my experience (except in Ethernet switches). Even dynamic programming is relatively uncommon, and search needs heuristics most of the time to be useful.

Topics