Open Access. Powered by Scholars. Published by Universities.®

Theory and Algorithms Commons

Open Access. Powered by Scholars. Published by Universities.®

1177 Full-Text Articles 1398 Authors 234518 Downloads 90 Institutions

All Articles in Theory and Algorithms

Faceted Search

1177 full-text articles. Page 1 of 42.

Vertex Weighted Spectral Clustering, Mohammad Masum 2017 East Tennessee State University

Vertex Weighted Spectral Clustering, Mohammad Masum

Electronic Theses and Dissertations

Spectral clustering is often used to partition a data set into a specified number of clusters. Both the unweighted and the vertex-weighted approaches use eigenvectors of the Laplacian matrix of a graph. Our focus is on using vertex-weighted methods to refine clustering of observations. An eigenvector corresponding with the second smallest eigenvalue of the Laplacian matrix of a graph is called a Fiedler vector. Coefficients of a Fiedler vector are used to partition vertices of a given graph into two clusters. A vertex of a graph is classified as unassociated if the Fiedler coefficient of the vertex is close to ...


An Analysis Of The Application Of Simplified Silhouette To The Evaluation Of K-Means Clustering Validity, Hector-Hugo Franco-Penya, John D. Kelleher, John Pugh, Robert Ross 2017 Dublin Institute of Technology

An Analysis Of The Application Of Simplified Silhouette To The Evaluation Of K-Means Clustering Validity, Hector-Hugo Franco-Penya, John D. Kelleher, John Pugh, Robert Ross

Conference papers

Silhouette is one of the most popular and effective internal measures for the evaluation of clustering validity. Simplified Silhouette is a computationally simplified version of Silhouette. However, to date Simplified Silhouette has not been systematically analysed in a specific clustering algorithm. This paper analyses the application of Simplified Silhouette to the evaluation of k-means clustering validity and compares it with the k-means Cost Function and the original Silhouette from both theoretical and empirical perspectives. The theoretical analysis shows that Simplified Silhouette has a mathematical relationship with both the k-means Cost Function and the original Silhouette, while empirically, we show that ...


Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg 2017 Loyola University Chicago

Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

Magic tricks based on computer science concepts help grab student attention and can motivate them to delve more deeply. Error detection ideas long used by computer scientists provide a rich basis for working magic; probably the most well known trick of this type is one included in the CS Unplugged activities. This paper shows that much more powerful variations of the trick can be performed, some in an unplugged environment and some with computer assistance. Some of the tricks also show off additional concepts in computer science and discrete mathematics.


Game Specific Approaches To Monte Carlo Tree Search For Dots And Boxes, Jared Prince 2017 Western Kentucky University

Game Specific Approaches To Monte Carlo Tree Search For Dots And Boxes, Jared Prince

Honors College Capstone Experience/Thesis Projects

In this project, a Monte Carlo tree search player was designed and implemented for the child’s game dots and boxes, the computational burden of which has left traditional artificial intelligence approaches like minimax ineffective. Two potential improvements to this player were implemented using game-specific information about dots and boxes: the lack of information for decision-making provided by the net score and the inherent symmetry in many states. The results of these two approaches are presented, along with details about the design of the Monte Carlo tree search player. The first improvement, removing net score from the state information, was ...


Quo Vadis-A Framework For Intelligent Routing In Large Communication Networks., Armin Mikler, Johnny S. Wong, Vasant Honavar 2017 Iowa State University

Quo Vadis-A Framework For Intelligent Routing In Large Communication Networks., Armin Mikler, Johnny S. Wong, Vasant Honavar

Johnny Wong

This paper presents Quo Vadis, an evolving framework for intelligent traffic management in very large communication networks. Quo Vadis is designed to exploit topological properties of large networks as well as their spatio-temporal dynamics to optimize multiple performance criteria through cooperation among nodes in the network. It employs a distributed representation of network state information using local load measurements supplemented by a less precise global summary. Routing decisions in Quo Vadis are based on parameterized heuristics designed to optimize various performance metrics in an anticipatory or pro-active as well as compensatory or reactive mode and to minimize the overhead associated ...


Tree-Based Algorithm To Find The K-Th Value In Distributed Systems, Yoonsik Cheon, Johnny S. Wong 2017 Iowa State University

Tree-Based Algorithm To Find The K-Th Value In Distributed Systems, Yoonsik Cheon, Johnny S. Wong

Johnny Wong

In this paper, we study distributed algorithms for finding the k-th value in the decentralized systems. First we consider the case of circular configuration of processors where no processor knows the total number of participants. Later a network of arbitrary configuration is examined and a tree-based algorithm is proposed. The proposed algorithm requires O(N) messages and O(log N) rounds of message passing, where N is the number of nodes in the network.


Utility-Theoretic Heuristics For Intelligent Adaptive Routing In Large Communcation Networks, Armin Mikler, Vasant Honavar, Johnny S. Wong 2017 Iowa State University

Utility-Theoretic Heuristics For Intelligent Adaptive Routing In Large Communcation Networks, Armin Mikler, Vasant Honavar, Johnny S. Wong

