Engineering Commons^™

Ternary Logic Design In Topological Quantum Computing, Muhammad Ilyas, Shawn Cui, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

A quantum computer can perform exponentially faster than its classical counterpart. It works on the principle of superposition. But due to the decoherence effect, the superposition of a quantum state gets destroyed by the interaction with the environment. It is a real challenge to completely isolate a quantum system to make it free of decoherence. This problem can be circumvented by the use of topological quantum phases of matter. These phases have quasiparticles excitations called anyons. The anyons are charge-flux composites and show exotic fractional statistics. When the order of exchange matters, then the anyons are called non-Abelian anyons. Majorana …

Development Of A Configurable Real-Time Event Detection Framework For Power Systems Using Swarm Intelligence Optimization, Umar Farooq

Dissertations and Theses

Modern power systems characterized by complex topologies require accurate situational awareness to maintain an adequate level of reliability. Since they are large and spread over wide geographical areas, occurrence of failures is inevitable in power systems. Various generation and transmission disturbances give rise to a mismatch between generation and demand, which manifest as frequency events. These events can take the form of negligible frequency deviations or more severe emergencies that can precipitate cascading outages, depending on the severity of the disturbance and efficacy of remedial action schema. The impacts of such events have become more critical with recent decline in …

Methodologies For Quantum Circuit And Algorithm Design At Low And High Levels, Edison Tsai

Dissertations and Theses

Although the concept of quantum computing has existed for decades, the technology needed to successfully implement a quantum computing system has not yet reached the level of sophistication, reliability, and scalability necessary for commercial viability until very recently. Significant progress on this front was made in the past few years, with IBM planning to create a 1000-qubit chip by the end of 2023, and Google already claiming to have achieved quantum supremacy. Other major industry players such as Intel and Microsoft have also invested significant amounts of resources into quantum computing research.

Any viable computing system requires both hardware and …

Quantum Grover's Oracles With Symmetry Boolean Functions, Peng Gao

Dissertations and Theses

Quantum computing has become an important research field of computer science and engineering. Among many quantum algorithms, Grover's algorithm is one of the most famous ones. Designing an effective quantum oracle poses a challenging conundrum in circuit and system-level design for practical application realization of Grover's algorithm.

In this dissertation, we present a new method to build quantum oracles for Grover's algorithm to solve graph theory problems. We explore generalized Boolean symmetric functions with lattice diagrams to develop a low quantum cost and area efficient quantum oracle. We study two graph theory problems: cycle detection of undirected graphs and generalized …

Sequentially-Closed And Forward-Closed String Rewriting Systems, Yu Zhang

Legacy Theses & Dissertations (2009 - 2024)

In this dissertation we introduce the new concept of sequentially-closed string rewriting systems which generalizes forward-closed string rewriting systems and monadic string rewriting systems. We also investigate subclasses and properties of finite and regular sequentially-closed systems and forward-closed systems.

Sparse Coding On Stereo Video For Object Detection, Sheng Y. Lundquist, Melanie Mitchell, Garrett T. Kenyon

Computer Science Faculty Publications and Presentations

Deep Convolutional Neural Networks (DCNN) require millions of labeled training examples for image classification and object detection tasks, which restrict these models to domains where such a dataset is available. We explore the use of unsupervised sparse coding applied to stereo-video data to help alleviate the need for large amounts of labeled data. In this paper, we show that unsupervised sparse coding is able to learn disparity and motion sensitive basis functions when exposed to unlabeled stereo-video data. Additionally, we show that a DCNN that incorporates unsupervised learning exhibits better performance than fully supervised networks. Furthermore, finding a sparse representation …

Synchronous Subgraphs In Networks, Navita Jain

Legacy Theses & Dissertations (2009 - 2024)

Community detection is a central problem in network analysis. The majority of existing work defines communities as subsets of nodes that are structurally well-connected and isolated from the rest of the network. Apart from their underlying connectivity, nodes in real-world networks exhibit temporal activity: user posts in social networks, browsing activity on web pages and neuron activations in brain networks to name a few. While edges encode potential for community interactions, participation in the community can be quantified by synchronized member activity. Given both the network structure and individual node activity, how can we detect communities that are both well-connected …

Tetrahedral Mesh Optimization And Generation Via Topological Transformations And Gradient Based Node Perturbation, Christopher B. Hilbert

Masters Theses and Doctoral Dissertations

A general tetrahedral mesh optimization scheme utilizing both topological changes (i.e. flips) and gradient-based vertex optimization (i.e. smoothing) is demonstrated. This scheme is used in the optimization of tetrahedral meshes created by third-party software as well as a grid generation methodology created for this work. The particular algorithms involved are explained in detail including, an explication of the primary optimization metric, weighted condition number. In addition, a thorough literature review regarding tetrahedral mesh generation is given.

