CS Theses & Dissertations 2007

For 2007 graduation dates (in alphabetical order by last name):

Planning dynamic vehicle motion using move trees
Adam, Andrew
DOI : 10.14288/1.0052035
URI : http://hdl.handle.net/2429/31505
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. van de Panne

Value-focused GAI network structure elicitation given a domain Ontology
Al Baqui, Abeera Farzana
DOI : 10.14288/1.0052054
URI : http://hdl.handle.net/2429/31542
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisors : Dr. Poole, Dr. Carenini

D-width, metric embedding, and their connections
Ali Safari (Safari Ghahsareh), Mohammad
DOI : 10.14288/1.0052053
URI : http://hdl.handle.net/2429/31491
Degree : Doctor of Philosophy – PhD
Graduation date: 2007-11
Supervisor : Dr. Evans

Embedding between metric spaces is a very powerful algorithmic tool and has been used for finding good approximation algorithms for several problems. In particular, embedding to an [cursive l]₁ norm has been used as the key step in an approximation algorithm for the sparsest cut problem. The sparsest cut problem, in turn, is the main ingredient of many algorithms that have a divide and conquer nature and are used in various fields. While every metric is embeddable into [cursive l]₁ with distortion O (log n) [13], and the bound is tight [39], for special classes of metrics better bounds exist. Shortest path metrics for trees and outerplanar graphs are isometrically embeddable into [cursive l]₁ [41]. Series-parallel graphs [28] and k-outerplanar graphs [19] (for constant k) are embeddable into[cursive l]₁ with constant distortion planar graphs and bounded tree-width graphs are conjectured to have constant distortion in embedding to [cursive l]₁ . Bounded tree-width graphs are one of most general graph classes on which several hard problems are tractable. We study the embedding of series-parallel graphs (or, more generally, graphs with tree-width two) into [cursive l]₁ and also the embedding between two line metrics. We then move our attention to the generalization of tree-width to digraphs and hypergraphs and study several relevant problems.

Optimality in Binary Search Trees and Variable-to-Fixed Length Encoding
Alparslan, Mehmet Argun
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Evans

Combining unsupervised and supervised machine learning to build user models for intelligent learning environments
Amershi, Saleema Amin
DOI : 10.14288/1.0052078
URI : http://hdl.handle.net/2429/31622
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Conati

Toward an understanding of context-awareness and collaborative narratives in mobile video creation
Anderson, Nels Christian
DOI : 10.14288/1.0052036
URI : http://hdl.handle.net/2429/31543
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Krasic

Exploring the design space for concurrent use of personal and large displays for in-home collaboration
Arksey, Nicole
DOI : 10.14288/1.0052070
URI : http://hdl.handle.net/2429/31546
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Booth

Schlieren-based flow imaging
Atcheson, Bradley
DOI : 10.14288/1.0052062
URI : http://hdl.handle.net/2429/31833
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Heidrich

Hierarchical tree approach to group key management using the group Diffie-Hellman protocol
Au, Peter King Pong
DOI : 10.14288/1.0052077
URI : http://hdl.handle.net/2429/31736
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Vuong

Energy-time complexity of algorithms : modelling the trade-offs of CMOS VLSI
Bingham, Bradley Donald
DOI : 10.14288/1.0302116
URI : http://hdl.handle.net/2429/32142
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Greenstreet

Compressible subsonic flow on a staggered grid
Bonner, Michael Patrick
DOI : 10.14288/1.0052066
URI : http://hdl.handle.net/2429/32290
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Bridson

Mixed-initiative support for customizing graphical user interfaces
Bunt, Andrea Katharine
DOI :  10.14288/1.0051695
URI : http://hdl.handle.net/2429/31263
Degree : Doctor of Philosophy – PhD
Graduation date: 2007-11
Supervisors : Dr. Conati, Dr. McGrenere