Johnny Wong

Utility theory offers an elegant and powerful theoretical framework for design and analysis of autonomous adaptive communication networks. Routing of messages in such networks presents a real-time instance of a multi-criterion quasi-optimization problem in a dynamic and uncertain environment. In this paper, we examine several heuristic decision functions that can be used to guide messages along a near-optimal (e.g., minimum delay) path in a large network. We present an analysis of properties of such heuristics under a set of simplifying assumptions about the network topology and load dynamics. In particular, we identify the conditions under which one such utility-theoretic ...


Encryption Backdoors: A Discussion Of Feasibility, Ethics, And The Future Of Cryptography, Jennifer A. Martin 2017 Seattle Pacific University

Encryption Backdoors: A Discussion Of Feasibility, Ethics, And The Future Of Cryptography, Jennifer A. Martin

Honors Projects

In the age of technological advancement and the digitization of information, privacy seems to be all but an illusion. Encryption is supposed to be the white knight that keeps our information and communications safe from unwanted eyes, but how secure are the encryption algorithms that we use? Do we put too much trust in those that are charged with implementing our everyday encryption systems? This paper addresses the concept of backdoors in encryption: ways that encryption systems can be implemented so that the security can be bypassed by those that know about its existence. Many governments around the world are ...


Neural Network Ai For Fightingice, Alan D. Robison 2017 California Polytechnic State University, San Luis Obispo

Neural Network Ai For Fightingice, Alan D. Robison

Computer Engineering

Game AI in the fighting game genre, along the lines of Street Fighter, Mortal Kombat and Tekken, is traditionally script-based, with hard-coded reactions to various situations. Though this approach is often easy to understand and tweak, it requires substantial time and understanding of the game to implement in a way that is challenging and satisfying for the player due to the very large possibility space. This paper explores the use of neural networks as an alternative approach by implementing and training a network to select an action to take each frame based on the game state.


Community Detection In Social Networks, Ketki Kulkarni 2017 San Jose State University

Community Detection In Social Networks, Ketki Kulkarni

Master's Projects

The rise of the Internet has brought people closer. The number of interactions between people across the globe has gone substantially up due to social awareness, the advancements of the technology, and digital interaction. Social networking sites have built societies, communities virtually. Often these societies are displayed as a network of nodes depicting people and edges depicting relationships, links. This is a good and e cient way to store, model and represent systems which have a complex and rich information. Towards that goal we need to nd e ective, quick methods to analyze social networks. One of the possible solution ...


Influence Detection And Spread Estimation In Social Networks, Madhura Kaple 2017 San Jose State University

Influence Detection And Spread Estimation In Social Networks, Madhura Kaple

Master's Projects

A social network is an online platform, where people communicate and share information with each other. Popular social network features, which make them di erent from traditional communication platforms, are: following a user, re-tweeting a post, liking and commenting on a post etc. Many companies use various social networking platforms extensively as a medium for marketing their products. A xed amount of budget is alloted by the companies to maximize the positive in uence of their product. Every social network consists of a set of users (people) with connections between them. Each user has the potential to extend its in ...


An Improved Algorithm For Learning To Perform Exception-Tolerant Abduction, Mengxue Zhang 2017 Washington University in St Louis

An Improved Algorithm For Learning To Perform Exception-Tolerant Abduction, Mengxue Zhang

Engineering and Applied Science Theses & Dissertations

Abstract

Inference from an observed or hypothesized condition to a plausible cause or explanation for this condition is known as abduction. For many tasks, the acquisition of the necessary knowledge by machine learning has been widely found to be highly effective. However, the semantics of learned knowledge are weaker than the usual classical semantics, and this necessitates new formulations of many tasks. We focus on a recently introduced formulation of the abductive inference task that is thus adapted to the semantics of machine learning. A key problem is that we cannot expect that our causes or explanations will be perfect ...


Algorithmic Factorization Of Polynomials Over Number Fields, Christian Schulz 2017 Rose-Hulman Institute of Technology

Algorithmic Factorization Of Polynomials Over Number Fields, Christian Schulz

Mathematical Sciences Technical Reports (MSTR)

The problem of exact polynomial factorization, in other words expressing a polynomial as a product of irreducible polynomials over some field, has applications in algebraic number theory. Although some algorithms for factorization over algebraic number fields are known, few are taught such general algorithms, as their use is mainly as part of the code of various computer algebra systems. This thesis provides a summary of one such algorithm, which the author has also fully implemented at https://github.com/Whirligig231/number-field-factorization, along with an analysis of the runtime of this algorithm. Let k be the product of the degrees of ...


Computing Limit Points Of Quasi-Components Of Regular Chains And Its Applications, Parisa Alvandi 2017 The University of Western Ontario

Computing Limit Points Of Quasi-Components Of Regular Chains And Its Applications, Parisa Alvandi

Electronic Thesis and Dissertation Repository