A Theory Of Name Resolution, Pierre Néron, Andrew Tolmach, Eelco Visser, Guido Wachsmuth

Computer Science Faculty Publications and Presentations

We describe a language-independent theory for name binding and resolution, suitable for programming languages with complex scoping rules including both lexical scoping and modules. We formulate name resolution as a two-stage problem. First a language-independent scope graph is constructed using language-specific rules from an abstract syntax tree. Then references in the scope graph are resolved to corresponding declarations using a language-independent resolution process. We introduce a resolution calculus as a concise, declarative, and language- independent specification of name resolution. We develop a resolution algorithm that is sound and complete with respect to the calculus. Based on the resolution calculus we …

Biogeography-Based Optimization For Combinatorial Problems And Complex Systems, Dawei Du

ETD Archive

Biogeography-based optimization (BBO) is a heuristic evolutionary algorithm that has shown good performance on many problems. In this dissertation, three problem1s 1 are researched for BBO: convergence speed and optimal solution convergence of BBO,1 1BBO application to combinatorial problems, and BBO application to complex systems. The first problem is to analyze BBO from two perspectives: how the components of BBO affect its convergence speed and the reason that BBO converges to the optimal solution. For the first perspective, which is convergence speed, we analyze the two essential components of BBO -- population construction and information sharing. For the second perspective, …

Oppositional Biogeography-Based Optimization, Mehmet Ergezer

ETD Archive

This dissertation outlines a novel variation of biogeography-based optimization (BBO), which is an evolutionary algorithm (EA) developed for global optimization. The new algorithm employs opposition-based learning (OBL) alongside BBO migration to create oppositional BBO (OB BO). Additionally, a new opposition method named quasi-reflection is introduced. Quasireflection is based on opposite numbers theory and we mathematically prove that it has the highest expected probability of being closer to the problem solution among all OBL methods that we explore. Performance of quasi-opposition is validated by mathematical analysis for a single-dimensional problem and by simulations for higher dimensions. Experiments are performed on benchmark …

External Control Interface, Dynamic Modeling And Parameter Estimation Of A Research Treadmill, Omer Sirin

ETD Archive

Treadmills providing linear continuous movement are used for robotic testing of prostheses in order to study their operating characteristics. However, traditional exercise treadmills are not able to simulate various conditions such as avoiding an obstacle, climbing, descending, reversing direction, or stopping instantly. The focus of this thesis is to examine control algorithms (position, speed and force) for the drive mechanism of a research treadmill to fulll the gap in the situations described above. The system consists of a power supply, a computer with Matlab, and the treadmill that includes a DC motor, a pulley and belt. Also, an external encoder …

Using Multi-Processors To Reconstruct Images With Proton Computed Tomography, Chenwei Xu

Theses Digitization Project

This project will employ the use of multi-processor technology to reconstruct image data as fast as possible. Two-dimensional image reconstruction technique reconstructs images by solving a linear equation: A x x =b, where A is the path matrix of proton histories, b is electron matrix of the image, and x is the matrix of image. One row in matrix A represents one beam. Matrix A consists of a number of beam projections to the image, and each projection consists of a number of beams. Contains source code.

Compressive Sensing Based Imaging Via Belief Propagation, Preethi Modur Ramachandra

Masters Theses and Doctoral Dissertations

Multiple description coding (MDC) using Compressive Sensing (CS) mainly aims at restoring an image from a small subset of samples with reasonable accuracy using an iterative message passing decoding algorithm commonly known as Belief Propagation (BP). The CS technique can accurately recover any compressible or sparse signal from a lesser number of non-adaptive, randomized linear projection samples than that specified by the Nyquist rate. In this work, we demonstrate how CS-based encoding generates measurements from the sparse image signal and the measurement matrix. Then we demonstrate how a BP decoding algorithm reconstructs the image from the measurements generated. In our …

Distributed Biogeography Based Optimization For Mobile Robots, Arpit Shah

ETD Archive

I present hardware testing of an evolutionary algorithm (EA) known as distributed biogeography based optimization (DBBO). DBBO is an extended version of biogeography based optimization (BBO). Typically, EAs require a central computer to control the evaluation of candidate solutions to some optimization problem, and to control the sharing of information between those candidate solutions. DBBO, however, does not require a centralized unit to control individuals. Individuals independently run the EA and find a solution to a given optimization problem. Both BBO and DBBO are based on the theory of biogeography, which describes how organisms are distributed geographically in nature. I …

Resizable, Scalable, Concurrent Hash Tables, Josh Triplett, Paul E. Mckenney, Jonathan Walpole

Computer Science Faculty Publications and Presentations

