Theory and Algorithms Commons^™

Calculating Staircase Slope From A Single Image, Nicholas Joseph Clarke

Master's Theses

Realistic modeling of a 3D environment has grown in popularity due to the increasing realm of practical applications. Whether for practical navigation purposes, entertainment value, or architectural standardization, the ability to determine the dimensions of a room is becoming more and more important. One of the trickier, but critical, features within any multistory environment is the staircase. Staircases are difficult to model because of their uneven surface and various depth aspects. Coupling this need is a variety of ways to reach this goal. Unfortunately, many such methods rely upon specialized sensory equipment, multiple calibrated cameras, or other such impractical setups. …

Using Probabilistic Graphical Models To Solve Np-Complete Puzzle Problems, Fengjiao Wu

Master's Projects

Probabilistic Graphical Models (PGMs) are commonly used in machine learning to solve problems stemming from medicine, meteorology, speech recognition, image processing, intelligent tutoring, gambling, games, and biology. PGMs are applicable for both directed graph and undirected graph. In this work, I focus on the undirected graphical model. The objective of this work is to study how PGMs can be applied to find solutions to two puzzle problems, sudoku and jigsaw puzzles. First, both puzzle problems are represented as undirected graphs, and then I map the relations of nodes to PGMs and Belief Propagation (BP). This work represents the puzzle grid …

Trip: Tracking Rhythms In Plants, An Automated Leaf Movement Analysis Program For Circadian Period Estimation, Kathleen Greenham, Ping Lou, Sara E. Remsen, Hany Farid, C Robertson Mcclung

Dartmouth Scholarship

Background: A well characterized output of the circadian clock in plants is the daily rhythmic movement of leaves. This process has been used extensively in Arabidopsis to estimate circadian period in natural accessions as well as mutants with known defects in circadian clock function. Current methods for estimating circadian period by leaf movement involve manual steps throughout the analysis and are often limited to analyzing one leaf or cotyledon at a time.

Methods: In this study, we describe the development of TRiP (Tracking Rhythms in Plants), a new method for estimating circadian period using a motion estimation algorithm that can …

Compression Of Video Tracking And Bandwidth Balancing Routing In Wireless Multimedia Sensor Networks, Yin Wang, Jianjun Yang, Ju Shen, Bryson Payne, Juan Guo, Kun Hua

Computer Science Faculty Publications

There has been a tremendous growth in multimedia applications over wireless networks. Wireless Multimedia Sensor Networks(WMSNs) have become the premier choice in many research communities and industry. Many state-of-art applications, such as surveillance, traffic monitoring, and remote heath care are essentially video tracking and transmission in WMSNs. The transmission speed is constrained by the big file size of video data and fixed bandwidth allocation in constant routing paths. In this paper, we present a CamShift based algorithm to compress the tracking of videos. Then we propose a bandwidth balancing strategy in which each sensor node is able to dynamically select …

Adviser: A Web-Based Algorithm Portfolio Deviser, Mustafa Misir, Stephanus Daniel Handoko, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

The basic idea of algorithm portfolio [1] is to create a mixture of diverse algorithms that complement each other’s strength so as to solve a diverse set of problem instances. Algorithm portfolios have taken on a new and practical meaning today with the wide availability of multi-core processors: from an enterprise perspective, the interest is to make best use of parallel machines within the organization by running different algorithms simultaneously on different cores to solve a given problem instance. Parallel execution of a portfolio of algorithms as suggested by [2, 3] a number of years …

Beyond Traits: Social Context Based Personality Model, Jaroslaw Kochanowicz, Ah-Hwee Tan, Daniel Thalmann

Research Collection School Of Computing and Information Systems

The relation between individual’s personality and environmental context is a key issue in psychology, recently also in character simulations. This paper contributes to both domains by proposing a socio-cognitive, contextual personality model - a new voice in a century old problem of personality, but also an approach to simulating groups of more humanlike agents. After analyzing the influence of popularity of ‘trait personality models’ on psychology and computer simulation, we propose Social Context based Personality model - a continuation and specification of the Cognitive-Affective Personality System theory. The discussion, model and implementation are provided, followed by an example application in …

