none
Test rules for algorithms implementation, what are they? RRS feed

  • Question

  • I wonder, how could I test my implementation of some algorithm?

    What are the exact options for the test?

    1). Is algorithm decomposing on determinate / non-determinate final state machine required?

    For example, KMP ( Knuth-Morris-Pratt ) algo is decomposing on FSM ( finite state machine ) on University of California educational site:http://www.ics.uci.edu/~eppstein/161/960222.html

    2). Unit-testing?

    3). Smth else?

    Thanks,

    Best Regards

    Saturday, July 21, 2012 11:42 AM

Answers

  • You have to write testable code.

    • That may mean writing a function that you can pass some arguments and get a known result.
    • That may mean that you write your code so that you can do this many times with many different test cases without polluting the results of other runs.
    • That may mean that you break your code up into many functions, and test each of those functions in this way.
    • That may mean that you have a set of data and you step forward one "iteration" of your algorithm, then interrogate your large data set again to make sure it reflects the new state.
    • That may mean that you expose inner workings of your algorithm, such as loop counters, or other temporary storage, so that they can be examined and verified.

    Saturday, July 21, 2012 1:21 PM
  • Normally the term that is used to determine if software if fully tested is "Coverage".  We normally try to test software statement we have > 95% coverage. coverage refereing to testing each line of sode in the program.

    There are really two criteria testing software

    1) Test using different inputs to get different output results.

    2) Make sure all the paths in your software are fully tested.  You also want to make sure you can go from each path in the software to evary other path in the software.  There are software simultor available that will automatically give you statistics on you coverage of software during testing.

    A linear program with no multiple paths is simpliest type program to test.  But still with no loops data results can be different like when you subtract two numbers your results can be positive, negative, and zero.  You also have situations when you add two numbers you can get results that have different number of decimal places which can produce formating errors.

    So to fully test software you want to make sure you use a combination of random inputs as well as inputs that will test exteme limits of the software input and output (high and low values).

     


    jdweng

    Saturday, July 21, 2012 2:30 PM
  • It's funny that you say I helped you with the practice-side of testing but you want to know more about the theoretical, because in my mind, I gave you theoretical information.  :/  It was generalized because you question was quite general:  "How could I test my implementation of some algorithm?"  So I hope I'm not too far off track with my reply.  I do sort of feel like I don't understand what kind of information you're after.

    By the way, FSM actually stands for finite state machine, not final.

    If you just want to write a unit test for your KMP implementation of a string search, your unit test would test the API of the string search.  Which is something like this:

    index = search( searchText, patternText )

    Your code coverage test would test the code coverage of your implementation.  Your implementation would be broken up into functions such that those functions could be unit tested themselves.  You would expose the indices used by the algorithm as well as the contents of the "partial match" table used by KMP.

    On the other hand...

    If you're just asking about how to unit test an FSM, then we can talk about that.  An FSM is just a machine with no external variables.  The "program" of a finite state machine can be run by maintaining its state and the next character in the string of input.  So to test it you could just structure your unit test to test any FSM function.  Such a function is of the form:

    nextState = FSM( currentState, input );

    Most people would test it by just checking the terminal state given a string of input, but you can unit test however you want.  It kind of depends how much of a warm fuzzy feeling you need at the end.  After all, a test result is just that.  It amounts to a fact.  It doesn't prove anything. It certainly doesn't prove your algorithm is correct, nor does it prove your implementation is correct.

    Your unit test can test all possible input for each possible state.  Or it could test a handful of cases that produce 100% coverage, or it could just test a few cases.  It's totally up to you and the resources at your disposal.


    Saturday, July 21, 2012 9:54 PM

All replies

  • You have to write testable code.

    • That may mean writing a function that you can pass some arguments and get a known result.
    • That may mean that you write your code so that you can do this many times with many different test cases without polluting the results of other runs.
    • That may mean that you break your code up into many functions, and test each of those functions in this way.
    • That may mean that you have a set of data and you step forward one "iteration" of your algorithm, then interrogate your large data set again to make sure it reflects the new state.
    • That may mean that you expose inner workings of your algorithm, such as loop counters, or other temporary storage, so that they can be examined and verified.

    Saturday, July 21, 2012 1:21 PM
  • You have to write testable code.

    • That may mean writing a function that you can pass some arguments and get a known result.
    • That may mean that you write your code so that you can do this many times with many different test cases without polluting the results of other runs.
    • That may mean that you break your code up into many functions, and test each of those functions in this way.
    • That may mean that you have a set of data and you step forward one "iteration" of your algorithm, then interrogate your large data set again to make sure it reflects the new state.
    • That may mean that you expose inner workings of your algorithm, such as loop counters, or other temporary storage, so that they can be examined and verified.


    Thanks for the practice information, but what about decomposing algorithms on FSM ( final state machines ) like in the link I have posted earlier? You have written well about practice-side of testing ( mor for development process ), but I want to admit also theoretical side.
    • Edited by magesi Saturday, July 21, 2012 1:32 PM
    Saturday, July 21, 2012 1:31 PM
  • Normally the term that is used to determine if software if fully tested is "Coverage".  We normally try to test software statement we have > 95% coverage. coverage refereing to testing each line of sode in the program.

    There are really two criteria testing software

    1) Test using different inputs to get different output results.

    2) Make sure all the paths in your software are fully tested.  You also want to make sure you can go from each path in the software to evary other path in the software.  There are software simultor available that will automatically give you statistics on you coverage of software during testing.

    A linear program with no multiple paths is simpliest type program to test.  But still with no loops data results can be different like when you subtract two numbers your results can be positive, negative, and zero.  You also have situations when you add two numbers you can get results that have different number of decimal places which can produce formating errors.

    So to fully test software you want to make sure you use a combination of random inputs as well as inputs that will test exteme limits of the software input and output (high and low values).

     


    jdweng

    Saturday, July 21, 2012 2:30 PM
  • It's funny that you say I helped you with the practice-side of testing but you want to know more about the theoretical, because in my mind, I gave you theoretical information.  :/  It was generalized because you question was quite general:  "How could I test my implementation of some algorithm?"  So I hope I'm not too far off track with my reply.  I do sort of feel like I don't understand what kind of information you're after.

    By the way, FSM actually stands for finite state machine, not final.

    If you just want to write a unit test for your KMP implementation of a string search, your unit test would test the API of the string search.  Which is something like this:

    index = search( searchText, patternText )

    Your code coverage test would test the code coverage of your implementation.  Your implementation would be broken up into functions such that those functions could be unit tested themselves.  You would expose the indices used by the algorithm as well as the contents of the "partial match" table used by KMP.

    On the other hand...

    If you're just asking about how to unit test an FSM, then we can talk about that.  An FSM is just a machine with no external variables.  The "program" of a finite state machine can be run by maintaining its state and the next character in the string of input.  So to test it you could just structure your unit test to test any FSM function.  Such a function is of the form:

    nextState = FSM( currentState, input );

    Most people would test it by just checking the terminal state given a string of input, but you can unit test however you want.  It kind of depends how much of a warm fuzzy feeling you need at the end.  After all, a test result is just that.  It amounts to a fact.  It doesn't prove anything. It certainly doesn't prove your algorithm is correct, nor does it prove your implementation is correct.

    Your unit test can test all possible input for each possible state.  Or it could test a handful of cases that produce 100% coverage, or it could just test a few cases.  It's totally up to you and the resources at your disposal.


    Saturday, July 21, 2012 9:54 PM