No description available.

Ternary Content Addressable Memory or in short TCAM is a special type of memory that can execute a certain set of operations in parallel on all of its words. Because of power consumption and relatively small storage capacity, it has only been used in special environments. Over the past few years its cost has been reduced and its storage capacity has increased signifi cantly and these exponential trends are continuing. Hence it can be used in more general environments for larger problems. In this research we study how to exploit its computational power in order to speed up fundamental problems and needless to say that we barely scratched the surface. The main problems that has been addressed in our research are namely Boolean matrix multiplication, approximate subset queries using bloom filters, Fixed universe priority queues and network flow classi cation. For Boolean matrix multiplication our simple algorithm has a run time of O (d(N^2)/w) where N is the size of the square matrices, w is the number of bits in each word of TCAM and d is the maximum number of ones in a row of one of the matrices. For the Fixed universe priority queue problems we propose two data structures one with constant time complexity and space of O((1/ε)n(U^ε)) and the other one in linear space and amortized time complexity of O((lg lg U)/(lg lg lg U)) which beats the best possible data structure in the RAM model namely Y-fast trees. Considering each word of TCAM as a bloom filter, we modify the hash functions of the bloom filter and propose a data structure which can use the information capacity of each word of TCAM more efi ciently by using the co-occurrence probability of possible members. And finally in the last chapter we propose a novel technique for network flow classi fication using TCAM.

Thesis (M. Phil.)--University of Hong Kong, 1997. / Includes bibliographical references (leaf 83-84).

Thesis (Ph. D.)--University of Washington, 2005. / Vita. Includes bibliographical references (p. 155-165).

We perform an Integrated complexity analysis on a number of combinatorial problems arising from the field of computational biology. The classic framework of NP-completeness, algorithmic design techniques for bounded width graphs, and parameterized computational complexity together provide a clear and detailed map of the intrinsic hardness of the following problems: INTERVALIZING COLORED GRAPHS and SHORTEST COMMON SUPERSEQUENCE. The fundamental concern of parameterized complexity is the apparent qualitative difference in algorithmic behaviour displayed by many problems when one or more input parameters are bounded. For many problems, only a small range of values for these parameters capture most instances arising in practice. This is certainly the case in computational biology in several specific arenas such as DNA physical mapping or multiple sequence alignment. At its most general level, parameterized complexity partitions problems into two classes: fixed parameter tractable (FPT) and fixed parameter intractable (hard for classes of the W-hierarchy.) The former indicates that the particular parameterization may allow for efficient practical algorithms whilst the latter indicates the parameterization is not effective (asymptotically) in alleviating the intractability. The problem INTERVALIZING COLORED GRAPHS (ICG) models in a straightforward albeit limited way the determination of contig assemblies in the mapping of DNA. We show ICG to be NP-complete (no polynomial time algorithm unless P=NP), not finite-state (a very general algorithmic design technique for bounded width graphs fails), and hard for the parameterized complexity class W[1] (a specific parameterized version of ICG does not admit an efficient algorithm unless many other well-known - and apparently hard - problems admit efficient algorithms). Both SHORTEST COMMON SUPERSEQUENCE and its sister problem LONGEST COMMON SUBSEQUENCE have applications in multiple sequence alignment. We show that SHORTEST COMMON SUPERSEQUENCE PARAMETERIZED BY THE NUMBER OF INPUT STRINGS AND THE SIZE OF THE ALPHABET is hard for complexity class W[1]. As is the case with ICG, this implies that it does not admit efficient algorithms unless some unlikely computational complexity collapses occur. / Graduate

Keywords: entanglement, complexity, entropy, measurement In chapter 1 the basic principles of communication complexity are introduced. Two-party communication is described explicitly, and multi-party communication complexity is described in terms of the two-party communication complexity model. The relation to entropy is described for the classical communication model. Important concepts from quantum mechanics are introduced. More advanced concepts, for example the generalized measurement, are then presented in detail. In chapter 2 the di erent measures of entanglement are described in detail, and concrete examples are provided. Measures for both pure states and mixed states are described in detail. Some results for the Schmidt decomposition are derived for applications in communication complexity. The Schmidt decomposition is fundamental in quantum communication and computation, and thus is presented in considerable detail. Important concepts such as positive maps and entanglement witnesses are discussed with examples. Finally, in chapter 3, the communication complexity model for quantum communication is described. A number of examples are presented to illustrate the advantages of quantum communication in the communication complexity scenario. This includes communication by teleportation, and dense coding using entanglement. A few problems, such as the Deutsch-Jozsa problem, are worked out in detail to illustrate the advantages of quantum communication. The communication complexity of sampling establishes some relationships between communication complexity, the Schmidt rank and entropy. The last topic is coherent communication complexity, which places communication complexity completely in the domain of quantum computation. An important lower bound for the coherent communication complexity in terms of the Schmidt rank is dervived. This result is the quantum analogue to the log rank lower bound in classical communication complexity. / Prof. W.H. Steeb

