What's next in Algorithms (after this course)?

What else should you know about algorithms?

The five broad areas of algorithms

The word algorithm is likely to show up in any area that features computation. This is one reason why there it is hard to list a set of "fundamental" algorithms that every CS student should know. What is more important, of course, is algorithmic thinking: the ability to solve problems using efficient algorithms, and to reason about the strengths and limitations of different algorithms.

That said, there are broad areas of algorithms where the algorithms appear to share some common formal background and therefore seem to belong in the same course. I will describe what I believe are the natural groupings, each of which could constitute a semester-long or two-semester course.

Discrete algorithms. This is the standard required algorithms course in a CS department, based on discrete math. The standard topics include: data structures, sorting, searching, graphs, dynamic programming, NP-completeness, approximations.

Logic algorithms. This body of algorithms lies at the intersection of mathematical logic and computer science, covering algorithms for satisfiability, theorem-proving, planning, verification, and model-checking.

Nonlinear continuous algorithms. This category uses the mathematical background of calculus and probability, and brings together common themes algorithms for applications like robotics, machine-learning, nonlinear optimization, and simulation of physical and man-made systems.

Linear (continuous) algorithms. The other side of the continuous domain consists of algorithms that based on linear algebra, and find application in areas such as computer vision, graphics, 3D modeling, linear optimization (LP), and information retrieval.

Other discrete algorithms. Finally, I'm sure I'm going annoy some colleagues by lumping together a number of algorithm topics into the unfortunately named "other" category. These include: parallel and distributed algorithms, network protocols, computational geometry and security. Each one of these, building on the foundation in the standard discrete algorithms course, could easily become a Discrete-Algorithms II course.

It's worth pointing out that some algorithms are hard to classify. For example, where does the famed Fast Fourier Transform (FFT) belong? In some ways the FFT is classically discrete because divide-and-conquer reduces the naive O(n²) DFT to the O(n log(n)) FFT. But at the same time, the application domain is signal processing, which suggests nonlinear-continuous as the appropriate category. I have put this in the standard course both because of the former reason and because ... who can resist the temptation of algorithms that process music?

Next, let's take a look at each of the latter four areas in more detail, and suggest some "next steps".

Logic algorithms

Logic is most often taught as a theory course in CS departments. Such a course starts with basic logic (truth tables, for example) and ends with theories of logic, incompletness and other great theorems in the field of computation and logic. At the same time, the applications of logic-based algorithms have grown in recent years. Unfortunately, there appears to be no single book that adequately covers this body of material that includes:

Satisfiability. There are now a slew of fast-heuristics for the classic SAT problem that go well-beyond the ancient and venerable DPLL algorithm. These newer techniques uses sophisticated data-structures and feature the all-important notion of conflict-directed clause-learning. As a result, whereas DPLL could barely handle a few hundred variables, modern SAT solvers can routinely solve problems with millions of variables. SAT solvers are now the core underlying technology for a variety of applications.

Theorem-proving. The goal of theorem-provers is to take a mathematical statement, some starting axioms, and try to find a proof for it by performing a giant search in the state-space of logic inferences. Naturally, there are strategies and there are complexities introduced by the mathematical domain of the theorems. Still, theorem-provers have had some success in discovering proofs for known mathematical conjectures.

Verification and model-checking If you build a software system, how do you know it is correct? That is, what's the guarantee that there isn't some weird input that will cause the system to crash or behave weirdly? This is no small matter for mission critical applications. For example, NASA does not want to send out a 10-year space probe only to have some silly C-programming error bring down the probe. So, one would like tools to automatically reason about programs - this is the goal of verification or model-checking. Some surprising gains have been made with tools like SPIN or SMV. This course would include the theory behind these tools.

Planning. The problem of planning in artificial intelligence has long received attention in the AI community. Planning and logic have much overlap, as the SAT-PLAN algorithm demonstrates. Indeed, knowledge in planning-systems is often represented using logic. Thus, a course on logic algorithms should cover this important topic.

Where to learn more? Unfortunately, there isn't yet a single book that adequately covers all of the above. Here are some books I've found:

