Theory and Algorithms Commons^™

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 …

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 …

Metalogic Notes, Saverio Perugini

Computer Science Working Papers

A collection of notes, formulas, theorems, postulates and terminology in symbolic logic, syntactic notions, semantic notions, linkages between syntax and semantics, soundness and completeness, quantified logic, first-order theories, Goedel's First Incompleteness Theorem and more.

Statistics Notes, Saverio Perugini

Computer Science Working Papers

A collection of terms, definitions, formulas and explanations about statistics.

Feature Selection And Classification Methods For Decision Making: A Comparative Analysis, Osiris Villacampa

CCAC Theses and Dissertations

The use of data mining methods in corporate decision making has been increasing in the past decades. Its popularity can be attributed to better utilizing data mining algorithms, increased performance in computers, and results which can be measured and applied for decision making. The effective use of data mining methods to analyze various types of data has shown great advantages in various application domains. While some data sets need little preparation to be mined, whereas others, in particular high-dimensional data sets, need to be preprocessed in order to be mined due to the complexity and inefficiency in mining high dimensional …

A Dynamic Programming Algorithm For Finding The Optimal Placement Of A Secondary Structure Topology In Cryo-Em Data, Abhishek Biswas, Desh Ranjan, Mohammad Zubair, Jing He

Computer Science Faculty Publications

The determination of secondary structure topology is a critical step in deriving the atomic structures from the protein density maps obtained from electron cryomicroscopy technique. This step often relies on matching the secondary structure traces detected from the protein density map to the secondary structure sequence segments predicted from the amino acid sequence. Due to inaccuracies in both sources of information, a pool of possible secondary structure positions needs to be sampled. One way to approach the problem is to first derive a small number of possible topologies using existing matching algorithms, and then find the optimal placement for each …

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.

Operator Calculus Algorithms For Multi-Constrained Paths, Jamila Ben Slimane, Rene' Schott, Ye Qiong Song, G. Stacey Staples, Evangelia Tsiontsiou

SIUE Faculty Research, Scholarship, and Creative Activity

Classical approaches to multi-constrained routing problems generally require construction of trees and the use of heuristics to prevent combinatorial explosion. Introduced here is the notion of constrained path algebras and their application to multi-constrained path problems. The inherent combinatorial properties of these algebras make them useful for routing problems by implicitly pruning the underlying tree structures. Operator calculus (OC) methods are generalized to multiple non-additive constraints in order to develop algorithms for the multi constrained path problem and multi constrained optimization problem. Theoretical underpinnings are developed first, then algorithms are presented. These algorithms demonstrate the tremendous simplicity, flexibility and speed …

Singular Value Computation And Subspace Clustering, Qiao Liang

Theses and Dissertations--Mathematics

In this dissertation we discuss two problems. In the first part, we consider the problem of computing a few extreme eigenvalues of a symmetric definite generalized eigenvalue problem or a few extreme singular values of a large and sparse matrix. The standard method of choice of computing a few extreme eigenvalues of a large symmetric matrix is the Lanczos or the implicitly restarted Lanczos method. These methods usually employ a shift-and-invert transformation to accelerate the speed of convergence, which is not practical for truly large problems. With this in mind, Golub and Ye proposes an inverse-free preconditioned Krylov subspace method, …

Intersection Of Art And Science, Petronio Bendito, Tim Korb

Lawson Building Exhibitions on the Intersection of Art and Science

The Intersection of Art and Science exhibition is an interdisciplinary educational project that examines a wide range of expressive approaches explored by international artists working at the intersection of art, mathematics, computer science, and technology. It is a joint collaboration between the Department of Computer Science and the Patti and Rusty Rueff School of Visual and Performing Arts at Purdue University. Featured artists: Sergio Albiac, Anne Burns, Conan Chadbourne, Hans Dehlinger, Brian Evans, Richard Hassell, Patrick Bingham-Hall, John Arden Hiigli, So Yoon Lym, Gabriel Meyer, and Robert M. Spann. The exhibition was curated by Dr. Petronio Bendito and Dr. Tim …

Parameters Estimation Of Material Constitutive Models Using Optimization Algorithms, Kiswendsida Jules Kere

Williams Honors College, Honors Research Projects

Optimization Algorithms are very useful for solving engineering problems. Indeed, optimization algorithms can be used to optimize engineering designs in terms of safety and economy. Understanding the proprieties of materials in engineering designs is very important in order to make designs safe. Materials are not really perfectly homogeneous and there are heterogeneous distributions in most materials. In this paper, Self-OPTIM which is an inverse constitutive parameter identification framework will be used to identify parameters of a linear elastic material constitutive model. Data for Self-OPTIM will be obtained using ABAQUS simulation of a dog-bone uniaxial test. Optimization Algorithms will be used …

What Is Answer Set Programming To Propositional Satisfiability, Yuliya Lierler

Computer Science Faculty Publications

Propositional satisfiability (or satisfiability) and answer set programming are two closely related subareas of Artificial Intelligence that are used to model and solve difficult combinatorial search problems. Satisfiability solvers and answer set solvers are the software systems that find satisfying interpretations and answer sets for given propositional formulas and logic programs, respectively. These systems are closely related in their common design patterns. In satisfiability, a propositional formula is used to encode problem specifications in a way that its satisfying interpretations correspond to the solutions of the problem. To find solutions to a problem it is then sufficient to use a …

Hash-Map-Eradicator: Filtering Non-Target Sequences From Next Generation Sequencing Reads, Jonathon Brenner, Catherine Putonti

Bioinformatics Faculty Publications

Contemporary DNA sequencing technologies are continuously increasing throughput at ever decreasing costs. Moreover, due to recent advances in sequencing technology new platforms are emerging. As such computational challenges persist. The average read length possible has taken a giant leap forward with the PacBio and Nanopore solutions. Regardless of the platform used, impurities within the DNA preparation of the sample - be it from unintentional contaminants or pervasive symbiots - remains an issue. We have developed a new tool, HAsh-MaP-ERadicator (HAMPER), for the detection and removal of non-target, contaminating DNA sequences. Integrating hash-based and mapping-based strategies, HAMPER is both memory and …