<p>The global routing problem is becoming more and more important in the design of today's integrated circuits. A small chip may contain up to millions of components and wires. Although global routing can be formulated as an integer linear programming problem, it is hard to solve directly using currently available solvers. We discuss a relaxation of the problem to a linear programming (LP) formulation with a fractional solution. However, the relaxation yields an NP-hard problem. In this thesis, we introduce three relaxations: the primal (<em>Pc</em>), the Lagrange dual (<em>Dc</em>), and the unimodular (<em>PI</em>) formulation. At optimality, all three problems have the same objective value. A new way to tackle the LP problem is introduced: first solve the <em>Dc</em> and try to find Lagrange multipliers in order to build the <em>PI</em> model, from which an integer solution can be obtained directly. An implementation based on the discussed approaches was tested using IBM benchmarks.</p> / Master of Applied Science (MASc)

<p>This thesis considers the Shannon capacity of multiuser multiple input multiple output (MIMO) wireless communication systems. That is, the fundamental limit on the rates at which data can be reliably communicated. The focus is on scenarios in which the channel has long coherence times and perfect channel state information is available to both transmitters and receivers. The thesis considers two important design problems in multiuser MIMO wireless communication systems: the design of the sumrate optimal input distribution for the MIMO multiple access channel (MIMO MAC), and the design of the sum-rate optimal input distribution for the MIMO broadcast channel (MIMO BC).</p> <p>The thesis considers algorithms for solving these design problems that are based on the principle of iterative water-filling. The contributions of the thesis are twofold. First, a correct and rigorous proof of convergence of the family of water-filling algorithms is derived. This proof overcomes weaknesses in the previous attempts of others to prove convergence. Second, an efficient algorithm is presented for the water-filling procedure that lies at the heart of the iterative water-filling algorithm. This algorithm will open the door for further efficient utilization of the iterative water-filling algorithm. This novel algorithm is based on the principle of Fibonacci search, and since the iterative water filling algorithm involves repeated water-filling procedures, the impact of this efficient algorithm is magnified.</p> <p>The outcomes of this research are that the iterative water-filling algorithms are mathematically validated for the above-mentioned design problems in multiuser MIMO wireless communication systems, and that the implementation of these algorithms is made more efficient through the application of the efficient Fibonacci search method for the underlying water-filling procedure.</p> / Master of Applied Science (MASc)

<p>Why sexual reproduction and recombination are prevalent among living organisms is one of the most intriguing questions in biology. It has been studied extensively from a multitude of perspectives ranging from multi-locus population genetics models, in-vivo and more recently in-silico systems. The analysis of complex metabolic networks in living organisms reveals that they can be decomposed into several functionally distinct sub-groups, called modules. This property of modular organization has been accepted as a general organizational feature of biological networks, and has important consequences for the evolution of biologically complex features through different combinations of simpler functions. In this light it has been shown that sexual populations can develop a form of modularity on the genetic level, called mixability, where alleles are selected for their ability to function under a wide variety of genetic contexts, much like a module.</p> <p>However the functional implications of mixability still remain to be seen. We wish to assess whether mixability can develop in a simplified model of populations undergoing evolution for increased biological complexity through the construction of their genomes into simple metabolic chains. We modelled the fitness and growth of complexity in sexual and asexual populations in the presence of recurrent mutations which increase the ability of genes to interact with one another. Our results show that mixability is selected for in sexual populations when genetic diversity is high and under certain conditions gives sexual populations a competitive edge over asexual populations through increased genetic complexity. This provides a starting point for examining the effect of mixability upon growing genetic networks and its role in influencing larger scale modularity, which thus far has not been significantly explored.</p> / Master of Science (MS)

