This course provides a comprehensive introduction to the modern study of computer algorithms.
As Donald Knuth, one of the most prominent computer scientists of our time put it:
| It has often been said that a person does not really understand something until after teaching it to someone else. Actually, a person does not really understand something until after teaching it to a computer, i.e., expressing it as an algorithm...An attempt to formalize [problems] as algorithms leads to a much deeper understanding than if we simply try to comprehend things in the traditional way. |
This course will focus on the design of algorithms, usually with the goal of bounding worst-case running time in terms of the input size.
Computer programs would not exist without algorithms, they are the cornerstone of computer science. Specific algorithm design techniques can be interpreted as problem-solving strategies that are useful regardless of whether a computer is involved in the solution. Many students are surprised to discover that this course does not include a programming component at all. Since we will not be programming in this course, how do we know if the algorithms we create will actually work? The answer lies in the mathematical analysis of algorithms. Using mathematical proof techniques, we can prove, as no implementation can, that an algorithm is actually correct (i.e., it produces the claimed output for the given input), and that the algorithm will finish after executing a certain number of steps. We will learn how to describe the upper bounds on the running time of algorithms and we will see that no algorithm exists to solve a problem faster than its proven lower bound. You will learn that many common algorithms have running time that is polynomially-bounded and that there exist intractable problems for which no polynomial time solution is known. For these intractable problems, we will look at approximation algorithms that can offer near-optimal solutions in polynomial time. Brute-force, divide-and-conquer, greedy, and dynamic programming techniques will be studied in the context of trees, graphs, matrices and other well-known data structures.
The course begins by covering mathematical preliminaries such as proving the correctness of some well-known algorithms using induction on loop invariants. We will use the RAM model of computation, in which instructions are processed sequentially, as well as the convenience of asymptotic (i.e., big-Oh) notation to compare the efficiency of various algorithms. Techniques for the mathematical analysis of both nonrecursive and recursive algorithms will be covered early on. Later, we will consider classes of problems, known as P (those problems solvable in polynomial time) and NP (those problems for which no polynomial-time solution is known, but for which a solution can be verified in polynomial time), and use a proof technique called reduction to prove a problem is in NP.
Useful Links