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

ISN Logo

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)

 

 

Material Type:

Coding example, Article / White paper

ISN Logo

Technical Format:

zip archive, PDF document, text file

Location:

Go to materials

Date Added:

12/22/2010

Date Modified:

12/22/2010

Author:

Akshay Singh, Pune, India
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. The parallel solution has been implemented using akkithreads – a C++ wrapper over the Pthreads library with additional features such as JobQueues (Static / Dynamic) and a ThreadPool implementation.

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 Algorithm to String Matching Problem

 

 

Material Type:

Coding example

ISN Logo

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

ISN Logo

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

ISN Logo

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

ISN Logo

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

ISN Logo

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

ISN Logo

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
Para obtener información más completa sobre las optimizaciones del compilador, consulte nuestro Aviso de optimización.