Graphical user interfaces (GUIs) are becoming increasingly complex, motivating research into ways of providing users with interfaces that are customized or personalized to their individual needs. Two opposing approaches to interface customization that have received the most attention to date are adaptable and adaptive approaches. An adaptable approach places the user in charge of customizing the interface, whereas with an adaptive approach, the system performs the customization automatically. Since both the adaptive and adaptable approaches have unique advantages and disadvantages, this thesis investigates a mixed-initiative solution to interface customization that aims to maximize each of their advantages, while minimizing their disadvantages. As our first step, we conducted an exploratory experiment with simulated users. Using GOMS analysis, we evaluated the benefits of an appropriately customized interface. We also identified ways in which adaptive support could help users customize more efficiently, and identified user and task factors that impact effective customization. Based on the results of our simulation experiment, we designed and implemented the MICA (Mixed-Initiative Customization Assistance) system. MICA provides users with a facility to customize their interfaces according to their needs, but also provides them with system-controlled adaptive support to help them customize effectively. MICA's adaptive support relies on a novel application of GOMS analysis to reason about the potential performance implications of different customization decisions. Using this formal reasoning, MICA generates customization recommendations aimed at maximizing the user's performance with the interface. MICA also communicates predicted time savings to the user in its rationale component, which describes why and how MICA makes recommendations. We evaluated our mixed-initiative approach through two user studies. Study One examined the general benefits of MICA's approach in comparison to a purely adaptable alternative. The results indicate that users prefer MICA's support to customizing independently, that MICA's support positively impacts performance with the interface (in terms of time on task), and that MICA reduces customization time. Study Two explored the utility of MICA's rationale. With a focus on qualitative data, the study revealed that the majority of users wish to have access to the rationale for reasons such as increased understanding and predictability of MICA's recommendations and increased trust in the system. The study also indicated that not all users want access to the rationale, suggesting that fine-grained transparency and predictability may not be important to all users in all contexts. Since previous work has advocated the importance of interaction transparency and predictability, the results of Study Two suggest that it would be beneficial to gain a more general understanding of when and why rationale is useful.

Quantum algorithms for finding extrema with unary predicates and related problems
Chan, Man Hon
DOI : 10.14288/1.0052063
URI : http://hdl.handle.net/2429/31586
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Kirkpatrick

Mechanism Design and Veto Mechanisms for Sequential Meeting Scheduling
Cook, James
Master’s essay available online : https://bibrrs.library.ubc.ca/vwebv/holdingsInfo?bibId=216585
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Poole

Solving reachable sets on a manifold
Cross, Elizabeth Ann
DOI : 10.14288/1.0052081
URI : http://hdl.handle.net/2429/31651
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Mitchell

Generalized high availability via virtual machine replication
Cully, Brendan Anthony
DOI : 10.14288/1.0052067
URI : http://hdl.handle.net/2429/31648
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisors : Dr. Feeley, Dr. Warfield

An effective guidance strategy for abstraction-guided simulation
de Paula, Flavio Miana
DOI : 10.14288/1.0051996
URI : http://hdl.handle.net/2429/32341
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Hu

Assistive Workflow Assembly for Life-Sciences Web Service Composition in the BioMoby Semantic Web Framework
DiBernardo, Michael Domenic
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Pottinger

Dynamic Join Points: Model and Interactions
Dutchyn, Christopher John
PhD thesis available online : https://bibrrs.library.ubc.ca/vwebv/holdingsInfo?bibId=216562
Degree : Doctor of Philosophy – PhD
Graduation date: 2007-05
Supervisor : Dr. Kiczales

By modeling dynamic join points, pointcuts, and advice in a continuation-passing style interpreter, we provide a fundamental account of these aop mechanisms. This account frames interesting type-and-effect properties of the mechanisms, such as the range of interactions between advised code and advice, and provides a general framework for describing these aspect interactions.

Bayesian network structure learning for the uncertain experimentalist : with applications to network biology
Eaton, Daniel James
DOI : 10.14288/1.0052083
URI : http://hdl.handle.net/2429/31610
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. K. Murphy

Formal equivalence checking of software specifications vs. hardware implementations
Feng, Xiushan
DOI : 10.14288/1.0051649
URI : http://hdl.handle.net/2429/30866
Degree : Doctor of Philosophy – PhD
Graduation date: 2007-05
Supervisor : Dr. Hu

