Zone des développeurs Intel® : Courseware - Algorithmic Strategies

• Brute-force algorithms
• Greedy algorithms
• Divide-and-conquer
• Backtracking
• Branch-and-bound
• Heuristics
• Pattern matching and string/text algorithms
• Numerical approximation algorithms
• Parallel Solution to Cat-and-Mouse strategy game problem (Vyukov)
•  Material Type: Coding example, Article / White paper Technical Format: text file, zip archive, Word document Location: Go to materials Date Added: 12/22/2010 Date Modified: 12/22/2010 Author Dmitry Vyukov, Moscow, Russia Description:The included code and white paper provides a parallel solution for enumerating the total number of possible wins, losses, and draws for a two-person strategy game. A Cat and Mouse move on a directed graph; the Cat attempts to catch the Mouse, while the Mouse attempts to occupy a goal node within the maximum number of moves allowed. Even though the problem deals with graphs, the solution given is based on dynamic programming. A detailed description of how to apply dynamic programming to this problem is included in the write-up. Parallelism is implemented with Pthreads. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Graduate students, Undergraduate students Language: English Keywords: Strategy, game, graph traversal, dynamic programming, parallel algorithm, Threading Challenge Contest, Pthreads
• Parallel Solution to Cat-and-Mouse strategy game problem (akki)
• Parallel solution to Taxi Path Problem (spillner)
•  Material Type: Coding example, Article / White paper Technical Format: text file, zip archive, PDF document Location: Go to materials Date Added: 12/21/2010 Date Modified: 12/21/2010 Author Brent Spillner, USA Description:The included code and white paper provides a parallel solution for enumerating Delannoy paths visualized as paths of a taxi through a grid of city streets. Paths that exclude the use of diagonals are enumerated. The two directions of legal moves can be encoded by a single bit each. From these paths, any combination of “01” or “10” is where a diagonal can be substituted within the diagonal-free paths. Parallelism is used to generate sets of bit-sequence path representations and is implemented using Pthreads. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Graduate students, Undergraduate students Language: English Keywords: Delannoy number, Manhattan distance, grid traversal, parallel algorithm, divide and conquer, Threading Challenge Contest, Hamming weight, Pthreads
• Parallel Algorithm to String Matching Problem
•  Material Type: Coding example Technical Format: text file, zip archive, PDF document Location: Go to materials Date Added: 7/28/2010 Date Modified: 7/28/2010 Author Bradley C. Kuszmaul, MIT Computer Science and Artificial Intelligence Laboratory Description:The included code and white paper provides a parallel solution for the DNA string matching problem, as described in the included problem description text file. The included write-up gives an overview of Cilk++ and some of the tools available for Cilk programming. The Rabin-Karp hashing method and a simple search algorithm to compare the query string with a successive database substrings is presented and analyzed. After some serial optimizations are described, the write-up describes how the algorithm is parallelized using Cilk++. The code was intended for Linux OS platforms. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Undergraduate students Language: English Keywords: String matching, DNA string matching, Cilk++, RabinKarp hashing, rolling hash search
• The Knight's Tour: A Concurrent Solution
•  Material Type: Coding example Technical Format: Word document, text file, .sln, Excel spreadsheet, zip archive Location: Go to materials Date Added: 7/28/2010 Date Modified: 7/28/2010 Author Peter Hinsbeeck, Intel Description:Several years ago, an ex-colleague of the author returned from a job interview with an interesting story. He was given the option to choose from a short list of problems to solve in a given time period. One of them was the classic “Knight’s Tour” problem from the game of chess. Since then, the author often thought about how he might respond to such a job interview question, and, how easily his solution might parallelize. DISCLAIMER: This material includes the author’s approach to the problem; serial and parallelized versions of the code; and a spreadsheet that shows the timings obtained for each version. Recommended Audience: Advanced programmers, Beginning programmers, Undergraduate students Language: English Keywords: Knights Tour, serial solution, parallel solution
• Parallel algorithm to solve a Knight’s Tour problem variation(BradleyKuszmaul)
•  Material Type: Coding example Technical Format: text file, PDF document, zip archive Location: Go to materials Date Added: 7/28/2010 Date Modified: 7/28/2010 Author Bradley C. Kuszmaul, MIT Computer Science and Artificial Intelligence Laboratory Description:The included source code implements a variation of the Knight’s Tour problem that counts the number of possible tours of a given length in parallel, as described in the included problem description text file. The algorithm enumerates legal paths that are half of the set length and then matches up the endpoints of different half tours to identify and count the number of tours that will return the knight to the original square. The parallelization was done with a combination of Cilk++ and POSIX Threads. The code was intended for Linux OS and includes a makefile to build the applications. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Undergraduate students Language: English Keywords: Knights Tour, Cilk++, POSIX Threads, Pthreads, Hamiltonian path
• Parallel algorithm to solve a Knight’s Tour problem variation(Jonas D'Mentia)
•  Material Type: Coding example Technical Format: text file, .docx, .rar Location: Go to materials Date Added: 7/28/2010 Date Modified: 7/28/2010 Author Jonas D’Mentia, Kearneys Spring, Queensland, Australia Description:The included source code implements a variation of the Knight’s Tour problem that counts the number of possible tours of a given length in parallel, as described in the included problem description text file. The write-up defines a brute force serial method and then an optimization to that algorithm. The optimized algorithm enumerates legal paths that are half of the set length and then matches up the endpoints (leaves on a search tree) of different half tours to identify and count the number of tours that will return the knight to the original square. Discussion of the parallel solution identifies three possible places within the serial algorithm that could be made to execute in parallel. The analysis for two of these computations proves that the required computations are not very amenable to parallelization, but the third is implemented using OpenMP. The code was intended for Windows OS and includes Microsoft Visual Studio solution and project files to build the application. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Undergraduate students Language: English Keywords: Knights Tour, OpenMP, search tree, Hamiltonian path
• Parallel algorithm to solve a Knight’s Tour problem variation(Matthew McGowan)
•  Material Type: Coding example Technical Format: text file, zip archive Location: Go to materials Date Added: 7/28/2010 Date Modified: 7/28/2010 Author Matthew McGowan, Gvarv, Norway Description:The included source code implements a variation of the Knight’s Tour problem that counts the number of possible tours of a given length in parallel, as described in the included problem description text file. The algorithm enumerates legal, acyclic paths that are half of the given length and then matches up the endpoints of different half tours to identify and count the number of tours that will return the knight to the original square. After some analysis, it is determined that the matching of the half tours was the most compute intense portion of the algorithm. This recursive computation is parallelized through Java threads by spawning tasks at different levels of the recursion (in order to not have too many tasks with little or no work to be done). Several coding and memory access optimizations that were implemented are included in the write-up. Besides the Java source files, MS-DOS compilation and execution batch files are included to build and run the application. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Undergraduate students Language: English Keywords: Knights Tour, Java, Java threads, Hamiltonian path, parallelizing recursion
• Parallel Algorithm to solve a Knight's Tour Problem Variation (Lin Jinpo)
•  Material Type: Coding example Technical Format: Word document, text file, zip archive Location: Go to materials Date Added: 7/28/2010 Date Modified: 7/28/2010 Author Lin Jinpo, Guangzhou, China Description:The included source code implements a variation of the Knight’s Tour problem that counts the number of possible tours of a given length in parallel, as described in the included problem description text file. The algorithm used is a straightforward backtracking algorithm supported by a breadth-first order expansion of possible moves from the current square to define parallel tasks. Once the tasks are defined, each does a depth-first search from the given square that defines the task. Parallelization of the depth-first search portion of the code is accomplished with OpenMP. The code was intended for Windows OS and includes Microsoft Visual Studio solution and project files to build the application. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Undergraduate students Language: English Keywords: Knights Tour, OpenMP, breadthfirst search, depthfirst search, Hamiltonian path