We present algorithms for shrinking and expanding a hash table while allowing concurrent, wait-free, linearly scalable lookups. These resize algorithms allow the hash table to maintain constant-time performance as the number of entries grows, and reclaim memory as the number of entries decreases, without delaying or disrupting readers.

We implemented our algorithms in the Linux kernel, to test their performance and scalability. Benchmarks show lookup scalability improved 125x over readerwriter locking, and 56% over the current state-of-the-art for Linux, with no performance degradation for lookups during a resize.

To achieve this performance, this hash table implementation uses a new concurrent …

Application Of Cuda In The Boolean Domain For The Unate Covering Problem, Eric Paul, Bernd Steinbach, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

NVIDIA’s Compute Unified Device Architecture (CUDA) is a relatively-recent development that allows to realize very fast algorithms for several Constraint Satisfaction and Computer Aided Design tasks. In this paper we present an approach to use Graphics Processing Units (GPU) and CUDA for solving Unate Covering Problem, a practical problem related to SAT. In particular we present a CUDA-enabled Petrick Function Minimizer. We compare the performance of a pipeline-processor (CPU) and a parallel processor (GPU) implementation of the matrix-multiplication method for solving unate covering problems.

Fully Anisotropic Split-Tree Adaptive Refinement Mesh Generation Using Tetrahedral Mesh Stitching, Vincent Charles Betro

Masters Theses and Doctoral Dissertations

Due to the myriad of geometric topologies that modern computational fluid dynamicists desire to mesh and run solutions on, the need for a robust Cartesian Mesh Generation algorithm is paramount. Not only do Cartesian meshes require less elements and often help resolve flow features but they also allow the grid generator to have a great deal of control in so far as element aspect ratio, size, and gradation. Fully Anisotropic Split-Tree Adaptive Refinement (FASTAR) is a code that allows the user to exert a great deal of control and ultimately generate a valid, geometry conforming mesh. Due to the split-tree …

Waypoint Generation Based On Sensor Aimpoint, Shannon M. Farrell

Theses and Dissertations

Secretary of Defense Robert M. Gates has emphasized a need for a greater number of intelligence, surveillance, and reconnaissance (ISR) assets to support combatant commanders and military operations globally. Unmanned systems, especially MAVs, used as ISR platforms provide the ability to maintain covertness during missions and help reduce the risk to human life. This research develops waypoint generation algorithms required to keep a point of interest (POI) in the field of view (FOV) of a fixed sensor on a micro air vehicle (MAV) in the presence of a constant wind.
Fixed sensors, while cheaper and less prone to mechanical failure …

An Algorithm For Identifying Novel Targets Of Transcription Factor Families: Application To Hypoxia-Inducible Factor 1 Targets, Yue Jiang, Bojan Cukic, Donald A. Adjeroh, Heath D. Skinner, Jie Lin, Qingxi J. Shen, Bing-Hua Jiang

Electrical & Computer Engineering Faculty Research

Efficient and effective analysis of the growing genomic databases requires the development of adequate computational tools. We introduce a fast method based on the suffix tree data structure for predicting novel targets of hypoxia-inducible factor 1 (HIF-1) from huge genome databases. The suffix tree data structure has two powerful applications here: one is to extract unknown patterns from multiple strings/sequences in linear time; the other is to search multiple strings/sequences using multiple patterns in linear time. Using 15 known HIF-1 target gene sequences as a training set, we extracted 105 common patterns that all occur in the 15 training genes …

Classical Search And Quantum Search Algorithms For Synthesis Of Quantum Circuits And Optimization Of Quantum Oracles, Sazzad Hossain

Dissertations and Theses

We observe an enormous increase in the computational power of digital computers. This was due to the revolution in manufacturing processes and controlling semiconductor structures on submicron scale, ultimately leading to the control of individual atoms. Eventually, the classical electric circuits encountered the barrier of quantum mechanics and its effects. However, the laws of quantum mechanics can be also used to produce computational devices that lead to extraordinary speed increases over classical computers. Thus quantum computing becomes a very promising and attractive research area. The Computer Aided Design for Quantum circuits becomes an essential ingredient for such emerging research which …

Significance Of Logic Synthesis In Fpga-Based Design Of Image And Signal Processing Systems, Mariusz Rawski, Henry Selvaraj, Bogdan J. Falkowski, Tadeusz Luba

Electrical & Computer Engineering Faculty Research

This chapter, taking FIR filters as an example, presents the discussion on efficiency of different implementation methodologies of DSP algorithms targeting modern FPGA architectures. Nowadays, programmable technology provides the possibility to implement digital systems with the use of specialized embedded DSP blocks. However, this technology gives the designer the possibility to increase efficiency of designed systems by exploitation of parallelisms of implemented algorithms. Moreover, it is possible to apply special techniques, such as distributed arithmetic (DA). Since in this approach, general-purpose multipliers are replaced by combinational LUT blocks, it is possible to construct digital filters of very high performance. Additionally, …

