This dissertation focuses on two connected areas: quantum computation and quantum control. Two proposals to construct a quantum computer, using nuclear magnetic resonance (NMR) and superconductivity, are introduced. We give details about the modeling, qubit realization, one and two qubit gates and measurement in the language that mathematicians can understand and fill gaps in the original literatures. Two experimental examples using liquid NMR are also presented. Then we proceed to investigate an example of quantum control, that of a magnetometer using quantum feedback. Previous research has shown that feedback makes the measurement robust to an unknown parameter, the number of atoms involved, with the assumption that the feedback is noise free. To evaluate the effect of the feedback noise, we extend the original model by an input noise term. We then compute the steady state performance of the Kalman filter for both the closed-loop and open-loop cases and retrieve the estimation error variances. The results are compared and criteria for evaluating the effects of input noise are obtained. Computations and simulations show that the level of input noise affects the measurement by changing the region where closed loop feedback is beneficial.

No description available.

Many problems of practical significance are known to be NP-hard, and hence, are unlikely to be solved by polynomial-time algorithms. There are several ways to cope with the NP-hardness of a certain problem. The most popular approaches include heuristic algorithms, approximation algorithms, and randomized algorithms. Recently, parameterized computation and complexity have been receiving a lot of attention. By taking advantage of small or moderate parameter values, parameterized algorithms provide new venues for practically solving problems that are theoretically intractable. In this dissertation, we design efficient parameterized algorithms for several wellknown NP-hard problems and prove strong lower bounds for some others. In doing so, we place emphasis on the development of new techniques that take advantage of the structural properties of the problems. We present a simple parameterized algorithm for Vertex Cover that uses polynomial space and runs in time O(1.2738k + kn). It improves both the previous O(1.286k + kn)-time polynomial-space algorithm by Chen, Kanj, and Jia, and the very recent O(1.2745kk4 + kn)-time exponential-space algorithm, by Chandran and Grandoni. This algorithm stands out for both its performance and its simplicity. Essential to the design of this algorithm are several new techniques that use structural information of the underlying graph to bound the search space. For Vertex Cover on graphs with degree bounded by three, we present a still better algorithm that runs in time O(1.194k + kn), based on an “almost-global” analysis of the search tree. We also show that an important structural property of the underlying graphs – the graph genus – largely dictates the computational complexity of some important graph problems including Vertex Cover, Independent Set and Dominating Set. We present a set of new techniques that allows us to prove almost tight computational lower bounds for some NP-hard problems, such as Clique, Dominating Set, Hitting Set, Set Cover, and Independent Set. The techniques are further extended to derive computational lower bounds on polynomial time approximation schemes for certain NP-hard problems. Our results illustrate a new approach to proving strong computational lower bounds for some NP-hard problems under reasonable conditions.

Much research has been done on wireless sensor networks. However, most protocols and algorithms for such networks are based on the ideal model Unit Disk Graph (UDG) model or do not assume any model. Furthermore, many results assume the knowledge of location information of the network. In practice, sensor networks often deviate from the UDG model significantly. It is not uncommon to observe stable long links that are more than five times longer than unstable short links in real wireless networks. A more general network model, the quasi unit-disk graph (quasi-UDG) model, captures much better the characteristics of wireless networks. However, the understanding of the properties of general quasi-UDGs has been very limited, which is impeding the design of key network protocols and algorithms. In this dissertation we study the properties for general wireless sensor networks and develop new topological/geometrical techniques for wireless sensor networking. We assume neither the ideal UDG model nor the location information of the nodes. Instead we work on the more general quasi-UDG model and focus on figuring out the relationship between the geometrical properties and the topological properties of wireless sensor networks. Based on such relationships we develop algorithms that can compute useful substructures (planar subnetworks, boundaries, etc.). We also present direct applications of the properties and substructures we constructed including routing, data storage, topology discovery, etc. We prove that wireless networks based on quasi-UDG model exhibit nice properties like separabilities, existences of constant stretch backbones, etc. We develop efficient algorithms that can obtain relatively dense planar subnetworks for wireless sensor networks. We also present efficient routing protocols and balanced data storage scheme that supports ranged queries. We present algorithmic results that can also be applied to other fields (e.g., information management). Based on divide and conquer and improved color coding technique, we develop algorithms for path, matching and packing problem that significantly improve previous best algorithms. We prove that it is unlikely for certain problems in operation science and information management to have any relatively effective algorithm or approximation algorithm for them.

