Properties and algorithms of the (n, k)-star graphs

The (n, k)-star interconnection network was proposed in 1995 as an attractive alternative to the n-star topology in parallel computation. The (n, k )-star has significant advantages over the n-star which itself was proposed as an attractive alternative to the popular hypercube. The major advantage of the (n, k )-star network is its scalability, which makes it more flexible than the n-star as an interconnection network. In this thesis, we will focus on finding graph theoretical properties of the (n, k )-star as well as developing parallel algorithms that run on this network. The basic topological properties of the (n, k )-star are first studied. These are useful since they can be used to develop efficient algorithms on this network. We then study the (n, k )-star network from algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms for basic communication, prefix computation, and sorting, etc. A literature review of the state-of-the-art in relation to the (n, k )-star network as well as some open problems in this area are also provided.

Properties and algorithms of the (n, k)-arrangement graphs

The (n, k)-arrangement interconnection topology was first introduced in 1992. The (n, k )-arrangement graph is a class of generalized star graphs. Compared with the well known n-star, the (n, k )-arrangement graph is more flexible in degree and diameter. However, there are few algorithms designed for the (n, k)-arrangement graph up to present. In this thesis, we will focus on finding graph theoretical properties of the (n, k)- arrangement graph and developing parallel algorithms that run on this network. The topological properties of the arrangement graph are first studied. They include the cyclic properties. We then study the problems of communication: broadcasting and routing. Embedding problems are also studied later on. These are very useful to develop efficient algorithms on this network. We then study the (n, k )-arrangement network from the algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms such as prefix sums computation, sorting, merging and basic geometry computation: finding convex hull on the (n, k )-arrangement graph. A literature review of the state-of-the-art in relation to the (n, k)-arrangement network is also provided, as well as some open problems in this area.

Properties and algorithms of the hyper-star graph and its related graphs

The hyper-star interconnection network was proposed in 2002 to overcome the drawbacks of the hypercube and its variations concerning the network cost, which is defined by the product of the degree and the diameter. Some properties of the graph such as connectivity, symmetry properties, embedding properties have been studied by other researchers, routing and broadcasting algorithms have also been designed. This thesis studies the hyper-star graph from both the topological and algorithmic point of view. For the topological properties, we try to establish relationships between hyper-star graphs with other known graphs. We also give a formal equation for the surface area of the graph. Another topological property we are interested in is the Hamiltonicity problem of this graph. For the algorithms, we design an all-port broadcasting algorithm and a single-port neighbourhood broadcasting algorithm for the regular form of the hyper-star graphs. These algorithms are both optimal time-wise. Furthermore, we prove that the folded hyper-star, a variation of the hyper-star, to be maixmally fault-tolerant.

Properties and Algorithms of the KCube Graphs

The KCube interconnection topology was rst introduced in 2010. The KCube graph is a compound graph of a Kautz digraph and hypercubes. Compared with the at- tractive Kautz digraph and well known hypercube graph, the KCube graph could accommodate as many nodes as possible for a given indegree (and outdegree) and the diameter of interconnection networks. However, there are few algorithms designed for the KCube graph. In this thesis, we will concentrate on nding graph theoretical properties of the KCube graph and designing parallel algorithms that run on this network. We will explore several topological properties, such as bipartiteness, Hamiltonianicity, and symmetry property. These properties for the KCube graph are very useful to develop efficient algorithms on this network. We will then study the KCube network from the algorithmic point of view, and will give an improved routing algorithm. In addition, we will present two optimal broadcasting algorithms. They are fundamental algorithms to many applications. A literature review of the state of the art network designs in relation to the KCube network as well as some open problems in this field will also be given.

Properties and Algorithms of the KCube Interconnection Networks

