Index

A

acyclicity test depth-first search adjacency list adjacency matrix algorithm describing greedy Amdahl's law amortized constant-time analysis apriori experimental

apriori analysis arbitrage array fixed-size resizable atomicity AVL tree insertion removal

B

B-tree backtracking search Bellman-Ford algorithm big-O notation big-omega notation big-theta notation binary heap decrease-priority operation downheap operation heap property implementations increase-priority operation insert operation max operation memory representation remove-max operation upheap operation binary search C++ implementation pseudocode running time Scala implementation

binary search tree AVL insertion largest key listing predecessor key red-black removal rotation running time search smallest key successor key bit array bit set bit vector breadth-first search pseudocode running time

C

circular buffer complexity class P computation fork independent join span work computational problem decidable decision problem function problem longest path median minimum spanning tree minimum Steiner tree optimization problem primality shortest path subset sum

computing cluster connected component convolution counting sort cycle directed graph undirected graph

D

DAG data race decision problem depth-first forest depth-first search acyclicity test basic version depth-first forest depth-first tree extended version pseudocode running time strongly connected component timestamp topological sort depth-first tree deque dictionary digraph Dijkstra's algorithm

direct-access table directed acyclic graph disjoint sets abstract data type balancing find-set operation make-set operation path compression representation with a forest union operation double-ended queue doubly-linked list dynamic programming activity-selection problem Fibonacci numbers longest common subsequence memoization rod cutting solution construction subset-sum

E

edge directed weight embarrassingly parallel problem exhaustive search experimental analysis insertion sort matrix multiplication mergesort parallel mergesort parallel mergesort with parallel merge quicksort selection sort

F

false sharing Fibonacci numbers dynamic programming forest fork

fork-join framework nested parallelism task function problem

G

generic programming generics GPU graph adjacency list adjacency matrix connected directed edge-weighted representation undirected vertex attribute

graphics processing unit greedy algorithm activity-selection problem Dijkstra's algorithm Kruskal's algorithm minimum spanning tree Prim's algorithm

H

hash function, [1] cryptographic for compound objects for integers for strings key universe hash table chaining closed hashing clustering collision collision probability collision resolution double hashing independent uniform permutation hashing linear probing load factor open addressing open hashing primary clustering probe sequence probing quadratic probing rehashing removing keys secondary clustering separate chaining simple uniform hashing

hash value, [1] heapsort

I

image filtering immutable linked list inorder traversal insertion sort experimental analysis running time stability

integration numeric trapezoidal rule

J

join

K

kernel Gaussian blur

Kosaraju's algorithm Kruskal's algorithm

L

level order traversal linear search pseudocode running time linked list doubly-linked immutable mutable

little-o notation little-omega notation load factor hash table resizable array Lomuto's partitioning algorithm longest common subsequence dynamic programming

M

map ordered unordered matrix multiplication experimental analysis instruction-level parallelism parallel running time transposition memoization dynamic programming merge operation parallel

mergesort experimental analysis main routine memory requirement merge parallel running time small sub-arrays Moore's law multicore processor mutable linked list

N

non-recursive notation big-O big-omega big-theta little-o little-omega

NP-complete problem approaches for solving subset-sum

O

optimization problem, [1]

P

parallel count, [1], [2] matrix multiplication merge operation mergesort parallel for-loop partitioning algorithm quicksort path directed graph shortest undirected graph weight

pivot element quicksort postorder traversal preorder traversal Prim's algorithm priority queue problem embarrassingly parallel pruning technique pseudocode binary search breadth-first search depth-first search linear search

Q

queue quicksort equal elements experimental analysis Lomuto's partitioning algorithm partitioning algorithm pivot element pivot element selection running time stability

R

radix sort recurrence binary search subset sum algorithm recursive recursive program running time red-black tree insertion removal resizable array capacity expansion factor load factor size reverse Polish notation, [1] rod cutting dynamic programming

running time average-case best-case binary search binary search tree breadth-first search depth-first search insertion sort linear search matrix multiplication measuring in Scala mergesort of algorithms quicksort recursive program selection sort subset sum algorithm worst-case

S

selection sort experimental analysis running time stability separable filter set ordered unordered shortest paths Bellman-Ford algorithm Dijkstra's algorithm in DAGs small sub-arrays mergesort sorting by key by ordering sorting algorithm counting sort heapsort in place insertion sort lower bounds in running time memory requirement mergesort quicksort radix sort selection sort stable

span spanning tree generic greedy algorithm Kruskal's algorithm minimum Prim's algorithm weight speedup stability insertion sort quicksort selection sort stack Steiner tree strongly connected component depth-first search subset sum algorithm running time subset-sum backtracking search algorithm dynamic programming algorithm proving NP-completeness sudoku problem reducing to satisfiability

T

template metaprogramming thread synchronization time slice timestamp depth-first search topological sort trapezoidal rule

tree binary complete binary data structure representation definition free full binary rooted traversing

W

work