What is the Hamming Distance Problem?

By computing cross correlations to solve the hamming distance problem, what time and space complexity can we expect?

Briefly explain how to solve the hamming distance problem using cross correlations

Name a situation where the cross correlation method to solve the hamming distance problem is worse than the naive method

For the O(n(rootm)logm) method, how many times must a symbol occur for it to be classed as frequent?

How many frequent symbols can there be?

Stage 1 involves counting the number of matches involving frequent symbols. What is the time complexity of this step?

Stage 1 involves counting the matches involving frequent symbols using cross correlations. How does this differ from stage 2, which involves counting the matches involving infrequent symbols?

How quick is stage 2 of the O(n(rootm)logm) algorithm?

How quickly can we classify each symbol as frequent or infrequent?

How can we improve the O(n(rootm)logm) algorithm to O(n (rootmlogm))?