Optimal "Big Data" Aggregation Systems - From Theory To Practical Application, William J. Culhane Iv

Open Access Dissertations

The integration of computers into many facets of our lives has made the collection and storage of staggering amounts of data feasible. However, the data on its own is not so useful to us as the analysis and manipulation which allows manageable descriptive information to be extracted. New tools to extract this information from ever growing repositories of data are required.

Some of these analyses can take the form of a two phase problem which is easily distributed to take advantage of available computing power. The first phase involves computing some descriptive partial result from some subset of the original …

The Apprentices' Tower Of Hanoi, Cory Bh Ball

Electronic Theses and Dissertations

The Apprentices' Tower of Hanoi is introduced in this thesis. Several bounds are found in regards to optimal algorithms which solve the puzzle. Graph theoretic properties of the associated state graphs are explored. A brief summary of other Tower of Hanoi variants is also presented.

Efficient Estimation Of Cluster Population, Sanjeev K C

UNLV Theses, Dissertations, Professional Papers, and Capstones

Partitioning a given set of points into clusters is a well known problem in pattern recognition, data mining, and knowledge discovery. One of the well known methods for identifying clusters in Euclidean space is the K-mean algorithm. In using the K-mean clustering algorithm it is necessary to know the value of k (the number of clusters) in advance. We propose to develop algorithms for good estimation of k for points distributed in two dimensions. The techniques we pursue include a bucketing method, g-hop neighbors, and Voronoi diagrams. We also present experimental results for examining the performances of the bucketing method …

Map: A Computational Model For Adaptive Persuasion, Yilin Kang, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

While a variety of persuasion agents have been created and applied in different domains such as marketing, military training and health industry, there is a lack of a model which provides a unified framework for different persuasion strategies. Specifically, persuasion is not adaptable to the individuals’ personal states in different situations. Grounded in the Elaboration Likelihood Model (ELM), this paper presents a computational model called Model for Adaptive Persuasion (MAP) for virtual agents. MAP is a semi-connected network model which enables an agent to adapt its persuasion strategies through feedback. We have implemented and evaluated a MAP-based virtual nurse agent …

Oscar: Online Selection Of Algorithm Portfolios With Case Study On Memetic Algorithms, Mustafa Misir, Stephanus Daniel Handoko, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

This paper introduces an automated approach called OSCAR that combines algorithm portfolios and online algorithm selection. The goal of algorithm portfolios is to construct a subset of algorithms with diverse problem solving capabilities. The portfolio is then used to select algorithms from for solving a particular (set of) instance(s). Traditionally, algorithm selection is usually performed in an offline manner and requires the need of domain knowledge about the target problem; while online algorithm selection techniques tend not to pay much attention to a careful construction of algorithm portfolios. By combining algorithm portfolios and online selection, our hope is to design …

Positive Influence Dominating Set Generation Via A New Greedy Algorithm, Matthew Rink

Computer Science Honors Papers

Current algorithms in the Positive Influence Dominating Set (PIDS) problem domain are focused on a specific type of PIDS, the Total Positive Influence Dominating Set (TPIDS). We have developed an algorithm specifically targeted towards the non-total type of PIDS. In addition to our new algorithm, we adapted two existing TPIDS algorithms to generate PIDS. We ran simulations for all three algorithms, and our new algorithm consistently generates smaller PIDS than either existing algorithm, with our algorithm generating PIDS approximately 5% smaller than the better of the two existing algorithms.

Modeling Traffic At An Intersection, Kaleigh L. Mulkey, Saniita K. Fasenntao

Symposium of Student Scholars

