Tree-based methods have wide applications for solving large-scale problems in electromagnetics, astrophysics, quantum chemistry, fluid mechanics, acoustics, and many more areas. This thesis focuses on their applicability for solving large-scale problems in electromagnetics. The Barnes-Hut (BH) algorithm and the Fast Multipole Method (FMM) are introduced along with a survey of important previous work. The required theory for applying those methods to problems in electromagnetics is presented with particular emphasis on the capacitance extraction problem and broadband full-wave scattering. A novel single source approximation is introduced for approximating clusters of electrostatic sources in multi-layered media. The approximation is derived by matching the spectra of the field in the vicinity of the stationary phase point. Combined with the BH algorithm, a new algorithm is shown to be an efficient method for evaluating electrostatic fields in multilayered media. Specifically, the new BH algorithm is well suited for fast capacitance extraction. The BH algorithm is also adapted to the scalar Helmholtz kernel by using the same methodology to derive an accurate single source approximation. The result is a fast algorithm that is suitable for accelerating the solution of the Electric Field Integral Equation (EFIE) for electrically small structures. Finally, a new version of FMM is presented that is stable and efficient from the low frequency regime to mid-range frequencies. By applying analytical derivatives to the field expansions at the observation points, the proposed method can rapidly evaluate vectorial kernels that arise in the FMM-accelerated solution of EFIE, the Magnetic Field Integral Equation (MFIE), and the Combined Field Integral Equation (CFIE).

Operations research and queue theory have many different applications, providing tremendous value for different organizations. With the rise of fast computers and better data, stochastic processes can be better modeled into simulations to provide results of higher quality. The application of Operations Research is a very interesting intersection of mathematics, statistics, computer science and management science. In this project, the benefits of using point wise stationary approximations and stationary independent period by period approximationsto simulate staffing requirements at LAX (Los Angeles International Airport) in conjuction are examined with the motivation of reducing arrival processing times. This paper then examines the performance of different airport layouts, utilizing a discrete event simulation.

In this study, the two-dimensional cutting stock problem (2DCSP) is considered. This is a problem that occurs in the cutting of a number of smaller rectangular pieces or items from a set of large stock rectangles. It is assumed that the set of large objects is sufficient to accommodate all the small items. A heuristic procedure is developed to solve the two-dimensional single stock-size cutting stock problem (2DSSSCSP). This is the special case where the large rectangles are all of the same size. The major objective is to minimize waste and the number of stock sheets utilized. The heuristic procedures developed to solve the 2DSSSCSP are based on the generation of cutting pattern. The Wang algorithm and a specific commercial software package are made use of to generate these patterns. The commercial software was chosen from a set of commercial software packages available in the market. A combinatoric process is applied to generate sets of cutting patterns using the Wang algorithm and the commercial software. The generated cutting patterns are used to formulate an integer linear programming model which is solved using an optimization solver. Empirical experimentation is carried out to test the heuristic procedures using data obtained from both small and real world application problem instances. The results obtained shows that the heuristic procedures developed produce good quality results for both small and real life problem instances. It is quite clear that the heuristic procedure developed to solve the 2DSSSCSP produces cutting patterns which are acceptable in terms of waste generated and may offer useful alternatives to approaches currently available. Broadly stated, this study involves investigating available software (commercial) in order to assess, formulate and investigate methods to attempt to benchmark software systems and algorithms and to employ ways to enhance solutions obtained by using these software systems. / Thesis (M.Sc. (Computer Science))--North-West University, Potchefstroom Campus, 2011.

The topic of exact, exponential-time algorithms for NP-hard problems has received a lot of attention, particularly with the focus of producing algorithms with stronger theoretical guarantees, e.g. upper bounds on the running time on the form O(c^n) for some c. Better methods of analysis may have an impact not only on these bounds, but on the nature of the algorithms as well. The most classic method of analysis of the running time of DPLL-style ("branching" or "backtracking") recursive algorithms consists of counting the number of variables that the algorithm removes at every step. Notable improvements include Kullmann's work on complexity measures, and Eppstein's work on solving multivariate recurrences through quasiconvex analysis. Still, one limitation that remains in Eppstein's framework is that it is difficult to introduce (non-trivial) restrictions on the applicability of a possible recursion. We introduce two new kinds of complexity measures, representing two ways to add such restrictions on applicability to the analysis. In the first measure, the execution of the algorithm is viewed as moving between a finite set of states (such as the presence or absence of certain structures or properties), where the current state decides which branchings are applicable, and each branch of a branching contains information about the resultant state. In the second measure, it is instead the relative sizes of the modelled attributes (such as the average degree or other concepts of density) that controls the applicability of branchings. We adapt both measures to Eppstein's framework, and use these tools to provide algorithms with stronger bounds for a number of problems. The problems we treat are satisfiability for sparse formulae, exact 3-satisfiability, 3-hitting set, and counting models for 2- and 3-satisfiability formulae, and in every case the bound we prove is stronger than previously known bounds.