Computing limit is a fundamental task in mathematics and different mathematical concepts are defined in terms of limit computations. Among these mathematical concepts, we are interested in three different types of limit computations: first, computing the limit points of solutions of polynomial systems represented by regular chains, second, computing tangent cones of space curves at their singular points which can be viewed as computing limit of secant lines, and third, computing the limit of real multivariate rational functions.

For computing the limit of solutions of polynomial systems represented by regular chains, we present two different methods based on Puiseux series ...


Solving Capacitated Data Storage Placement Problems In Sensor Networks, Zhenfei Wu 2017 The University of Western Ontario

Solving Capacitated Data Storage Placement Problems In Sensor Networks, Zhenfei Wu

Electronic Thesis and Dissertation Repository

Data storage is an important issue in sensor networks as the large amount of data collected by the sensors in such networks needs to be archived for future processing. In this thesis we consider sensor networks in which the information produced by the sensors needs to be collected by storage nodes where the information is compressed and then sent to a central storage node called the sink. We study the problem of selecting k sensors to be used as storage nodes so as to minimize the total cost of sending information from the sensors to the storage nodes and from ...


Washington State Public Teachers' Ambient Positional Instability From A Statistical Approach Of Retrospective Study & Prospective Study, Bowen Cai, Robert Boruch 2017 University of Pennsylvania

Washington State Public Teachers' Ambient Positional Instability From A Statistical Approach Of Retrospective Study & Prospective Study, Bowen Cai, Robert Boruch

GSE Publications

The purpose of this research is to study the movements of teachers’ churn rate in the state of Washington over the past 14 years. The research of teachers’ churn rate is an integrative study, with retrospective part and prospective part. Retrospective study includes the analysis of descriptive statistics (level I), statistical inference (level II) and causal inference (level III) (Berk, R.A. (2016) Statistical Learning from a Regression Perspective. Philadelphia, PA: Springer). Prospective study is mainly about forecasting and statistical inference that generated from the predictions. In this research, we are using longitudinal data analysis. The good point of longitudinal ...


Ds-Pso: Particle Swarm Optimization With Dynamic And Static Topologies, Dominick Sanchez 2017 Bowdoin College

Ds-Pso: Particle Swarm Optimization With Dynamic And Static Topologies, Dominick Sanchez

Honors Projects

Particle Swarm Optimization (PSO) is often used for optimization problems due to its speed and relative simplicity. Unfortunately, like many optimization algorithms, PSO may potentially converge too early on local optima. Using multiple neighborhoods alleviates this problem to a certain extent, although premature convergence is still a concern. Using dynamic topologies, as opposed to static neighborhoods, can encourage exploration of the search space at the cost of exploitation. We propose a new version of PSO, Dynamic-Static PSO (DS-PSO) that assigns multiple neighborhoods to each particle. By using both dynamic and static topologies, DS-PSO encourages exploration, while also exploiting existing knowledge ...


Electrodynamical Modeling For Light Transport Simulation, Michael G. Saunders 2017 East Tennessee State University

Electrodynamical Modeling For Light Transport Simulation, Michael G. Saunders

Undergraduate Honors Theses

Modernity in the computer graphics community is characterized by a burgeoning interest in physically based rendering techniques. That is to say that mathematical reasoning from first principles is widely preferred to ad hoc, approximate reasoning in blind pursuit of photorealism. Thereby, the purpose of our research is to investigate the efficacy of explicit electrodynamical modeling by means of the generalized Jones vector given by Azzam [1] and the generalized Jones matrix given by Ortega-Quijano & Arce-Diego [2] in the context of stochastic light transport simulation for computer graphics. To augment the status quo path tracing framework with such a modeling technique ...


Music Feature Matching Using Computer Vision Algorithms, Mason Hollis 2017 University of Arkansas, Fayetteville

Music Feature Matching Using Computer Vision Algorithms, Mason Hollis

Computer Science and Computer Engineering Undergraduate Honors Theses

This paper seeks to establish the validity and potential benefits of using existing computer vision techniques on audio samples rather than traditional images in order to consistently and accurately identify a song of origin from a short audio clip of potentially noisy sound. To do this, the audio sample is first converted to a spectrogram image, which is used to generate SURF features. These features are compared against a database of features, which have been previously generated in a similar fashion, in order to find the best match. This algorithm has been implemented in a system that can run as ...


Exploiting Contextual Information For Fine-Grained Tweet Geolocation, Wen Haw CHONG, Ee-peng LIM 2017 Singapore Management University

Exploiting Contextual Information For Fine-Grained Tweet Geolocation, Wen Haw Chong, Ee-Peng Lim

Research Collection School Of Information Systems

The problem of fine-grained tweet geolocation is to link tweets to their posting venues. We solve this in a learning to rank framework by ranking candidate venues given a test tweet. The problem is challenging as tweets are short and the vast majority are non-geocoded, meaning information is sparse for building models. Nonetheless, although only a small fraction of tweets are geocoded, we find that they are posted by a substantial proportion of users. Essentially, such users have location history data. Along with tweet posting time, these serve as additional contextual information for geolocation. In designing our geolocation models, we ...


Digital Commons powered by bepress