Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | LIN, CJ | en_US |
dc.date.accessioned | 2014-12-08T15:04:13Z | - |
dc.date.available | 2014-12-08T15:04:13Z | - |
dc.date.issued | 1994-01-01 | en_US |
dc.identifier.issn | 0898-1221 | en_US |
dc.identifier.uri | http://hdl.handle.net/11536/2718 | - |
dc.description.abstract | We present a formal systolic algorithm to solve the dynamic programming problem for an optimal binary search tree. For a fixed integer j such that 2 less-than-or-equal-to j less-than-or-equal-to n, first we derive a linear systolic array to evaluate the minimal cost c(i,j) for 1 less-than-or-equal-to i < j. Then we combine these (n - 1) linear systolic arrays to form a two-dimensional systolic array. The computational model consists of inverted right perpendicular (n2 + 2n - 4)/4 inverted left perpendicular processing elements. The algorithm requires (2n - 3) time steps to solve this problem. The elapsed time within a time step is independent of the problem size n. It is suitable for the VLSI implementation due to the identical and simple structure of processing elements. We also prove the correctness of this algorithm by induction. | en_US |
dc.language.iso | en_US | en_US |
dc.title | A SYSTOLIC ALGORITHM FOR DYNAMIC-PROGRAMMING | en_US |
dc.type | Article | en_US |
dc.identifier.journal | COMPUTERS & MATHEMATICS WITH APPLICATIONS | en_US |
dc.citation.volume | 27 | en_US |
dc.citation.issue | 1 | en_US |
dc.citation.spage | 1 | en_US |
dc.citation.epage | 10 | en_US |
dc.contributor.department | 交大名義發表 | zh_TW |
dc.contributor.department | 應用數學系 | zh_TW |
dc.contributor.department | National Chiao Tung University | en_US |
dc.contributor.department | Department of Applied Mathematics | en_US |
dc.identifier.wosnumber | WOS:A1994MJ43100001 | - |
dc.citation.woscount | 2 | - |
Appears in Collections: | Articles |
Files in This Item:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.