Big-O and Brute-force Algorithms
This function is Little-O(n^3) and Little-Omega(n^2).
What is n^2 log n?
The Binary Search Tree requires that Java interface to be implemented by the key class whereas the Digital Search Tree doesn't.
What is Comparable?
The size of the keyspace if keys are SSNs.
What is 10^9?
This type of randomized algorithms is guaranteed correct but probably fast.
What is Las Vegas?
The two main approaches to compression.
What are lossless and lossy compression?
This technique increases the practicality of a brute-force algorithm but doesn't affect its asymptotic performance.
What is pruning?
The number of levels of a Radix Search Trie that has 100 5-bit keys.
What is no such trie?
Because of this principle, collisions cannot be avoided if |keyspace| > m.
What is the pigeon hole principle?
The preprocessing cost of this algorithm is amortized when you search within the same text over and over.
What is Rabin-Karp?
This data structure is well suited for storing the LZW codebook during compression.
What is DL Trie?
In Assignment 1, you tried hard to have that asymptotic running-time of the non-recursive part of your backtracking method.
What is O(1)?
The average number of comparisons to search in an 32-way Search Trie that has 2^20 keys.
What is 4?
This is an entry inside a linear-probing hash-table and it has the highest probability that a key x will be inserted into it.
The number of modular multiplications you need to compute the Rabin-Karp fingerprint of the string "bcde" given the fingerprint of the string "abcd."
What is 1?
In LZW with variable-width codewords, assuming you start with a 7-bit codeword, this is the number of entries in the codebook after which you have to increase the codeword width.
What is 128?
This is the running time of a brute-force approach to the searching problem (given a key, indicate whether or not it exists in a set of items).
Theta(n)
At least this number of references are wasted in an 256-way Search Trie if all keys begin with the word "name."
The number of probes asymptotically needed to find an empty index in an almost-full hash-table that uses double hashing for collision resolution.
What is m? or What is n?
The total number of character comparisons that must be done using the mismatched character heuristic of the Boyer-Moore string matching algorithm for the following text and pattern:
Text: ABCDXABCDYABCDZABCDE
Pattern: ABXYZ
What is 7?
This compression approach can compress a message to have more than 1 bit of information per bit of compressed message.
What is lossy compression?
This is the maximum file size you can sort using the Hybrid Merge Sort Algorithm with a memory size of 1000 bytes and an item size of one byte (assuming you do only one merge operation).
What is 1,000,000 bytes?
You need this number of nodes in a DLB Trie that has the keys: she, sells, sea, shells, by, the, sea, shore.
What is 20?
Assuming a good hash function, this is the average key-lookup time in a hash table that uses separate chaining for collision resolution.
What is alpha?
You change the pattern index (j) to this value when you are searching for the pattern ABBABAC using KMP, four letters of the pattern have already been matched and the current text letter is B.
What is 5?
Huffman compression will compress the file AAABBBAAB into this number of bits ignoring the trie storage overhead.
What is 9?