Notice: Function _load_textdomain_just_in_time was called incorrectly. Translation loading for the twentyfifteen domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /var/www/sunapi386.ca/wordpress/wp-includes/functions.php on line 6121
December 2014 – sunapi386's Blog

Parallel Algorithms: Prefix Sum Application On Graph

Preparing for advanced algorithms exam (CS450 at EPFL), and I just truly understood a problem. First reaction is: “TIL prefix sum is a stack. So powerful!”.


The problem:

You are given a cycle of n vertices with an additional set T of edges between these n vertices (in addition to the n edges that form the cycle). You are to determine whether it is possible to draw the edges of T inside the cycle in such a manner that no two edges cross. Develop a parallel algorithm that runs on O(logn) time and uses linear total work to solve this problem.

Continue reading Parallel Algorithms: Prefix Sum Application On Graph