Gigantic Graphs
This implementation is best when the graph is dense.
What is an Adjacency Matrix?
Technique that allows programmers to code as if there is more RAM than actually exists.
What is Virtual Memory?
These are inevitable in any hash table and must be handle with some scheme.
What are collisions?
AVL trees are always this.
These sorts merely swap adjacent records.
DFS uses this to traverse a graph?
What is recursion?
Finds a suitable free list block by selecting the biggest block.
What is worst fit?
Collisions are handled within the table.
What is open hashing?
A Huffman Encoding tree is a version of this tree.
What is a trie?
Divide list in half
sort the half
merge sorted halves together
What is merge sort?
The process of laying out the vertices in linear order.
What is topological sort?
The technique of collecting lost memory and returning pointers that are unused. Different languages differ in application.
What is garbage collection?
These indicate a record used to occupy this slot.
What is a tombstone?
A height balanced balanced BST like tree.
What is a 2-3 Tree?
The fastest known general purpose sorting algorithm.
What is quick sort?
BFS uses this to traverse a graph.
What is a queue?
This type of sort uses multiple runs, to to R, and sorts the data from runs, into buffers and then sorts the buffers.
What is external file merge sort?
The process of finding an alternate slot if the home slot is full.
What is probe sequence?
This tree stores records, or pointers to records, in leaves. Internal nodes only aid in search.
This sort exploits the best-case performance of insertion sort.
What is shellsort?
To prevent infinite loops in graph traversal we use these for each vertex.
What is a mark bit?
Data is placed into an array in RAM and placed into a heap. Sorting occurs with sift-down.
What is external file heap sort?
We have to use pre-calcuated permutations of values since this method is challanging to implement.
What is random probing?
In B+ trees, leaf nodes must remain at this capacity.
What is half full?
This sort places elements into bins based on the MOST sig digit.
What is radix sort?