Ever-growing complexity is forcing logic design to move above the register transfer level (RTL). For example, functional specifications are being written in software. These specifications are written for clarity, and are not optimized or intended for synthesis. Since the software is the target of functional validation, equivalence verification between the software specification and the RTL implementation is needed. This thesis introduces new techniques to reduce the complexity of this verification and increase the capability of current verification techniques. The first contribution improves the efficiency of sequential equivalence verification. I introduce a partitioned model checking approach using Annotated Control Flow Graphs (ACFG) to represent software specifications for sequential circuits. The approach partitions the software and hardware states based on the structure of the ACFG, and uses the flow and the edge annotations in the ACFG to guide the state-space exploration. Experimental results show that the new partitioned model checking approach runs faster than the standard global reachability analysis. The second contribution increases the scalability of combinational equivalence verification between a high-level software specification and RTL. Unlike conventional RTL-to-gate combinational equivalence verification, there are fewer structural similarities between the two models, and it is harder to find equivalent points. Furthermore, each path through the software can compute a different result, and there are an exponential number of paths. I first adapt the concept of cutpoints from hardware verification and define the analogous concept of software cutpoints, then implement a proof-of-concept cutpoint approach in my verification tool for the TI C6x family of DSPs. Experimental results show large improvements in both runtime and memory usage. Next, I introduce outpoints into the equivalence verification of software specifications vs. hardware implementations. I present a novel way to introduce cutpoints early, during the analysis of the software, rather than after a low-level hardware-equivalent has been generated, thereby avoiding the exponential enumeration of software paths as well as the logic blow-up of tracking merged paths. I evaluate this method on a challenge problem suggested by colleagues in industry. Experimental results show large improvements in runtime and memory usage due to the early cutpoint insertion.

Realistic materials and illumination environments
Ghosh, Abhijeet
DOI : 10.14288/1.0052049
URI : http://hdl.handle.net/2429/31311
Degree : Doctor of Philosophy – PhD
Graduation date: 2007-11
Supervisor : Dr. Heidrich

Throughout its history, the field of computer graphics has been striving towards increased realism. This goal has traditionally been described by the notion of photo-realism, and more recently and in many cases the more ambitious goal of perceptual realism. Photo-realistic image synthesis involves many algorithms describing the phenomena of light transport in a scene as well as its interaction with various materials. On the other hand, research in perceptual realism typically involves various tone mapping algorithms for display devices as well as algorithms that mimic the natural response of the human visual system in order to recreate the visual experience of a real scene. An important aspect of realistic rendering is the accurate modeling of the scene elements such as light sources and material reflectance properties. This dissertation proposes a set of new techniques for efficient acquisition of material properties as well as new algorithms for high quality rendering with acquired data. Here, we are mostly concerned with the acquisition and rendering of local illumination effects. In particular, we propose a new optical setup for efficient acquisition of the bidirectional reflectance distribution function (BRDF) with basis illumination and various Monte Carlo strategies for efficient sampling of direct illumination. The dissertation also looks into the display end of the image synthesis pipeline and proposes algorithms for displaying scenes on high dynamic range (HDR) displays for visual realism, and for tying the room illumination with the viewing environment for a sense of presence and immersion in a virtual environment. Here, we develop real-time rendering algorithms for driving the HDR displays as well as for active control of room illumination based on dynamic scene content. Thus, we propose contributions to the acquisition, rendering, and display end of the image synthesis pipeline while targeting real-time rendering applications, as well as high quality off-line rendering with realistic materials and illumination environments.

PyRemote : object mobility in the Python programming language
Häggholm, Petter Bengt
DOI : 10.14288/1.0052061
URI : http://hdl.handle.net/2429/31573
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Hutchinson

Failure recovery with priority progress multicast
Han, Jung-Rung
DOI : 10.14288/1.0052009
URI : http://hdl.handle.net/2429/32720
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Krasic

A virtual testbed to evaluate worm defense techniques
Hao, Shuang
DOI : 10.14288/1.0052064
URI : http://hdl.handle.net/2429/31789
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Aiello, Dr. Hutchinson

Fluid AOP : task-specific modularity
Hon, Terry
DOI : 10.14288/1.0052012
URI : http://hdl.handle.net/2429/32732
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Kiczalese

The annotators' perspective on co-authoring with structured annotations
Htun, Yamin
DOI : 10.14288/1.0052060
URI : http://hdl.handle.net/2429/31923
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisors : Dr. McGrenere, Dr. Booth

Stpc : a robust incentive mechanism for improving DHT-based peer-to-peer systems
Huang, Gary Gang
DOI : 10.14288/1.0051991
URI : http://hdl.handle.net/2429/32759
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Vuong

An introduction to virtual machines implementation and applications
Huang, Qian
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Hutchinson

Biomimetic information retrieval with spreading-activation networks
Huggett, Michael William Peter
DOI : 10.14288/1.0052031
URI : http://hdl.handle.net/2429/31334
Degree : Doctor of Philosophy – PhD
Graduation date: 2007-11
Supervisor : Dr. Rosenberg, Dr. Rasmussen (SLAIS)

