Please enable JavaScript.
Coggle requires JavaScript to display documents.
SETS - Coggle Diagram
SETS
Unordered collection of distinct items
Can be defined by a listening of its elements or by a comum property
Most important set operations:
Checking mambership
Union o two sets
Intersection of two sets
Ways to implement in a computer:
Universal set with bit vectors
With list structure
Differences between a set and a list:
Sets cannot contain identical elements
If it contains, we call it "multiset" or "bag"
Set is unordered
Most often operations to perform
Search for a given item in a given set
Add new item
Delect a item
To use these tree operations we use a data structure called
DICTIONARY
SPACE AND TIME TRADE-OFFS
Space and time efficiencies fight against each other
input enhancement
counting methods for sorting
Boyer-Moore algorithm for string matching and its simplified version suggested by Horspool
prestructuring
hashing
A very efficient way to implement dictionaries
Hashing is based on the idea of distributing keys among a one-dimensional array
indexing with B-trees
dynamic programming