Browsing by Author "CHIEN, BC"

Now showing 1 - 5 of 5

ANALYSIS OF THE MULTIGROUP METHOD FOR MANIPULATING MULTIPLE STACKS
(1993-02-01)
CHIEN, BC
;
CHEN, RJ
;
YANG, WP
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
The multiple stacks problem is that a number of stacks have to be manipulated in a finite continuous memory, simultaneously. Many applications need the support of multiple stacks, e.g., the parallel computing with shared memory. There are two approaches mentioned in [1] for manipulating multiple stacks. In this paper, we present and analyze the Multigroup method which combines the concept of coexisting. By the concept of coexisting, storage sharing in a linear data structure is possible. We show that the new method has better performance than the two previous approaches, and improves the extra manipulating time.
COMPETITIVE ANALYSIS OF THE ONLINE ALGORITHMS FOR MULTIPLE STACKS SYSTEMS
(1992-01-01)
CHIEN, BC
;
CHEN, RJ
;
YANG, WP
;
資訊工程學系
;
資訊科學與工程研究所
An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. A competitive algorithm is an on-line algorithm whose cost is bounded by the cost of any other algorithm, even the algorithm is an optimal off-line algorithm, multipling a constant. This paper discusses the algorithms used to manipulate the multiple stacks problem, which is one of the on-line problems. We find the optimal off-line algorithm first, then show that the Knuth's algorithm is not a competitive algorithm, but Garwick's algorithm is competitive when the number Of stacks n is 2. Furthermore the competitive ratio found here is a low bound if the Garwick's algorithm is also & competitive algorithm for n greater-than-or-equal-to 3.
COMPETITIVE ANALYSIS OF THE ONLINE ALGORITHMS FOR MULTIPLE STACKS SYSTEMS
(1992)
CHIEN, BC
;
CHEN, RJ
;
YANG, WP
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. A competitive algorithm is an on-line algorithm whose cost is bounded by the cost of any other algorithm, even the algorithm is an optimal off-line algorithm, multipling a constant. This paper discusses the algorithms used to manipulate the multiple stacks problem, which is one of the on-line problems. We find the optimal off-line algorithm first, then show that the Knuth's algorithm is not a competitive algorithm, but Garwick's algorithm is competitive when the number Of stacks n is 2. Furthermore the competitive ratio found here is a low bound if the Garwick's algorithm is also & competitive algorithm for n greater-than-or-equal-to 3.
MANIPULATING MULTIPLE STACKS WITH ORDERED-HEAP
(1993-08-15)
CHIEN, BC
;
YANG, WP
;
CHEN, RJ
;
資訊工程學系
;
Department of Computer Science
A new method for manipulating multiple stacks based on dynamic data structure is proposed in this paper. A simple data structure called ordered-heap is developed, in which nodes are preserved as a heap, and kept inorder traversal sequence remains unchanged. By employing ordered-heap to a multiple-stacks environment, it is easy and efficient to simultaneously handle several variable-size stacks in a sequential memory area. Our experiments show that not only the total number of item movements in the proposed method is much smaller than in the previous methods, but also the overhead for maintaining data structure in the proposed method is kept within a reasonable range.
THE WORST CASE ANALYSIS OF ALGORITHM ON MULTIPLE STACKS MANIPULATION
(1992-11-19)
CHIEN, BC
;
YANG, WP
;
資訊工程學系
;
Department of Computer Science