The main purpose of this project is to build a mathematical model for traffic at a busy intersection. We use elements of Queueing Theory to build our model: the vehicles driving into the intersection are the “arrival process” and the stop light in the intersection is the “server.”

We collected traffic data on the number of vehicles arriving to the intersection, the duration of green and red lights, and the number of vehicles going through the intersection during a green light. We built a SAS macro code to simulate traffic based on parameters derived from the data.

In our program …

Gaussian Weighted Neighborhood Connectivity Of Nonlinear Line Attractor For Learning Complex Manifolds, Theus H. Aspiras, Vijayan K. Asari, Wesam Sakla

Electrical and Computer Engineering Faculty Publications

The human brain has the capability to process high quantities of data quickly for detection and recognition tasks. These tasks are made simpler by the understanding of data, which intentionally removes redundancies found in higher dimensional data and maps the data onto a lower dimensional space. The brain then encodes manifolds created in these spaces, which reveal a specific state of the system. We propose to use a recurrent neural network, the nonlinear line attractor (NLA) network, for the encoding of these manifolds as specific states, which will draw untrained data towards one of the specific states that the NLA …

Efficient Thermal Image Segmentation Through Integration Of Nonlinear Enhancement With Unsupervised Active Contour Model, Fatema Albalooshi, Evan Krieger, Paheding Sidike, Vijayan K. Asari

Electrical and Computer Engineering Faculty Publications

Thermal images are exploited in many areas of pattern recognition applications. Infrared thermal image segmentation can be used for object detection by extracting regions of abnormal temperatures. However, the lack of texture and color information, low signal-to-noise ratio, and blurring effect of thermal images make segmenting infrared heat patterns a challenging task. Furthermore, many segmentation methods that are used in visible imagery may not be suitable for segmenting thermal imagery mainly due to their dissimilar intensity distributions.

Thus, a new method is proposed to improve the performance of image segmentation in thermal imagery. The proposed scheme efficiently utilizes nonlinear intensity …

Java Animated Software For Teaching The Frank-Wolfe Algorithm For Static Traffic Network Equilibrium, Zhi Li

Computational Modeling & Simulation Engineering Theses & Dissertations

The popular Frank-Wolfe (FW) algorithm for solving the network equilibrium problems plays an important role in transportation simulation. Not only has the basic Frank Wolfe algorithm been studied, but also other variations of the FW algorithm (such as Conjugate Frank Wolfe and Bi-Conjugate Frank Wolfe algorithms) have been extensively studied by the research communities.

