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.

In this thesis, we consider joint beamforming, power, and channel allocation in a multi-user and multi-channel underlay cognitive radio network (CRN). In this system, beamforming is implemented at each SU-TX to minimize the co-channel interference. The formulated joint optimization problem is a non-convex, mixed integer nonlinear programming (MINLP) problem. We propose a solution which consists of two stages. At first, given a channel allocation, a feasible solutions for power and beamforming vectors are derived by converting the problem into a convex form with an introduced optimal auxiliary variable and semidefinite relaxation (SDR) approach. Next, two explicit searching algorithms, i.e., genetic algorithm (GA) and simulated annealing (SA)-based algorithm are proposed to determine optimal channel allocations. Simulation results show that beamforming, power and channel allocation with SA (BPCA-SA) algorithm achieves a close optimal sum-rate with a lower computational complexity compared with beamforming, power and channel allocation with GA (BPCA-GA) algorithm. Furthermore, our proposed allocation scheme shows significant improvement than zero-forcing beamforming (ZFBF).

Given graphs G,H, is it possible to find a matching which, when deleted from G, destroys all copies of H? The answer is obvious for some inputs—notably, when G is a large complete graph the answer is “no”—but in general this can be a very difficult question. In this thesis, we study this decision problem when H is a fixed tree or cycle; our aim is to identify those H for which it can be solved efficiently. The H-transverse matching problem, TM(H) for short, asks whether an input graph admits a matching M such that no subgraph of G − M is isomorphic to H. The main goal of this thesis is the following dichotomy. When H is a triangle or one of a few small-diameter trees, there is a polynomial-time algorithm to find an H-transverse matching if one exists. However, TM(H) is NP-complete when H is any longer cycle or a tree of diameter ≥ 4. In addition, we study the restriction of these problems to structured graph classes. / Graduate

In this thesis we introduce and study an A-optimal minimax design criterion for two-level fractional factorial designs, which can be used to estimate a linear model with main effects and some interactions. The resulting designs are called A-optimal minimax designs, and they are robust against the misspecification of the terms in the linear model. They are also efficient, and often they are the same as A-optimal and D-optimal designs. Various theoretical results about A-optimal minimax designs are derived. A couple of search algorithms including a simulated annealing algorithm are discussed to search for optimal designs, and many interesting examples are presented in the thesis. / Graduate / 0463 / yinyue@uvic.ca

This thesis addresses one of the major outstanding problems in the study of self-assembled InAs quantum dots (QDs): their physical profile after deposition of a capping layer and post-growth processing. The optical properties of QDs depend critically on the shape, composition and strain profile, yet these parameters are inaccessible to most experimental techniques once the dots are buried. Data from various x-ray scattering experiments are presented here, along with a novel approach to simulating diffuse scattering using an atomistic model based on Keating energy minimisation. The size and position of the diffuse scattering on the low-Q side of the Bragg peak, which are strongly influenced by the shape and composition of the QDs, has been used to determine that the QDs are truncated pyramids with a diagonal base length of 28 nm, with their edges aligned along the [100] and [010] directions. The composition profile varies from pure InAs at the top to 40-60% InAs at the base. These properties all agree with recent cross-sectional scanning tunnelling microscopy (X-STM) measurements by Bruls et al. It was shown that post-growth annealing causes a reduction in the In content of the QDs, primarily by diffusion from the base of the dot into the wetting layer. Grazing incidence small angle x-ray scattering (GISAXS) measurements have been made from samples of QDs produced with varying growth interruptions (GI) before deposition of the capping layer. The QDs were found to be highly diffuse. After a GI, the dots have been shown to change shape anisotropically, with two facets becoming sharper. An investigation of the use of resonant scattering to study buried QDs has shown that the method of contrast variation is of limited use for enhancing the measurement of diffuse features away from the Bragg peak. It is unsuitable for the study of buried nanostructures.

Tapered I-section members have been employed widely for the design of long-span structures such as large clear-span buildings, stadiums, and bridges because of their structural efficiency. For optimized member design providing maximum strength and stiffness at minimum cost, general non-prismatic (tapered and/or stepped cross-sections) as well as singly-symmetric cross-sections have been commonly employed. Fabricators equipped to produce web-tapered members can create a wide range of optimized members from a minimal stock of different plates and coil. Linearly tapered web plates can be nested to minimize scrap. In many cases, the savings in material and manufacturing efficiencies lead to significant cost savings relative to the use of comparable rolled shapes. To employ Design Guide 25 (DG25) which provides guidance for the application of the provisions of the AISC Specification to the design of frames composed of general non-prismatic members, designers need a robust and general capability for determining the elastic buckling loads. Furthermore, robust tools are needed to facilitate the selection of optimum non-prismatic member designs based on minimum cost. This research addresses the calculation of the elastic buckling loads for general non-prismatic members subjected to general loadings and bracing conditions (typically involving multiple brace points along a given member). This research develops an elastic buckling analysis tool (SABRE2) that can be used to define general geometries, loadings and bracing conditions and obtain a rigorous calculation of the elastic buckling load levels. The three-dimensional finite element equations using open section thin-walled beam theory are derived and formulated using a co-rotational approach including load height effects of transverse loads, stepped flange dimensions, and bracing and support height effects. In addition, this research addresses an algorithmic means to obtain automatic optimized member and frame designs using the above types of members based on Genetic Algorithms (GA). These capabilities are implemented in the tool SABRE2D, which provides a graphical user interface for optimized member and frame design based on updated DG25 provisions and the elastic buckling load calculations from SABRE2.

