Problem Detail: Yesterday while returning home, I walked past a house that had a camera. For some reason I started thinking about how these cameras work, and how you would use them in case of robbery. While thinking about everything that might happen in case of robbery, one problem came into my mind and it can be described as follows. Suppose that you and your family decided to go on a trip abroad, that would last for around 7 days. After spending some nice time with your family, you return back only to realize that your home had been robbed. You call the police and the police asks for the data stored in the camera. Now, you know for sure that the robbery happened during those 7 days that you were gone, and you definitely know that the camera will show the people doing the robbery at some specific point of time, problem is, you do not know when. Now, assuming that no one had seen anything at all and that the only source of information would be the data stored by the camera, how would the police find the time during which the robbery happened? Can they do something better than watching every single second of the footage available? In computer science terms, assume that you are given an array of size $N$, where all the elements are white, except for one which is black. Now you can imagine that the white elements are just images stored by the camera and the indexes of the array represent seconds. If no robbers are depicted in the image, then this image is white, otherwise it is black. So now you want to find that second where the robbers are depicted in the image, so you are looking for the index of the black element in your array. Can you do better than actually scanning the entire array to find that index?
Asked By : jsguy
Answered By : D.W.
For your problem with the array: No, there is no better algorithm. That’s the best you can do. Any deterministic algorithm will in the worst case have to look at every array element (technically: at least $n-1$ of the $n$ elements). This can be proven by an adversarial algorithm: consider any algorithm, and imagine it has looked at $n-2$ elements and hasn’t found the black element yet. Then I claim a correct algorithm has to examine at least one more array element. If it doesn’t, then look at what output it produces, and see which of those two elements it blames; you can now construct an array that puts the black element at the other element (the one it didn’t blame and hasn’t looked at yet). That array will be entirely consistent with everything the algorithm has seen so far, so the algorithm will produce the wrong output on that array. For your problem with the camera video: In real life, there are much better techniques available. For instance, you can do “change detection” to find the frames in the video that are different (show a change from the previous frame) and look only at those. There are more sophisticated things you can do, but this illustrates that in practice you can often do much better, by taking advantage of domain-specific information about video surveillance.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/43953
