Other Algorithms Flashcards
Binary search tree runtime
Search
Average: O log n
Worst case: O n
Insert/delete
Avg O log n
Red-black tree
A binary search tree that balances it self
B-tree
A binary search tree used to store data in databases
Inverted index
A hash that maps words to locations
Uses of an inverted index
Commonly used in search
Fourier transform
Breaks down something into components.
Ie a song into frequencies and notes
Used for mp3 algorithm
Parallel algorithms
Running an algorithm across multiple cores/servers etc.
Challenges with parallel algorithms
-Overhead of managing parallelism
-Load balancing
MapReduce
A popular distributed algorithm used by Apache Hadoop
What is MApReduce useful for
Working with large data sets across multiple servers
Map function
Applies the same function to each element of an array
Reduce function
Transform an array to a single item
Probabilistic algorithms
Could give false positives but don’t give false negatives
Fast and use less data
Bloom filter
Probabilistic data structure
HyperLogLog
Approximates the number of unique elements in a set
SHA
Secure hash algorithm
A one way string to string hash
Hash
Short string
Uses of SHA
It can tell you if two files/strings/etc are the same
Uses to store and check passwords
Locality sensitive hashing
A hash algorithm that generate similar hashes for similar strings.
Could be used to compare if files/sites are similar to each other.
Diffie-Hellman
A public key encrypts
A private key decrypts
Linear programming
Used for optimization
