XRDS

Crossroads The ACM Magazine for Students

Sign In

Association for Computing Machinery

Articles Tagged: Algorithms

Articles & Features

Staying disciplined during an interdisciplinary degree

Grafitter

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

PDF | HTML | In the Digital Library

Are your friends who they say they are?

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

PDF | HTML | In the Digital Library

Introduction

By Justin Solomon, June 2009

PDF | HTML | In the Digital Library

Courier problems

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

PDF | HTML | In the Digital Library

An overview of privacy preserving data mining

By Aris Gkoulalas-Divanis, Vassilios S. Verykios, June 2009

PDF | HTML | In the Digital Library

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

PDF | HTML | In the Digital Library

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

PDF | HTML | In the Digital Library

Data encryption

By Ed DeHart, September 2008

PDF | HTML | In the Digital Library

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

PDF | HTML | In the Digital Library

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

PDF | HTML | In the Digital Library

On the complexity of Katamari Damacy

By Gregory M. Zaverucha, December 2007

PDF | HTML | In the Digital Library

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

PDF | HTML | In the Digital Library

Hearing the Hype

By Daniel Alex Finkelstein, December 2007

PDF | HTML | In the Digital Library

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

PDF | HTML | In the Digital Library

Voice activity detection

By Deepti Singh, Frank Boland, September 2007

PDF | HTML | In the Digital Library

Computational recreations

By Jonathan Doyle, September 2007

PDF | HTML | In the Digital Library

Interesting complexity

By Caio Camargo, December 2006

PDF | HTML | In the Digital Library

Timing attacks on RSA

By Wing H. Wong, May 2005

PDF | HTML | In the Digital Library

Introduction

By William Stevenson, September 2004

PDF | HTML | In the Digital Library

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

PDF | HTML | In the Digital Library

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

PDF | HTML | In the Digital Library

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

PDF | HTML | In the Digital Library

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

PDF | HTML | In the Digital Library

A parallel algorithm for DNA alignment

By Thomas Royce, Rance Necaise, March 2003

PDF | HTML | In the Digital Library

Optimizing application performance

By M. Tyler Maxwell, Kirk W. Cameron, August 2002

PDF | HTML | In the Digital Library

Managing XML data storage

By Jerry Emerick, June 2002

PDF | HTML | In the Digital Library

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

PDF | HTML | In the Digital Library

Connector

By Kostas Pentikousis, July 2001

PDF | HTML | In the Digital Library

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.
The list goes on. A number of programs allow you to write scripts to control their operation; infact, just the other day I downloaded a neural network simulator which provided a little programming language to steer the simulation.How will you implement your language? There's the ad hoc approach, of course, but it's not well suited to languages whose design is complex or frequently changing. You also end up writing code to perform tasks which can be effectively automated.You might also consider using existing languages like Tcl [18] and Python [6]. These languages are designed to either be embedded in an existing application, or easily extended. This is a good solution when it can be used, saving a lot of time and effort. However, there may be concerns about tying your language to one which is itself changing, or the syntax and semantics of your language may not match those of such a "host" language.A third approach is to use compiler tools to implement your language. Most were designed for the implementation of large programming languages, but the same principles and techniques apply equally well to little languages. This article is the story of one such tool -- a parser generator tool -- and more importantly, what sort of tool is going to replace it, and why.

By John Aycock, July 2001

PDF | HTML | In the Digital Library

Public key cryptography

By Pradosh Kumar Mohapatra, September 2000

PDF | HTML | In the Digital Library

Charlotte

By Stuart Patterson, June 2000

PDF | HTML | In the Digital Library

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

PDF | HTML | In the Digital Library

Web hunting

By G. Michael Youngblood, June 1999

PDF | HTML | In the Digital Library

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

PDF | HTML | In the Digital Library

Levels of detail & polygonal simplification

This paper covers the techniques of Polygonal Simplification in order to produce Levels of Detail (LODs). The problem of creating LODs is a complex one: how can simpler versions of a model be created? How can the approximation error be measured? How can the visual degradation be estimated? Can all this be done automatically? After exposing the basic aims and principles of polygonal simplification, we compare recent algorithms and state their various qualities and weaknesses.

By Mike Krus, Patrick Bourdot, Françoise Guisnel, Gullaume Thibault, May 1997

PDF | HTML | In the Digital Library

Reasoning about computational resource allocation

Anytime Algorithms are algorithms that exchange execution time for quality of results. Since many computational tasks are too complicated to be completed at real-time speeds, anytime algorithms allow systems to intelligently allocate computational time resources in the most effective way, depending on the current environment and the system's goals. This article briefly covers the motivations for creating anytime algorithms, the history of their development, a definition of anytime algorithms, and current research involving anytime algorithms.

By Joshua Grass, September 1996

PDF | HTML | In the Digital Library