<p>This thesis provides a Fully Polynomial Time Approximation Scheme (FPTAS) for the minimum total weighted tardiness (TWT) problem with a constant number ofdistinct due dates.</p> <p>Given a sequence ofjobs on a single machine, each with a weight, processing time, and a due date, the tardiness of a job is the amount of time that its completion time goes beyond its due date. The TWT problem is to find a schedule of the given jobs such that the total weighted tardiness is minimized. This problem is NP-hard even when the number of distinct due dates is fixed. In this thesis, we present a dynamic programming algorithm for the TWT problem with a constant number of distinct due dates first and then adopt a rounding scheme to obtain an FPTAS.</p> <p>Three major points that we make in this algoritlun are: we observe a series of structural properties of optimal schedules so that we shrink the state space of the DP; we make use of preemption (i.e. allowing the processing of a job to be interrupted and restarted later) for the design of the DP; the rounding scheme that we adopt guarantees that a factor 1+ ℇ of the optimal solution is generated and the algorithm runs within a polynomial time of the problem size.</p> / Master of Applied Science (MASc)

The amount of multimedia content available via the Internet, and the number of formats in which it is encoded, stored and delivered continues to grow rapidly. So too the number and diversity of the devices and software applications which produce, process and consume such content. This constantly changing landscape presents an increasing challenge to interoperability, since more and more software and hardware must be upgraded as new formats are developed. However, many of the operations performed on multimedia content are similar across coding formats. In recognising this, this thesis proposes several approaches to format-independent media processing, with an emphasis on content delivery. This considerably simplifies interoperability, since support for a new content format may be provided by disseminating a data file, rather than requiring application and device providers to extend and modify their software and hardware. A fundamental requirement for format-independence is the ability to describe the structure of any given format in a way that exposes how it may be fragmented for delivery or processing, and how other data important to the processing (for instance temporal or scalability parameters) can be extracted from the binary data. Several meta-syntax languages are evaluated that (to greater or lesser degree) perform this function. Of these, the most suitable for general use in format-independent processors is found to be MPEG-21’s Bitstream Syntax Description Language (BSDL). Its general suitability notwithstanding, BSDL exhibits several critical flaws when used to describe and process modern content formats. In response, this thesis proposes several new features for the language which significantly reduce processing complexity, and provide extensibility for complex data types. These features are implemented and validated using bitstreams of real-world length, which enable a linear response of approximately 10 times the speed of playback (on the particular test machine used), for videos up to one hour in duration. Digital media increasingly encompasses a wide range of metadata, as well as collections of related content (a DVD and it’s “special features”, for instance). Several recent standards address generic virtual containers for such rich content. While these standards—which include MPEG-21 and TVAnytime—provide numerous tools for interacting with rich media objects, they do not provide a framework for streaming or delivery of such data. This thesis presents the Bitstream Binding Language (BBL), a format-independent tool that describes how multimedia content and metadata may be bound into delivery formats. Using a BBL description, a generic processor can map rich content (an MPEG-21 Digital Item, for example) into a streaming or static delivery format. BBL provides a universal syntax for fragmentation and packetisation of both XML and binary data, and allows new content and metadata formats to be delivered without requiring the addition of new software to the delivery infrastructure. The BBL framework is validated and tested against a number of application scenarios including a format-independent streaming server, generic metadata syntax translation, virtual container assembly, and a format-independent hinter.Finally, it is observed that much of the semantic metadata that is generated to describe multimedia content could also be used to improve the decisions that must be made in order to transmit it effectively. Indeed, methods have been proposed for using specific semantic concepts in the delivery process. However, until now, no high-level system has been proposed that is able to take arbitrary semantic metadata, and utilise it in the multimedia delivery decision-making process. This thesis proposes such a system. It combines the aforementioned semantic concepts with other existing work in Rate-Distortion Optimisation for multimedia delivery, scalable content formats, and syntax description, and then develops a generalised framework to permit an arbitrary range of semantic metadata and optimisation techniques to be utilised. This objective is accomplished by utilising schema languages to describe the details of any given content or metadata, so that declarative mapping rules can be specified for translating from format-specific data points to format-independent concepts that are directly used by the framework. This translation can then be performed using software or hardware that knows nothing about the specific format it is processing.This thesis describes a particular embodiment of the semantic-aware multimedia delivery system which was implemented in order to verify its key assertions. It presents the results of subjective testing that was performed on several short news clips encoded using H.264/SVC scalable video coding, and Scalable-To-Lossless (SLS) au dio coding. Each clip was adapted to four target bitrates, using both of two methods: (a) using the semantic-aware system to devote a greater proportion of the available bandwidth to that part of the content (audio or video) that was conveying more of the semantics at any given time; and (b) at a constant bit-rate with the same average rate as clip (a). Test participants were shown each pair of clips (a and b) in a random order and were asked to evaluate which was more successful at conveying the meaning of the story. The result of this subjective testing was a 72% preference for those clips which had been adapted so as to devote more bandwidth to the semantically-important parts of the content.

