Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Computational experiments on algorithms can supplement theoretical analysis by showing what algorithms, implementations and speed-up methods work best for specific machines or problems. This book guides the reader through the nuts and bolts of the major experimental questions: What should I measure? What inputs should I test? How do I analyze the data? To answer these questions the book draws on ideas from algorithm design and analysis, computer systems, and statistics and data analysis. The wide-ranging discussion includes a tutorial on system clocks and CPU timers, a survey of strategies for tuning algorithms and data structures, a cookbook of methods for generating random combinatorial inputs, and a demonstration of variance reduction techniques. The book can be used by anyone who has taken a course or two in data structures and algorithms. A companion website, AlgLab (www.cs.amherst.edu/alglab) contains downloadable files, programs and tools for use in experimental projects.

Computer algorithms. --- Algorithmes. --- Mathematics. --- Math --- Science --- Algorithms

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Complex analysis --- Discrete mathematics --- Computer science --- Artificial intelligence. Robotics. Simulation. Graphics --- Computer. Automation --- discrete wiskunde --- complexe analyse (wiskunde) --- grafische vormgeving --- informatica --- database management --- programmatielogica --- algoritmen --- KI (kunstmatige intelligentie) --- numerieke analyse

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

The Workshop on Experimental Algorithms, WEA, is intended to be an int- national forum for research on the experimental evaluation and engineering of algorithms, as well as in various aspects of computational optimization and its applications. The emphasis of the workshop is the use of experimental me- ods to guide the design, analysis, implementation, and evaluation of algorithms, heuristics, and optimization programs. WEA 2008 was held at the Provincetown Inn, Provincetown, MA, USA, on May 30 – June 1, 2008. This was the seventh workshop of the series, after Rome (2007),Menorca(2006),Santorini(2005),RiodeJaniero(2004),Asconia(2003), and Riga (2001). This volume contains all contributed papers accepted for presentation at the workshop. The 26 contributed papers were selected by the Program Committee onthebasisofatleastthreerefereereports,somecontributedbytrustedexternal referees. In addition to the 26 contributed papers, the program contained two invited talks. Camil Demetrescu, of the University of Rome “La Sapienza,” spoke on “Visualization in Algorithm Engineering.” David S. Johnson of AT & T Labs – Research, gave a talk on “Bin Packing: From Theory to Experiment and Back Again.” We would like to thank the authors who responded to the call for papers, our invited speakers, the members of the ProgramCommittee, the external referees, and the Organizing Committee members for making this workshop possible.

Computer algorithms --- Algorithmes --- Congresses. --- Congrès --- Computer Science --- Engineering & Applied Sciences --- Computer science. --- Software engineering. --- Computer programming. --- Data structures (Computer science). --- Algorithms. --- Computer science --- Numerical analysis. --- Computer Science. --- Software Engineering/Programming and Operating Systems. --- Programming Techniques. --- Numerical Analysis. --- Algorithm Analysis and Problem Complexity. --- Data Structures. --- Discrete Mathematics in Computer Science. --- Mathematics. --- Mathematical analysis --- Computer mathematics --- Discrete mathematics --- Electronic data processing --- Algorism --- Algebra --- Arithmetic --- Information structures (Computer science) --- Structures, Data (Computer science) --- Structures, Information (Computer science) --- File organization (Computer science) --- Abstract data types (Computer science) --- Computers --- Electronic computer programming --- Electronic digital computers --- Programming (Electronic computers) --- Coding theory --- Computer software engineering --- Engineering --- Informatics --- Science --- Mathematics --- Foundations --- Programming --- Computer software. --- Data structures (Computer scienc. --- Computational complexity. --- Complexity, Computational --- Machine theory --- Software, Computer --- Computer systems --- Computer science—Mathematics. --- Artificial intelligence—Data processing. --- Discrete mathematics. --- Software Engineering. --- Data Science. --- Discrete mathematical structures --- Mathematical structures, Discrete --- Structures, Discrete mathematical --- Numerical analysis

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Symmetric multiprocessors (SMPs) dominate the high-end server market and are currently the primary candidate for constructing large scale multiprocessor systems. Yet, the design of e cient parallel algorithms for this platform c- rently poses several challenges. The reason for this is that the rapid progress in microprocessor speed has left main memory access as the primary limitation to SMP performance. Since memory is the bottleneck, simply increasing the n- ber of processors will not necessarily yield better performance. Indeed, memory bus limitations typically limit the size of SMPs to 16 processors. This has at least twoimplicationsfor the algorithmdesigner. First, since there are relatively few processors availableon an SMP, any parallel algorithm must be competitive with its sequential counterpart with as little as one processor in order to be r- evant. Second, for the parallel algorithm to scale with the number of processors, it must be designed with careful attention to minimizing the number and type of main memory accesses. In this paper, we present a computational model for designing e cient al- rithms for symmetric multiprocessors. We then use this model to create e cient solutions to two widely di erent types of problems - linked list pre x com- tations and generalized sorting. Both problems are memory intensive, but in die rent ways. Whereas generalized sorting algorithms typically require a large numberofmemoryaccesses, they areusuallytocontiguousmemorylocations. By contrast, prex computation algorithms typically require a more modest qu- tity of memory accesses, but they are are usually to non-contiguous memory locations.

Computer algorithms --- Computer Science --- Engineering & Applied Sciences --- Computer science. --- Computer programming. --- Data structures (Computer science). --- Algorithms. --- Computer graphics. --- Application software. --- Computer Science. --- Programming Techniques. --- Data Structures, Cryptology and Information Theory. --- Computer Applications. --- Algorithm Analysis and Problem Complexity. --- Data Structures. --- Computer Graphics. --- Data structures (Computer scienc. --- Computer software. --- Data Structures and Information Theory. --- Automatic drafting --- Graphic data processing --- Graphics, Computer --- Computer art --- Graphic arts --- Electronic data processing --- Engineering graphics --- Image processing --- Software, Computer --- Computer systems --- Informatics --- Science --- Digital techniques --- Algorism --- Algebra --- Arithmetic --- Application computer programs --- Application computer software --- Applications software --- Apps (Computer software) --- Computer software --- Information structures (Computer science) --- Structures, Data (Computer science) --- Structures, Information (Computer science) --- File organization (Computer science) --- Abstract data types (Computer science) --- Computers --- Electronic computer programming --- Electronic digital computers --- Programming (Electronic computers) --- Coding theory --- Foundations --- Programming --- Computer algorithms. --- Algorithms