In this work, the basic Frank Wolfe algorithm is re-visited for the purpose of developing a useful, user-friendly, and appealing Java computer animation for enhancing the teaching effectiveness of this fundamental transportation static network equilibrium algorithm. Since the shortest path (SP) algorithms (such as the well-known …

An Iterated Local Search Algorithm For Solving The Orienteering Problem With Time Windows, Aldy Gunawan, Hoong Chuin Lau, Kun Lu

Research Collection School Of Computing and Information Systems

The Orienteering Problem with Time Windows (OPTW) is a variant of the Orienteering Problem (OP). Given a set of nodes including their scores, service times and time windows, the goal is to maximize the total of scores collected by a particular route considering a predefined time window during which the service has to start. We propose an Iterated Local Search (ILS) algorithm to solve the OPTW, which is based on several LocalSearch operations, such as swap, 2-opt, insert and replace. We also implement the combination between AcceptanceCriterion and Perturbation mechanisms to control the balance between diversification and intensification of the …

Active Tile Self-Assembly And Simulations Of Computational Systems, Daria Karpenko

USF Tampa Graduate Theses and Dissertations

Algorithmic self-assembly has been an active area of research at the intersection of computer science, chemistry, and mathematics for almost two decades now, motivated by the natural self-assembly mechanism found in DNA and driven by the desire for precise control of nanoscale material manufacture and for the development of nanocomputing and nanorobotics. At the theoretical core of this research is the Abstract Tile Assembly Model (aTAM), the original abstract model of DNA tile self-assembly. Recent advancements in DNA nanotechnology have been made in developing strand displacement mechanisms that could allow DNA tiles to modify themselves during the assembly process by …

Leading Undergraduate Students To Big Data Generation, Jianjun Yang, Ju Shen

Computer Science Faculty Publications

People are facing a flood of data today. Data are being collected at unprecedented scale in many areas, such as networking, image processing, virtualization, scientific computation, and algorithms. The huge data nowadays are called Big Data. Big data is an all encompassing term for any collection of data sets so large and complex that it becomes difficult to process them using traditional data processing applications. In this article, the authors present a unique way which uses network simulator and tools of image processing to train students abilities to learn, analyze, manipulate, and apply Big Data. Thus they develop students hands-on …

Reconstruction Privacy: Enabling Statistical Learning, Ke Wang, Chao Han, Ada Waichee Fu, Raymond C. Wong, Philip S. Yu

Research Collection School Of Computing and Information Systems

Non-independent reasoning (NIR) allows the information about one record in the data to be learnt from the information of other records in the data. Most posterior/prior based privacy criteria consider NIR as a privacy violation and require to smooth the distribution of published data to avoid sensitive NIR. The drawback of this approach is that it limits the utility of learning statistical relationships. The differential privacy criterion considers NIR as a non-privacy violation, therefore, enables learning statistical relationships, but at the cost of potential disclosures through NIR. A question is whether it is possible to (1) allow learning statistical relationships, …

A Heuristic Evolutionary Method For The Complementary Cell Suppression Problem, Hira B. Herrington

CCAC Theses and Dissertations

Cell suppression is a common method for disclosure avoidance used to protect sensitive information in two-dimensional tables where row and column totals are published along with non-sensitive data. In tables with only positive cell values, cell suppression has been demonstrated to be non-deterministic NP-hard. Therefore, finding more efficient methods for producing low-cost solutions is an area of active research.

Genetic algorithms (GA) have shown to be effective in finding good solutions to the cell suppression problem. However, these methods have the shortcoming that they tend to produce a large proportion of infeasible solutions. The primary goal of this research was …

Hole Detection And Shape-Free Representation And Double Landmarks Based Geographic Routing In Wireless Sensor Networks, Jianjun Yang, Zongming Fei, Ju Shen

Computer Science Faculty Publications

In wireless sensor networks, an important issue of geographic routing is “local minimum” problem, which is caused by a “hole” that blocks the greedy forwarding process. Existing geographic routing algorithms use perimeter routing strategies to find a long detour path when such a situation occurs. To avoid the long detour path, recent research focuses on detecting the hole in advance, then the nodes located on the boundary of the hole advertise the hole information to the nodes near the hole. Hence the long detour path can be avoided in future routing. We propose a heuristic hole detecting algorithm which identifies …

On Processing Reverse K-Skyband And Ranked Reverse Skyline Queries, Yunjun Gao, Qing Liu, Baihua Zheng, Mou Li, Gang Chen, Qing Li

Research Collection School Of Computing and Information Systems

In this paper, for the first time, we identify and solve the problem of efficient reverse k-skyband (RkSB) query processing. Given a set P of multi-dimensional points and a query point q, an RkSB query returns all the points in P whose dynamic k-skyband contains q. We formalize RkSB retrieval, and then propose five algorithms for computing the RkSB of an arbitrary query point efficiently. Our methods utilize a conventional data-partitioning index (e.g., R-tree) on the dataset, and employ pre-computation, reuse and pruning techniques to boost the query efficiency. In addition, we extend our solutions to tackle an interesting variant …

Dynamic Game-Theoretic Models To Determine The Value Of Intrusion Detection Systems In The Face Of Uncertainty, David Paul Moured

CCAC Theses and Dissertations

Firms lose millions of dollars every year to cyber-attacks and the risk to these companies is growing exponentially. The threat to monetary and intellectual property has made Information Technology (IT) security management a critical challenge to firms. Security devices, including Intrusion Detections Systems (IDS), are commonly used to help protect these firms from malicious users by identifying the presence of malicious network traffic. However, the actual value of these devices remains uncertain among the IT security community because of the costs associated with the implementation of different monitoring strategies that determine when to inspect potentially malicious traffic and the costs …

Two Compact Incremental Prime Sieves, Jonathan P. Sorenson

Scholarship and Professional Work - LAS

A prime sieve is an algorithm that finds the primes up to a bound n. We say that a prime sieve is incremental, if it can quickly determine if n+1 is prime after having found all primes up to n. We say a sieve is compact if it uses roughly √n space or less. In this paper, we present two new results.

• We describe the rolling sieve, a practical, incremental prime sieve that takes O(n log log n) time and O(√n log n) bits of space.

• We also …

Near-Optimal Online Multiselection In Internal And External Memory, Jonathan P. Sorenson, Jérémy Barbay, Ankur Gupta, S. Srinivasa Rao

Scholarship and Professional Work - LAS

We introduce an online version of the multiselection problem, in which q selection queries are requested on an unsorted array of n elements. We provide the first online algorithm that is 1-competitive with online algorithm proposed by Kaligosi et al.[ICALP 2005] in terms of comparison complexity. Our algorithm also supports online search queries efficiently.

We then extend our algorithm to the dynamic setting, while retaining online functionality, by supporting arbitrary insertions and deletions on the array. Assuming that the insertion of an element is immediately preceded by a search for that element, we show that our dynamic online algorithm performs …

Research Agenda Into Human-Intelligence/Machine-Intelligence Governance, Teddy Steven Cotter

Engineering Management & Systems Engineering Faculty Publications

Since the birth of modern artificial intelligence (AI) at the 1956 Dartmouth Conference, the AI community has pursued modeling and coding of human intelligence into AI reasoning processes (HI Þ MI). The Dartmouth Conference's fundamental assertion was that every aspect of human learning and intelligence could be so precisely described that it could be simulated in AI. With the exception of knowledge specific areas (such as IBM's Big Blue and a few others), sixty years later the AI community is not close to coding global human intelligence into AI. In parallel, the knowledge management (KM) community has pursued understanding of …

