Wyniki wyszukiwania - BazTech

1

External Memory Algorithms for String Problems

Roh K., Crochemore M., Iliopoulos C.S., Park K.

Fundamenta Informaticae

|

2008

|

Vol. 84, nr 1

17-32

EN

In this paper we present external memory algorithms for some string problems. External memory algorithms have been developed in many research areas, as the speed gap between fast internal memory and slow external memory continues to grow. The goal of external memory algorithms is to minimize the number of input/output operations between internal memory and external memory. These years the sizes of strings such as DNA sequences are rapidly increasing. However, external memory algorithms have been developed for only a few string problems. In this paper we consider five string problems and present external memory algorithms for them. They are the problems of finding the maximum suffix, string matching, period finding, Lyndon decomposition, and finding the minimum of a circular string. Every algorithm that we present here runs in a linear number of I/Os in the external memory model with one disk, and they run in an optimal number of disk I/Os in the external memory model with multiple disks.

2

An Improved Boolean Circuit for Maximum Matching in a Convex Bipartite Graph

Park E., Park K.

Fundamenta Informaticae

|

2008

|

Vol. 84, nr 1

81-97

EN

The Boolean circuit is a simple and realistic model for parallel computation. Chung and Lee considered the problem of finding a maximum matching in a convex bipartite graph, which has two sets of vertices, A and B, such that for any vertex v of A, the neighbors of v in B are contiguous. They gave a Boolean circuit for the problem in O(log2 n +lognźloglognźlogb) depth and O(bn3) size, where n is the number of vertices in set A of the convex bipartite graph and b is the number of bits representing a vertex. Using Boolean circuits of prefix computation, odd-even merge, and some other parallel techniques, we present an improved Boolean circuit for the same problem in O(log2nź(logb+loglogn)) depth and O(bn2logn) size.

3

Microstructural characterization and mechanical properties of Mg-xSn-Al-Zn alloys

Kim B., Jeon J., Park K., Park B., Park Y., Park I.

Archives of Materials Science and Engineering

|

2008

|

Vol. 30, nr 2

93-96

EN

Purpose: In this study, the microstructure and mechanical properties of as-cast Mg-xSn-Al-Zn alloys were investigated. Design/methodology/approach: Ingot was fabricated by a squeeze cast. The alloys were induction melted at 750stopniC in a mild steel crucible under CO2+2%SF6 mixed gas atmosphere and cast into a permanent mould coated with boron nitride spray held at approximately 350 stopniC . Tensile tests were carried out at room temperature in a screw-driven tensile testing machine and crosshead speed was 0.2 mm/min. Microstructural observation was carried out using a optical microscope (OM) and a scanning electron microscope (SEM) equipped with energy dispersive X-ray spectrometer (EDS). Findings: It is found that the tensile strength and elongation decreased at room temperature increased with Sn concentration. As a consequence, 5wt% Sn addition was the one exhibiting the best tensile properties at room temperature. The micro-hardness of the alloy continuously increased with increasing the Sn concentration. Practical implications: The investigations of microstructure of commercially magnesium alloys are important for achieving desired mechanical behaviour of the material. Originality/value: The fracture behaviors of magnesium alloys are investigated.

4

A Simple and Scalable Algorithm for the IP Address Lookup Problem

Lee I., Park K., Choi Y., Chung S.K.

Fundamenta Informaticae

|

2003

|

Vol. 56, nr 1,2

181-190

EN

The IP address lookup problem is to find the longest matching IP prefix from a routing table for a given IP address and it has been a central bottleneck in speeding up the Internet. In this paper we propose a new algorithm for this problem based on the segment tree data structure. Given n IP prefixes, our algorithm does the IP address lookup in O(logn) time. It also handles the insertion and deletion of IP prefixes efficiently without rebuilding the whole data structure.