 |
 |
Joint CMU-Pitt Ph.D. Program in Computational Biology
Robert F. Murphy and Ivet Bahar, Directors
Curriculum - Core Course - Algorithms
CMU 15-750 Algorithms [Course web page]
This is a graduate course in the design and (mathematical) analysis of algorithms. Our goal is to understand in depth the methods and ideas previously seen in undergraduate Data Structures and Algorithms courses -- to the point where one can use these ideas to do cutting-edge research.
The course will give numerous case studies, each consisting of: 1. A crisp well-defined computational problem. 2. A model of computation, including a clear definition for what constitutes a STEP of computation in the model. 3. One or more algorithms for solving the given computational problem. 4. Analysis of each algorithm ie. a count of the number of steps each algorithm takes.
We hone tools from undergraduate algorithms and data structures for designing efficient algorithms, including: *greedy *divide-and-conquer *dynamic programming *network flow *linear programming and *randomization. We develop new tools such as *Lattice Reduction *Semi-Definite Programming and *Probabilistic Method. In addition, we forge tools for deciding whether or not a computational problem can be solved efficiently. These tools include the Theory of NP-completeness, which you saw as an undergraduate, and methods from complexity theory, which you did not.
|
|
|