by Chi-lok Chan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1994. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Scheduling Problems of Chain-like Task System --- p.4 / Chapter 2.1 --- Introduction --- p.4 / Chapter 2.2 --- Problem Assumptions and Notations Definition --- p.7 / Chapter 2.3 --- Related Works --- p.9 / Chapter 2.3.1 --- Bokhari's Algorithm --- p.10 / Chapter 2.3.2 --- Sheu and Chiang's Algorithm --- p.12 / Chapter 2.3.3 --- Hsu's Algorithm --- p.12 / Chapter 2.4 --- Decision Algorithms for Un-mergeable Task System --- p.18 / Chapter 2.4.1 --- Feasible Length-K Schedule --- p.18 / Chapter 2.4.2 --- Generalized Decision Test --- p.23 / Chapter 2.5 --- Dominated and Non-dominated Task Systems --- p.26 / Chapter 2.5.1 --- Algorithm for Dominated Task System --- p.26 / Chapter 2.5.2 --- Property of Non-dominated Task System --- p.27 / Chapter 2.6 --- A Searching-Based Algorithm for the Optimization Problem --- p.28 / Chapter 2.6.1 --- Algorithm --- p.29 / Chapter 2.6.2 --- Complexity Analysis --- p.31 / Chapter 2.7 --- A Searching Algorithm Based on a Sorted Matrix --- p.33 / Chapter 2.7.1 --- Sorted Matrix --- p.33 / Chapter 2.7.2 --- Algorithm for the Optimization Problem --- p.35 / Chapter 2.7.3 --- Complexity Analysis --- p.40 / Chapter 2.8 --- A Constructive Algorithm for the Optimization Problem --- p.43 / Chapter 2.9 --- A Modified Constructive Algorithm --- p.46 / Chapter 2.9.1 --- Algorithm --- p.46 / Chapter 2.9.2 --- Worst-Case Analysis --- p.50 / Chapter 2.9.3 --- Sufficient Condition for Efficient Algorithm H --- p.58 / Chapter 2.9.4 --- Average-Case Analysis --- p.62 / Chapter 2.10 --- Performance Evaluation --- p.65 / Chapter 2.10.1 --- Optimal Schedule --- p.65 / Chapter 2.10.2 --- Space Complexity Analysis --- p.67 / Chapter 2.10.3 --- Time Complexity Analysis --- p.68 / Chapter 2.10.4 --- Simulation of Algorithm F and Algorithm H --- p.70 / Chapter 2.11 --- Conclusion --- p.74 / Chapter 3 --- Vehicle Scheduling Problems with Time Window Constraints --- p.77 / Chapter 3.1 --- Introduction --- p.77 / Chapter 3.2 --- Problem Formulation and Notations --- p.79 / Chapter 3.3 --- NP-hardness of VSP-WINDOW-SLP --- p.83 / Chapter 3.3.1 --- A Transformation from PARTITION --- p.83 / Chapter 3.3.2 --- Intuitive Idea of the Reduction --- p.85 / Chapter 3.3.3 --- NP-completeness Proof --- p.87 / Chapter 3.4 --- Polynomial Time Algorithm for the VSP-WINDOW on a Straight Line with Common Ready Time --- p.98 / Chapter 3.5 --- Strong NP-hardness of VSP-WINDOW-TREEP --- p.106 / Chapter 3.5.1 --- A Transformation from 3-PARTITION --- p.107 / Chapter 3.5.2 --- NP-completeness Proof --- p.107 / Chapter 3.6 --- Conclusion --- p.111 / Chapter 4 --- Conclusion --- p.115 / Bibliography --- p.119

A Boolean matrix is a matrix with elements from the Boolean semiring ({0, 1}, +, x), where the addition and multiplication are as usual with the exception that 1 + 1 = 1. In this thesis we study eight classes of monoids whose elements are Boolean matrices. Green's relations are five equivalence relations and three pre-orders which are defined on an arbitrary monoid M and describe much of its structure. In the monoids we consider the equivalence relations are uninteresting - and in most cases completely trivial - but the pre-orders are not and play a vital part in understanding the structure of the monoids. Each of the three pre-orders in each of the eight classes of monoids can be viewed as a computational decision problem: given two elements of the monoid, are they related by the pre-order? The main focus of this thesis is determining the computational complexity of each of these twenty-four decision problems, which we successfully do for all but one.

Yang, Lin. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 57-61). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Problems and Main Results --- p.2 / Chapter 1.1.1 --- Firefighting on Trees --- p.2 / Chapter 1.1.2 --- Maximum k-Vertex Cover on Trees --- p.3 / Chapter 1.2 --- Background --- p.3 / Chapter 1.2.1 --- Random Separation --- p.4 / Chapter 1.2.2 --- Kernelization --- p.5 / Chapter 1.2.3 --- Infeasibility of Polynomial Kernel --- p.6 / Chapter 1.3 --- Organization of the Thesis --- p.7 / Chapter 2 --- Firefighting on Trees --- p.9 / Chapter 2.1 --- Definitions and Notation --- p.10 / Chapter 2.2 --- FPT Algorithms --- p.13 / Chapter 2.2.1 --- Saving k Vertices --- p.14 / Chapter 2.2.2 --- Saving k Leaves --- p.19 / Chapter 2.2.3 --- Protecting k Vertices --- p.23 / Chapter 2.3 --- Approximation --- p.29 / Chapter 2.3.1 --- A (1 ´ؤ 1/e)-Approximation Algorithm --- p.29 / Chapter 2.3.2 --- LP-Repsecting Rounding cannot Do Better --- p.33 / Chapter 3 --- Maximum k-Vertex Cover on Trees --- p.38 / Chapter 3.1 --- Maximum k Vertex Cover on Trees --- p.39 / Chapter 3.2 --- k-MVC on Degree Bounded Graphs --- p.45 / Chapter 3.3 --- k-MVC on Degeneracy Bounded Graphs --- p.46 / Chapter 3.4 --- Extension to Maximum k Dominating Set --- p.47 / Chapter 4 --- Conclusion --- p.49 / Chapter 4.1 --- The Firefighter problem --- p.49 / Chapter 4.2 --- The Maximum k-Vertex Cover problem --- p.53 / Acknowledgement --- p.55 / Bibliography --- p.57

Typescript (photocopy). / Digitized by Kansas Correctional Industries