| This dissertation describes a number of novel parallel algorithms for solving maze-routing problems and string matching problems on a proposed reconfigurable mesh architecture.; Section I reviews the field of reconfigurable parallel computing. This includes an introduction to a number of reconfigurable architectures proposed in the literature and a list of references to the current literature on algorithms in the field of reconfigurable computing.; Section II presents a number of time-efficient algorithms to solve the maze-routing problem. Maze-routing algorithms are used in VLSI routing and robot path planning. In that section, definitions for absolute shortest path (ASP), shortest duplex-path (SDP), shortest triplex-path (STP), and single shortest path (SSP) are given. Then, O(1) algorithms are presented for: (i) testing the existence of specific types of paths, (ii) finding an ASP and a SDP. In addition, fast algorithms are presented for finding the STP and the SSP. The simulation results indicate that a large percentage of the shortest paths that exist between two randomly selected terminals fall into one of the categories studied in this section.; Section III presents a number of time-efficient algorithms to solve the exact string matching and approximate string matching problems. These problems received much attention over the years due to their importance on various areas such as, DNA sequencing, text comparison, and spelling correction. Especially with the introduction of search engines dealing with tremendous amount of information on the WWW, these problems deserve special attention and speed becomes a major issue. Given a text T of length n and a pattern P of length m, the first algorithm finds the exact matching between T and P in O(1) time. The second algorithm finds the approximate matching between T and P in O(k) time, where k is the maximum distance between T and P. The third algorithm considers only the replacement operation in the calculation of the edit distance and finds the approximate matching between T and P in O(1) time. |
