Winter 2017 Instructor: Vlad Wojcik
Assignment 1: Due Date: 03 March 2017, 2 PM.
In preparation to this assignment please familiarize yourself with the anatomy of the cochlea: http://en.wikipedia.org/wiki/Cochlea and the principle of operation of the cochlear implant: http://en.wikipedia.org/wiki/Cochlear_implant .
As discussed in class, hearing is similar in its nature to vision, but operates in 1D space of sequential signals. As such it constitutes a good introductory topic to vision.
As related ideas, you may want to compare the concepts of the Riemann integral with the Lebesgue integral.
Problem 1 [10 marks]:
Write a program that would read in two strings and identify within them all occurrences of a largest common substring. Observe that that substring may not be unique - your program should be able to identify all instances of all such substrings in both parent strings. Observe further that each instance of that substring may occur several times in each parent string. All these substring occurrences should be identified by your program.
Prepare input data to illustrate full capability of your program. You will be asked to demonstrate its functionality.
Problem 2 [30 marks]:
Vlad's best canine friend, Pyro, was a very smart dog. Pyro had an uncanny skill of recognizing Vlad's whistle. This is impressive because Vlad can never whistle twice in the same way (his lips may be moist, or dry, or chapped, the wind may or may not blow in Vlad's face, etc.). Moreover, Pyro could not be fooled by strangers trying to imitate Vlad's whistle: He may have listened for a moment, even look at that person, perhaps wag his tail (as if saying "Nice try, dude ...") and then ignored the imposter.
How Pyro did it? He used sound sensors in his cochlea. Each sensor fires when the surrounding air pressure deviates from the average pressure by a specified amount.
Fig.1. depicts the typical airwave of Vlad's whistle (blue) and that of the imposter (maroon). Pyro's battery of sensors created sets of time intervals generated by airwave pressure deviations. Partial behaviour of a sensor set at 0.8 units of air pressure is shown in Fig.1 above. The horizontal blue line (drawn slightly below the value of 0.8 so as not to overlap with horizontal maroon line) during the first interval when air pressure exceeds 0.8 units corresponds pretty much to the horizontal maroon line, generated by the signal of the imposter. That particular sensor cannot detect any difference between the two signals then.
The situation changes during the second interval. Vlad is able to keep air pressure above the 0.8 units level, generating one interval, while the imposter is unable to do so and generates two intervals separated by a short gap. Was this enough to convince Pyro that the second signal is a fake? Not always. For a given threshold pressure the sets of intervals generated by two signals must have differed by a specified amount for Pyro to detect the fakery.
Design an algorithm that would analyze the behaviour of one sensor. That algorithm would compare the remembered set of intervals to the incoming set of intervals in real-time and alert the user that they differ by a specified amount as soon as that happens.
Let's assume that Pyro's cochlea contains 2*N sensors that equally divide the air pressure interval from -3 to 3 units. Write a program that would use your algorithm to graph the time needed by Pyro to detect "whistle fraud" as a function of N = 1 ... 15. Assume that two sets of intervals are different enough to detect fraud if they differ by one time unit.
For the purpose of demonstration consider the honest whistle to follow the function y = 2*sin(x) + sin(3*x) + sin(5*x),
while the fraud follows y = 2.1*sin(x) + 1.1*sin(3.03*x) + 0.9*sin(4.97*x)
You will be asked to demonstrate your programs to your prof. and submit all printouts in an envelope during demonstration.
Instructor: Vlad Wojcik
Revised: Thursday, 09-Feb-2017 11:52 PM
Copyright © 2007 Brock University