Intel® Developer Zone:
Courseware - Recursion

  • The concept of recursion
  • Recursive mathematical functions
  • Simple recursive functions
  • Divide-and-conquer strategies
  • Recursive backtracking
  • Parallel solution to Taxi Path Problem (Vyukov)
  • Material Type:

    Coding example, Article / White paper

    ISN Logo

    Technical Format:

    text file, Word document, zip archive

    Location:

    Go to materials

    Date Added:

    12/21/2010

    Date Modified:

    12/21/2010

    Author

    Dmitry Vyukov, Moscow, Russia
    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. The code solves the problem through recursive enumeration of all possible permutations. A dynamic partitioning scheme is used to achieve good load balance and task granularity. 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:

    Delannoy number, Manhattan distance, grid traversal, parallel algorithm, recursion, divide and conquer, Threading Challenge Contest, Pthreads
  • Parallel solution to Taxi Path Problem (RuiDiao)
  • Material Type:

    Coding example, Article / White paper

    ISN Logo

    Technical Format:

    PDF document, zip archive, text file

    Location:

    Go to materials

    Date Added:

    12/21/2010

    Date Modified:

    12/21/2010

    Author

    Rui Diao, Academy of Mathematics and Systems Science, Chinese Academy of Sciences
    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. A divide and conquer algorithm is used to recursively build paths. The symmetric property of enumerated routes is used to conserve computation time and storage space. Parallelism is achieved using Intel Cilk Plus.

    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, recursion, divide and conquer, Threading Challenge Contest, Intel Cilk Plus
  • Parallel solution to Taxi Path Problem (mdma)
  • Material Type:

    Coding example, Article / White paper

    ISN Logo

    Technical Format:

    zip archive, text file, .odt

    Location:

    Go to materials

    Date Added:

    12/21/2010

    Date Modified:

    12/21/2010

    Author

    Matthew Mcgowan, Gvarv, Norway
    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. A divide and conquer algorithm divides the Cartesian grid into smaller regions. These subregions are themselves further recursively subdivided until the base case, a 1x1 block, is reached. For the base case, the set of paths are known in advance. The subdivided blocks are then joined together, to create larger blocks with longer paths, until eventually the complete grid has been built and the full set of paths generated. Each block-size is solved once and the results are reused multiple times. Parallelism is achieved using Java and Java Threads.

    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, recursion, divide and conquer, Threading Challenge Contest, java, java threads
  • Parallel solution to Taxi Path Problem (ddrogahn)
  • Material Type:

    Coding example, Article / White paper

    ISN Logo

    Technical Format:

    .odt, PDF document, text file, zip archive

    Location:

    Go to materials

    Date Added:

    12/21/2010

    Date Modified:

    12/21/2010

    Author

    Dan Rogahn, 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. A stack is used to hold incomplete paths that are popped and taken a step further until the destination point is reached. The stack elements could be popped and processed in parallel from a thread-safe stack structure. Parallelism is achieved using Intel Threading Building Blocks.

    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, stack, divide and conquer, Threading Challenge Contest, Intel Threading Building Blocks, TBB
  • Parallel solution to Taxi Path Problem (akki)
  • Material Type:

    Coding example, Article / White paper

    ISN Logo

    Technical Format:

    PDF document, zip archive, text file

    Location:

    Go to materials

    Date Added:

    12/21/2010

    Date Modified:

    12/21/2010

    Author

    Akshay Singh, Pune, India
    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. A divide and conquer algorithm is used to solve the problem. A dynamic programming mechanism to store solved sub-problems is used eliminate duplicate computations. 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:

    Delannoy number, Manhattan distance, grid traversal, parallel algorithm, recursion, divide and conquer, dynamic programming, Threading Challenge Contest, Pthreads