Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets and Dictionaries, Space and Time Trade-Offs - Coggle Diagram
Sets and Dictionaries
Set
A set can be described as an unordered collection (possibly empty) of distinct items called elements of the set
Operations
finding the union of two sets
finding the intersection of two sets
checking membership of a given item in a given set
Applications
The first considers only sets that are subsets of some large set U, called the universal set
If set U has n elements, then any subset S of U can be represented by a bit string of size n, called a bit vector
the ith element is 1 if and only if the ith element of U is included in set S. Thus, to continue with our example, if U = {1, 2, 3, 4, 5, 6, 7, 8, 9}, then S = {2, 3, 5, 7} is represented by the bit string 011010100
The second and more common way to represent a set for computing purposes is to use the list structure to indicate the set’s elements.
the two principal points of distinction between sets and lists.
First, a set cannot contain identical elements;
a list can.
Second, a set is an unordered collection of items; therefore, changing the order of its elements does not change the set.
Dictionaries
A data structure that implements these three operations: searching for a given item, adding a new item, and deleting an item from the collection
Hashing
Trees
Array
Set union problem
Space and Time Trade-Offs
the idea is to preprocess the problem’s input, in whole or in part, and store the additional information obtained to accelerate solving the problem afterward
input enhancement
counting methods for sorting
Boyer-Moore algorithm for string matching and its simplified version suggested by Horspool
prestructuring
Exploits space-for-time trade-offs simply uses extra space to facilitate faster and/or more flexible access to the data
hashing
Hashing is based on the idea of distributing keys among a one-dimensional array H[0..m − 1] called a hash table.
The distribution is done by computing, for each of the keys, the value of some predefined function h called the hash function. This function assigns an integer between 0 and m − 1, called the hash address, to a key.
A hash function needs to distribute keys among the cells of the hash table as evenly as possible. (This requirement makes it desirable, for most applications, to have a hash function dependent on all bits of a key, not just some of them.
Open Hashing (Separate Chaining)
In open hashing, keys are stored in linked lists attached to cells of a hash table. Each list contains all the keys hashed to its cell.
Closed Hashing (Open Addressing)
In closed hashing, all keys are stored in the hash table itself without the use of linked lists.
A hash function has to be easy to compute.
A hash table’s size should not be excessively large compared to the number of keys, but it should be sufficient to not jeopardize the implementation’s time efficiency (see below).
indexing with B-trees
some processing is done before a problem in question is actually solved but, unlike the input-enhancement variety, it deals with access structuring
dynamic programming