Return to Video

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

English (United States) subtitles

改訂