A core part of many pattern recognition algorithms involves comparisons between pairs of points. For example,...

  

Transcribed Image Text:

A core part of many pattern recognition algorithms involves comparisons between pairs of points. For example, in optical character recognition, a pattern such as a alpha-numeric character might be compared to templates to identify that pattern. For the following questions Suppose we have K templates and N patterns. a) What is the running time complexity for an algorithm that finds the closest template for every pattern by comparing every template? (2 P.) b) Suppose each comparison (with appropriate pre-processing) takes 0.05 ms and we have K = 5000 tem- plates in our character database (to cover all the different fonts). How long would it take to recognize a typical page of text assuming N=1000 characters per page? (2 P.) c) Now suppose we implement a new algorithm that using a data structure that allows us to narrow down the possible set of closest templates by half at each iteration. What is the running time of this new algorithm? (1 P.) d) What is the new average time per page? (2 P.) e) Suppose we increase the size of our character database to 10,000. In terms of percentage of the original running time, how much do each of the two algorithms increase? (4 P.) A core part of many pattern recognition algorithms involves comparisons between pairs of points. For example, in optical character recognition, a pattern such as a alpha-numeric character might be compared to templates to identify that pattern. For the following questions Suppose we have K templates and N patterns. a) What is the running time complexity for an algorithm that finds the closest template for every pattern by comparing every template? (2 P.) b) Suppose each comparison (with appropriate pre-processing) takes 0.05 ms and we have K = 5000 tem- plates in our character database (to cover all the different fonts). How long would it take to recognize a typical page of text assuming N=1000 characters per page? (2 P.) c) Now suppose we implement a new algorithm that using a data structure that allows us to narrow down the possible set of closest templates by half at each iteration. What is the running time of this new algorithm? (1 P.) d) What is the new average time per page? (2 P.) e) Suppose we increase the size of our character database to 10,000. In terms of percentage of the original running time, how much do each of the two algorithms increase? (4 P.)