How do computers solve problems?
In the past two years, you have learned to express increasingly sophisticated thought processes as programs. But as complex as your programs have been, the problems they solve have been relatively simple. The solutions are straightforward: the hard part is thinking clearly enough to express these straightforward processes precisely.
This year, in contrast, we will tackle problems whose solutions are far from obvious. How does a GPS calculate the optimal route, among billions of possibilities? How does Commonwealth assign students to courses (and courses to days and periods), so that the maximum number of student requests are satisfied? How does a hospital residency program match residents with hospitals, taking into account mutual preferences? How should resources be allocated to programs running simultaneously on your computer? How do we solve a maze, or a Sudoku puzzle? How can you design new algorithms to tackle real-world problems you encounter?
As the course title suggests, our study with proceed in two phases:
Data structures. Much of efficient problem solving is choosing how to represent information. We will begin the year by developing an encyclopedia of data representation tools and analyzing their strengths and weaknesses. We will think much more concretely this year than in the past about how data is arranged physically in memory, and what implications this has for the running times and memory efficiency of our programs.
Algorithm design. Once we have our basic data structures down, we will turn to the study of algorithm design. We will study classic algorithms in computer science, with two goals: first, to understand general patterns in algorithm design, and second, because they are useful starting off points for tackling new, slightly different problems.
By the end of this course, you should be able to examine a non-trivial problem and design appropriate data structures and algorithms for solving it.