Intel® Developer Zone:
Courseware - Advanced Analysis

  • Amortized analysis
  • Online and offline algorithms
  • Randomized algorithms
  • Dynamic programming
  • Combinatorial optimization
  • Parallel algorithm for 3-Satisfiability Problem (Jianan Hao)
  • Material Type:

    Coding example, Problem set

    ISN Logo

    Technical Format:

    PDF document, text file, zip archive

    Location:

    Go to materials

    Date Added:

    03/17/2010

    Date Modified:

    03/17/2010

    Author

    Jianan Hao, Intel
    Description:

    The included source code implements a parallel solution to an input instance of the 3-Satisfiability problem, as described in the included problem description text file. The input form of the Boolean expression is conjunctive normal form. 

    The included write-up describes a depth-first search algorithm to find a solution. As variables are given either a TRUE or FALSE assignment, an attempt is made to reduce the number of variables in clauses based on current settings of variables already examined along the current search path. Windows Threads is used to implement the parallelism; Intel Threading Building Blocks (TBB) and OpenMP were considered but discarded for cited reasons. 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:

    3SAT, Boolean satisfiability, conjunctive normal form, CNF, Windows Threads, depth first search
  • Parallel algorithm for Bounded Knapsack Problem (Dmitry Vyukov)
  • Material Type:

    Coding example, Problem set

    ISN Logo

    Technical Format:

    text file, zip archive, Word document

    Location:

    Go to materials

    Date Added:

    03/17/2010

    Date Modified:

    03/17/2010

    Author

    Dmitry Vyukov, Intel
    Description:

    The included code and solution write-up provides a parallel solution for the bounded knapsack problem, as described in the included problem description text file. The included write-up gives an overview of a dynamic programming algorithm to choose between possible solutions. In order to reduce the computational complexity, some preprocessing techniques are applied as described in the write-up. The parallelization of the dynamic programming portion of the algorithm was found to be untenable. However, the preprocessing steps offered enough independent work to make parallelization worthwhile. Intel Threading Building Blocks (TBB) is used for implementing the parallelism within the preprocessing tasks. 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:

    Intel TBB, TBB, knapsack, bounded knapsack problem, Intel Threading Building Blocks, dynamic programming
  • Parallel algorithm to Bounded Knapsack Problem (matteocilk.com)
  • Material Type:

    Coding example, Problem set

    ISN Logo

    Technical Format:

    text file, PDF document, zip archive

    Location:

    Go to materials

    Date Added:

    03/17/2010

    Date Modified:

    03/17/2010

    Author

    Matteo Frigo, (matteocilk.com), Cilk Arts
    Description:

    The included code and solution write-up provides a parallel solution for the bounded knapsack problem, as described in the included problem description text file. The included write-up gives an overview of a branch-and-bound technique (as opposed to a dynamic programming algorithm) to enumerate possible solutions. The three heuristics that are implemented in the code (linear-programming relaxation, minimum-weight heuristic, and dominator heuristic) are described. The algorithm is parallelized using Cilk++ in order to launch recursive search tasks. 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, Beginning programmers, Undergraduate students

    Language:

    English

    Keywords:

    Cilk++, C, branchandbound technique, Search