Theory. A great starting book, nicely organized and complete with proofs is this one: A First Course in Logic: An Introduction to Model Theory, Proof Theory, Computability, and Complexity by S.Hedman.
Theory and algorithms The book that comes closest to lying at the intersection of algorithms and logic is the very readable book entitled Logic in Computer Science: Modelling and Reasoning about Systems by M.Huth and M.Ryan.
SAT-Plan and planning in general is covered as chapters in many intro AI texts, such as the popular one by Russell and Norvig.

Nonlinear continous algorithms

I find it fascinating that some of the most compelling applications of computer science today are completely absent from the standard curriculum. These applications include:

Machine-learning. Consider the problem of face-recognition: can you write an algorithm that takes as input images of faces and can accurately identify the person in the image? For example, Picasa has one - have you tried it? Other such example machine-learning problems include: handwriting-recognition (for tablet PCs), fingerprint identification (for law enforcement), voice recognition.

Robotics. How do you control a robot's motion? What predictive models can one use in robotics? How can you use noisy sensor data to help guide a robot? All these problems feature a combination of continuous math and some probability.

Simulation. How do you write a simulation, say, of vehicular traffic? How do you write a simulation of a factory or a manufacturing process?

Nonlinear optimization. Given a nonlinear function of n variables, how do you find the optimal values for the variables (to minimize or maximize the function)? Nonlinear optimization is the basis for many, many applications in economics, finance, engineering, and science.

In most universities, the above topics are usually offered as individual courses. In the CS undergrad curriculum, or even the Master's curriculum, there is no room to take all four. Seeing this, I put together a "foundation" course to cover these areas in a single course that mirrors our standard discrete algorithms course (which, incidentally, is also a hodge-podge of related topics).

Another reason for putting these ideas into a single course is that they help reinforcement fundamental ideas in continuous math, namely, calculus and probability. Just as discrete algorithms build on discrete math, so do continuous algorithms build on key concepts in calculus (such as gradients, integration) and probability (distributions, random variables).

Where to learn more?

Take the Continuous Algorithms course.
Machine-learning. To start, you could read through Machine Learning: An Algorithmic Perspective by S.Marsland. The longer-lived textbooks include the ones by Duda and Hart (Pattern Recognition) and the comprehensive text by Bishop (Pattern Recognition and Machine Learning). The latter two are not for the faint of (mathematical) heart.
Robotics. Unfortunately, there isn't yet a single book on robotics that covers both control, planning, and kinemetics. A good start but difficult read, however, is the free online book Planning Algorithms by S.LaValle. Principles of Robot Motion by H.Choset et al, and Probabilistic Robotics by S.Thrun et al are also good books.
Simulation. The book Discrete Event Simulation by Leemis and Park is a solid introduction to the discrete side of simulation. For the continuous side (simulating physical systems), see An Introduction to Computer Simulation Methods by H.Gould, J.Tobochnik, and W.Christian.
Optimization. This is a big topic. Indeed, some people say that the better way to teach optimization is to divide it into convex and non-convex optimization, and for that, there are a whole slew of books. Meanwhile, a solid introduction is provided in books like An Introduction to Optimization by E.K.P.Chong and S.H.Zak.
Numerical methods. The general area of algorithms for the continuous domain is huge, and includes the most ancient and classic category of numerical algorithms. Indeed, there are whole courses and books on this topic. A nice starter book that I found: Numerical Methods Using Matlab by J.H.Mathews and K.K.Fink. To get a high-level view of the field of numerical computing and applications as a whole, see The Nature of Mathematical Modeling by N.A.Gershenfeld.

Linear (continous) algorithms

Interestingly, from an algorithmic viewpoint, the continuousm domain appears to divide neatly into linear and nonlinear. In fact, this is also somewhat true in math departments, which usually teach a separate linear algebra course.

The compelling applications in computer science include:

Vision. As cameras get cheaper, computer vision is growing into a huge sub-field by itself, with vision infrastructures used in guidance, security, health, and biological research, for example. Many fundamental algorithms in vision and image processing start with a 2D array of pixels (the matrix) and apply operations to the matrix. These operations remove noise, detect edges, identify regions, and so on. And most involve matrix and vector operations, the foundation of linear algebra.

