## Number of Tests - Software Debugging

• 0:00 - 0:05
Removing any of these subsets will result in a passing test,
• 0:05 - 0:11
which means that we again have to increase the granularity by doubling n in here.
• 0:11 - 0:14
Now we split the input into six subsets,
• 0:14 - 0:18
resulting in six more attempts to remove individual parts--
• 0:18 - 0:20
all of them will pass --
• 0:20 - 0:23
and then we have to increase the granularity again, which would be 12.
• 0:23 - 0:26
But now our input only has 8 characters,
• 0:26 - 0:29
and we can't split an 8 character input into 12 subsets
• 0:29 - 0:32
unless these subsets would be empty.
• 0:32 - 0:36
So we're going to fix this a bit by setting up this minimum function over here.
• 0:36 - 0:40
We make sure that n cannot grow beyond the size of the input,
• 0:40 - 0:43
which means that in our case n would now be 8.
• 0:43 - 0:46
This is the final stage of delta debugging
• 0:46 - 0:50
where it tries to remove one character after another,
• 0:50 - 0:53
but all of these removals result in passing test cases,
• 0:53 - 0:56
so what we get in the end is this very string
• 0:56 - 1:00
and we have now shown that every single character in here
• 1:00 - 1:06
is relevant, because removing it changes the outcome of a test from fail to pass.
• 1:06 - 1:10
So, what delta debugging gives us in the end is an input --a simplified input--
• 1:10 - 1:13
where every single part is relevant.
• 1:13 - 1:18
At this point you may wonder how many tests does delta debugging actually take?
• 1:18 - 1:21
You can see that at the very end when every single character has
• 1:21 - 1:24
to be removed individually, the number of tests of course
• 1:24 - 1:28
is proportional to the length of the simplified input.
• 1:28 - 1:32
In the worst case--that is, for very pathological examples--
• 1:32 - 1:36
the complexity of delta debugging is squared with respect to its input.
• 1:36 - 1:39
However, there is a nice situation in which delta debugging
• 1:39 - 1:44
simply becomes a binary search and is as efficient as a binary search.
• 1:44 - 1:48
So, when does delta debugging need a logarithmic number of tests?
• 1:48 - 1:50
Is this when all tests fail?
• 1:50 - 1:55
Is this when there is always 1/2 that can be removed and fails?
• 1:55 - 1:58
Is this when all tests pass?
• 1:58 - 2:01
Or is this never? Check all that apply.
タイトル：
Number of Tests - Software Debugging
Video Language:
English
Team:
Udacity
プロジェクト：
CS259 - Software Debugging
Duration:
02:02
 Udacity Robot edited English (United States) subtitles for Number of Tests - Software Debugging

# English (United States) subtitles

## 改訂

• API
Udacity Robot