Exploring Algorithmic Musical Key Recognition, Nathan J. Levine

CMC Senior Theses

The following thesis outlines the goal and process of algorithmic musical key detection as well as the underlying music theory. This includes a discussion of signal-processing techniques intended to most accurately detect musical pitch, as well as a detailed description of the Krumhansl-Shmuckler (KS) key-finding algorithm. It also describes the Java based implementation and testing process of a musical key-finding program based on the KS algorithm. This thesis provides an analysis of the results and a comparison with the original algorithm, ending with a discussion of the recommended direction of further development.

Graph-Based Regularization In Machine Learning: Discovering Driver Modules In Biological Networks, Xi Gao

Theses and Dissertations

Curiosity of human nature drives us to explore the origins of what makes each of us different. From ancient legends and mythology, Mendel's law, Punnett square to modern genetic research, we carry on this old but eternal question. Thanks to technological revolution, today's scientists try to answer this question using easily measurable gene expression and other profiling data. However, the exploration can easily get lost in the data of growing volume, dimension, noise and complexity. This dissertation is aimed at developing new machine learning methods that take data from different classes as input, augment them with knowledge of feature relationships, …

Spiking Neural Networks: Neuron Models, Plasticity, And Graph Applications, Shaun Donachy

Theses and Dissertations

Networks of spiking neurons can be used not only for brain modeling but also to solve graph problems. With the use of a computationally efficient Izhikevich neuron model combined with plasticity rules, the networks possess self-organizing characteristics. Two different time-based synaptic plasticity rules are used to adjust weights among nodes in a graph resulting in solutions to graph prob- lems such as finding the shortest path and clustering.