Nesting System With Quantization And Knowledge Base Applied, Leszek Koszalka, Grzegorz Chmaj

Electrical & Computer Engineering Faculty Research

Nesting algorithms deal with placing two dimensional shapes on the given canvas. In this paper a binary way of solving the nesting problem is proposed. Geometric shapes are quantized into binary form, which is used to operate on them. After finishing nesting they are converted back into original geometrical form. Investigations showed, that there is a big influence of quantization accuracy for the nesting effect. However, greater accuracy results with longer time of computation. The proposed knowledge base system is able to strongly reduce the computational time.

Use Of Tabu Search In A Solver To Map Complex Networks Onto Emulab Testbeds, Jason E. Macdonald

Theses and Dissertations

The University of Utah's solver for the testbed mapping problem uses a simulated annealing metaheuristic algorithm to map a researcher's experimental network topology onto available testbed resources. This research uses tabu search to find near-optimal physical topology solutions to user experiments consisting of scale-free complex networks. While simulated annealing arrives at solutions almost exclusively by chance, tabu search incorporates the use of memory and other techniques to guide the search towards good solutions. Both search algorithms are compared to determine whether tabu search can produce equal or higher quality solutions than simulated annealing in a shorter amount of time. It …

Improved Hyperspectral Image Testing Using Synthetic Imagery And Factorial Designed Experiments, Joseph P. Bellucci

Theses and Dissertations

The goal of any remote sensing system is to gather data about the geography it is imaging. In order to gain knowledge of the earth's landscape, post-processing algorithms are developed to extract information from the collected data. The algorithms can be intended to classify the various ground covers in a scene, identify specific targets of interest, or detect anomalies in an image. After the design of an algorithm comes the difficult task of testing and evaluating its performance. Traditionally, algorithms are tested using sets of extensively ground truthed test images. However, the lack of well characterized test data sets and …

Ternary Quantum Logic, Normen Giesecke

Dissertations and Theses

The application of Moore's Law would not be feasible by using the computing systems fabrication principles that are prevalent today. Fundamental changes in the field of computing are needed to keep Moore's Law operational. Different quantum technologies are available to take the advancement of computing into the future. Logic in quantum technology uses gates that are very different from those used in contemporary technology. Limiting itself to reversible operations, this thesis presents different methods to realize these logic gates. Two methods using Generalized Ternary Gates and Muthukrishnan Stroud Gates are presented for synthesis of ternary logic gates. Realizations of well-known …

Image Quality Assessment Using Artificial Neural Networks, Alexander Havstad

Theses: Doctorates and Masters

not available

A Fast And Simple Algorithm For Computing M Shortest Paths In Stage Graph, M. Sherwood, Laxmi P. Gewali, Henry Selvaraj, Venkatesan Muthukumar

Electrical & Computer Engineering Faculty Research

We consider the problem of computing m shortest paths between a source node s and a target node t in a stage graph. Polynomial time algorithms known to solve this problem use complicated data structures. This paper proposes a very simple algorithm for computing all m shortest paths in a stage graph efficiently. The proposed algorithm does not use any complicated data structure and can be implemented in a straightforward way by using only array data structure. This problem appears as a sub-problem for planning risk reduced multiple k-legged trajectories for aerial vehicles.

Logic Synthesis For Layout Regularity Using Decision Diagrams, Malgorzata Chrzanowska-Jeske, Alan Mishchenko, Jinsong Zhang, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

This paper presents a methodology for logic synthesis of Boolean functions in the form of regular structures that can be mapped into standard cells or programmable devices. Regularity offers an elegant solution to hard problems arising in layout and test generation, at no extra cost or at the cost of increasing the number of gates, which does not always translate into the increase of circuit area. Previous attempts to synthesize logic into regular structures using decision diagrams suffered from an increase in the number of logic levels due to multiple repetitions of control variables. This paper proposes new techniques, which …

A Fast And Simple Algorithm For Computing M-Shortest Paths In State Graph, M. Sherwood, Laxmi P. Gewali, Henry Selvaraj, Venkatesan Muthukumar

Electrical & Computer Engineering Faculty Research

We consider the problem of computing m shortest paths between a source node s and a target node t in a stage graph. Polynomial time algorithms known to solve this problem use complicated data structures. This paper proposes a very simple algorithm for computing all m shortest paths in a stage graph efficiently. The proposed algorithm does not use any complicated data structure and can be implemented in a straightforward way by using only array data structure. This problem appears as a sub-problem for planning risk reduced multiple k-legged trajectories for aerial vehicles.