5,323
edits
Parallel Algorithms: Difference between revisions
→Graph Connectivity
| Line 654: | Line 654: | ||
;Notes | ;Notes | ||
* The progression of edge weights up the tree are monotonically increasing so there are no cycles | * The progression of edge weights up the tree are monotonically increasing so there are no cycles | ||
==Tricks== | |||
===Removing duplicates in an array=== | |||
Assume you have an Arbitrary CRCW | |||
* Given array A of size n with entries 0 to n-1 | |||
* For each entry pardo | |||
** Write B[A[i]] == i | |||
** Only one write will succeed for each unique A[i] | |||
** Check if B[A[i]] == i | |||
===Compaction of an <math>n^2</math> array with <math>\leq n</math> elements in <math>O(\log n)</math> time=== | |||
* Split our <math>n^2</math> array to n subarrays, each of size <math>n</math> | |||
* Run <math>n</math> parallel compactions on each subarray | |||
* Perform one compaction on the size of each subarray | |||
* Compact all elements using (total size of prev subarrays + position in current subarray) | |||
==Hardware/Architecture== | ==Hardware/Architecture== | ||