Browsing by Author "LEE, RCT"

Now showing 1 - 19 of 19

A NEW PARALLEL SORTING ALGORITHM BASED UPON MIN-MID-MAX OPERATIONS
(1984-01-01)
TSENG, SS
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
A NEW PARALLEL SORTING ALGORITHM BASED UPON MIN-MID-MAX OPERATIONS
(1984-01-01)
TSENG, SS
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
A PARALLEL ALGORITHM FOR FINDING CONGRUENT REGIONS
(1990-02-01)
SHIH, ZC
;
LEE, RCT
;
YANG, SN
;
資訊工程學系
;
Department of Computer Science
A PARALLEL ALGORITHM TO SOLVE THE STABLE MARRIAGE PROBLEM
(1984)
TSENG, SS
;
LEE, RCT
;
工學院
;
資訊工程學系
;
College of Engineering
A PARALLEL SORTING SCHEME WHOSE BASIC OPERATION SORTS N ELEMENTS
(1985-12-01)
TSENG, SS
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
A SYSTOLIC ALGORITHM FOR EXTRACTING REGIONS FROM A PLANAR GRAPH
(1989-08-01)
SHIH, ZC
;
LEE, RCT
;
YANG, SN
;
資訊工程學系
;
Department of Computer Science
AMORTIZED ANALYSIS OF SOME DISK SCHEDULING ALGORITHMS - SSTF, SCAN, AND N-STEP SCAN
(1992)
CHEN, TS
;
YANG, WP
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
The amortized analysis is a useful tool for analyzing the time-complexity of performing a sequence of operations. The disk scheduling problem involves a sequence of requests in general. In this paper, the performances of representative disk scheduling algorithms, SSTF, SCAN, and N-StepSCAN, are analyzed in the amortized sense. A lower bound of the amortized complexity for the disk scheduling problem is also derived. According to our analysis, SCAN is not only better than SSTF and N-StepSCAN, but also an optimal algorithm. Various authors have studied the disk scheduling problem based on some probability models and concluded that the most acceptable performance is obtained from SCAN. Our result therefore supports their conclusion.
AN O(N LOG N) MINIMAL SPANNING TREE ALGORITHM FOR N-POINTS IN THE PLANE
(1986)
CHANG, RC
;
LEE, RCT
;
交大名義發表
;
National Chiao Tung University
MINIMUM RECTANGULAR PARTITION PROBLEM FOR SIMPLE RECTILINEAR POLYGONS
(1990-07-01)
LIOU, WT
;
TAN, JJM
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
ON THE AVERAGE LENGTH OF DELAUNAY TRIANGULATIONS
(1984)
CHANG, RC
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
OPTIMAL SPEEDING UP OF PARALLEL ALGORITHMS BASED UPON THE DIVIDE-AND-CONQUER STRATEGY
(1984)
TANG, CY
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
PASSWORD AUTHENTICATION USING NEWTON INTERPOLATING POLYNOMIALS
(1991)
LIN, CH
;
CHANG, CC
;
WU, TC
;
LEE, RCT
;
資訊科學與工程研究所
A password authentication mechanism based upon Newton's interpolating polynomial and a strong cryptographic operation such as DES (data encryption standard) is proposed in this paper. The mechanism can respond to any login request very efficiently. It is suitable for real-time applications and can be implemented in microcomputer system. With the properties of Newton's interpolating polynomial, high system performance can be achieved. The basic idea of our method is that users in the system are congregated together. Any illegal modification by an intruder to some user's parameter on the host tables will influence the others and can be easily detected. However, legitimate modification of password could be made efficiently.
PERFORMANCE ANALYSES OF CARTESIAN PRODUCT FILES AND RANDOM FILES
(1984)
CHANG, CC
;
DU, MW
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
SPECIAL SUBGRAPHS OF WEIGHTED VISIBILITY GRAPHS
(1992-08-24)
HSU, FR
;
LEE, RCT
;
CHANG, RC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
SYMBOLIC GRAY CODE AS A PERFECT MULTIATTRIBUTE HASHING SCHEME FOR PARTIAL MATCH QUERIES
(1982)
CHANG, CC
;
LEE, RCT
;
DU, MW
;
資訊工程學系
;
Department of Computer Science
THE AVERAGE PERFORMANCE ANALYSIS OF A CLOSEST-PAIR ALGORITHM
(1984)
CHANG, RC
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
THE HIERARCHICAL ORDERING IN MULTIATTRIBUTE FILES
(1983)
CHANG, CC
;
DU, MW
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
THE SEARCHING OVER SEPARATORS STRATEGY TO SOLVE SOME NP-HARD PROBLEMS IN SUBEXPONENTIAL TIME
(1993-04-01)
HWANG, RZ
;
CHANG, RC
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
In this paper we propose a new strategy for designing algorithms, called the searching over separators strategy. Suppose that we have a problem where the divide-and-conquer strategy can not be applied directly. Yet, also suppose that in an optimal solution to this problem, there exists a separator which divides the input points into two parts, A(d) and C(d), in such a way that after solving these two subproblems with A(d) and C(d) as inputs, respectively, we can merge the respective subsolutions into an optimal solution. Let us further assume that this problem is an optimization problem. In this case our searching over separators strategy will use a separator generator to generate all possible separators. For each separator, the problem is solved by the divide-and-conquer strategy. If the separator generator is guaranteed to generate the desired separator existing in an optimal solution, our searching over separators strategy will always produce an optimal solution. The performance of our approach will critically depend upon the performance of the separator generator. It will perform well if the total number of separators generated is relatively small. We apply this approach to solve the discrete Euclidean P-median problem (DEPM), the discrete Euclidean P-center problem (DEPC), the Euclidean P-center problem (EPC), and the Euclidean traveling salesperson problem (ETSP). We propose O(n(o(square-root P))) algorithms for the DEPM problem, the DEPC problem, and the EPC problem, and we propose an O(n(o(square-root n))) algorithm for the ETSP problem, where n is the number of input points.
THE SLAB DIVIDING APPROACH TO SOLVE THE EUCLIDEAN P-CENTER PROBLEM
(1993-01-01)
HWANG, RZ
;
LEE, RCT
;
CHANG, RC
;
資訊工程學系
;
Department of Computer Science
Given n demand points on the plane, the Euclidean P-Center problem is to find P supply points, such that the longest distance between each demand point and its closest supply point is minimized. The time complexity of the most efficient algorithm, up to now, is 0(n2P-1 . log n). In this paper, we present an algorithm with time complexity 0(n0(square-root P))).