Graphics and 3D modeling. Graphics, it is said, is linear algebra on steroids. Indeed, any represention of a 3D world involves coordinates, geometrical objects and operations on those objects. Many of these are expressed in terms of vector and matrix operations. Now, this not entirely true because smooth surfaces in graphics are often represented using families of non-linear functions (think Bezier curves). Nonetheless, a great deal of basic 3D transformations are based on matrices.

Text processing and information retrieval. Linear algebra surprisingly shows up in the fundamental problem of text-retrival: given a query and a large collection of documents, identify the documents most relevant to the query. Techniques such as the Singular Value Decomposition (SVD), which is a foundational decomposition in linear algebra, have grown to play an important role in information retrieval.

Linear programming (LP). The linear version of the continuous optimization problem is still known by its old name: linear programming (which has nothing to do with our use of the term programming), or LP for short. LP is a classic and storied problem, for which the only viable algorithm for four decades was the exponential Simplex algorithm. Later, in the 1990's, Karmarkar's polynomial-time algorithm turned out to be effective for many LP problems. LP also plays a significant role in some combinatorial optimization problems such as TSP, offering the only reasonable way to find optimal solutions.

Where to learn more?

Take A computational introduction to linear algebra or see the books listed in that description.
Vision. An easy to read intro book: Computer Vision by L.G.Shapiro and G.C.Stockman.
Graphics and 3D modeling.
Text processing and information retrieval. An excellent source is the free on-line text on Information Retrieval C.D.Manning, P.Raghavan and H.Schütze.
Linear programming (LP). LP is covered in many standard algorithms textbooks, as a chapter. For a more rigorous, CS-centric exposition, see the excellent (and slim) text entitled Linear Programming by H.Karloff.

Other discrete algorithms

In this catch-all category we will place:

Parallel algorithms. In the old days, exquisitely complicated parallel machines were built that occupied large rooms and need special cooling. These days, a rack is sufficient (for a cluster) and shortly, your average processor chip is expected to come with multiple, perhaps 100s, of processor cores. Parallel computing will undoubtedly see a surge in applications. That said, it is not immediately obvious how to write a parallel algorithm that makes the best use of resources. For example, given n elements and p processors, should one divvy up the elements among the processors, sort in parallel and then merge? Or should some merging occur at earlier steps? Is there a fundamental limit to the parallelism possible? These questions form the basis of parallel computing. And of course, there's the hard programming problem - using conventional languages to write parallel programs.

Distributed algorithms and protocols. In contrast to parallel computing, distributed computing tries to address the question: can a collection of loosely connected computers (nodes) work together to achieve some kinds of tasks unique to disributed systems? For example, how can you generate consensus on time, so that all nodes agree to a common clock? How can you make this happen when some messages can get lost or face arbitrarily long delays? How do you store data across a distributed system? How do you communicate in ways that ensure messages reach? These questions drive the field of distributed computing and network protocols.

Security. At first glance, security appears to be about cryptography: how to encode text so that it's hard to decrypt without knowing the "key". But this turns out not to be true; security is much more than crytography. For example, how would you design a system to allow electronic payment so that neither the payer nor the recipient can deny the transaction took place? Security is obviously a hot topic now, and there isn't as yet a set of "standard" algorithms that every student must learn. Instead, there is the theory of public-key cryptography, which along with other primitives, is widely used to build higher-level protocols to address problems like the secure-payment one above.

Computational geometry. Given two geometric figures, each with m and n line-segments, how can you efficiently determine whether they intersect? Given a point and a polygon, is the point inside or outside? Given a set of (more than 4) points, what is the best sphere that approximately puts all points on the surface? These questions are typical in computational geometry, and have found various interesting applications.

All of the above topics are typically taught as individual courses in CS departments today. This is probably as it should be, because it's hard to see that there are any common principles that recommend a unifying course. Indeed, what's common is what was common earlier: discrete math. Thus, each of these could serve as a viable Discrete-Algorithms-II course.

Where to learn more:

Parallel algorithms. The book Algorithms: Sequential, Parallel, and Distributed by K.Berman and J.L.Paul covers all three topics areas.
Distributed algorithms and protocols. For distributed algorithms, see, for example, Distributed Algorithms by N.Lynch. For networks, see Computer Networks by J.Kurose and K.Ross.
Computational geometry. A good starting book is Computational Geometry in C by J.O'Rourke.