Information management systems act as a prosthetic scaffold for human memory. They retain and organize information objects to be conveniently recalled in support of knowledge-based tasks. We note a striking similarity between the functions of human memory and the processes in computational information retrieval. For this reason, we ask whether it is viable to purposely design information management systems biomimetically , i.e., in a manner inspired by biological systems. Based on a comparison of cognitive models of human memory and computational information retrieval algorithms, we propose the Principles of Mnemonic Associative Knowledge (P-MAK) to describe the necessary components of biomimetic systems: the constraints of computing machines, the properties of human memory, how semantic knowledge representations are constructed, and the contexts in which information is usefully retrieved. The goal of P-MAK is to describe systems that are simple, inspectable, comprehensible, and easy to use. Since human memory as described by cognitive network models is analogous to a large associative hypertext repository, P-MAK's principles suggest that networks would be an appropriate representation format. Therefore, we build a semantic similarity network from a document corpus using information retrieval (IR) algorithms, and describe how these processes are comparable to the functions of human semantic memory. To approximate an optimal link distribution, we introduce a novel link-pruning technique to tune the network to a small-world topology. We show in a user study that a semantic network based on cognitive models can improve user access to information. The ability to recall information in appropriate contexts is also a useful property of human memory. Based on models of human episodic memory, we propose a real-time, incremental temporal index that captures some of the regularity of human information behaviour. Temporal patterns are represented using a novel cue-event-object (CEO) model, in which observed events are related to a collection of cues. The cues describe time, place, or sensory qualities and are analogous to cognitive schemas. Cues are combined to represent an event, analogous to cognitive convergence zones. The model connects related cues, events, and objects together to encode the relations present in observed occurrences. The CEO model simulates cognitive reinforcement learning to build patterns of user information behaviour. If an object is used consistently at a given time, the links connecting cues, event, and object all grow stronger; otherwise, they decay and are "forgotten". The resulting network structure can function as a recommender system by using spreading activation to retrieve objects at times and under circumstances where they have previously proven themselves useful. The model also allows users to pose queries such as when an event typically occurs, or what items are used at particular times. In a user-log experiment, we show that the CEO model quickly learns to make correct predictions of user behaviour, and increases in accuracy the more data that it is given.

RNA secondary structure prediction using hierarchical folding
Jabbari, Hosna
DOI : 10.14288/1.0052065
URI : http://hdl.handle.net/2429/32001
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Condon

Focusing knowledge work with task context
Kersten, Mik
DOI : 10.14288/1.0302110
URI : http://hdl.handle.net/2429/30897
Degree : Doctor of Philosophy – PhD
Graduation date: 2007-11
Supervisor : Dr. G. Murphy

By making information easy to browse and query, current software tools make it possible for knowledge workers to access vast amounts of information available in document repositories and on the web. However, when displaying dozens of web page search hits, hundreds of files and folders in a document hierarchy, or tens of thousands of lines of source code, these tools overload knowledge workers with information that is not relevant to the task-at-hand. The result is that knowledge workers waste time clicking, scrolling, and navigating to find the subset of information needed to complete a task. This problem is exacerbated by the fact that many knowledge workers constantly multi-task. With each task switch, they lose the context that they have built up in the browsing and query views. The combination of context loss and information overload has adverse effects on productivity because it requires knowledge workers to repeatedly locate the information that they need to complete a task. The larger the amount of information available and the more frequent the multi-tasking, the worse the problem becomes. We propose to alleviate this problem by focusing the software applications a knowledge worker uses on the information relevant to the task-at-hand. We represent the information related to the task with a task context model in which the relevant elements and relations are weighted according to their frequency and recency of access. We define operations on task context to support tailoring the task context model to different kinds of knowledge work activities. We also describe task-focused user interface mechanisms that replace the structure-centric display of information with a task-centric one. We validate the task context model with three field studies. Our preliminary feasibility study of six industry programmers tested a prototype implementation of the task context model and task-focused user interface for an integrated development environment. Our second study involved sixteen industry programmers using a production quality implementation of the task context model; these programmers experienced a statically significant increase in productivity when using task context. Our third field study tested a prototype implementation of the task context model for a file and web browsing application. The results of this study showed that task context generalizes beyond programming applications, reducing information overload and facilitating multi-tasking in a cross-section of knowledge work domains.

Optimistic and pessimistic shortest paths on uncertain terrains
Kholondyrev, Yury
DOI : 10.14288/1.0052001
URI : http://hdl.handle.net/2429/32577
Degree : Master of Science – MS
Supervisor : Dr. Evans
Graduation date: 2007-11

