Given a list of descriptions of all of the buildings in Manhattan, how could you effectively produce a description of the Manhattan skyline as seen from a boat on the East River? Or, suppose that for all of the towns in the U.S., you have information on all of the roads that connect them. How would you determine the shortest route between any two of the towns? The most obvious ways of solving these problems turn out to be very inefficient. This course is concerned with investigating methods of designing efficient and reliable algorithms to solve these and other computational problems. By carefully analyzing the underlying structure of the problem to be solved it is often possible to dramatically decrease the resources (amount of time and/or space) needed to find a solution. Through this analysis we can also give proof that an algorithm will perform correctly and determine its running time and space requirements. We will present several algorithm design strategies that build on data structures and programming techniques introduced in Computer Science 136. These include: induction, divide-and-conquer, dynamic programming, and greedy algorithms. Particular topics to be considered will include shortest path and other network problems; problems in computational geometry; searching, sorting and order statistics and some advanced data structures such as balanced binary search trees, heaps, and union-find structures. In addition, an introduction to complexity theory and the complexity classes P and NP will be provided. As time permits, additional topics such as probabilistic and parallel algorithms will be studied. Evaluation will be based primarily on problem assignments, programs, and exams. Prerequisites: Computer Science 136 and Mathematics 251.

Hour: BRUCE