# Converting a Cilk Arts Cilk++ application to Intel® Cilk™ Plus

This document summarizes the differences between the Cilk Arts implementation and the Intel® Cilk™ Plus implementation. It contains specific guidelines for porting Cilk Arts code to Cilk Plus code.
• Linux*
• Microsoft Windows* (XP, Vista, 7)
• C/C++
• Intel® C++ Compiler
• Intel® Parallel Composer
• Software condicional "WhatIf"
• CILK++
• Cilk Plus
• Computación en paralelo
• # Parallel solution to Hosoya Index of Graph Problem (Kuszmaul)

The included code and white paper provides a parallel solution for the Hosoya Index problem, as described in the included problem description text file. Parallelism is achieved using Cilk++.

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.

# Parallel algorithm to Solve the Graph Coloring Problem (Bradley Kuszmaul)

The included source code implements a variation of the Graph Coloring decision problem, as described in the included problem description text file. The algorithm implemented searches a “Zykov tree”, which computes the chromatic number of a graph by a recursive recurrence relation (as shown in the write-up). Each subexpression in the relation can be used to find a graph coloring of modified graphs. The concept of vertices that dominate other vertices in the graph helps drives the search through the recurrence relation. The parallelization was done with Cilk++.

# Parallel algorithm to solve Maximum Independent Set problem (Bradley Kuszmaul)

The included source code finds a Maximum Independent Set (MIS) of a given graph, 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 serial algorithm is a recursive search of paths with and without nodes in the MIS. However, an upper bound on the size of the MIS and the degree of nodes is proved used within this basic algorithm. The parallelization was done with Cilk++ and involves spawning search tasks for the two recursive calls from the serial code.

# Parallel algorithm to solve a Hamiltonian Path problem variation (Travelling Baseball Fan) (Bradley Kuszmaul)

The included source code implements a variation of the Hamiltonian Path problem, called the Travelling Baseball Fan 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 serial algorithm is a recursive search of all paths. To this basic algorithm, two heuristics have been added to reduce search time: remaining-degree and remaining-city.

# Parallel algorithm to 3-D Convex Hull Problem (Bradley Kuszmaul)

The included code and white paper provides a parallel solution for the 3-D Convex Hull problem, as described in the included problem description text file. Parallelism is achieved using Cilk++. Possible points for the convex hull are found by repeatedly selecting four points from the input set and finding the largest volumes of the formed tetrahedrons (using matrix determinants). An O(n^4) algorithm confirms those points that are actually on the convex hull from the possible points previously found.

# Parallel algorithm for finding intersections of line segments in 3-D (Bradley Kuszmaul)

The included source code implements a parallel search for intersections of input line segments within a 3-D space, as described in the included problem description text file. Three different methods of solution are initially considered. Complexity analysis and potential parallelization of the first two (brute force search, sweep-line algorithm) are considered and used to eliminate each from further consideration. The third method, Tree Decomposition, is chosen and explained in detail.

# Parallel algorithm to Bounded Knapsack Problem (matteocilk.com)

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.