Model repair and editing tools
Kraevoy, Vladislav
DOI : 10.14288/1.0302113
URI : http://hdl.handle.net/2429/31370
Degree : Doctor of Philosophy – PhD
Graduation date: 2007-11
Supervisor : Dr. Sheffer

With the declining production cost and improvement of scanning technology, three-dimensional model acquisition systems are rapidly becoming more affordable. At the same time, personal computers with graphics hardware capable of displaying complex 3D models have become inexpensive enough to be available to a large population. As a result, there is, potentially, an opportunity to consider new virtual reality uses from areas as diverse as cultural heritage exploration and retail sales applications that will allow people to view associated large classes of realistic 3D objects on home computers and media devices. Although there are many physical techniques for acquiring 3D data, including laser scanners, CT or MRI scans, the basic pipeline of operations (Figure 1.1) lacks a sufficient set of tools to take the acquired data and produce a usable 3D model. This dissertation proposes a set of efficient and robust 3D data reconstruction and editing tools for such a pipeline. We look at the fundamental problems of range scan data completion, modeling, and parameterization. We propose a new cross-parameterization method for efficient calculation of a low-distortion bijective mapping between models. Recent research in digital geometry processing suggests multiple new applications for such a mapping, including pair-wise model editing [11] transferring texture and surface properties (BRDFs, normal maps, etc) [61], and fitting template meshes to multiple data sets [7, 55]. We also extend our cross-parameterization technique to support models with gaps and holes. This allows us to develop a new and robust method for template-based range scan data completion. One of the most significant obstacles in computer graphics is providing easy-to-use tools for creating and editing detailed 3D models. To this end, we present a new set of tools with which non-expert user can create detailed geometric models quickly and easily. In particular, we propose a new modeling system for creating new, original models by mixing and matching parts of pre-existing models. In this way, we eliminate the need for a user to perform complex geometric operations, and thereby reduce the modeling process to that of part selection. This dissertation also proposes a new technique for image-based modeling that allows a user to easily transform a sketch or picture into a 3D model using a 3D template model. The 3D template provides the geometric detail that cannot be inferred from an image alone. This allows the user to create detailed geometric models from pictures alone. We also introduce a real-time editing algorithm that allows the creation of new models through the deformation of existing ones. Our proposed editing algorithm has applications in such common geometric operations as mesh deformation, morphing, and blending. Thus, we propose contributions to the model repair and editing pipeline that simplifies the task of creating and repairing detailed 3D models.

Monotone schemes for degenerate and non-degenerate parabolic problems 
Limic, Mirna
DOI : 10.14288/1.0052071
URI : http://hdl.handle.net/2429/31763
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Mitchell

Summarizing user action sequences with data analysis
Low, Bertrand Yilun
DOI : 10.14288/1.0052059
URI : http://hdl.handle.net/2429/31983
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Lakshmanan

Tracking and recognizing actions of multiple hockey players using the boosted particle filter
Lu, Wei-Lwun
DOI : 10.14288/1.0052068
URI : http://hdl.handle.net/2429/31853
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Little

Using emergent team structure to focus collaboration
Minto, Shawn William
DOI : 10.14288/1.0052079
URI : http://hdl.handle.net/2429/32062
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. G. Murphy

A domain specific language for encoding design rules
Morgan, Clinton Alan
DOI : 10.14288/1.0052056
URI : http://hdl.handle.net/2429/32115
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. De Volder

Tailored scaffolding for meta-cognitive skills during analogical problem solving
Muldner, Katarzyna
DOI : 10.14288/1.0052048
URI : http://hdl.handle.net/2429/31443
Degree : Doctor of Philosophy – PhD
Graduation date: 2007-11
Supervisor : Dr. Conati

