Explore tens of thousands of sets crafted by our community.
Parallel Algorithms for Data Structures
20
Flashcards
0/20
HashTable - Parallel Insert/Search
Concurrent Hash Table with fine-grained locks - Complexity: O(1) expected
Merge Find Set - Parallel Union/Find
Parallel Union-Find - Complexity: O(log* n) amortized
Dictionary - Parallel Lookup/Insert
Concurrent Skip List - Complexity: O(log n) expected
Linked List - Parallel Search
Parallel search - Complexity: O(n/p + log p)
Multi-dimensional Array - Parallel Transposition
Parallel Matrix Transpose - Complexity: O(n^2/p)
Stack - Parallel Push/Pop
Lock-free stack algorithm - Complexity: O(1) amortized
Balanced Binary Tree - Parallel Insert/Delete
Concurrent AVL Tree - Complexity: O(log n)
Priority Queue - Parallel Access
Parallel Heap - Complexity: O(log n/p + log p)
Disjoint Set - Parallel Batch Operations
Parallel Batch Finds and Unions - Complexity: O((m + n) log* n)
Matrix - Parallel Multiplication
Cannon's Algorithm - Complexity: O(n^3/p^(1/3))
Graph - Parallel DFS
Parallel Depth First Search - Complexity: O(V + E/p)
Vector - Parallel Prefix Sum
Parallel Prefix Sum (Scan) - Complexity: O(log n)
Sparse Matrix - Parallel Computation
Parallel Sparse Matrix-Vector Multiplication - Complexity: O(nnz/p + n)
Array - Parallel Sorting
Parallel Merge Sort - Complexity: O(n log n)
Binary Tree - Parallel Traversal
Pre-order traversal in parallel - Complexity: O(log n)
Graph - Parallel BFS
Parallel Breadth First Search - Complexity: O(V + E/p)
Dynamic Array - Parallel Resize
Parallel Memory Allocation & Copy - Complexity: O(n/p)
Graph - Parallel Connected Components
Shiloach-Vishkin Algorithm - Complexity: O(log n)
Queue - Parallel Enqueue/Dequeue
Lock-free queue algorithm - Complexity: O(1) amortized
Graph - Parallel Minimum Spanning Tree
Parallel Borůvka's Algorithm - Complexity: O(log n)
© Hypatia.Tech. 2024 All rights reserved.