The amount of multimedia content available via the Internet, and the number of formats in which it is encoded, stored and delivered continues to grow rapidly. So too the number and diversity of the devices and software applications which produce, process and consume such content. This constantly changing landscape presents an increasing challenge to interoperability, since more and more software and hardware must be upgraded as new formats are developed. However, many of the operations performed on multimedia content are similar across coding formats. In recognising this, this thesis proposes several approaches to format-independent media processing, with an emphasis on content delivery. This considerably simplifies interoperability, since support for a new content format may be provided by disseminating a data file, rather than requiring application and device providers to extend and modify their software and hardware. A fundamental requirement for format-independence is the ability to describe the structure of any given format in a way that exposes how it may be fragmented for delivery or processing, and how other data important to the processing (for instance temporal or scalability parameters) can be extracted from the binary data. Several meta-syntax languages are evaluated that (to greater or lesser degree) perform this function. Of these, the most suitable for general use in format-independent processors is found to be MPEG-21’s Bitstream Syntax Description Language (BSDL). Its general suitability notwithstanding, BSDL exhibits several critical flaws when used to describe and process modern content formats. In response, this thesis proposes several new features for the language which significantly reduce processing complexity, and provide extensibility for complex data types. These features are implemented and validated using bitstreams of real-world length, which enable a linear response of approximately 10 times the speed of playback (on the particular test machine used), for videos up to one hour in duration. Digital media increasingly encompasses a wide range of metadata, as well as collections of related content (a DVD and it’s “special features”, for instance). Several recent standards address generic virtual containers for such rich content. While these standards—which include MPEG-21 and TVAnytime—provide numerous tools for interacting with rich media objects, they do not provide a framework for streaming or delivery of such data. This thesis presents the Bitstream Binding Language (BBL), a format-independent tool that describes how multimedia content and metadata may be bound into delivery formats. Using a BBL description, a generic processor can map rich content (an MPEG-21 Digital Item, for example) into a streaming or static delivery format. BBL provides a universal syntax for fragmentation and packetisation of both XML and binary data, and allows new content and metadata formats to be delivered without requiring the addition of new software to the delivery infrastructure. The BBL framework is validated and tested against a number of application scenarios including a format-independent streaming server, generic metadata syntax translation, virtual container assembly, and a format-independent hinter.Finally, it is observed that much of the semantic metadata that is generated to describe multimedia content could also be used to improve the decisions that must be made in order to transmit it effectively. Indeed, methods have been proposed for using specific semantic concepts in the delivery process. However, until now, no high-level system has been proposed that is able to take arbitrary semantic metadata, and utilise it in the multimedia delivery decision-making process. This thesis proposes such a system. It combines the aforementioned semantic concepts with other existing work in Rate-Distortion Optimisation for multimedia delivery, scalable content formats, and syntax description, and then develops a generalised framework to permit an arbitrary range of semantic metadata and optimisation techniques to be utilised. This objective is accomplished by utilising schema languages to describe the details of any given content or metadata, so that declarative mapping rules can be specified for translating from format-specific data points to format-independent concepts that are directly used by the framework. This translation can then be performed using software or hardware that knows nothing about the specific format it is processing.This thesis describes a particular embodiment of the semantic-aware multimedia delivery system which was implemented in order to verify its key assertions. It presents the results of subjective testing that was performed on several short news clips encoded using H.264/SVC scalable video coding, and Scalable-To-Lossless (SLS) au dio coding. Each clip was adapted to four target bitrates, using both of two methods: (a) using the semantic-aware system to devote a greater proportion of the available bandwidth to that part of the content (audio or video) that was conveying more of the semantics at any given time; and (b) at a constant bit-rate with the same average rate as clip (a). Test participants were shown each pair of clips (a and b) in a random order and were asked to evaluate which was more successful at conveying the meaning of the story. The result of this subjective testing was a 72% preference for those clips which had been adapted so as to devote more bandwidth to the semantically-important parts of the content.

