Theory and Algorithms Commons^™

Quantum Random Walk Search And Grover's Algorithm - An Introduction And Neutral-Atom Approach, Anna Maria Houk

Physics

In the sub-field of quantum algorithms, physicists and computer scientist take classical computing algorithms and principles and see if there is a more efficient or faster approach implementable on a quantum computer, i.e. a ”quantum advantage”. We take random walks, a widely applicable group of classical algorithms, and move them into the quantum computing paradigm. Additionally, an introduction to a popular quantum search algorithm called Grover’s search is included to guide the reader to the development of a quantum search algorithm using quantum random walks. To close the gap between algorithm and hardware, we will look at using neutral-atom (also …

Towards Distributed Node Similarity Search On Graphs, Tianming Zhang, Yunjun Gao, Baihua Zheng, Lu Chen, Shiting Wen, Wei Guo

Research Collection School Of Computing and Information Systems

Node similarity search on graphs has wide applications in recommendation, link prediction, to name just a few. However, existing studies are insufficient due to two reasons: (i) the scale of the real-world graph is growing rapidly, and (ii) vertices are always associated with complex attributes. In this paper, we propose an efficiently distributed framework to support node similarity search on massive graphs, which considers both graph structure correlation and node attribute similarity in metric spaces. The framework consists of preprocessing stage and query stage. In the preprocessing stage, a parallel KD-tree construction (KDC) algorithm is developed to form a newly …

Evaluating Driving Performance Of A Novel Behavior Planning Model On Connected Autonomous Vehicles, Keyur Shah

Honors Scholar Theses

Many current algorithms and approaches in autonomous driving attempt to solve the "trajectory generation" or "trajectory following” problems: given a target behavior (e.g. stay in the current lane at the speed limit or change lane), what trajectory should the vehicle follow, and what inputs should the driving agent apply to the throttle and brake to achieve this trajectory? In this work, we instead focus on the “behavior planning” problem—specifically, should an autonomous vehicle change lane or keep lane given the current state of the system?

In addition, current theory mainly focuses on single-vehicle systems, where vehicles do not communicate with …

Accelerating The Information-Theoretic Approach Of Community Detection Using Distributed And Hybrid Memory Parallel Schemes, Md Abdul Motaleb Faysal

LSU New Orleans Theses and Dissertations

There are several approaches for discovering communities in a network (graph). Despite being approximating in nature, discovering communities based on the laws of Information Theory has a proven standard of accuracy. The information-theoretic algorithm known as Infomap developed a decade ago for detecting communities, did not foresee the tremendous growth of social networking, multimedia, and massive information boom. To discover communities in massive networks, we have designed a distributed-memory-parallel Infomap in the MPI framework. Our design reaches scalability of over 500 processes capable of processing networks with millions of edges while maintaining quality comparable to the sequential Infomap. We have …

Higher-Order Link Prediction Using Graph Embeddings, Neeraj Chavan

Master's Projects

Link prediction is an emerging field that predicts if two nodes in a network are likely to be connected or not in the near future. Networks model real-world systems using pairwise interactions of nodes. However, many of these interactions may involve more than two nodes or entities simultaneously. For example, social interactions often occur in groups of people, research collaborations are among more than two authors, and biological networks describe interactions of a group of proteins. An interaction that consists of more than two entities is called a higher-order structure. Predicting the occurrence of such higher-order structures helps us solve …

Rehearsal Scheduling Problem, Thuan Bao

Master's Projects

Scheduling is a common task that plays a crucial role in many industries such as manufacturing or servicing. In a competitive environment, effective scheduling is one of the key factors to reduce cost and increase productivity. Therefore, scheduling problems have been studied by many researchers over the past thirty years. Rehearsal scheduling problem (RSP) is similar to the popular resource-constrained project scheduling problem (RCPSP); however, it does not have activity precedence constraints and the resources’ availabilities are not fixed during processing time. RSP can be used to schedule rehearsal in theatre industry or to schedule group scheduling when each member …

Graphical Representation Of Text Semantics, Karl Kevin Tiba Fossoh

Master of Science in Computer Science Theses

A text is a set of words conveying a particular semantic based on their order, representation and structure. Those elements can be associated through a different set of interpretations, based on frequency and proportionality. The problem with context is that numbers do not help understand the semantics and fall short to convey the message of the text. The graphical representation of text semantics focuses on the conversion of text to images. Contrarily to word clouds that simply produce frequency mapping of words within the text and topic models that essentially give context to word frequencies and proportionalities, images keep intact …

Csp-Completeness And Its Applications, Alexander Durgin

McKelvey School of Engineering Graduate Student Theses & Dissertations

We build off of previous ideas used to study both reductions between CSPrefutation problems and improper learning and between CSP-refutation problems themselves to expand some hardness results that depend on the assumption that refuting random CSP instances are hard for certain choices of predicates (like k-SAT). First, we are able argue the hardness of the fundamental problem of learning conjunctions in a one-sided PAC-esque learning model that has appeared in several forms over the years. In this model we focus on producing a hypothesis that foremost guarantees a small false-positive rate while minimizing the false-negative rate for such hypotheses. Further, …

Voxel Optimization, Scott Bengs

Student Academic Conference

Voxel Optimization This poster presentation covers optimization for voxels. They can be thought of as three dimensional pixels. Vo coming from volume and xel from pixel. Voxels are just values placed in a 3D grid. Voxels have many interesting uses in the medical and scientific field, especially in geology. One use in computer science is storing world information for video games or graphical applications. One very popular example is Minecraft, a game that allows all of the world to be changed, that uses cube shaped voxels. The first topic will be on the naive approach of building a model from …

The Theory Of Cryptography In Bitcoin, Can Hong

Mathematics Senior Capstone Papers

Bitcoin is a well known virtual currency, or cryptocurrency. It was created by a group of people using the name Satoshi Nakamoto in 2008. Currently, many people are utilizing Bitcoin for personal gains and transactions. To keep transactions secure requires techniques from modern cryptography. In this paper, we explain certain aspects of the cryptography of Bitcoin. We are going to discuss two components of the cryptography of Bitcoin—hash functions and signatures. We will describe what the hash function and signature are, give some examples of hash functions, and discuss certain criteria that good hash functions should satisfy.

Predictive Modeling Of Asynchronous Event Sequence Data, Jin Shang

LSU Doctoral Dissertations

Large volumes of temporal event data, such as online check-ins and electronic records of hospital admissions, are becoming increasingly available in a wide variety of applications including healthcare analytics, smart cities, and social network analysis. Those temporal events are often asynchronous, interdependent, and exhibiting self-exciting properties. For example, in the patient's diagnosis events, the elevated risk exists for a patient that has been recently at risk. Machine learning that leverages event sequence data can improve the prediction accuracy of future events and provide valuable services. For example, in e-commerce and network traffic diagnosis, the analysis of user activities can be …

Generating Acoustic Projections Using 3d Models, Jake A. Brazelton

Senior Honors Projects, 2020-current

Raytracing is used in commercial graphics engines most commonly for lighting effects, but it also has many uses when it comes to acoustic simulation. Adopted directly from these computer graphics programs, the formulas presented herein enable the visualization of acoustic intensity levels throughout a 3D space using Python 3 and the OpenGL library. In addition to visualization, they also provide the ability to calculate the reverberation time and critical distance of an enclosed space in relation to its size and material makeup. The described application bundles all of these components together in a Qt5 application that allows users to view …

Applying Imitation And Reinforcement Learning To Sparse Reward Environments, Haven Brown

Computer Science and Computer Engineering Undergraduate Honors Theses

The focus of this project was to shorten the time it takes to train reinforcement learning agents to perform better than humans in a sparse reward environment. Finding a general purpose solution to this problem is essential to creating agents in the future capable of managing large systems or performing a series of tasks before receiving feedback. The goal of this project was to create a transition function between an imitation learning algorithm (also referred to as a behavioral cloning algorithm) and a reinforcement learning algorithm. The goal of this approach was to allow an agent to first learn to …

On The Explanation And Implementation Of Three Open-Source Fully Homomorphic Encryption Libraries, Alycia Carey

Computer Science and Computer Engineering Undergraduate Honors Theses

While fully homomorphic encryption (FHE) is a fairly new realm of cryptography, it has shown to be a promising mode of information protection as it allows arbitrary computations on encrypted data. The development of a practical FHE scheme would enable the development of secure cloud computation over sensitive data, which is a much-needed technology in today's trend of outsourced computation and storage. The first FHE scheme was proposed by Craig Gentry in 2009, and although it was not a practical implementation, his scheme laid the groundwork for many schemes that exist today. One main focus in FHE research is the …

Heuristics For Sparsest Cut Approximations In Network Flow Applications, Fernando Vilas

Computer Science and Engineering Theses and Dissertations

The Maximum Concurrent Flow Problem (MCFP) is a polynomially bounded problem that has been used over the years in a variety of applications. Sometimes it is used to attempt to find the Sparsest Cut, an NP-hard problem, and other times to find communities in Social Network Analysis (SNA) in its hierarchical formulation, the HMCFP. Though it is polynomially bounded, the MCFP quickly grows in space utilization, rendering it useful on only small problems. When it was defined, only a few hundred nodes could be solved, where a few decades later, graphs of one to two thousand nodes can still be …

Shakespeare In The Eighteenth Century: Algorithm For Quotation Identification, Marion Pauline Chiariglione

Graduate Theses and Dissertations

Quoting a borrowed excerpt of text within another literary work was infrequently done prior to the beginning of the eighteenth century. However, quoting other texts, particularly Shakespeare, became quite common after that. Our work develops automatic approaches to identify that trend. Initial work focuses on identifying exact and modified sections of texts taken from works of Shakespeare in novels spanning the eighteenth century. We then introduce a novel approach to identifying modified quotes by adapting the Edit Distance metric, which is character based, to a word based approach. This paper offers an introduction to previous uses of this metric within …

Dependency Mapping Software For Jira, Project Management Tool, Bentley Lager

Computer Science and Computer Engineering Undergraduate Honors Theses

Efficiently managing a software development project is extremely important in industry and is often overlooked by the software developers on a project. Pieces of development work are identified by developers and are then handed off to project managers, who are left to organize this information. Project managers must organize this to set expectations for the client, and ensure the project stays on track and on budget. The main block in this process are dependency chains between tasks. Dependency chains can cause a project to take much longer than anticipated or result in the under utilization of developers on a project. …

Achieving Causal Fairness In Machine Learning, Yongkai Wu

Graduate Theses and Dissertations

Fairness is a social norm and a legal requirement in today's society. Many laws and regulations (e.g., the Equal Credit Opportunity Act of 1974) have been established to prohibit discrimination and enforce fairness on several grounds, such as gender, age, sexual orientation, race, and religion, referred to as sensitive attributes. Nowadays machine learning algorithms are extensively applied to make important decisions in many real-world applications, e.g., employment, admission, and loans. Traditional machine learning algorithms aim to maximize predictive performance, e.g., accuracy. Consequently, certain groups may get unfairly treated when those algorithms are applied for decision-making. Therefore, it is an imperative …

Robust Graph Learning From Noisy Data, Zhao Kang, Haiqi Pan, Steven C. H. Hoi, Zenglin Xu

Research Collection School Of Computing and Information Systems

Learning graphs from data automatically have shown encouraging performance on clustering and semisupervised learning tasks. However, real data are often corrupted, which may cause the learned graph to be inexact or unreliable. In this paper, we propose a novel robust graph learning scheme to learn reliable graphs from the real-world noisy data by adaptively removing noise and errors in the raw data. We show that our proposed model can also be viewed as a robust version of manifold regularized robust principle component analysis (RPCA), where the quality of the graph plays a critical role. The proposed model is able to …

A Matheuristic Algorithm For Solving The Vehicle Routing Problem With Cross-Docking, Aldy Gunawan, Audrey Tedja Widjaja, Pieter Vansteenwegen, Vincent F. Yu

Research Collection School Of Computing and Information Systems

This paper studies the integration of the vehicle routing problem with cross-docking, namely VRPCD. The aim is to find a set of routes to deliver single products from a set of suppliers to a set of customers through a cross-dock facility, such that the operational and transportation costs are minimized, without violating the vehicle capacity and time horizon constraints. A two-phase matheuristic approach that uses the routes of the local optima of an adaptive large neighborhood search (ALNS) as columns in a set-partitioning formulation of the VRPCD is designed. This matheuristic outperforms the state-of-the-art algorithms in solving a subset of …

Advancing Performance Of Retail Recommendation Systems, Lisa Leininger, Johnny Gipson, Kito Patterson, Brad Blanchard

SMU Data Science Review

This paper presents two recommendation models, one traditional and one novel, for a retail men's clothing company. J. Hilburn is a custom-fit, menswear clothing company headquartered in Dallas, Texas. J. Hilburn employs stylists across the United States, who engage directly with customers to assist in selecting clothes that fit their size and style. J. Hilburn tasked the authors of this paper to leverage data science techniques to the given data set to provide stylists with more insight into clients’ purchase patterns and increase overall sales. This paper presents two recommendation systems which provide stylists with automatic predictions about possible clothing …

Improving Syntactic Relationships Between Language And Objects, Benjamin Wilke, Tej Tenmattam, Anand Rajan, Andrew Pollock, Joel Lindsey

SMU Data Science Review

This paper presents the integration of natural language processing and computer vision to improve the syntax of the language generated when describing objects in images. The goal was to not only understand the objects in an image, but the interactions and activities occurring between the objects. We implemented a multi-modal neural network combining convolutional and recurrent neural network architectures to create a model that can maximize the likelihood of word combinations given a training image. The outcome was an image captioning model that leveraged transfer learning techniques for architecture components. Our novelty was to quantify the effectiveness of transfer learning …

Data-Driven Investment Decisions In P2p Lending: Strategies Of Integrating Credit Scoring And Profit Scoring, Yan Wang

Doctor of Data Science and Analytics Dissertations

In this dissertation, we develop and discuss several loan evaluation methods to guide the investment decisions for peer-to-peer (P2P) lending. In evaluating loans, credit scoring and profit scoring are the two widely utilized approaches. Credit scoring aims at minimizing the risk while profit scoring aims at maximizing the profit. This dissertation addresses the strengths and weaknesses of each scoring method by integrating them in various ways in order to provide the optimal investment suggestions for different investors. Before developing the methods for loan evaluation at the individual level, we applied the state-of-the-art method called the Long Short Term Memory (LSTM) …

Philosophical Perspectives, Jochen Albrecht

Publications and Research

This entry follows in the footsteps of Anselin’s famous 1989 NCGIA working paper entitled “What is special about spatial?” (a report that is very timely again in an age when non-spatial data scientists are ignorant of the special characteristics of spatial data), where he outlines three unrelated but fundamental characteristics of spatial data. In a similar vein, I am going to discuss some philosophical perspectives that are internally unrelated to each other and could warrant individual entries in this Body of Knowledge. The first one is the notions of space and time and how they have evolved in …

Nonlinear Least Squares 3-D Geolocation Solutions Using Time Differences Of Arrival, Michael V. Bredemann

Mathematics & Statistics ETDs

This thesis uses a geometric approach to derive and solve nonlinear least squares minimization problems to geolocate a signal source in three dimensions using time differences of arrival at multiple sensor locations. There is no restriction on the maximum number of sensors used. Residual errors reach the numerical limits of machine precision. Symmetric sensor orientations are found that prevent closed form solutions of source locations lying within the null space. Maximum uncertainties in relative sensor positions and time difference of arrivals, required to locate a source within a maximum specified error, are found from these results. Examples illustrate potential requirements …

Fast Clustering Using A Grid-Based Underlying Density Function Approximation, Daniel Brown

Master of Science in Computer Science Theses

Clustering is an unsupervised machine learning task that seeks to partition a set of data into smaller groupings, referred to as “clusters”, where items within the same cluster are somehow alike, while differing from those in other clusters. There are many different algorithms for clustering, but many of them are overly complex and scale poorly with larger data sets. In this paper, a new algorithm for clustering is proposed to solve some of these issues. Density-based clustering algorithms use a concept called the “underlying density function”, which is a conceptual higher-dimension function that describes the possible results from the continuous …

Achieving Obfuscation Through Self-Modifying Code: A Theoretical Model, Heidi Waddell

Senior Honors Theses

With the extreme amount of data and software available on networks, the protection of online information is one of the most important tasks of this technological age. There is no such thing as safe computing, and it is inevitable that security breaches will occur. Thus, security professionals and practices focus on two areas: security, preventing a breach from occurring, and resiliency, minimizing the damages once a breach has occurred. One of the most important practices for adding resiliency to source code is through obfuscation, a method of re-writing the code to a form that is virtually unreadable. …

Storage Management Strategy In Mobile Phones For Photo Crowdsensing, En Wang, Zhengdao Qu, Xinyao Liang, Xiangyu Meng, Yongjian Yang, Dawei Li, Weibin Meng

Department of Computer Science Faculty Scholarship and Creative Works

In mobile crowdsensing, some users jointly finish a sensing task through the sensors equipped in their intelligent terminals. In particular, the photo crowdsensing based on Mobile Edge Computing (MEC) collects pictures for some specific targets or events and uploads them to nearby edge servers, which leads to richer data content and more efficient data storage compared with the common mobile crowdsensing; hence, it has attracted an important amount of attention recently. However, the mobile users prefer uploading the photos through Wifi APs (PoIs) rather than cellular networks. Therefore, photos stored in mobile phones are exchanged among users, in order to …

Feature Extraction And Analysis Of Binaries For Classification, Micah Flack

Annual Research Symposium

The research project, Feature Extraction and, Analysis of Binaries for Classification, provides an in-depth examination of the features shared by unlabeled binary samples, for classification into the categories of benign or malicious software using several different methods. Because of the time it takes to manually analyze or reverse engineer binaries to determine their function, the ability to gather features and then instantly classify samples without explicitly programming the solution is incredibly valuable. It is possible to use an online service; however, this is not always viable depending on the sensitivity of the binary. With Python3 and the Pefile library, we …

Cylindrical Similarity Measurement For Helices In Medium-Resolution Cryo-Electron Microscopy Density Maps, Salim Sazzed, Peter Scheible, Maytha Alshammari, Willy Wriggers, Jing He

College of Sciences Posters

Cryo-electron microscopy (cryo-EM) density maps at medium resolution (5-10 Å) reveal secondary structural features such as α-helices and β-sheets, but they lack the side chains details that would enable a direct structure determination. Among the more than 800 entries in the Electron Microscopy Data Bank (EMDB) of medium-resolution density maps that are associated with atomic models, a wide variety of similarities can be observed between maps and models. To validate such atomic models and to classify structural features, a local similarity criterion, the F1 score, is proposed and evaluated in this study. The F1 score is theoretically normalized to a …