Vertex shader, one of the core parts in 3D graphics systems, is to speed up the operations of coordinate transformation and lighting in 3D graphics pipeline, and vector ALU is the key part of a vertex shader. This thesis proposes several unified architectures that integrate the floating-point vector arithmetic unit and special function unit in order to share some hardware resource. We propose three different architectures for the design of the unified vector ALU. The first architecture includes a single-instruction-multiple-data (SIMD) vector arithmetic unit, and uses table-based method with first-order approximation to calculate some special functions. The second architecture use higher-order approximation to reduce the table sizes and share the floating-point multipliers in the SIMD vector unit. The proposed third architecture has two copies of hardware that can compute two dot-product operations in parallel and thus increase the throughput of the matrix computation by a factor of two. Furthermore, the two dot-product units can be used to perform the interpolation for special function calculation.

The research presented in this thesis was motivated by the need to improve introductory physics courses. Introductory physics courses are generally the first courses in which students learn to create models to solve complex problems. However, many students taking introductory physics courses fail to acquire a command of the concepts, methods and tools presented in these courses. The reforms proposed by this thesis focus on altering the content of introductory courses rather than content delivery methods as most reforms do. This thesis explores how the performance on a widely used test of conceptual understanding in mechanics compares between students taking a course with updated and modified content and students taking a traditional course. Better performance by traditional students was found to stem from their additional practice on the types of items which appeared on the test. The results of this work brought into question the role of the introductory physics course for non-majors. One aspect of this new role is the teaching of new methods such as computation (the use of a computer to solve numerically, simulate and visualize physical problems). This thesis explores the potential benefits for students who learn computation as part of physics course. After students worked through a suite of computational homework problems, many were able to model a new physical situation with which they had no experience. The failure of some students to model this new situation might have stemmed from their unfavorable attitudes towards learning computation. In this thesis, we present the development of a new tool for characterizing students' attitudes. Preliminary measurements indicated significant differences between successful and unsuccessful students.

Thesis (M.Ed.), Memorial University of Newfoundland, 2000. / Bibliography: leaves 134-140.

Thesis (Ph. D.)--University of Texas at Austin, 2003. / Vita. Includes bibliographical references. Available also from UMI Company.

Previous research has examined the effectiveness of Direct Instruction Curriculum over the past thirty years in a variety of areas including rate of learning, effectiveness on different types of learners, and comparisons to other types of instruction. This study attempted to determine the effects of the use of a direct instruction math curriculum on higher-order problem solving. Two groups of 3 5 students each participated. The procedures included administering the Kauffman Achievement test to determine current grade level in math and reading. The Saxon Math Second Grade Curriculum was used to instruct the participants. The effects on higher-order problem solving with the Corrective Math Curriculum were assessed on two different dependent measures: solution of word problems consisting of both addition and subtraction operations, and performance of the students within the curriculum. Results were assessed using the delayed multiple baseline design.

We have recently developed and tested a new computational method for experiment prototyping at the Advanced Test Reactor (ATR). The method significantly reduces neutronic computation time while maintaining computational accuracy. In this thesis, we present the method and describe the techniques that we used to implement it. We then qualitatively and quantitatively analyze its performance for absorptive and multiplicative experiment perturbations over a single region and across multiple regions of the ATR. We conclude with a discussion of future research that might be conducted on the method. / text