The KCube interconnection network was first introduced in 2010 in order to exploit the good characteristics of two well-known interconnection networks, the hypercube and the Kautz graph. KCube links up multiple processors in a communication network with high density for a fixed degree. Since the KCube network is newly proposed, much study is required to demonstrate its potential properties and algorithms that can be designed to solve parallel computation problems. In this thesis we introduce a new methodology to construct the KCube graph. Also, with regard to this new approach, we will prove its Hamiltonicity in the general KC(m; k). Moreover, we will find its connectivity followed by an optimal broadcasting scheme in which a source node containing a message is to communicate it with all other processors. In addition to KCube networks, we have studied a version of the routing problem in the traditional hypercube, investigating this problem: whether there exists a shortest path in a Qn between two nodes 0n and 1n, when the network is experiencing failed components. We first conditionally discuss this problem when there is a constraint on the number of faulty nodes, and subsequently introduce an algorithm to tackle the problem without restrictions on the number of nodes.

Decoding algorithms using side-effect machines

Bioinformatics applies computers to problems in molecular biology. Previous research has not addressed edit metric decoders. Decoders for quaternary edit metric codes are finding use in bioinformatics problems with applications to DNA. By using side effect machines we hope to be able to provide efficient decoding algorithms for this open problem. Two ideas for decoding algorithms are presented and examined. Both decoders use Side Effect Machines(SEMs) which are generalizations of finite state automata. Single Classifier Machines(SCMs) use a single side effect machine to classify all words within a code. Locking Side Effect Machines(LSEMs) use multiple side effect machines to create a tree structure of subclassification. The goal is to examine these techniques and provide new decoders for existing codes. Presented are ideas for best practices for the creation of these two types of new edit metric decoders.

Cues to action : do they result in belief and behavioural change in women?

With incidence rates of osteoporosis increasing (Osteoporosis Canada, 2007), preventative efforts to minimize costs associated with condition diagnosis are a public health priority. Cues to action are specific internal (e.g., physical symptoms, family member with a condition) or external stimuli (e.g., public service announcements, health education campaigns) that are necessary to trigger appropriate health behaviours and serve to create an awareness of the health threat (Mattson, 1999). To date, limited understanding of the scope of influence cues to action have on health beliefs and behaviour associated with osteoporosis is known. The present investigation was designed to address this gap in the literature. More specifically, the influence of cues to action, a public service announcement (PSA) developed by Osteoporosis Canada and a bone screening by way of Quantitative Ultrasound, on health beliefs and health-enhancing physical activity (HEPA) across a four week period was investigated. Peri-and postmenopausal women (N= 174) were randomly assigned to one of three conditions 1) an osteoporosis public service announcement (PSA) condition; 2) a bone screening condition via quantitative ultrasound techniques, and 3) a PSA attention control condition. Health beliefs associated with osteoporosis were taken at three time points: prior to the cue to action intervention, immediately following the intervention, and four weeks post intervention. Knowledge of osteorporosis risk factors and HEP A were assessed pre and post-intervention only. Results of a regression analysis suggested that baseline health beliefs predicted baseline HEPA (R2 adj = .24; F (9, 161) = 6.49,p = .000; 95% CI = .12 - .35) with exercise barriers (p = -.33) being a negative predictor and health motivation (p = .21) being a positive predictor of HEP A. Baseline health beliefs predicted With incidence rates of osteoporosis increasing (Osteoporosis Canada, 2007), preventative efforts to minimize costs associated with condition diagnosis are a public health priority. Cues to action are specific internal (e.g., physical symptoms, family member with a condition) or external stimuli (e.g., public service announcements, health education campaigns) that are necessary to trigger appropriate health behaviours and serve to create an awareness of the health threat (Mattson, 1999). To date, limited understanding of the scope of influence cues to action have on health beliefs and behaviour associated with osteoporosis is known. The present investigation was designed to address this gap in the literature. More specifically, the influence of cues to action, a public service announcement (PSA) developed by Osteoporosis Canada and a bone screening by way of Quantitative Ultrasound, on health beliefs and health-enhancing physical activity (HEPA) across a four week period was investigated. Peri-and postmenopausal women (N= 174) were randomly assigned to one of three conditions 1) an osteoporosis public service announcement (PSA) condition; 2) a bone screening condition via quantitative ultrasound techniques, and 3) a PSA attention control condition. Health beliefs associated with osteoporosis were taken at three time points: prior to the cue to action intervention, immediately following the intervention, and four weeks post intervention. Knowledge of osteorporosis risk factors and HEP A were assessed pre and post-intervention only. Results of a regression analysis suggested that baseline health beliefs predicted baseline HEPA (R2 adj = .24; F (9, 161) = 6.49,p = .000; 95% CI = .12 - .35) with exercise barriers (p = -.33) being a negative predictor and health motivation (p = .21) being a positive predictor of HEP A. Baseline health beliefs predicted

