The use of randomized algorithms and protocols is ubiquitous in computer science. Randomized solutions are typically faster and simpler than deterministic ones for the same problem. In addition, many computational problems (for example in cryptography and distributed computing) are impossible to solve without access to randomness. In computer science, access to randomness is usually modeled as access to a string of uncorrelated uniformly random bits. Although it is widely believed that many physical phenomena are inherently unpredictable, there is a gap between the computer science model of randomness and what is actually available. It is not clear where one could find such a source of uniformly distributed bits. In practice, computers generate random bits in ad-hoc ways, with no guarantees on the quality of their distribution. One aim of this thesis is to close this gap and identify the weakest assumption on the source of randomness that would still permit the use of randomized algorithms and protocols. This is achieved by building randomness extractors ... Such an algorithm would allow us to use a compromised source of randomness to obtain truly random bits, which we could then use in our original application. Randomness extractors are interesting in their own right as combinatorial objects that look random in strong ways. They fall into the class of objects whose existence is easy to check using the probabilistic method (i.e., almost all functions are good randomness extractors), yet finding explicit examples of a single such object is non-trivial. Expander graphs, error correcting codes, hard functions, epsilon biased sets and Ramsey graphs are just a few examples of other such objects. Finding explicit examples of extractors is part of the bigger project in the area of derandomization of constructing such objects which can be used to reduce the dependence of computer science solutions on randomness. These objects are often used as basic building blocks to solve problems in computer science. The main results of this thesis are: Extractors for Independent Sources: The central model that we study is the model of independent sources. Here the only assumption we make (beyond the necessary one that the source of randomness has some entropy/unpredictability), is that the source can be broken up into two or more independent parts. We show how to deterministically extract true randomness from such sources as long as a constant (as small as 3) number of sources is available with a small amount of entropy. Extractors for Small Space Sources: In this model we assume that the source is generated by a computationally bounded processes -- a bounded width branching program or an algorithm that uses small memory. This seems like a plausible model for sources of randomness produced by a defective physical device. We build on our work on extractors for independent sources to obtain extractors for such sources. Extractors for Low Weight Affine Sources: In this model, we assume that the source gives a random point from some unknown low dimensional affine subspace with a low-weight basis. This model generalizes the well studied model of bit-fixing sources. We give new extractors for this model that have exponentially small error, a parameter that is important for an application in cryptography. The techniques that go into solving this problem are inspired by the techniques that give our extractors for independent sources. Ramsey Graphs: A Ramsey graph is a graph that has no large clique or independent set. We show how to use our extractors and many other ideas to construct new explicit Ramsey graphs that avoid cliques and independent sets of the smallest size to date. Distributed Computing with Weak Randomness: Finally, we give an application of extractors for independent sources to distributed computing. We give new protocols for Byzantine Agreement and Leader Election that work when the players involved only have access to defective sources of randomness, even in the presence of completely adversarial behavior at many players and limited adversarial behavior at every player. In fact, we show how to simulate any distributed computing protocol that assumes that each player has access to private truly random bits, with the aid of defective sources of randomness. / text

M. Tech. Information Networks / This dissertation reports on the development of an algorithm based on e-commerce matchmaking to select students. The student selection is an important strategic decision making task for the management of higher educational institutions and human resource departments of corporate organizations. The selection task has proven to be tedious mainly because of the decision process, the fundamental assumptions made and the level of accuracy achieved. The decision error that results from inaccurate student selection process is one source of skill mismatch. This work therefore seeks to improve the student selection accuracy using matchmaking approach. In doing so, e-commerce matchmaking method is applied to student selection and offered as an effective way of integrating cognitive and noncognitive skills to improve the selection accuracy. The efficacy of the matchmaking algorithm is demonstrated through a prototype implementation of the algorithm and specifically applied to university student selection.

Coupled spring equations for modelling the motion of two springs with weights attached, hung in series from the ceiling are described. For the linear model using Hooke’s Law, the motion of each weight is described by a fourthorder linear differential equation. A nonlinear model is also described and damping and external forcing are considered. The model has many features that permit the meaningful introduction of many concepts including: accuracy of numerical algorithms, dependence on parameters and initial conditions, phase and synchronization, periodicity, beats, linear and nonlinear resonance, limit cycles, harmonic and subharmonic solutions. These solutions produce a wide variety of interesting motions and the model is suitable for study as a computer laboratory project in a beginning course on differential equations or as an individual or a small-groupundergraduate research project.

Division is one of the most fundamental arithmetic operations and is used extensively in engineering, scientific, mathematical and cryptographic applications. The implementation of arithmetic operation such as division, is complex and expensive in hardware. Unlike addition and subtraction, division requires several iterative computational steps on given operands to produce the result. Division, in the past has often been perceived as an infrequently used operation and received not as much attention but it is one of the most difficult operations in computer arithmetic. The techniques of implementation in hardware of such an iterative computation impacts the speed, the area and power of the digital circuit. For this reason, we consider two division algorithms based on their step size in shift. Algorithm 1 operates on fixed shift step size and has a fixed number of iteration while the Algorithms 2 operates on variable shift step size and requires considerably fewer number of iterations. In this thesis, technique is provided to save power and speed up the overall computation. It also looks at different design goal strategies and presents a comparative study to asses how each of the two design perform in terms of area, delay and power consumption. / Graduate / salmankh@uvic.ca

published_or_final_version / abstract / Computer Science / Master / Master of Philosophy

published_or_final_version / abstract / Electrical and Electronic Engineering / Master / Master of Philosophy

published_or_final_version / abstract / toc / Computer Science and Information Systems / Master / Master of Philosophy

published_or_final_version / abstract / toc / Electrical and Electronic Engineering / Master / Master of Philosophy

published_or_final_version / Computer Science / Master / Master of Philosophy

published_or_final_version / Computer Science / Master / Master of Philosophy