Theses, Dissertations, and other Required Graduate Degree Essays

Receive updates for this collection

This collection contains digitized SFU theses except for those theses submitted within the last 12 months. If you cannot find the thesis you are looking for please search Recently Submitted Theses as it may be a recently submitted thesis and thus not yet available in Summit.

Algorithms for Problems in Voting and Scheduling

Author: 
Date created: 
2016-11-24
Abstract: 

In this dissertation, we study the voting problem and the ranking problem in computational social choice, as well as a matching problem in a restricted graph. We present our results for these problems in two parts.Part I: Election, Ranking, and Heuristics. Voting is commonly used to reach consensus among a group of people. Voting models often deal with a set of voters, each of whom has a preference over a set of alternatives. Each voter submits a ranking of the alternatives, and the outcome is decided by a voting rule. Computational voting theory is an interdisciplinary research area which considers the computational problems that arise in voting. Selecting the winner(s) of an election is one such problem. The problem of computing the winner(s) using most voting rules is easy. However, there are a few rules for which this problem becomes computationally hard. In the first part of this thesis, we study two important voting and ranking rules under which computing the winner(s) is hard. The first voting procedure we study in this thesis is the Chamberlin-Courant system. The Chamberlin-Courant system is a proportional representation system that does not restrict candidates to have a minimum number of votes to be selected in an assembly. We consider domination analysis of a 2-Opt heuristic for the winner determination problem under the Chamberlin-Courant system. We show that the 2-Opt heuristic produces solutions no worse than the average solution in polynomial time. The next problem we consider in this dissertation is Linear Ordering Problem. Linear ordering problem is a classic optimization problem which can be used to model problems in graph theory, machine scheduling, and ranking. Relatively recently, there has been some success in using Mixed Integer Program (MIP) heuristic for NP-hard optimization problems. We report our experience with using a MIP heuristic for the problem. Part II: Matching.The first problem we consider in this part is the Linear Ordering Problem. We show how the linear program of this problem can be solved by using a primal-dual based combinatorial algorithm instead of the Simplex method. Next, we address the cyclical scheduling problem which is used to schedule shifts for workers in a factory. Given a set of n work periods, each worker is assigned a shift where he works for n-2 consecutive periods and takes off the remaining two periods. Thus, for n=7, a typical shift may be to work from Monday to Friday and take off Saturday and Sunday. Each shift may also have a cost associated with it. Furthermore, the factory requires that a given number of workers be available for each period (this requirement may vary from period to period). The objective is to assign a shift to each worker such that the daily requirement is fulfilled and the total cost of the shifts is minimized. We use the primal-dual method to solve the (n-2,n) cyclical scheduling problem by solving a series of b-matching problems on a cycle of n vertices.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Ramesh Krishnamurti
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Dissertation) Ph.D.

Specialized Macro-Instructions for Von-Neumann Accelerators

Author: 
Date created: 
2016-11-30
Abstract: 

In the last few decades, Von-Neumann super-scalar processors have been the superior approach for improving general purpose processing and hardware specialization was used as a complementary approach. However, the imminent end of Moore's law indicates voltage scaling and per-transistor switching power can not scale down with the same peace as what Moore's law predicts. As a result, there is a new interest in hardware specialization to improve performance, power and energy efficiency on specific tasks.This dissertation proposes a Von-Neumann based accelerator, Chainsaw, and demonstrates that many of the fundamental overheads (e.g., fetch-decode) can be amortized by adopting the appropriate instruction abstraction. We have developed a complete LLVM-based compiler prototype and simulation infrastructure and demonstrated that an 8-lane Chainsaw is within 73% of the performance of an ideal dataflow architecture while reducing the energy consumption by 45% compared to a 4-way out of order processor.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Arrvindh Shriraman
Martin Ester
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

A multi-state model for a life insurance product with integrated health rewards program

Author: 
Date created: 
2016-12-02
Abstract: 

With the prevalence of chronic diseases that account for a significant portion of deaths, a new approach to life insurance has emerged to address this issue. The new approach integrates health rewards programs with life insurance products; the insureds are classified by fitness statuses according to their level of participation and would get premium reductions at the superior statuses. We introduce a Markov chain process to model the dynamic transition of the fitness statuses, which are linked to corresponding levels of mortality risks reduction. We then embed this transition process into a stochastic multi-state model to describe the new life insurance product. Formulas are given for calculating its benefit, premium, reserve and surplus. These results are compared with those of the traditional life insurance. Numerical examples are given for illustration.

Document type: 
Graduating extended essay / Research project
File(s): 
Senior supervisor: 
Yi Lu
Department: 
Science: Department of Statistics and Actuarial Science
Thesis type: 
(Project) M.Sc.

Three essays on economic history and experimental economics

Date created: 
2016-12-08
Abstract: 

