Algorithms are recipes for solving computational problems. In this course we will study fundamental algorithms for solving a variety of problems, including sorting, searching and graph algorithms. More importantly, we will focus on general design and analysis techniques that underlie these algorithms. For example, we will examine divide-and-conquer, dynamic programming, greediness, and probabilistic approaches. With an understanding of these techniques, you will be prepared to design some of your own algorithms.
Algorithms are judged not only by how well they solve a problem, but also by how effectively they use resources like time and space. We will learn techniques for analyzing time and space complexity of algorithms and will use these to evaluate tradeoffs between different algorithms. We will also see that problems can be organized into a hierarchy that measures their inherent difficulty by the efficiency of the best possible algorithm for solving them.
The prerequisite for this class is CS 102: Programming Languages - 2 with JAVA, CS 202: Data Structures and CS 103: Calculus - 1. You should feel comfortable with simple data structures (arrays, lists, trees, stacks and queues) as well as recursion. You should also feel comfortable with basic calculus concepts such as limits and derivatives.
In addition you should be prepared to learn some new mathematical techniques. In order to analyze algorithms, we'll need to use some mathematical methods that may be new to you. We will learn these methods in class, and they are also explained well in the textbook.
- Teacher: Nurlan Shaidullaev