Staying disciplined during an interdisciplinary degree
By Daniel W. Goldberg, December 2009
Articles Tagged: Algorithms
Articles & Features
Grafitter
"Know thyself". Carved in stone in front of the Temple of Apollo at Delphi, that was the first thing people saw when they visited the Oracle to find answers. The benefits of knowing oneself are many. It fosters insight, increases self-control, and promotes positive behaviors such as exercise and energy conservation.
By Ian Li, Anind Dey, Jodi Forlizzi, December 2009
Are your friends who they say they are?
How sure are you that your friends are who they say they are? In real life, unless you are the target of some form of espionage, you can usually be fairly certain that you know whom your friends are because you have a history of shared interests and experiences. Likewise, most people can tell, just by using common sense, if someone is trying to sell them on a product, idea, or candidate. When we interact with people face-to-face, we reevaluate continuously whether something just seems off based on body language and other social and cultural cues.
By Roya Feizy, Ian Wakeman, Dan Chalmers, December 2009
Introduction
By Justin Solomon, June 2009
Courier problems
Courier problems comprise a set of recently proposed combinatorial optimization problems, which are inspired by some novel requirements in railway wagon scheduling. In these problems, scheduling strategies of some mobile couriers are considered. These mobile couriers initially reside at some fixed location. They are assigned some duties of commodity transfer between different pairs of locations. The scenario may be static or dynamic. The motivation is to optimize the movement of the couriers over the constraint of the traversed path or the associated cost. We discuss here some varieties of the courier problems formalized on graphs and address the potential methods of their solution.
By Malay Bhattacharyya, June 2009
An overview of privacy preserving data mining
By Aris Gkoulalas-Divanis, Vassilios S. Verykios, June 2009
Detecting steganography on a large scale
By William Ella, December 2008
Motion planning for skateboard-like robots in dynamic environments
By Salik Syed, September 2008
The use of compiler optimizations for embedded systems software
Optimizing embedded applications using a compiler can generally be broken down into two major categories: hand-optimizing code to take advantage of a particular processor's compiler and applying built-in optimization options to proven and well-polished code. The former is well documented for different processors, but little has been done to find generalized methods for optimal sets of compiler options based on common goal criteria such as application code size, execution speed, power consumption, and build time. This article discusses the fundamental differences between these two general categories of optimizations using the compiler. Examples of common, built-in compiler options are presented using a simulated ARM processor and C compiler, along with a simple methodology that can be applied to any embedded compiler for finding an optimal set of compiler options.
By Joe Bungo, September 2008
Geometric and path tracing methods for simulating light transport through volumes of water particles
The visual appearance of volumes of water particles, such as clouds, waterfalls, and fog, depends both on microscopic interactions between light rays and individual droplets of water, and also on macroscopic interactions between multiple droplets and paths of light rays. This paper presents a model that builds upon a typical single-scattering volume renderer to correctly account for these effects. To accurately simulate the visual appearance of a surface or a volume of particles in a computer-generated image, the properties of the material or particle must be specified using a Bidirectional Reflectance Distribution Function (BRDF), which describes how light reflects off of a material, and the Bidirectional Transmittance Distribution Function (BTDF), which describes how light refracts into a material. This paper describes an optimized BRDF and BTDF for volumes of water droplets, which takes their geometry into account in order to produce well-known effects, such as rainbows and halos. It also describes how a multiple-scattering path tracing volume integrator can be used to more accurately simulate macroscopic light transport through a volume of water, creating a more "cloudlike" appearance than a single-scattered volume integrator. This paper focuses on replicating the visual appearance of volumes of water particles, and although it makes use of physical models, the techniques presented are not intended to be physically accurate.
By James Hegarty, September 2008
Data encryption
By Ed DeHart, September 2008
Finding an optimal tooth color match
By Cara Cocking, March 2008
Visualizing flow data using assorted glyphs
This project visualizes a scientific dataset containing two-dimensional flow data from a simulated supernova collapse provided by astrophysics researchers. We started our project by designing visualizations using multiple hand drawings representing the flow data without taking into consideration the implementation constraints of our designs. We implemented a few of our hand drawn designs. We used an assortment of simple geometric graphical objects, called glyphs, such as, dots, lines, arrows, and triangles to represent the flow at each sample point. We also incorporated transparency in our visualizations. We identified two important goals for our project: (1) design different types of graphical glyphs to support flexibility in their placement and in their ability to represent multidimensional data elements, and (2) build an effective visualization technique that uses glyphs to represent the two-dimensional flow field.
By Amit Prakash Sawant, Christopher G. Healey, December 2007
Trends in real-time rendering
Fans of PC role-playing games need no introduction to Bioware-the Edmonton, Alberta based developer of Baldur's Gate, Neverwinter Nights, and Jade Empire, among others. The company recently opened a studio in Austin, Texas to develop a massively multiplayer online role-playing game (MMORPG, or simply MMO) for an unannounced intellectual property. Ben Earhart, client technology lead on the new project, took a few hours out of his busy schedule to discuss with Crossroads the future of real-time rendering-3-D graphics that render fast enough to respond to user input, such as those required for video games.
By James Stewart, December 2007
On the complexity of Katamari Damacy
By Gregory M. Zaverucha, December 2007
An approach for detecting prosodic phrase boundaries in spoken english
Prosodic phrasing is the means by which speakers of any given language break up an utterance into meaningful chunks. The term "prosody" itself refers to the tune or intonation of an utterance, and therefore prosodic phrases literally signal the end of one tune and the beginning of another. This study uses phrase break annotations in the Aix-MARSEC corpus of spoken English as a "gold standard" for measuring the degree of correspondence between prosodic phrases and the discrete syntactic grouping of prepositional phrases, where the latter is defined via a chunk parsing rule using nltk_lite's regular expression chunk parser.
A three-way comparison is also introduced between the "gold standard" chunk parsing rule and human judgment in the form of intuitive predictions about phrasing. Results show that even with a discrete syntactic grouping and a small sample of text, problems may arise for this rule-based method due to uncategorical behavior in parts of speech. Lack of correspondence between intuitive prosodic phrases and corpus annotations highlights the optional nature of certain boundary types. Finally, there are clear indications, supported by corpus annotations, that significant prosodic phrase boundaries occur within sentences and not just at full stops.
By Claire Brierley, Eric Atwell, December 2007
Hearing the Hype
By Daniel Alex Finkelstein, December 2007
Use of motion field warping to generate cardiac images
In this study, we developed an algorithmic method to analyze late contrast-enhanced (CE) magnetic resonance (MR) images, revealing the so-called hibernating myocardium. The algorithm is based on an efficient and robust image registration algorithm. Using our method, we are able to integrate the static late CE MR image with its corresponding cardiac cine MR images, constructing cardiac motion CE MR images, which are referred to as cardiac cine CE MR images. This method appears promising as an improved cardiac viability assessment tool
By Gang Gao, Paul Cockshott, September 2007
Voice activity detection
By Deepti Singh, Frank Boland, September 2007
Computational recreations
By Jonathan Doyle, September 2007
Interesting complexity
By Caio Camargo, December 2006
Aligning DNA sequences using dynamic programming
By Eric C. Rouchka, September 2006
Introduction to programming shared-memory and distributed-memory parallel computers
By Cory Quammen, October 2005
An introduction to quantum cryptography
By Nick Papanikolaou, May 2005
An introduction to side channel cryptanalysis of RSA
By Artemios G. Voyiatzis, May 2005
Timing attacks on RSA
By Wing H. Wong, May 2005
Obfuscation of the standard XOR Encryption algorithm
By Zachary A. Kissel, May 2005
Introduction
By William Stevenson, September 2004
Computer security and intrusion detection
Computer attacks are now commonplace. By connecting your computer to the Internet, you increase the risk of having someone break in, install malicious programs and tools on it, and possibly use it to attack other machines on the Internet by controlling it remotely.Several major banks have been subject to attacks, in which attackers gained access into customers' accounts and viewed detailed information about the activities on these accounts. In some instances the attackers stole credit card information to blackmail e-commerce companies by threatening to sell this information to unauthorized entities. Several online trading companies and e-commerce sites were shut down temporarily due to major packet flood attacks, also known as Denial-of-Service (DoS) attacks, causing these companies to lose revenue, customer satisfaction, and trust [10]. A major software development company discovered that attackers had broken into its network and stolen the source code for future releases of its popular products. Just recently, the source code of the future flagship product belonging to a major software development company was stolen and made publicly available on the Internet.In order to combat this growing trend of computer attacks, both academic and industry groups have been developing systems to monitor networks and systems and raise alarms of suspicious activities. These systems are called Intrusion Detection Systems (IDS).
By Khaled Labib, September 2004
WiFi exposed
Over the past few years, IEEE 802.11 wireless networks have become increasingly widely deployed. Wireless LANs can be found in coffee shops, airports, hospitals, and all major institutes. However, as for conventional wired networks, the spread of such networks may have been faster than the diffusion of security knowledge about them. As a consequence, 802.11 is the new playground for many hackers, who are attracted to the environment by virtue of its anonymity. Attacks may be traced back to the wireless network, but the intruder could have been anyone driving by within the radius of the network, making it hard, if not impossible, for him/her to be traced. Securing wireless networks is a hard task, because the standard solutions do not work effectively in guaranteeing privacy and authentication, as this article shows; as a consequence, many wireless networks are left open.This article is structured as follows: initially, an overview of the 802.11 protocol is presented. This is followed by an analysis of the steps involved in connection to and use of such a network, first in the absence of encryption and then taking into account WEP. Attacks for these different scenarios are presented and analyzed, leading to the conclusion that WEP is unsuitable as the sole security measure for such links. Finally, attacks on wired networks that are connected to a wireless LAN are analyzed.The article concludes that existing standards for wireless security as applied to the most widely used wireless standard, 802.11, are inadequate in several ways, can be attacked using publicly available tools, and lead to a false sense of security. Some advice about mitigation of threats is offered throughout the article, but the most effective solution is awareness of potential attacks and the maximization of the amount of time and effort needed to break into the network by using defence in depth.
By Andrea Bittau, September 2004
DNA smart card for financial transactions
In this paper, a secure environment for electronic commerce is introduced. The environment is formed via a synthesis of biometrics consumer authentication with a security token. Such a token is a smart card containing cryptographic keys and a cryptographic microprocessor for data encryption. The keys are used to further authenticate the possessor of the card as the actual owner and also to facilitate secure electronic financial transactions. New technologies like these bring benefits to society by enhancing the standard of living, however, numerous challenges are introduced [1].Biometrics is a Greek composite word stemming from the synthesis of bio and metric, meaning life measurement. In this context, the science of biometrics is concerned with the accurate measurement of unique biological characteristics of an individual in order to securely identify them to a computer or other electronic system. Biological characteristics measured usually include fingerprints, voice patterns, retinal and iris scans, face patterns, and even the chemical composition of an individual's DNA [9].
By Sofia Gleni, Panagiotis Petratos, September 2004
A distributed security scheme for ad hoc networks
In an ad hoc wireless network where wired infrastructures are not feasible, energy and bandwidth conservation are the two key elements presenting challenges to researchers. Limited bandwidth makes a network easily congested by the control signals of the routing protocol. Routing schemes developed for wired networks seldom consider restrictions of this type. Instead, they assume that the network is mostly stable and that the overhead for routing messages is negligible. Considering these differences between wired and wireless network, it is necessary to develop a wireless routing protocol that limits congestion in the network [1, 5, 8, 9, 10, 11].This paper proposes minor modifications to the existing Ad hoc On Demand Vector (AODV) routing protocol (RFC 3561) in order to restrict congestion in networks during a particular type of Denial of Service (DoS) attack. In addition to this, it incurs absolutely no additional overhead [4]. We describe the DoS attack caused due to Route Request (RREQ) flooding and its implications on existing AODV-driven Mobile Ad hoc Networks (MANET) [2, 14]. To combat this DoS attack, a proactive scheme [12] is proposed. We present an illustration to describe the implications of RREQ flooding on pure AODV and the modified AODV protocols. To quantify the effectiveness of the proposed scheme, we simulated a DoS [6] attack in a mobile environment and study the performance results.
By Dhaval Gada, Rajat Gogri, Punit Rathod, Zalak Dedhia, Nirali Mody, Sugata Sanyal, Ajith Abraham, September 2004
Associative memory and the board game Quarto
By Zachary A. Kissel, December 2003
A parallel algorithm for DNA alignment
By Thomas Royce, Rance Necaise, March 2003
Optimizing application performance
By M. Tyler Maxwell, Kirk W. Cameron, August 2002
Managing XML data storage
By Jerry Emerick, June 2002
Introduction to programming shared-memory and distributed-memory parallel computers
By Cory Quammen, April 2002
Software verification and validation with destiny
This paper presents an introduction to computer-aided theorem proving and a new approach using parallel processing to increase power and speed of this computation. Automated theorem provers, along with human interpretation, have been shown to be powerful tools in verifying and validating computer software. Destiny is a new tool that provides even greater and more powerful analysis enabling greater ties between software programs and their specifications.
By Josiah Dykstra, April 2002
An introduction to Java servlet programming
By Vandana Pursnani, December 2001
Evolutionary learning in mobile robot navigation
By Cory Quammen, December 2001
Connector
By Kostas Pentikousis, July 2001
Why bison is becoming extinct
At some point in your career, you're going to implement a computer language. You probably won't be implementing Java or C++. You may not even recognize it as a language. Truth be told, there are an awful lot of domain-specific languages, or "little languages" [7] in common use:
- configuration files,
- HTML/XML documents,
- shell scripts,
- network protocols,
- mail headers,
- command-line arguments.
By John Aycock, July 2001
Public key cryptography
By Pradosh Kumar Mohapatra, September 2000
Book review: information storage and retrieval systems
By Robert Korfhage, July 2000
Charlotte
By Stuart Patterson, June 2000
Image compression—from DCT to wavelets
By Subhasis Saha, March 2000
A hierarchical error controlled octree data structure for large-scale visualization
By Dmitriy V. Pinskiy, Joerg Meyer, Bernd Hamann, Kenneth I. Joy, Eric Brugger, Mark Duchaineau, March 2000
Web hunting
By G. Michael Youngblood, June 1999
Book review: introduction to computational biology
By Randolph Chung, September 1998
CMUnited
Robotic soccer is a challenging research domain involving multiple agents that need to collaborate in an adversarial environment to achieve specific objectives. This article describes CMUnited, the team of small robotic agents that we developed to enter the RoboCup-97 competition. We designed and built the robotic agents, devised the appropriate vision algorithm, and developed and implemented algorithms for strategic collaboration between the robots in an uncertain and dynamic environment. The robots can organize themselves in formations, hold specific roles, and pursue their goals. In game situations, they have demonstrated their collaborative behaviors on multiple occasions. The robots can also switch roles to maximize the overall performance of the team. We present an overview of the vision processing algorithm which successfully tracks multiple moving objects and predicts trajectories. The paper then focuses on the agents' behaviors ranging from low-level individual behaviors to coordinated, strategic team behaviors. CMUnited won the RoboCup-97 small-robot competition at IJCAI-97 in Nagoya, Japan.
By Manuela Veloso, Peter Stone, Kwun Han, Sorin Achim, April 1998