<p>We investigate the function ρ_<em>d</em>(<em>n</em>) = max { <em>r</em>(<em><strong>x</strong></em>) | <em><strong>x</strong></em> is a (<em>d</em>, <em>n</em>)-string } where <em>r</em>(<em><strong>x</strong></em>) is the number of runs in the string <em><strong>x</strong></em>, and a (<em>d</em>, <em>n</em>)-string is a string with length <em>n</em> and exactly <em>d</em> distinct symbols. Our investigation is motivated by the conjecture that ρ_<em>d</em>(<em>n</em>) ≤ <em>n</em>-<em>d</em>. We present and discuss fundamental properties of the ρ_<em>d</em>(<em>n</em>) function. The values of ρ_<em>d</em>(<em>n</em>) are presented in the (<em>d</em>, <em>n</em>-<em>d</em>)-table with rows indexed by <em>d</em> and columns indexed by <em>n</em>-<em>d</em> which reveals the regularities of the function. We introduce the concepts of the r-cover and core vector of a string, yielding a novel computational framework for determining ρ_<em>d</em>(<em>n</em>) values. The computation of the previously intractable instances is achieved via first computing a lower bound, and then using the structural properties to limit our exhaustive search only to strings that can possibly exceed this number of runs. Using this approach, we extended the known maximum number of runs in binary string from 60 to 74. In doing so, we find the first examples of run-maximal strings containing four consecutive identical symbols. Our framework is also applied for an arbitrary number of distinct symbols, <em>d</em>. For example, we are able to determine that the maximum number of runs in a string with 23 distinct symbols and length 46 is 23. Further, we discuss the structural properties of a shortest (<em>d</em>, <em>n</em>)-string <em><strong>x</strong></em> such that <em>r</em>(<em><strong>x</strong></em>) > <em>n</em>-<em>d</em>, should such a string exist.</p> / Doctor of Philosophy (PhD)

<p>A great variety of algebraic problems can be solved using Groebner bases, and computational commutative algebra is the branch of mathematics that focuses mainly on such problems. In this thesis we employ Buchberger's algorithm for finding Groebner bases by tailoring specialized instances of Buchberger's algorithm via code generation. We introduce a framework for meta programming and code generation in the F# programming language that removes the abstraction overhead of generic programs and produces type-safe and syntactically valid specialized instances of generic programs. Then, we discuss the concept of modularizing and decomposing the architecture of software products through a multistage design process and define what specialization of software means in the context of producing special instances. We provide a domain-specific language for the design of flexible, customizable, multistage programs. Finally, we utilize the aforementioned techniques and framework to produce a highly parametrized, abstract and generative program that finds Groebner bases based on Buchberger's original algorithm, which, given all the proper definitions and features of a specific problem in computational algebra, produces a specialized instance of a solver for this problem that can be shown to be correct and perform within the desired time complexity.</p> / Doctor of Philosophy (PhD)

<p>We study the application of reputation as an instigator of beneficial user behavior in selfish routing and when the network users rely on the network coordinator for information about the network. Instead of using tolls or artificial delays, the network coordinator takes advantage of the users' insufficient data, in order to manipulate them through the information he provides. The issue that arises then is what can be the coordinator's gain without compromising by too much on the trust the users put on the information provided, i.e., by maintaining a reputation for (at least some) trustworthiness.</p> <p>Our main contribution is the modeling of such a system as a repeated game of incomplete information in the case of single-commodity general networks. This allows us to apply known folk-like theorems to get bounds on the price of anarchy that are better than the well-known bounds without information manipulation.</p> / Master of Computer Science (MCS)

<p>Programs have multiple exits in the presence of certain control structures, e.g., exception handling and coroutines. These control structures offer flexible manipulations of control flow. However, their formalizations are overall specialized, which hinders reasoning about combinations of these control structures.</p> <p>In this thesis, we propose a unifying theory of multi-exit programs. We mechanically formalize the semantics of multi-exit programs as indexed predicate transformers, a generalization of predicate transformers by taking the tuple of postconditions on all exits as the parameter. We explore their algebraic properties and verification rules, then define a normal form for monotonic and for conjunctive indexed predicate transformers. We also propose a new notion of fail-safe correctness to model the category of programs that always maintain certain safe conditions when they fail, and a new notion of fail-safe refinement to express partiality in software development.</p> <p>For the indexed predicate transformer formalization, we illustrate its applications in three models of multi-exit control structures: the termination model of exception handling, the retry model of exception handling, and a coroutine model. Additionally, for the fail-safe correctness notion and the fail-safe refinement notion, we illustrate their applications in the termination model. Six design patterns in the termination model and one in the retry model are studied. All the verification rules and design patterns in the thesis have been formally checked by a verification tool.</p> / Doctor of Philosophy (PhD)

