Algorithms in the Information Age
[ Send this article to a friend ]
go to page: [ 1 | 2 ]
The computer is the workhorse of the Information Age, executing tasks of astonishing variety and difficulty. But without cleverly designed commands, even supercomputers balk at the problems set before them—a challenge of growing complexity, ironically, due in part to the increasingly powerful technology that drives these machines. Enter a new suite of intelligent algorithms to guide the computers of tomorrow to their targets.
In a lively series of ads for the popular search engine Ask.com, "lame algorithms" are dismissed as the very essence of uncool (never mind a longer path from points A to B). The savvy marketing team behind the campaign hopes to infuse a term once consigned to the unfashionable world of geek speak with newfound hipness. The time may be right. As it happens, all sequential processes, from sorting laundry to finding a route up Mt. Everest, are actually algorithms in disguise. Algorithmic recipes lead migrating herds to their watering holes and direct the formation of snowflakes and hurricanes.
It is in the realm of computer science, however, where the algorithm reigns supreme. All machine programming is based on these lists of instructions, which begin at an initial input state and proceed to some point of termination, a path that revved-up technology is making more challenging to navigate.
For researchers in the IIT Department of Computer Science (CS), smarter algorithms are a fundamental tool of the trade, designed, analyzed, and applied to diverse specialties, including information retrieval, wireless networking, market forecasting, computer simulation, and cryptography.
Beginnings
The CS department came into being by fits and starts. IIT Professor Peter Lykos, recruited to the IIT Department of Chemistry in 1955, had a keen interest in early computing, honing his skills on Argonne National Laboratory's IBM 650 computer. In 1959, Lykos introduced his chemistry majors to computing, instructing students to program a least-squares calculation of vapor pressure in a language known as Octal. Still, a fully fledged department devoted to computer science would have to wait.
In the 1960s, Charles Bauer, then assistant principal of Lane Technical High School, began teaching programming courses to Chicago students, using IIT's facilities. The enthusiasm for computer science was infectious, with area teachers eventually enrolling in Bauer's courses as well.
In 1971, with interest in computers mounting, the IIT CS department was founded. It quickly became the fifth largest department of the 25-department university, offering a range of CS classes, some of which persist today.
Stone Age to Digital Age
Algorithms in one form or another have been around since humanity's earliest activities. The hunting algorithms used in modern search engines are, in some respects, remnants of the algorithmic strategies for finding game in prehistory. Computer scientists refer to "greedy algorithms," "sorting algorithms," "genetic algorithms," and even "ant algorithms" (which mimic the statistical behavior of foraging insects).
The term algorithm dates to the Persian astronomer, mathematician, and geographer Muhammad ibn Mūsā al-Khwārizmī, whose ninth century treatise was translated into Latin three centuries later as Algoritmi de numero Indorum. Long before al-Khwārizmī, simple algorithms had found their way into an array of early computing devices, including the abacus (invented in Babylonia in the fourth century B.C.) and in the first century B.C. the Antikythera mechanism (a prediction tool for stellar and planetary motion).
By 1642, the philosopher-mathematician Blaise Pascal introduced a mechanical calculator. In the early 1820s, British mathematician Charles Babbage developed a large, steam-powered Difference Engine for calculating astronomical tables. Eventually, electricity, transistors, and microchip technology, along with a host of other innovations, revolutionized computers.
Today, these fleet-footed machines leaf through billions of Internet documents per second, model conditions of ocean and atmosphere a century into the future, and even act as digital matchmakers, drawing our soul mates from ever deepening tide pools of personal data. Algorithms form the dynamic core of these applications.
Building a Better Algorithm
 |
| IIT computer science professors [left to right] Xiang-Yang Li, Ed Reingold, Xian-He Sun, and Sanjiv Kapoor |
While algorithmic maneuvers in our daily lives can seem effortless, cajoling a machine into executing similar calculations can be daunting. As IIT Professor Ed Reingold, a theoretician of algorithms, explains, "The computer sees a problem one little piece of data at a time and that complicates things enormously.
Imagine, for example, trying to find your way from New York's Upper West Side to the Lower East Side. A few glances at a good city map would probably be enough to guide you to your destination. But the computer essentially has to examine the city's maze of intersections one at a time, forgetting about those it has looked at already. As Reingold explains, "If you boil the problem down to its essentials, you have an algorithm that manipulates a graph—an idealized structure that has points and connections between the points." Today, sophisticated graph algorithms are at the heart of programs like Mapquest and Google Maps.
IIT Professor Sanjiv Kapoor explains that algorithms need to do more than just provide accurate solutions. Simply put, a good algorithm has to accomplish its task quickly—it has to be efficient. This is the point where the art of algorithm design emerges.
Certain tasks like sorting playing cards by value and suit or arranging a group of seashells by color and shape can be handled rapidly by a variety of intelligent sorting algorithms. Adding more elements to be sifted and sorted increases the time required for the algorithm to finish the job, but the time increases almost linearly (actually, n log n). In mathematical jargon, such problems are solved in polynomial time.
Other problems are far thornier, requiring exponential time to solve. That can cost dearly, because increasing the elements to be examined can quickly swamp computing resources. Such challenges are known to computer scientists as NP-hard problems.
A classic case of NP-hard is the "traveling salesman problem," or TSP. Here, a salesman is sent to visit a number of different cities on his rounds, returning to his starting place after stopping once at each destination. He wants to do this at the lowest cost (i.e., in the most efficient manner). The problem is easy to pose but much tougher to solve than one might think.
As the number of cities to be visited by the salesman increases, the time required for a simple algorithm to crack the problem goes up exponentially. Thus, an algorithm that can deliver a solution for a 10-city trip in less than a second requires about 20,000 years of high-speed computing time when the problem expands to 20 cities!
NP-hard problems are often subdued using approximation algorithms—those that give a good, but not necessarily optimum, solution. The traveling salesman problem is critical for computer scientists because it recurs in endless variations and disguises, often requiring shrewd algorithmic solutions.
Kapoor studies one such NP-hard problem: finding the equilibrium point in stock and commodity markets. As he explains, "The question was raised by the French economist Leon Walras in 1874. How do these markets actually get to an equilibrium point? Or do they ever reach this point?" Today, Kapoor and others are pursuing the question through methods including algorithmic game theory, a field at the intersection of economics and traditional computer science. Kapoor and his colleagues believe they have found a type of algorithm, known as an auction process, that can find the equilibrium price for a given set of traded commodities, given certain preconditions. This process occurs naturally in the real world. "We showed that this mechanism can be made to work in polynomial time," Kapoor notes.
go to page: [ 1 | 2 ]
