SCS Undergraduate Thesis Topics
|Ian Huang||Guy Blelloch||Cache Efficient Dynamic Programming Algorithms|
Parallel dynamic programing algorithms typically have undesirable I/O complexities. We studied solutions to two different problems which are representative of many problems with dynamic programming solutions. One is Local Alignment, which has a constant number of dependencies. We studied multiple algorithms and implemented some in C++ and Cilk+. We also analyzed the algorithms from a theoretical and practical standpoint, and then compared it to other dynamic programming algorithms for solving Local Alignment. The other is Optimal Binary Search Trees which contains problems with varying numbers of dependencies. For this problem, we designed and implemented a cache efficient dynamic programing algorithm using a divide and conquer technique. We also analyzed the algorithm theoretically and practically. Our algorithm has the same work complexity as current dynamic programming algorithms, but lower I/O complexity.