Jeremy T. Fineman
Provost's Distinguished Associate ProfessorWagner Term Chair in Computer Science
Department of Computer Science
Georgetown University
Jeremy T. FinemanProvost's Distinguished Associate ProfessorWagner Term Chair in Computer Science Department of Computer Science Georgetown University |
|
This course explores various techniques used in the design and analysis of computer algorithms. Starting with the divide-and-conquer technique, the course covers various general approaches such as the greedy method and dynamic programming. Depending on time, various examples from the following problem domains will be considered: sorting, graph theory, shortest path, max-flow, matching, FFT, data compression, cryptography, and computational geometry. The notions of NP-completeness and computability may also be introduced.
This introductory graduate course explores the design and analysis of efficient algorithms. Topics covered include divide-and-conquer, greedy algorithms, and dynamic programming as well as more advanced topics like amortization, randomization, linear programming, memory-efficient algorithms, online algorithms, and approximation algorithms. Specific problem domains are subject to change but may include string algorithms, computational geometry, graph algorithms, combinatorial optimization, number theory, and computational sciences. Although there is some limited overlap of material, this course is not a replacement for an undergraduate algorithms course and hence assumes some basic understanding of algorithm analysis and discrete mathematics.
This course covers major theoretical results in data structures, including classic results as well as current research and open problems. The specific data structures covered are subject to change. Likely topics include: comparison-based search data structures, faster data structures on integers, data structures for dynamic graph problems, self adjusting data structures, data structures for geometric problems, external-memory and cache-oblivious data structures, and persistent data structures. One common analysis technique used throughout the course is amortization.
The main focus of this course is on parallel algorithms, but we will also briefly cover programming models and cache-coherence. The lectures primarily address design and analysis of algorithms, but there will also be one or two programming assignment(s) to illustrate some of the engineering issues. This course comprises two main units. The first unit is lecture based and intended to provide a background on parallel computing, focusing on some classic and recent results in parallel algorithms. The second unit is more research-centric, based around reading and presenting research papers. Most papers will be presented by students, but depending on enrollment and time, some may also be presented by me. There will also be an end-of-term project which may be systems or theory (students' choice).