Consumer-generated reviews play an important role in online purchase decisions for many consumers. However, the quality and helpfulness of online reviews varies significantly. In addition, the helpfulness of different consumer-generated reviews is not disclosed to consumers unless they carefully analyze the overwhelming number of available contents. Therefore, it is of vital importance to develop predictive models that can evaluate online product reviews efficiently and then display the most useful reviews to consumers, in order to assist them in making purchase decisions. This thesis examines the problem of building computational models for predicting whether a consumer-generated review is helpful based on consumers' online votes on other reviews (where a consumer's vote on a review is either HELPFUL or UNHELPFUL), with the aim of suggesting the most suitable products and vendors to consumers.In particular, we propose in this thesis three different helpfulness prediction approaches for consumer-generated reviews. Our entropy-based approach is relatively simple and suitable for applications requiring simple recommendation engine with fully-voted reviews. However, our entropy-based approach, as well as the existing approaches, lack a general framework and are all limited to utilizing fully-voted reviews. We therefore present a probabilistic helpfulness prediction framework to overcome these limitations. To demonstrate the versatility and flexibility of this framework, we propose an EM-based model and a logistic regression-based model. We show that the EM-based model can utilize reviews voted by a very small number of voters as the training set, and the logistic regression-based model is suitable for real-time helpfulness predicting of consumer-generated reviews. To our best knowledge, this is the first framework for modeling review helpfulness and measuring the goodness of models. Although this thesis primarily considers the problem of review helpfulness prediction, the presented probabilistic methodologies are, in general, applicable for developing recommender systems that make recommendation based on other forms of user-generated contents.

This thesis is concerned with the channel assignment (CA) problem in multi-channel multi-interface wireless mesh networks (M2WNs). First, for M2WNs with general topologies, we rigorously demonstrate using the combinatorial principle of inclusion/exclusion that the CA solution space can be quantified, indicating that its cardinality is greatly influenced by the number of radio interfaces installed on each router. Based on this analysis, a novel scheme is developed to construct a new reduced search space, represented by a lattice structure, that is searched more efficiently for a CA solution. The elements in the reduced lattice-based space, labeled Solution Structures (SS), represent groupings of feasible CA solutions satisfying the radio constraints at each node. Two algorithms are presented for searching the lattice structure. The first is a greedy algorithm that finds a good SS in polynomial time, while the second provides a user-controlled depthfirst search for the optimal SS. The obtained SS is used to construct an unconstrained weighted graph coloring problem which is then solved to satisfy the soft interference constraints. For the special class of full M2WNs (fM2WNs), we show that an optimal CA solution can only be achieved with a certain number of channels; we denote this number as the characteristic channel number and derive upper and lower bounds for that number as a function of the number of radios per router. Furthermore, exact values for the required channels for minimum interference are obtained when certain relations between the number of routers and the radio interfaces in a given fM2WN are satisfied. These bounds are then employed to develop closed-form expressions for the minimum channel interference that achieves the maximum throughput for uniform traffic on all communication links. Accordingly, a polynomial-time algorithm to find a near-optimal solution for the channel assignment problem in fM2WN is developed. Experimental results confirm the obtained theoretical results and demonstrate the performance of the proposed schemes.

The present work investigates the applicability of Genetic Algorithms (GA) to the problem of signal propagation in Native Neuronal Networks (NNNs). These networks are comprised of neurons, some of which receive input signals. The signals propagate though the network by transmission between neurons. The research focuses on the regeneration of the output signal of the network without knowing the original input signal. The computational complexity of the problem is prohibitive for the exact computation. We propose to use a heuristic approach called Genetic Algorithm. Three algorithms are developed, based on the GA technique. The developed algorithms are tested on two different networks with varying input signals. The results obtained from the testing indicate significantly better performance of the developed algorithms compared to the Uniform Random Search (URS) technique, which is used as a control group. The importance of the research is in the demonstration of the ability of GA-based algorithms to successfully solve the problem at hand.

