CSSE Seminar Series (CSSESS)
Welcome to the web page describing past, present, and future seminars presented by staff, students, and visitors to the Department of Computer Science and Software Engineering.
View past or future seminars; or view the CSSESS Home Page.
Seminar
The problem of maximum sum and K maximum sums and their VLSI solutions.
Speaker: Sung E Bae.
Institute: CSSE, UC.
Time/Place: 10:00 AM, Wed, 10 Dec, in Room 031, Erskine Building.
Abstract
Given an array of positive and negative values, we consider the problem of maximum sum. It is known that within the framework of sequential algorithms the maximum subarray problem can be solved in O(n3) time with an iterative approach and O(n^{3}(log{log{n}}/log{n})^{1/2} time with a divide-and-conquer approach.
Parallel algorithms for this problem are available, but they usually exploit the most relaxed, flexible architecture with a shared-memory. A VLSI implementation is an option to consider: VLSI circuits do not offer a shared memory and only allow very limited connection between nodes. If one can design an optimal algorithm despite these constraints, it is one of the most cost-effective ways of taking advantage of parallelism.
We managed to design a VLSI algorithm whose time is O(n) with the circuit size of O(n^{2}} based on the iterative approach. The problem of K maximum sums is a generalisation of the former problem. When an overlapping property needs to be observed, previous algorithms for the maximum sum are not directly applicable. We designed an O(K*n) algorithm for the K maximum subsequences problem, which was then modified to solve the K maximum subarrays problem in O(K*n^{3}) time.
Finally, we present a VLSI K maximum subarrays algorithm with O(K*n) steps and a circuit size of O(n^{2}). Note that both are cost-optimal in parallelisation of the sequential algorithms.
Biography
CSSE Masters' student.
View past or future seminars; or view the CSSESS Home Page.