While economists recognize the important role of formal institutions in the promotionof trade, there is increasing agreement that institutions are typically endogenous to culture.The question remains how institutions interact with cultural variables when they areimposed exogenously. In social psychology, the individualism/collectivism distinction isthought to be an important cultural variable underlying many behavioral differences. Inthe first chapter, Erik kimbrough and I design an experiment to explore the relationship betweensubjects’ dispositions to individualism/collectivism and their willingness to engagein trade under enforcement institutions of varying strength. Overall, we find a positive effectof strong institutions on trade, but once we control for individualism/collectivism,institutions have no significant effect, and we observe that individualists engage in trademore often than collectivists. This suggests that cultural dispositions may even outweighinstitutions in the promotion of trade.The choice of enforcement mechanism in conducting long-distance trade has long beenassociated with cultural dispositions to individualism and collectivism. Nevertheless, theselection process of a formal or an informal enforcement mechanism and how it relatesto the reliability of the third party enforcement is unknown. In the second chapter, I designeda laboratory experiment in which the options for both a safe local trade and a riskyyet more profitable long-distance trade are available. Long-distance trade is governed byeither a formal or an informal enforcement mechanism. I examined the choice of informalversus formal enforcement mechanism while controlling for the cultural dispositionof subjects. I found that individuals with a collectivist cultural orientation used informalenforcement when effective formal enforcement is available significantly more frequentlythan those with an individualist orientation. Those with individualistic cultural orientationsubstituted formal enforcement for informal enforcement when the former created areliable contract.Enforceable property rights are the first steppingstones toward economic development.While nobles in some Western European countries successfully constrained sovereigns’arbitrary taxation, their Middle Eastern counterparts failed to gain similar rights. In thethird chapter, I compare the impact of Islamic inheritance law and that of primogeniture onthe welfare of economic agents. In the model, I define three types of agents: the sovereign,nobles and peasants. The nobles, unlike the peasants, own land. Furthermore, noblesalso own firms/estates that produce food. To protect their produce, nobles engaged ina conflict with an extractive sovereign to determine the tax rate. The findings demonstratedthat primogeniture led to a lower tax rate and higher welfare level for both noblesand the sovereign. Peasants, however, due to lower wages, suffered under primogeniture.

Document type: 
Thesis
Senior supervisor: 
David Jacks
Department: 
Arts & Social Sciences: Department of Economics
Thesis type: 
(Dissertation) Ph.D.

The Canadian Shift among Filipinos in Metro Vancouver

Author: 
Date created: 
2016-12-06
Abstract: 

The present study provides preliminary insight into the linguistic patterns of Filipinos in Metro Vancouver, an important ethnic community in the region. Specifically, this thesis sought to explore whether Filipinos are (linguistically) integrated by determining if they participated in the Canadian Shift (CS), an on-going change in Canadian English involving the lowering and/or retracting of the vowels /æ, ɛ, ɪ/. Twelve second-generation Filipinos between the ages of 19 and 30 took part in sociolinguistic interviews, and formant frequency data based on 408 tokens of /æ, ɛ, ɪ/ were constructed from recordings of Boberg’s (2008) word list. The results revealed that CS is robust, with evidence of women in the lead. These indicated that there are no substrate language transfer effects at least concerning this phonetic variable. This study ultimately demonstrates that despite remaining a marginalized demographic, second-generation Filipinos are linguistically integrated and are therefore rightful members of the region’s speech community.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Panayiotis Pappas
Suzanne Hilgendorf
Department: 
Arts & Social Sciences: Department of Linguistics
Thesis type: 
(Thesis) M.A.

Structural Colour Images Inkjet Printed on Polymer Substrates Patterned with Nanostructural Pixels

Author: 
Date created: 
2016-11-24
Abstract: 

This work demonstrates a novel means of manufacturing nano-optical devices, functioning according to the principle of structural colouration, by inkjet printing silver nanoparticle ink on nanostructured surfaces. The structural colouration is created by a surface containing micro- or nano- features interacting with light. In this study, we use a polymer substrate patterned with different types of nanostructure arrays as structural pixels that give red, green, and blue primary colours. We utilize nanoimprint lithography to replicate the nanostructured substrate from a prefabricated stamp. These days, inkjet printing has become a scalable micropatterning technology due to its precise, flexible control and cost-effective additive process. In this current work, inkjet printing technology is employed to selectively activate pixels by printing silver nanoparticle ink on the nanosubstrate surface to gain colour mixing. In the experiments performed, a nanostructured substrate patterned with diffractive nanostructure arrays was implemented to print full-colour images. The effect of surface wettability, different concentrations of silver nanoparticle ink, drop and line spacing, and polymer nanostructures on the optical properties of the subpixels of dried silver printed dots, are investigated to achieve high printing resolution. This method is a key to achieving full-colour, scalable, high-throughput, flexible and cost-effective printing of structural colour images. The printed pictures demonstrate unique optically variable effects that distinguish from security products using pigments or printing inks in their manufacturing processes. Therefore, this technique is an ideal candidate for security and authentication applications that require customizable anti-counterfeiting features.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Bozena Kaminska
Department: 
Applied Sciences: School of Engineering Science
Thesis type: 
(Thesis) M.A.Sc.