Although examples play a key role in cognitive skill acquisition, research demonstrates that learning outcomes are heavily influenced by the meta-cognitive skills students bring to bear while using examples. This dissertation involves the design, implementation and evaluation of the Example Analogy (EA)-Coach, an Intelligent Tutoring System that provides adaptive support for meta-cognitive skills during a specific type of example-based learning known as analogical problem solving (APS, using examples to aid problem solving). To encourage the targeted meta-cognitive skills, the EA-Coach provides multiple levels of scaffolding, including an innovate example-selection mechanism that aims to choose examples with the best potential to trigger learning and enable problem solving for a given student. To find such examples, a key factor that needs to be taken into account is problem/example similarity, because it impacts the APS process. However, full understanding has yet to be reached on how various levels of similarity between a problem and an example influence students' APS behaviours and subsequent outcomes. Here, we provide a novel classification of problem/example differences and hypotheses regarding their impact on APS. In particular, we propose that certain differences between a problem and an example may actually be beneficial in helping students learn from APS, because they promote the necessary meta-cognitive skills. However, given the great variance in terms of knowledge and meta-cognitive skills that exists between students, a key challenge with our approach is how to select examples that provide enough scaffolding for different learners. Our solution to this challenge involves a two-step decision-theoretic process. First, the EA-Coach student model, which corresponds to a dynamic Bayesian network, is used to predict how a candidate example will help a student solve the problem and learn from doing so. Second, the model's prediction is quantified via a utility function, which assigns an expected utility to the candidate example. This process allows the framework to present to the student the example with the highest expected utility for enabling learning and problem solving. We evaluated this approach via a controlled laboratory study, which demonstrated the EA-Coach's pedagogical effectiveness for supporting problem solving and triggering meta-cognitive skills needed for learning during APS.

Implementation of the Smith-Waterman Algorithm on the FLEET Simulator
Pang, Alfred Yu-Han
Master’s essay available online : https://bibrrs.library.ubc.ca/vwebv/holdingsInfo?bibId=216586
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Greenstreet

Perception-based design, including haptic feedback in expressive music interfaces
Pedrosa, Ricardo
DOI : 10.14288/1.0052072
URI : http://hdl.handle.net/2429/32053
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. MacLean

A distributed snapshot protocol for virtual machines
Peng, Gang
DOI : 10.14288/1.0302115
URI : http://hdl.handle.net/2429/32049
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Hutchinson, Dr. Warfield

Hierarchical SegmentBoost A segment level classification approach to object recognition
Reynolds, Jordan Michael
DOI : 10.14288/1.0052069
URI : http://hdl.handle.net/2429/32286
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisors : Dr. K. Murphy, Dr. Little

Modeling developable surfaces from arbitrary boundary curves
Rose, Kenneth Lloyd Patrick
DOI : 10.14288/1.0052002
URI : http://hdl.handle.net/2429/32322
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Sheffer

A parallel workflow for online correlation and clique-finding : with applications to finance
Rostoker, Camilo Ellis
DOI : 10.14288/1.0051985
URI : http://hdl.handle.net/2429/29661
Degree : Master of Science - MSc
Graduation Date : 2007-05
Supervisors : Dr. Hoos, Dr. Wagner

Safari Ghahsareh, Mohammad Ali see Ali Safari, Mohammad

Comparing episodic and semantic interfaces for task boundary identification
Safer, Izzet
DOI : 10.14288/1.0302118
URI : http://hdl.handle.net/2429/32338
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. G. Murphy

Asking and answering questions during a programming change task 
Sillito, Jonathan
DOI : 10.14288/1.0052042
URI : http://hdl.handle.net/2429/31065
Degree : Doctor of Philosophy – PhD
Graduation date: 2007-05
Supervisor : Dr. De Volder

Despite significant existing empirical work, little is known about the specific kinds of questions programmers ask when evolving a code base. Understanding precisely what information a programmer needs about the code base as they work is key to determining how to better support the activity of programming. The goal of this research is to provide an empirical foundation for tool design based on an exploration of what programmers need to understand about a code base and of how they use tools to discover that information. To this end, we undertook two qualitative studies of programmers performing change tasks to medium to large sized programs. One study involved newcomers working on assigned change tasks to a medium-sized code base. The other study involved industrial programmers working on their own change tasks to code with which they had experience. The focus of our analysis has been on what information a programmer needs to know about a code base while performing a change task and also on how they go about discovering that information. Based on a systematic analysis of the data from these user studies as well as an analysis of the support that current programming tools provide for these activities, this research makes four key contributions: (1) a catalog of 44 types of questions programmers ask, (2) a categorization of those questions into four categories based on the kind and scope of information needed to answer a question, (3) a description of important context for the process of answering questions, and (4) a description of support that is missing from current programming tools.

The scalability of AspectJ
Singh, Arjun Assa
DOI : 10.14288/1.0052011
URI : http://hdl.handle.net/2429/32349
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Kiczales

Improving aspect mining with program dependencies 
Singh, Navjot
DOI : 10.14288/1.0052006
URI : http://hdl.handle.net/2429/32354
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Wohlstadter