Thesis studied correlations between swallowing accelerometry parameters and anthropometrics in 50 healthy participants. Anthropometrics include: age, gender, weight, height, body fat percent, neck circumference and mandibular length. Dual-axis swallowing signals, from a biaxial accelerometer were obtained for 5-saliva and 10-water (5-wet and 5-wet chin-tuck) swallows per participant. Two patient-independent automatic segmentation algorithms using discrete wavelet transforms of swallowing sequences segmented: 1) saliva/wet swallows and 2) wet chin-tuck swallows. Extraction of swallows hinged on dynamic thresholding based on signal statistics. Canonical correlation analysis was performed on sets of anthropometric and swallowing signal variables including: variance, skewness, kurtosis, autocorrelation decay time, energy, scale and peak-amplitude. For wet swallows, significant linear relationships were found between signal and anthropometric variables. In superior-inferior directions, correlations linked weight, age and gender to skewness and signal-memory. In anterior-posterior directions, age was correlated with kurtosis and signal-memory. No significant relationship was observed for dry and wet chin-tuck swallowing

One of the most fundamental computational problems in biology is that of inferring evolutionary histories of groups of species from sequence data. Such evolutionary histories, known as phylogenies are usually represented as binary trees where leaves represent extant species, whereas internal nodes represent their shared ancestors. As the amount of sequence data available to biologists increases, very fast phylogenetic reconstruction algorithms are becoming necessary. Currently, large sequence alignments can contain up to hundreds of thousands of sequences, making traditional methods, such as Neighbor Joining, computationally prohibitive. To address this problem, we have developed three novel fast phylogenetic algorithms. The first algorithm, QTree, is a quartet-based heuristic that runs in O(n log n) time. It is based on a theoretical algorithm that reconstructs the correct tree, with high probability, assuming every quartet is inferred correctly with constant probability. The core of our algorithm is a balanced search tree structure that enables us to locate an edge in the tree in O(log n) time. Our algorithm is several times faster than all the current methods, while its accuracy approaches that of Neighbour Joining. The second algorithm, LSHTree, is the first sub-quadratic time algorithm with theoretical performance guarantees under a Markov model of sequence evolution. Our new algorithm runs in O(n^{1+γ(g)} log^2 n) time, where γ is an increasing function of an upper bound on the mutation rate along any branch in the phylogeny, and γ(g) < 1 for all g. For phylogenies with very short branches, the running time of our algorithm is close to linear. In experiments, our prototype implementation was more accurate than the current fast algorithms, while being comparably fast. In the final part of this thesis, we apply the algorithmic framework behind LSHTree to the problem of placing large numbers of short sequence reads onto a fixed phylogenetic tree. Our initial results in this area are promising, but there are still many challenges to be resolved.

The goal of this thesis is to find provably correct methods for detecting conflicts between XACML rules. A conflict occurs when one rule permits a request and another denies that same request. As XACML deals with access control, we can help prevent unwanted access by verifying that it contains rules that do not have unintended conflicts. In order to help with this, we propose an algorithm to find these conflicts then use the Coq Proof Assistant to prove correctness of this algorithm. The algorithm takes a rule set specified in XACML and returns a list of pairs of indices denoting which rules conflict. It is then up to the policy writer to see if the conflicts are intended, or if they need modifying. Since we will prove that this algorithm is sound and complete, we can be assured that the list we obtain is complete and only contains true conflicts.

Given natural numbers n and k, with n>k, the Prouhet-Tarry-Escott (PTE) problem asks for distinct subsets of Z, say X={x_1,...,x_n} and Y={y_1,...,y_n}, such that x_1^i+...+x_n^i=y_1^i+...+y_n^i\] for i=1,...,k. Many partial solutions to this problem were found in the late 19th century and early 20th century. When k=n-1, we call a solution X=(n-1)Y ideal. This is considered to be the most interesting case. Ideal solutions have been found using elementary methods, elliptic curves, and computational techniques. This thesis focuses on the ideal case. We extend the framework of the problem to number fields, and prove generalizations of results from the literature. This information is used along with computational techniques to find ideal solutions to the PTE problem in the Gaussian integers. We also extend a computation from the literature and find new lower bounds for the constant C_n associated to ideal PTE solutions. Further, we present a new algorithm that determines whether an ideal PTE solution with a particular constant exists. This algorithm improves the upper bounds for C_n and in fact, completely determines the value of C_6. We also examine the connection between elliptic curves and ideal PTE solutions. We use quadratic twists of curves that appear in the literature to find ideal PTE solutions over number fields.