Hamming Distance

Description

Hamming
msladey
Flashcards by msladey, updated more than 1 year ago
msladey
Created by msladey almost 9 years ago
7
0

Resource summary

Question Answer
What is the Hamming Distance Problem? For every alignment i, output Ham(i), the hamming distance between P and T[i ... i+m-1]
By computing cross correlations to solve the hamming distance problem, what time and space complexity can we expect? O(n|sigma|logm) total time O(n) space
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 When the alphabet is longer than m
For the O(n(rootm)logm) method, how many times must a symbol occur for it to be classed as frequent? root m
How many frequent symbols can there be? root m at most
Stage 1 involves counting the number of matches involving frequent symbols. What is the time complexity of this step? O(n(rootm)logm)
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? An array of length (n - m + 1) is constructed initially containing zeros. During a single pass of T, if T[k] is infrequent, for all j such that T[k] = P[j], increase A[k - j] by one, as long as k - j > 0. A[i] is the number of matches at alignment i involving an infrequent symbol.
How quick is stage 2 of the O(n(rootm)logm) algorithm? O(n root m)
How quickly can we classify each symbol as frequent or infrequent? O(mlogm)
How can we improve the O(n(rootm)logm) algorithm to O(n (rootmlogm))? By changing the definition of frequent to be at least root(mlogm) occurrences.
Show full summary Hide full summary

Similar

Mathematical Preliminaries
msladey
Suffix Arrays
msladey
Suffix Trees
msladey
Range Minimum Query
msladey
Data Structures & Algorithms
Reuben Caruana
Computer science unit 2
Somto Ibeme
Algorithms ♡
lauren ♥
Computational Thinking ♡
lauren ♥
Searching and Sorting Algorithms
Josh Calvert
Systems Software Revision
cocacolai
Grafy I.
Michal Roch