Incomplete factorization preconditioners for least squares and linear and quadratic programming
Sirovljevic, Jelena
DOI : 10.14288/1.0052082
URI : http://hdl.handle.net/2429/32071
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Friedlander

Incorporating affect into the design of 1-D rotary physical controls
Swindells, Colin Edward
DOI : 10.14288/1.0052050
URI : http://hdl.handle.net/2429/31168
Degree : Doctor of Philosophy – PhD
Graduation date: 2007-05
Supervisors : Dr. MacLean, Dr. Booth

The visceral emotional reactions that users have to technologies is increasingly understood to be important in terms of safety, performance, and pleasure in its own right. This thesis systematically explores users's emotional (affect) reactions to everyday physical manual controls, in order to inform a design process that considers appropriate affective response as well as performance relationships. Design of both mechanical and emerging mechatronic physical controls are addressed. This novel design process includes parameterizing second order (inertial) dynamics using a system identification technique, and rendering models on a custom force-feedback knob. Next, this thesis explores biometric and self-reported measures of the affective responses elicited by these dynamics, and an iterative prototyping tool for rapid refinement of the "feel" of physical controls. This research impacts use of the passive physical interfaces such as mechanical knobs and sliders that are already ubiquitous in our everyday environments, as well as the active physical controls that are emerging in embedded computing environments such as cars, games, and medical devices.

Building large sets of haptic icons : rhythm as a design parameter, and between-subjects MDS for evaluation
Ternes, David Richard
DOI : 10.14288/1.0052080
URI : http://hdl.handle.net/2429/32268
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. MacLean

Valuation uncertainty and imperfect introspection in second-price auctions
Thompson, David Robert Martin
DOI : 10.14288/1.0052005
URI : http://hdl.handle.net/2429/32362
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Leyton-Brown

Tomographic reconstruction of transparent objects 
Trifonov, Borislav Danielov
DOI : 10.14288/1.0052044
URI : http://hdl.handle.net/2429/31338
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Heidrich

Hybrid design of MPI over SCTP
Tsai, Mike Yao Chen
DOI : 10.14288/1.0302119
URI : http://hdl.handle.net/2429/32492
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisor : Dr. Wagner

Secure query answering and privacy-preserving data publishing
Wang, Hui
DOI : 10.14288/1.0051391
URI : http://hdl.handle.net/2429/31721
Degree : Doctor of Philosophy – PhD
Graduation date: 2007-11
Supervisors : Dr. Lakshmanan

The last several decades have witnessed a phenomenal growth in the networking infrastructure connecting computers all over the world. The Web has now become an ubiquitous channel for information sharing and dissemination. More and more data is being exchanged and published on the Web. This growth has created a whole new set of research challenges, while giving a new spin to some existing ones. For example, XML(eXtensible Markup Language), a self-describing and semi-structured data format, has emerged as the standard for representing and exchanging data between applications across the Web. An important issue of data publishing is the protection of sensitive and private information. However, security/privacy-enhancing techniques bring disadvantages: security-enhancing techniques may incur overhead for query answering, while privacy-enhancing techniques may ruin data utility. In this thesis, we study how to overcome such overhead. Specifically, we address the following two problems in this thesis: (a) efficient and secure query evaluation over published XML databases, and (b) publishing relational databases while protecting privacy and preserving utility. The first part of this thesis focuses on efficiency and security issues of query evaluation over XML databases. To protect sensitive information in the published database, security policies must be defined and enforced, which will result in unavoidable overhead. Due to the security overhead and the complex structure of XML databases, query evaluation may become inefficient. In this thesis, we study how to securely and efficiently evaluate queries over XML databases. First, we consider the access-controlled database. We focus on a security model by which every XML element either is locally assigned a security level or inherits the security level from one of its ancestors. Security checks in this model can cause considerable overhead for query evaluation. We investigate how to reduce the security overhead by analyzing the subtle interactions between inheritance of security levels and the structure of the XML database. We design a sound and complete set of rules and develop efficient, polynomial-time algorithms for optimizing security checks on queries. Second, we consider encrypted XML database in a "database-as-service" model, in which the private database is hosted by an untrusted server. Since the untrusted server has no decryption key, its power of query processing is very limited, which results in inefficient query evaluation. We study how to support secure and efficient query evaluation in this model. We design the metadata that will be hosted on the server side with the encrypted database. We show that the presence of the metadata not only facilitates query processing but also guarantees data security. We prove that by observing a series of queries from the client and responses by itself, the server's knowledge about the sensitive information in the database is always below a given security threshold. The second part of this thesis studies the problem of preserving both privacy and the utility when publishing relational databases. To preserve utility, the published data will not be perturbed. Instead, the base table in the original database will be decomposed into several view tables. First, we define a general framework to measure the likelihood of privacy breach of a published view. We propose two attack models, unrestricted and restricted models, and derive formulas to quantify the privacy breach for each model. Second, we take utility into consideration. Specifically, we study the problem of how to design the scheme of published views, so that data privacy is protected while maximum utility is guaranteed. Given a database and its scheme, there are exponentially many candidates for published views that satisfy both privacy and utility constraints. We prove that finding the globally optimal safe and faithful view, i.e., the view that does not violate any privacy constraints and provides the maximum utility, is NP-hard. We propose the locally optimal safe and faithful view as the heuristic, and show how we can efficiently find a locally optimal safe and faithful view in polynomial time.

