Engineering Commons^™

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.

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 …

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 …

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 …

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 …

Extending The Network Life Time In Wsn Using Energy Efficient Algorithm, Venkata Sesha Sai Koundinya Goparaju

Electrical & Computer Engineering Theses & Dissertations

Wireless Sensor networks have many potential applications. These wireless sensor networks necessitate specific design requirements of which energy efficiency is vital. The sensor networks consist of sensor nodes that operate on battery power, and replacement of these batteries is very often a strenuous task, since networks are deployed in areas where the act of replacing the batteries proves impractical.

With the limited available energy of sensor nodes, most of the energy is drained during communication. An energy efficient routing algorithm can prolong the lifetime of the network by gradually depleting the nodes in the network. Many of the routing protocols …

Neighborhood Defined Adaboost Based Mixture Of Color Components For Efficient Skin Segmentation, Ramya Reddy Maaram

Electrical & Computer Engineering Theses & Dissertations

A skin segmentation algorithm robust to illumination changes and skin-like backgrounds is developed in this thesis. So far skin pixel classification has been limited to only individual color spaces and there has not been a comprehensive evaluation of which color components or combination of color components would provide the best classification accuracy, Color components in a given color space form the feature set for the classification of skin pixels. The combination of the color components or the features present within a single color space may not be the best when it comes to skin pixel classification as the discriminatory power …

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 …

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.

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.

Dynamic Load Distribution In Mist, K. Al-Saqabi, R. M. Prouty, Dylan Mcnamee, Steve Otto, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This paper presents an algorithm for scheduling parallel applications in large-scale, multiuser, heterogeneous distributed systems. The approach is primarily targeted at systems that harvest idle cycles in general-purpose workstation networks, but is also applicable to clustered computer systems and massively parallel processors. The algorithm handles unequal processor capacities, multiple architecture types and dynamic variations in the number of processes and available processors. Scheduling decisions are driven by the desire to minimize turnaround time while maintaining fairness among competing applications. For efficiency, the virtual processors (VPs) of each application are gang scheduled on some subset of the available physical processors.

Neural Generalized Predictive Control For Real-Time Control, Donald I. Soloway

Electrical & Computer Engineering Theses & Dissertations

In this thesis a computationally efficient Generalized Predictive Control (GPC) algorithm is presented and implemented. The algorithm is more efficient than others because the number of iterations needed for convergence is significantly lower with Newton-Raphson. The main additional cost with Newton-Raphson algorithm is the calculation of the Hessian. This overhead is not a problem because of the reduced number of iterations, making the algorithm suitable for real-time control. For nonlinear control applications, a neural network is used as a dynamical system predictor leading to a Neural Generalized Predictive Control (NGPC) algorithm which is presented in detail in this thesis. An …

Cyclo-Static Scheduling Of Large Grain Dataflow Algorithms On A Local Area Atamm Multicomputing Testbed, Sudeepto Roy

Electrical & Computer Engineering Theses & Dissertations

A strategy for cyclo-statically scheduling deterministic large grain dataflow (LGDF) algorithms for distributed execution on loosely coupled multicomputer architectures is presented in this research. The computational paradigm used is the ODU/NASA developed Algorithm To Architecture Mapping Model (ATAMM), which consists of marked graphs and Gantt chart representations that model the iterative execution of deterministic LGDF algorithms for different values of throughput and computation time. It is postulated that the behavior of these algorithms could be represented by the aggregate execution of an ensemble of cyclically shifted threads of a specific node sequence. Assuming the existence of one or more such …

Resource Utilization Model For The Algorithm To Architecture Mapping Model, Rakesh R. Patel

Electrical & Computer Engineering Theses & Dissertations

The analytical model for resource utilization, and the variable node time and conditional node model for the enhanced ATAMM model for a real-time data flow architecture, is presented in this research. The Algorithm To Architecture Mapping Model, ATAMM, is a Petri net based graph theoretic model developed at Old Dominion University, and is capable of modeling the execution of large-grained algorithms on a real-time data flow architecture. Using the resource utilization model, the resource envelope may be obtained directly from a given graph and, consequently, the maximum number of required resources may be evaluated. The node timing diagram for one …

Implementation And Analysis Of Np-Complete Algorithms On A Distributed Memory Computer, Joel S. Garmon

Theses and Dissertations

The purpose of this research is to explore methods used to parallelize NP-complete problems and the degree of improvement that can be realized using different methods of load balancing. A serial and four parallel A* branch and bound algorithms were implemented and executed on an Intel iPSC/2 hypercube computer. One parallel algorithm used a global, or centralized, list to store unfinished work and the other three parallel algorithms used a distributed list to store unfinished work locally on each processor. the three distributed list algorithms are: without load balancing, with load balancing, and with load balancing and work distribution. The …