<p>We investigate the problem of the maximum number of distinct primitively rooted squares in a string. In comparison to considering general strings, the number of distinct symbols in the string is introduced as an additional parameter of the problem. Let S(d,n) = max {s(x) | x is a (d,n)-string}, where s(x) denotes the number of distinct primitively rooted squares in a string x and a (d,n)-string denotes a string of length n with exactly d distinct symbols.</p> <p>Inspired by the d-step approach which was instrumental in Santos' tackling of the Hirsch conjecture, we introduce a (d,n-d) table with entries S(d,n) where d is the index for the rows and n-d is the index for the columns. We examine the properties of the S(d,n) function in the context of (d,n-d) table and conjecture that the value of S(d,n) is no more than n-d. We present several equivalent properties with the conjecture. We discuss the significance of the main diagonal of the (d,n-d) table, i.e. the square-maximal (d, 2d)-strings for their relevance to the conjectured bound for all strings. We explore their structural properties under both assumptions, complying or not complying with the conjecture, with the intention to derive a contradiction. The result yields novel properties and statements equivalent with the conjecture with computational application to the determination of the values S(d,n).</p> <p>To further populate the (d,n-d) table, we design and implement an efficient computational framework for computing S(d,n). Instead of generating all possible (d,n)-strings as the brute-force approach needs to do, the computational effort is significantly reduced by narrowing down the search space for square-maximal strings. With an easily accessible lower bound obtained either from the previously computed values inductively or by an effective heuristic search, only a relatively small set of candidate strings that might possibly exceed the lower bound is generated. To this end, the notions of s-cover and the density of a string are introduced and utilized. In special circumstances, the computational efficiency can be further improved by starting the s-cover with a double square structure. In addition, we present an auxiliary algorithm that returns the required information including the number of distinct squares for each generated candidate string. This algorithm is a modified version of FJW algorithm, an implementation based on Crochemore's partition algorithm, developed by Franek, Jiang and Weng. As of writing of this thesis, we have been able to obtain the maximum number of distinct squares in binary strings till the length of 70.</p> / Doctor of Philosophy (PhD)

The dissertation proposes, presents and analyzes a new design pattern, the Mutable Class pattern, to support the processing of large-scale heterogeneous data models with multiple families of algorithms. Handling data-algorithm associations represents an important topic across a variety of application domains. As a result, it has been addressed by multiple approaches, including the Visitor pattern and the aspect-oriented programming (AOP) paradigm. Existing solutions, however, bring additional constraints and issues. For example, the Visitor pattern freezes the class hierarchies of application models and the AOP-based projects, such as Spring AOP, introduce significant overhead for processing large-scale models with fine-grain objects. The Mutable Class pattern addresses the limitations of these solutions by providing an alternative approach designed after the Class model of the UML specification. Technically, it extends a data model class with a class mutator supporting the interchangeability of operations. Design patterns represent reusable solutions to recurring problems. According to the design pattern methodology, the definition of these solutions encompasses multiple topics, such as the problem and applicability, structure, collaborations among participants, consequences, implementation aspects, and relation with other patterns. The dissertation provides a formal description of the Mutable Class pattern for processing heterogeneous tree-based models and elaborates on it with a comprehensive analysis in the context of several applications and alternative solutions. Particularly, the commonality of the problem and reusability of this approach is demonstrated and evaluated within two application domains: computational accelerator physics and compiler construction. Furthermore, as a core part of the Unified Accelerator Library (UAL) framework, the scalability boundary of the pattern has been challenged and explored with different categories of application architectures and computational infrastructures including distributed three-tier systems. The Mutable Class pattern targets a common problem arising from software engineering: the evolution of type systems and associated algorithms. Future research includes applying this design pattern in other contexts, such as heterogeneous information networks and large-scale processing platforms, and examining variations and alternative design patterns for solving related classes of problems.

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.

Methods to advance the understanding of water and other aqueous systems are devel- oped. This work falls into three areas: The creation of better interaction potentials for water, improved methods for sampling configurational space, and the applications of these methods to understand systems of interest. Charge transfer has been shown by ab initio methods to be important in the water–water and water–ion interactions. A model for treating charge transfer in liquid water and aqueous systems is presented in this manuscript. The model is called Discrete Charge Transfer (DCT) and is based on the commonly-used TIP4P/2005 model, which represents the charge distribution of water molecules with three charge sites. Such models have been very successful in reproducing many of the physical properties of water. Charge transfer is introduced by transferring a small amount of charge, -0.02e, from the hydrogen bond acceptor to the hydrogen bond donor, as has been indicated by electronic structure calculations. We have parameterized both polarizable and non-polarizable potentials, optimized to include charge transfer. Methods to surmount the obstacles incurred by the introduction of charge transfer, which involve the amount of charge transfer at large distances and implementation into Molecular Dynamics simulation, is presented, along with our results assessing the importance of charge transfer in liquid water and aqueous systems. Also presented is a method for improving eciency of a sampling technique, Replica Exchange, by reducing the number of replicas. The improved method is called Replica Exchange with Driven Scaling (REDS2).

The main aim of the course advising system is to build a course recommendation path for students to help them plan courses to successfully graduate on time. The recommendation path displays the list of courses a student can take in each quarter from the first quarter after admission until the graduation quarter. The courses are filtered as per the student’s interest obtained from a questionnaire asked to the student. The business logic involves building the recommendation algorithm. Also, the application is functionality-tested end-to-end by using nightwatch.js which is built on top of node.js. Test cases are written for every module and implemented while building the application.

This study focuses on implementing a log analysis strategy that combines a neural network algorithm and wavelet transform. Wavelet transform allows us to extract the important hidden information and features of the original time series log data and offers a precise framework for the analysis of input information. While neural network algorithm constitutes a powerfulnonlinear function approximation which can provide detection and prediction functions. The combination of the two techniques is based on the idea of using wavelet transform to denoise the log data by decomposing it into a set of coefficients, then feed the denoised data into a neural network. The experimental outputs reveal that this strategy can have a better ability to identify the patterns among problems in a log dataset, and make predictions with a better accuracy. This strategy can help the platform maintainers to adopt corresponding actions to eliminate risks before the occurrence of serious damages.