The effects of static and diurnally-cycling temperature acclimations on thermal tolerances of rainbow trout, Salmo gairdneri

:ofiedian lethal temperatures ( LT50' s ) were determined for rainbow trout, Salmo gairdnerii, acclimated for a minimum of 21 days at 5 c onstant temperatures between 4 and 20 0 C. and 2 diel temperature fluctuations ( sinewave curves of amplitudes ± 4 and ± 7 0 C. about a mean temperature of 12 0 C. ) . Twenty-four-, 48-, and 96-hour LT50 estimates were c alculated f ollowing standard flow-through aquatic bioassay techniques and probi t transformation of mortality data. The phenomenon of delayed thermal mortality was also investigated. Shifts in upper incipient lethal temperature occurred as a result of previous thermal conditioning. It was shown that increases in constant acclimation temperature result in proportional l inear increases in thermal tolerances. The increase i n estimated 96-hour LT50's was approximately 0.13 0 c. X 1 0 C:1 between 8 and 20 0 C. The effect of acclimation to both cyclic temperature regimes was an increase in LT50 to values between the mean and maximum constant equivalent daily temperatures of the cycles. Twenty-four-, 48-, and 96-hour LT50 estimates of both cycles corresponded approximately to the LT50 values of the 16 0 C. c onstant temperature equivalent . This increase i n thermal tolerance was further demonstrated by the delayed thermal mortality experiments . Cycle amplitudes appeared to i nfluence thermal resistance through alterations in initi al mortality since mortality patterns characteristic of base temperature acclimations re-appeared after approximately 68 hours exposure to test temperatures for the 12 + 4 0 C. group, whereas mortality patterns stabilized and remained constant for a period greater than 192 hours with the larger therma l cycle ( 12 + 7 0 C. ). NO s ignificant corre lations between s pecimen weight and time-to-death was apparent. Data are discussed in relation to the establishment of thermal criteria for important commercial and sport fishes , such as the salmonids , as is the question whether previously reported values on lethal temperature s may have been under estimated.

Keyword Competition and Determinants of Ad Position in Sponsored Search Advertising

Given the significant growth of the Internet in recent years, marketers have been striving for new techniques and strategies to prosper in the online world. Statistically, search engines have been the most dominant channels of Internet marketing in recent years. However, the mechanics of advertising in such a market place has created a challenging environment for marketers to position their ads among their competitors. This study uses a unique cross-sectional dataset of the top 500 Internet retailers in North America and hierarchical multiple regression analysis to empirically investigate the effect of keyword competition on the relationship between ad position and its determinants in the sponsored search market. To this end, the study utilizes the literature in consumer search behavior, keyword auction mechanism design, and search advertising performance as the theoretical foundation. This study is the first of its kind to examine the sponsored search market characteristics in a cross-sectional setting where the level of keyword competition is explicitly captured in terms of the number of Internet retailers competing for similar keywords. Internet retailing provides an appropriate setting for this study given the high-stake battle for market share and intense competition for keywords in the sponsored search market place. The findings of this study indicate that bid values and ad relevancy metrics as well as their interaction affect the position of ads on the search engine result pages (SERPs). These results confirm some of the findings from previous studies that examined sponsored search advertising performance at a keyword level. Furthermore, the study finds that the position of ads for web-only retailers is dependent on bid values and ad relevancy metrics, whereas, multi-channel retailers are more reliant on their bid values. This difference between web-only and multi-channel retailers is also observed in the moderating effect of keyword competition on the relationships between ad position and its key determinants. Specifically, this study finds that keyword competition has significant moderating effects only for multi-channel retailers.