In recent years, new Artificial Intelligence technologies have mimicked examples of collective intelligence occurring in the natural world including flocks of birds, schools of fish, and swarms of bees. One company in particular, Unanimous AI, built a platform (UNU Swarm) that enables a group of humans to make decisions as a single mind by forming a real-time closed-loop feedback system for individuals. This platform has proven the ability to amplify the predictive ability of groups of humans in realms including sports, medicine, politics, finance, and entertainment. Previous research has demonstrated it is possible to further enhance knowledge accumulation within a crowd through curation and bias methods applied to individuals in the crowd.\newline This study explores the efficacy of applying a machine learning pipeline to identify the top performing individuals in the crowd based on a structural profile of survey responses. The ultimate goal is to select these users as Swarm participants to improve the accuracy of the overall system. Unanimous AI provided 24 weeks of survey data collection consisting of 1,139 users from the NHL 2017-2018 season. By applying a machine learning pipeline, this study able to curate a crowd consisting of users that had an average z-score 0.309 and Wisdom of the Crowd prediction accuracy of 61.5%, which is 4.1% higher than a randomly selected crowd and 1.4% lower than Vegas favorite picks.

<p>Many algorithms, particularly in the area of image processing, are expensive to develop and computationally resource intensive. We illustrate the advantages of symbolic code generation using an example - closed-loop visual target recognition and tracking in extreme lighting conditions. We quantify the effect of symbolic code generation methods on code efficiency, and explain how these methods allowed us to reduce the development time as well as improve reliability. Working directly with symbolic models improves software quality by reducing transcription errors, and enabled us to rapidly prototype different models for the visual tracking application, where the need to evaluate trackers in their real-time context precludes the effective use of scripting languages. We describe the model in detail, including formulations as an optimization problem; explain the challenges in solving the model; present our method of building the solvers; and summarize the impact on the performance of our methods.</p> / Master of Applied Science (MASc)

<p>A theory library for a mechanized mathematics system (MMS) is a collection of mathematical theories which serves as a database of mathematics. A powerful library plays a significant role in making an MMS useful. This thesis demonstrates some of the techniques needed for generating a large theory library for an MMS, that has capability of both computation and deduction, by developing a small portion of a theory library. In the theory library presented in this thesis, the module system Mei, a (lamda)-calculus style module system that supports higher-order functors, is employed to manage mathematical theories. Chiron, a logic derived from von-Neumann-Bernays-Godel set theory, is used as the underlying logic of the system, and biform theories, which can include both formulas and algorithms as axioms, are used to present mathematical theories. The theory library given in this thesis is based on the branch of mathematics called calculus.</p> / Master of Science (MS)

Record linkage is the task of identifying records within one or multiple databases that refer to the same entity. Currently, there exist many different approaches for record linkage. Some approaches incorporate the use of heuristic rules, mathematical models, Markov models, or machine learning. This thesis focuses on the application of record linkage to genealogical records within family trees. Today, large collections of genealogical records are stored in databases, which may contain multiple records that refer to a single individual. Resolving duplicate genealogical records can extend our knowledge on who has lived and more complete information can be constructed by combining all information referring to an individual. Simple string matching is not a feasible option for identifying duplicate records due to inconsistencies such as typographical errors, data entry errors, and missing data. Record linkage algorithms can be classified under two broad categories, a rule-based or heuristic approach, or a probabilistic-based approach. The Cocktail Approach, presented by Shirley Ong Ai Pei, combines a probabilistic-based approach with a rule-based approach for record linkage. This thesis discusses a re-implementation and adoption of the Cocktail Approach to genealogical records.