In view of the recent implementation of a publicly funded rotavirus vaccination program in Ontario, we undertook studies to help guide the design of a safety evaluation of the vaccine with respect to intussusception. We used administrative data to develop and validate an algorithm for intussusception, and quantified its incidence in Ontario. We also conducted a systematic review of study designs used to evaluate post-licensure vaccine safety, and discussed each design’s strengths and weaknesses. The validated algorithm for intussusception was sensitive (89.3%) and highly specific (>99.9%). We observed the highest mean incidence (34 / 100,000) in males <1 year of age. While other designs are more robust, the inability to ascertain individual vaccination status from Ontario’s administrative data dictated our selection of an ecological design for safety evaluation of rotavirus vaccine. Data assimilated from this thesis represent a critical step toward the timely evaluation of rotavirus vaccine safety in Ontario.

Financial derivatives play significant role in an investor's success. Financial option is one form of derivatives. Option pricing is one of the challenging and fundamental problems of computational finance. Due to highly volatile and dynamic market conditions, there are no closed form solutions available except for simple styles of options such as, European options. Due to the complex nature of the governing mathematics, several numerical approaches have been proposed in the past to price American style and other complex options approximately. Bio-inspired and nature-inspired algorithms have been considered for solving large, dynamic and complex scientific and engineering problems. These algorithms are inspired by techniques developed by the insect societies for their own survival. Nature-inspired algorithms, in particular, have gained prominence in real world optimization problems such as in mobile ad hoc networks. The option pricing problem fits very well into this category of problems due to the ad hoc nature of the market. Particle swarm optimization (PSO) is one of the novel global search algorithms based on a class of nature-inspired techniques known as swarm intelligence. In this research, we have designed a sequential PSO based option pricing algorithm using basic principles of PSO. The algorithm is applicable for both European and American options, and handles both constant and variable volatility. We show that our results for European options compare well with Black-Scholes-Merton formula. Since it is very important and critical to lock-in profit making opportunities in the real market, we have also designed and developed parallel algorithm to expedite the computing process. We evaluate the performance of our algorithm on a cluster of multicore machines that supports three different architectures: shared memory, distributed memory, and a hybrid architectures. We conclude that for a shared memory architecture or a hybrid architecture, one-to-one mapping of particles to processors is recommended for performance speedup. We get a speedup of 20 on a cluster of four nodes with 8 dual-core processors per node.

This thesis presents the research results on the development of a microwave tomography imaging algorithm capable of reconstructing the dielectric properties of the unknown object. Our focus was on the theoretical aspects of the non-linear tomographic image reconstruction problem with particular emphasis on developing efficient numerical and non-linear optimization for solving the inverse scattering problem. A detailed description of a novel microwave tomography method based on frequency dependent finite difference time domain, a numerical method for solving Maxwell's equations and Genetic Algorithm (GA) as a global optimization technique is given. The proposed technique has the ability to deal with the heterogeneous and dispersive object with complex distribution of dielectric properties and to provide a quantitative image of permittivity and conductivity profile of the object. It is shown that the proposed technique is capable of using the multi-frequency, multi-view, and multi-incident planer techniques which provide useful information for the reconstruction of the dielectric properties profile and improve image quality. In addition, we show that when a-priori information about the object under test is known, it can be easily integrated with the inversion process. This provides realistic regularization of the solution and removes or reduces the possibility of non-true solutions. We further introduced application of the GA such as binary-coded GA, real-coded GA, hybrid binary and real coded GA, and neural-network/GA for solving the inverse scattering problem which improved the quality of the images as well as the conversion rate. The implications and possible advantages of each type of optimization are discussed, and synthetic inversion results are presented. The results showed that the proposed algorithm was capable of providing the quantitative images, although more research is still required to improve the image quality. In the proposed technique the computation time for solution convergence varies from a few hours to several days. Therefore, the parallel implementation of the algorithm was carried out to reduce the runtime. The proposed technique was evaluated for application in microwave breast cancer imaging as well as measurement data from university of Manitoba and Institut Frsenel's microwave tomography systems.