Risk Assessment with the HCR-20v3 across Genders, Subsamples, and Time-Frames

Author: 
Date created: 
2016-11-24
Abstract: 

One of the most well-established violence risk assessment schemes, the HCR-20: Assessing Risk for Violence Manual, Version 2 (HCR-20v2; Historical/Clinical/Risk Management-20), has recently been revised. The present study evaluated the performance of the new HCR-20v3 in a sample of 119 participants on probation or recently discharged into the community (i.e., from incarceration or short-term psychiatric hospitalization). The HCR-20v3 demonstrated concurrent validity with the HCR-20v2 and was predictive, prospectively, of whether, and how rapidly, participants engaged in violence. The SRRs added incrementally to the presence and relevance scores. Generally, no moderation effects of subsample type were noted, with the exception of the impact of subsample on the ability of the C subscale to predict the likelihood of verbal violence, as well as its impact on the SRRs, which might more strongly predict violence for the participants who were receiving short-term psychiatric inpatient care. As pertains to gender, some moderation effects were observed at 6 weeks for violence and physical violence, but this was no longer the case at 8 months. However, the H relevance rating may be more strongly predictive of time to physical violence in women, than it is in men.Moreover, the HCR-20v3 components generally demonstrated a relationship to violent victimization, whereas they did not do so for suicide. Some ratings might exhibit a relationship to self-harm. There was no moderation effect of subsample type on the ability of HCR-20v3 to forecast violent victimization. The HCR-20v3 components were not predictive of violent victimization, suicide, or self-harm in men at 6 weeks, but some demonstrated a relationship with violent victimization at 8 months. For women, some of HCR-20v3 components were predictive of violent victimization and self-harm for both time-frames. The H presence score was more predictive of violent victimization in women. Generally, the higher the scores on all HCR-20v3 presence ratings, the sooner participants were violently victimized and there was no moderation effect of subsample type. However, there was a moderation effect of gender on the ability of the C subscale to forecast the imminence of this outcome, and this may also the case for the total presence score.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Kevin S. Douglas
Department: 
Arts & Social Sciences: Department of Psychology
Thesis type: 
(Dissertation) Ph.D.

Two Game Sweep: How Mid-Sized Publishers Make the Decision to Release Two Physical Formats of a Book, using Black Ice as a Case Study

Author: 
Date created: 
2016-11-21
Abstract: 

This report analyzes mid-sized publishers’ decisions regarding whether it is profitable to release a second physical format of a previously published book and the publicity practices for second releases at ECW Press, an independent Canadian publisher in Toronto, Ontario. The first chapter of this report describes the book being used as a case study, Black Ice, and discusses ECW Press’s decision to publish it. The second chapter summarizes the history of two-format publishing and how this influences the decisions pertaining to formats that publishers make today. Chapter three discusses how ECW Press decides which format is most appropriate for a book and the key factors that indicate to them that printing a subsequent trade paperback edition of a previously released hardcover will be profitable. The final chapter uses Black Ice as a publicity case study, demonstrating how mid-sized publishers publicize the release of the second edition of a book and how it differs from promoting the first release.

Document type: 
Graduating extended essay / Research project
File(s): 
Senior supervisor: 
John Maxwell
Department: 
Communication, Art & Technology: Publishing Program
Thesis type: 
(Project Report) M.Pub.

A data-driven approach to automatic tweet generation about traffic incidents

Author: 
Date created: 
2016-11-07
Abstract: 

Traffic congestion continues to be a major problem in large cities around the world and a source of frustration for drivers. Previous studies show that providing drivers with real-time traffic information will help them make better route planning and avoid congestion. In this research, we examine the use of data-driven natural language generation (NLG) techniques to automatically generate tweets from traffic incident data. From the task of automatic tweet generation, we discuss and propose a design of a traffic notification system that can deliver personalized and location-relevant real-time traffic information to drivers. The domain of our NLG work is novel with respect to the previous work in different domains including weather forecasts, educational reports and clinical reports. We evaluate the automatic generated tweets using BLEU-4. Our experimental results show that a well-prepared training corpus is important for better quality output, however, it is currently limited in traffic-related domains.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Fred Popowich
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Real-World Applications in Math Class

Date created: 
2016-10-18
Abstract: 

Calls to connect school mathematics to applications in the real-world are ubiquitous. I examine the experience of senior high school students as they encounter a student-centred real-world application task applying logarithms and exponential functions in a murder mystery context. I observed students through the task, analyzed their written solutions, and administered a follow-up questionnaire. Four case studies illustrate the range and nuanced experiences of students completing the real-world task. During the real-world task students experienced prolonged motivation, they made sense of abstract mathematics through the context of the task, and they benefited from group interactions. This empirical study provides support for the claimed benefits from the literature for the inclusion of real-world applications in the teaching and learning of secondary mathematics.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Peter Liljedahl
Department: 
Education: Faculty of Education
Thesis type: 
(Thesis (Education) ) M.Sc.