Access control in XML PDMS query answering
Wang, Shuan
DOI : 10.14288/1.0052052
URI : http://hdl.handle.net/2429/31428
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Lakshmanan, Dr. Pottinger

Preventing denial-of-service attacks with packet symmetry
Wood, Michael David
DOI : 10.14288/1.0052073
URI : http://hdl.handle.net/2429/32196
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisors : Dr. Aiello, Dr. Warfield

Bayesian inference on change point problems
Xuan, Xiang
DOI : 10.14288/1.0052076
URI : http://hdl.handle.net/2429/31707
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. K. Murphy

The design and implementation of a scheduler and route planner for wheelchair users 
Yang, Suling
DOI : 10.14288/1.0052058
URI : http://hdl.handle.net/2429/31745
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Mackworth

Tool support for understanding and diagnosing pointcut expressions
Ye, Lingdong
DOI : 10.14288/1.0052055
URI : http://hdl.handle.net/2429/32199
Degree : Master of Science – MSc
Graduation date: 2007-11
Supervisors : Dr. De Volder, Dr. Kiczales

Data-driven kinematic and dynamic models for character animation
Yin, KangKang
DOI : 10.14288/1.0052085
URI : http://hdl.handle.net/2429/31759
Degree : Doctor of Philosophy – PhD
Graduation date: 2007-11
Supervisor : Dr. Pai, Dr. van de Panne

Human motion plays a key role in the production of films, video games, virtual reality applications, and the control of humanoid robots. Unfortunately, it is hard to generate high quality human motion for character animation either manually or algorithmically. As a result, approaches based on motion capture data have become a central focus of character animation research in recent years. We observe three principal weaknesses in previous work using data-driven approaches for modelling human motion. First, basic balance behaviours and locomotion tasks are currently not well modelled. Second, the ability to produce high quality motion that is responsive to its environment is limited. Third, knowledge about human motor control is not well utilized. This thesis develops several techniques to generalize motion capture character animations to balance and respond. We focus on balance and locomotion tasks, with an emphasis on responding to disturbances, user interaction, and motor control integration. For this purpose, we investigate both kinematic and dynamic models. Kinematic models are intuitive and fast to construct, but have narrow generality, and thus require more data. A novel performance-driven animation interface to a motion database is developed, which allows a user to use foot pressure to control an avatar to balance in place, punch, kick, and step. We also present a virtual avatar that can respond to pushes, with the aid of a motion database of push responses. Consideration is given to dynamics using motion selection and adaption. Dynamic modelling using forward dynamics simulations requires solving difficult problems related to motor control, but permits wider generalization from given motion data. We first present a simple neuromuscular model that decomposes joint torques into feedforward and low-gain feedback components, and can deal with small perturbations that are assumed not to affect balance. To cope with large perturbations we develop explicit balance recovery strategies for a standing character that is pushed in any direction. Lastly, we present a simple continuous balance feedback mechanism that enables the control of a large variety of locomotion gaits for bipeds. Different locomotion tasks, including walking, running, and skipping, are constructed either manually or from motion capture examples. Feedforward torques can be learned from the feedback components, emulating a biological motor learning process that leads to more stable and natural motions with low gains. The results of this thesis demonstrate the potential of a new generation of more sophisticated kinematic and dynamic models of human motion.

A Region-Based Filter for Video Segmentation
Yurick, Michael Darius
Master’s thesis available online : https://bibrrs.library.ubc.ca/vwebv/holdingsInfo?bibId=216659
Degree : Master of Science – MSc
Graduation date: 2007-05
Supervisor : Dr. Little