Computer Science

Permanent URI for this collection

http://hdl.handle.net/10066/453

Browse

Now showing 1 - 20 of 188

Efficient Handling of Dependence Analysis for Arrays
(2001) Seater, Robert; Wonnacott, David G.
In this paper, I discuss what array dependence analysis is, and how we can phrase questions about dependencies as questions about integer feasibility. I present the straight forward approaches to dealing with equalities, inequalities, and disequalities. I also give a sampling of the more subtle approaches to each; with a particular focus on improving Fourier's Method and on the LI(2)-unit subdomain. Furthermore, I present the workings of a new approach to reduce the exponential behavior of disequality analysis.
The Number Field Sieve
(2002) Lukac, Martin
The Number Field Sieve is currently the fastest algorithm for factoring. This paper covers each step of the algorithm explaining in detail the mathematics behind this version of the algorithm. The conjectured time complexity of the Number Field Sieve is also covered in detail. Factoring integers is interesting because the majority of public key cryptography is based on the fact that it is difficult to factor very large number.
Timber Ho! : An Examination of the Properties of Special Balanced Search Trees
(2002) Barkan, David; Wonnacott, David G.
In Computer Science, we are always looking for ways to do things quickly and efficiently. A computer has the ability to solve problems quickly, but as the size of these problems becomes very large, we run the risk of wasting our available computational power on inefficient algorithms. This is especially important when considering data structures that potentially contain millions of bits of information. A binary search tree is a good implementation of such a data structure when considering fast search and insertion operations. With some conditions in place, these operations can be made to run in O(log n) time on a tree with n nodes. The most important condition is that the tree is balanced; without this condition a large tree could simply be a linked list and run in O(n) time, a significant slowdown. My thesis examines three binary (or near-binary) search trees with different properties that fulfill the balance condition. Search and insertion algorithms are given for each, along with analysis and correctness proofs. While these trees are not normally used in practical applications of computers, they demonstrate that the implementation of efficient algorithms and data structures is much more than a trivial matter.
Natural Language Processing and Translation using Augmented Transition Networks and Semantic Networks
(2003) Ramos, Juan; Kumar, Deepak
The problem of computers understanding and communicating with humans using natural languages such as English is a complicated task with many details to examine and explore. The goal of this project, then, is to examine some of the established data structures and methods used to enable computers to understand and generate natural language. In an attempt to contribute some original material, we will also consider how a computer might be able to translate sentences between English and Spanish. The techniques covered in this paper are well-established data structures and methods for parsing and generating natural language sentences. In particular, we will pay close attention to the augmented transition network model (ATN) and semantic networks. The ATN data structure is a powerful mechanism for interpreting natural language constructs, most notably due to its ability to both parse and generate language with a single network. Extending the ATN structure slightly will also allow for our goal of language translation. The semantic network model will assist in this endeavor by representing the input data as a network of entity nodes connected by labeled arcs that represent the relationship between nodes. This model abstracts the input into a form independent from the source and target languages, facilitating the task of translation immensely. Finally, we will provide a demonstration of how SNePS, a LISP-based system that incorporates ATNs and semantic networks, translates a simple set of sentences using the techniques described.
Locality and Parallel Optimizations for Parallel Supercomputing
(2003) Harrison, Ian; Wonnacott, David G.
Heuristic Counterpoint
(2004) Ambrogi, Timothy; Dougherty, John P.
This paper will introduce and formalize the problem of generating 16th-century Fuxian counterpoint using search algorithms. Several algorithms will be analyzed with respect to the problem domain, and the advantages of heuristics will be considered for each algorithm. The paper culminates with an in-detail description of the algorithms in question, and how they might be implemented.
Static and dynamic type systems
(2004) Rushton, Matthew V.; Wonnacott, David G.
This paper demonstrates the advantages and disadvantages of static and dynamic type systems. This is done through careful exposition of various implementations. As a motivating example, a subset of the ML language is used to investigate the Hindley-Milner type inference algorithm to which an original extension is made
Bi-level Lossless Compression Techniques
(2004) Bejile, Brian; Lindell, Steven
Image compression algorithms have evolved into some of the most complex structures in computing. Yet at the core of these algorithms are simple techniques that have been long known about data compression. This paper explores some of the fundamental techniques behind bi-level (black and white) image compression that have set the bar for much of the compression standards in existence today. More specifically, the paper focuses on compression techniques developed for the fax machine, for that development marked a turning point in the standardization of image compression techniques.
Thesis Shmesis: Representing Reduplication with Directed Graphs
(2004) Coleman, Jason; Raimy, Eric; Kumar, Deepak
This thesis studies the linguistic phenomena of reduplication. I will address two problems involving reduplication: the generation of reduplicative word forms and the recognition of reduplicative patterns. I will show how to represent reduplication using an augmented directed graph. The standard digraph is augmented with additional properties. I will then restate the problems of generation and recognition in terms of the reduplication graphs. While at first glance reduplication appears to be something that could only be of interest to linguists, after some formalization, the problem becomes one which is of interest to computer scientists as well.
Evaluating Inherited Attributes Using Haskell and Lazy Evaluation
(2005) Moss, William B.; Wonnacott, David G.
Parser generators designed for imperative programming languages (C++, Java, etc), such as YACC and CUPS, inevitably run into difficulty handling inherited attributes. In the past, this difficulty has been handled in one of two ways: 1) the problem is ignored, and inherited attributes must be manually calculated later using extra passes over the parse tree; and 2) for the L-attributed class of grammars, the parser generator provides some sort of ”hack,” allowing the user to access previous elements of the stack with no safeguards preventing a user from accessing incorrect data. Many functional programming languages, however, provide an easy solution to this problem. Using lazy evaluation, a parser generator written for a function programming language can sidestep the entire problem, relying on the language system to evaluate attributes (regardless of whether they are inherited or synthesized) as it needs them. This paper discusses a method for evaluating inherited and synthesized attributes in Haskell, specifically using Happy, a parser generator for Haskell. This paper will present specific examples of parsing inherited attributes in both functional and imperative languages, followed by the presentation of an algorithm for computing any inherited attribute in Happy.
Empirical Study of Graph Properties with Particular Interest Towards Random Graphs
(2005) Weinstein, Lee; Lindell, Steven
This paper is an empirical study mainly of graph properties for various graphs including both deterministic graphs, those with a set structure, and random graphs. The main properties that are analyzed are graph diameter, radius, the eccentricity distribution, and the degree of the graph. The goal is to see if random graphs models are ideal for networks which seek to minimize network traffic and still keep the distance between nodes small.
Concurrency in Multi-Core Processor Design
(2007) Clancy, Patrick; Wonnacott, David G.
It is possible to extend a microprocessor from a single core to a multiple cores by replicating the single core processor, and interfacing them to main memory bus via a bus arbitrator. With a multi-core processor, the possibilities for parallel programs are apparent, but the programmer must overcome those obstacles with lock based programming. Transactional Memory would provide a means for programmers to handle highly concurrent programming in a more forgiving environment. This thesis surveys these topics and discusses possible implementations in terms of the HERA architecture.
Natural Language Interaction with Robots
(2007) Walker, Alden; Dougherty, John P.; Kumar, Deepak
Natural language communication with robots has obvious uses in almost all areas of life. Computer-based natural language interaction is an active area of research in Computational Linguistics and AI. While there have been several NL systems built for specific computer applications, NL interaction with robots remains largely unexplored. Our research focuses on implementing a natural language interpreter for commands and queries given to a small mobile robot. Our goal is to implement a complete system for natural language understanding in this domain, and as such consists of two main parts: a system for parsing the subset of English our robot is to understand and a semantic analyzer used to extract meaning from the natural language. By using such a system we will be able to demonstrate that a mobile robot is capable of understanding NL commands and queries and responding to them appropriately.
An Explication of "A New Algorithm for Transitive Closures and Computation of Recursion in Relational Databases" by Yangjun Chen
(2008) Miller, Anne
In this paper, we discuss the algorithm for computing the transitive closure of a directed, acyclic graph of bounded degree given in Yangjun Chen’s paper, "A New Algorithm for Transitive Closures and Computation of Recursion in Relational Databases" [2]. We point out several errors, one in the correctness of the algorithm and one in the complexity, and modify the algorithm slightly to repair the former. (The error in complexity does not seem to be as easily fixable.) We then prove the correctness of the altered algorithm.
Digital Watermarking: An Overview of Watermarking in the Context of Digital Rights Management
(2008) Moser, Alexander S.
In this work we present a basic overview of digital rights management technologies, focusing heavily on a technical understanding of digital watermarking and its applications in copyright protection. We discuss the basic attributes and functions of digital watermarks before proceeding to a discussion of watermark implementations in images and audio. Our discussion of implementations leads us to a brief overview of attacks that might be used to remove a watermark or render it unreadable, and from here we attempt to place the watermark in a legal context.
From Tapestry to SVD: A Survey of the Algorithms That Power Recommender Systems
(2009) Huttner, Joseph; Lindell, Steven
This paper is a survey of the algorithms that power recommender systems. To start, the social and monetary relevance of recommender systems is outlined. Then we delve into the specifics of how the first recommender system, Tapestry, coined the idea of numerically defining customer similarity. Moving forward, we show how this central concept of similarity is re-hashed in present day recommender systems, namely that of Amazon.com. Specifically, we examine the complexity of a user-based approach in a large scale system such as Amazon's, identify its weaknesses, and see how these weaknesses are overcome using an item-based approach. The last component of this paper focuses on the Netflix Prize™ and investigates the single most important algorithm in the contest so far: an incremental approach to finding the singular value decomposition (SVD) of a mostly-blank matrix.
Anonymity on the Web: Understanding the Vulnerabilities of Internet Use
(2009) Hilton, Stephanie; Dougherty, John P.
Exploring Augmented Reality
(2009) Scheinerman, Matt; Dougherty, John P.
This paper illustrates a general overview of augmented reality, a type of technology that incorporates virtual reality and video images into one image. A subset of computer graphics, augmented reality is becoming more useful outside of research, inspiring new methods of human-computer interaction and interface design. This paper describes the history of augmented reality, including its origins in virtual reality, the various technologies required with its use, and its current and future applications.
Garbage Collection: An Overview of Dynamic Data Management
(2010) Picone, Nicholas; Dougherty, John P.
Automata-Theoretic Model Checking
(2011) Dworkin, Lili Anne; Lindell, Steven
When designing hardware or software, it is important to ensure that systems behave correctly. This is particularly crucial for life- or safety-critical systems, in which errors can be fatal. One approach to the formal verification of such designs is to convert both the system and a specification of its correct behavior into mathematical objects. Typically, the system is modeled as a transition system, and the specification as a logical formula. Then we rigorously prove that the system satisfies its specification. This paper explores one of the most successful applications of formal verification, known as model checking, which is a strategy for the verification of finite-state reactive systems. In particular, we focus on the automata-theoretic approach to model checking, in which both the system model and logical specification are converted to automata over infinite words. Then we can solve the model checking problem using established automata-theoretic techniques from mathematical logic. Since this approach depends heavily on the connections between formal languages, logic, and automata, our explanation is guided by a discussion of the relevant theory.

Browse

Browsing Computer Science by Issue Date

Results Per Page

Sort Options