The present thesis focuses on the design and analysis of randomized algorithms for accelerating several linear algebraic tasks. In particular, we develop simple, efficient, randomized algorithms for a plethora of fundamental linear algebraic tasks and we also demonstrate their usefulness and applicability to matrix computations and graph theoretic problems. The thesis can be divided into three parts. The first part concentrates on the development of randomized linear algebraic primitives, the second part demonstrates the application of such primitives to matrix computations, and the last part discusses the application of such primitives to graph problems. First, we present randomized approximation algorithms for the problems of matrix multiplication, orthogonal projection, vector orthonormalization and principal angles computation (a.k.a. canonical correlation analysis). Second, utilizing the tools developed in the first part, we present randomized and provable accurate approximation algorithms for the problems of linear regression and element-wise matrix sparsification. Moreover, we present an efficient deterministic algorithm for selecting a small subset of vectors that are in isotropic position. Finally, we exploit well-known interactions between linear algebra and spectral graph theory to develop and analyze graph algorithms. In particular, we present a near-optimal time deterministic construction of expanding Cayley graphs, an efficient deterministic algorithm for graph sparsification and a randomized distributed Laplacian solver that operates under the gossip model of computation.

In the publish/subscribe paradigm, information providers disseminate publications to all consumers who have expressed interest by registering subscriptions. This paradigm has found wide-spread applications, ranging from selective information dissemination to network management. However, all existing publish/subscribe systems cannot capture uncertainty inherent to the information in either subscriptions or publications. In many situations the large number of data sources exhibit various kinds of uncertainties. Examples of imprecision include: exact knowledge to either specify subscriptions or publications is not available; the match between a subscription and a publication with uncertain data is approximate; the constraints used to define a match is not only content based, but also take the semantic information into consideration. All these kinds of uncertainties have not received much attention in the context of publish/subscribe systems. In this thesis, we propose new publish/subscribe models to express uncertainties and semantics in publications and subscriptions, along with the matching semantics for each model. We also develop efficient algorithms to perform filtering for our models so that it can be applied to process the rapidly increasing information on the Internet. A thorough experimental evaluation is presented to demonstrate that the proposed systems can offer scalability to large number of subscribers and high publishing rates.

The goal of this research is to improve the breast cancer screening process based on magnetic resonance imaging (MRI). In a typical MRI breast examination, a radiologist is responsible for visually examining the MR images acquired during the examination and identifying suspect tissues for biopsy. It is known that if multiple radiologists independently analyze the same examinations and we biopsy any lesion that any of our radiologists flagged as suspicious then the overall screening process becomes more sensitive but less specific. Unfortunately cost factors prohibit the use of multiple radiologists for the screening of every breast MR examination. It is thought that instead of having a second expert human radiologist to examine each set of images, that the act of second reading of the examination can be performed by a computer-aided detection and diagnosis system. The research presented in this thesis is focused on the development of a computer-aided detection and diagnosis system for breast cancer screening from dynamic contrast-enhanced magnetic resonance imaging examinations. This thesis presents new computational techniques in supervised learning, unsupervised learning and classifier visualization. The techniques have been applied to breast MR lesion data and have been shown to outperform existing methods yielding a computer aided detection and diagnosis system with a sensitivity of 89% and a specificity of 70%.

Recurrent Neural Networks (RNNs) are powerful sequence models that were believed to be difficult to train, and as a result they were rarely used in machine learning applications. This thesis presents methods that overcome the difficulty of training RNNs, and applications of RNNs to challenging problems. We first describe a new probabilistic sequence model that combines Restricted Boltzmann Machines and RNNs. The new model is more powerful than similar models while being less difficult to train. Next, we present a new variant of the Hessian-free (HF) optimizer and show that it can train RNNs on tasks that have extreme long-range temporal dependencies, which were previously considered to be impossibly hard. We then apply HF to character-level language modelling and get excellent results. We also apply HF to optimal control and obtain RNN control laws that can successfully operate under conditions of delayed feedback and unknown disturbances. Finally, we describe a random parameter initialization scheme that allows gradient descent with momentum to train RNNs on problems with long-term dependencies. This directly contradicts widespread beliefs about the inability of first-order methods to do so, and suggests that previous attempts at training RNNs failed partly due to flaws in the random initialization.

One central question in theoretical computer science is how to solve problems accurately and quickly. Despite the encouraging development of various algorithmic techniques in the past, we are still at the very beginning of the understanding of these techniques. One particularly interesting paradigm is the greedy algorithm paradigm. Informally, a greedy algorithm builds a solution to a problem incrementally by making locally optimal decisions at each step. Greedy algorithms are important in algorithm design as they are natural, conceptually simple to state and usually efficient. Despite wide applications of greedy algorithms in practice, their behaviour is not well understood. However, we do know that in several specific settings, greedy algorithms can achieve good results. This thesis focuses on examining contexts in which greedy and greedy-like algorithms are successful, and extending them to more general settings. In particular, we investigate structural properties of graphs and set systems, families of special functions, and greedy approximation algorithms for several classic NP-hard problems in those contexts. A natural phenomenon we observe is a trade-off between the approximation ratio and the generality of those contexts.

The present thesis focuses on the design and analysis of randomized algorithms for accelerating several linear algebraic tasks. In particular, we develop simple, efficient, randomized algorithms for a plethora of fundamental linear algebraic tasks and we also demonstrate their usefulness and applicability to matrix computations and graph theoretic problems. The thesis can be divided into three parts. The first part concentrates on the development of randomized linear algebraic primitives, the second part demonstrates the application of such primitives to matrix computations, and the last part discusses the application of such primitives to graph problems. First, we present randomized approximation algorithms for the problems of matrix multiplication, orthogonal projection, vector orthonormalization and principal angles computation (a.k.a. canonical correlation analysis). Second, utilizing the tools developed in the first part, we present randomized and provable accurate approximation algorithms for the problems of linear regression and element-wise matrix sparsification. Moreover, we present an efficient deterministic algorithm for selecting a small subset of vectors that are in isotropic position. Finally, we exploit well-known interactions between linear algebra and spectral graph theory to develop and analyze graph algorithms. In particular, we present a near-optimal time deterministic construction of expanding Cayley graphs, an efficient deterministic algorithm for graph sparsification and a randomized distributed Laplacian solver that operates under the gossip model of computation.

This thesis proposes a automated test case generation technique for the aim of verifying/debugging High-level synthesis (HLS) tools. The work in this thesis builds a framework that automatically generates random programs with user specified features. These programs are used to verify the correctness of the compiled hardware by comparing the hardware simulation results with the software execution results. This way, users can have a large number of benchmarks to test their algorithms for HLS without having to manually develop test programs. The tool also provides additional ways of analyzing performance of HLS tools. Rather than being a replacement, this technique should serve as a useful complement to existing manually constructed test suites. Together, they can provide more comprehensive verification and analysis for HLS tools.

Protein function is the ultimate expression of the genetic code of every organism, and determining which proteins interact helps reveal their functions. MatrixMatchMaker (MMM) is a computational method of predicting protein-protein interactions that works by detecting co-evolution between pairs of proteins. Although MMM has several advanced features compared to other co-evolution-based methods, these come at the cost of high computation, and so the goal of this research is to improve the performance of MMM. First we redefine the computational problem posed by the method, and then develop a new algorithm to solve it, achieving a total speedup of 570x over the existing MMM algorithm for a biologically meaningful data set. We also develop hardware which has not yet succeeded in further improving the performance of MMM, but could serve as a platform that could lead to further gains.

Program verification is vital as more and more users are creating, downloading and executing foreign computer programs. Software verification tools provide a means for determining if a program adheres to a user’s security requirements, or security policy. There are many verification tools that exist for checking different types of policies on different types of programs. Currently however, there is no verification tool capable of determining if all types of programs satisfy all types of policies. This thesis describes a framework for supporting multiple verification tools to determine program satisfaction. A user’s security requirements are represented at multiple levels of abstraction as Intermediate Execution Environments. Using a sequence of configurations, a user’s security requirements are transformed from the abstract level to the tool level, possibly for multiple verification tools. Using a number of case studies, the validity of the framework is shown.

Master of Science / Department of Computing and Information Sciences / Daniel Andresen / Android balloon game application is an android application which helps in improving the children’s vocabulary power. This application provides a graphical user interface with words as questions and balloons as the options. The end user will have to select a balloon in order to select an answer. There are three modules in this application which are game mode, new game and high scores. In the basic module questions like Alpha_bet are included. Also as an enhancement, the game is made interesting by giving the user three lives to clear the levels of the game. Three small balloons are included in the application which resemble the three lives and once an incorrect answer is selected, the green balloon will be replaced by a red balloon depicting an incorrect answer. Also the scores will be computed for every correct option that is selected by the user. The score is incremented by ten points for every correct answer. And for the high score section, the game would maintain the list of top players. High score section will consist of the user’s name, score, time and date for the gameplay. Apart from that a next button is included which helps the user to skip a word which the user finds it difficult to answer. A hint option is also provided in the game which pronounces the word helping the user to guess the word correctly.