I heard different interpretations of sound and complete. I understand that completeness means finding a solution if there is one. What does it mean to say an algorithm is sound.
What does it mean to say an algorithm is Sound and Complete?
These are very specific terms as related to logic.
Here are some starting points:
Basically, soundness (of an algorithm) means that the algorithm doesn't yield any results that are untrue. If, for instance, I have a sorting algorithm that sometimes does not return a sorted list, the algorithm is not sound.
Completeness, on the other hand, means that the algorithm addresses all possible inputs and doesn't miss any. So, if my sorting algorithm never returned an unsorted list, but simply refused to work on lists that contained the number 7, it would not be complete.
It is sound and complete if it works on all inputs (semantically valid in the world of the program) and always gets the answer right.
I find Erik Dietrich's answer a tad confusing. The following is better:
An algorithm is sound if, anytime it returns an answer, that answer is true. An algorithm is complete if it guarantees to return a correct answer for any arbitrary input (or, if no answer exists, it guarantees to return failure).
Two important points:
Consider for an example a sorting algorithm A that receives as input a list of numbers. We say that A is sound if every time it returns a result that result is a sorted list. Likewise, we say that A is complete if guarantees to return a sorted list any time we give it a list of numbers.
There are much better answers at the SO. Basically, you provide some data collection and criteria to search. Sound algorithm catches you only the fish that matches the criteria but it may miss some data items. Complete algorithm produces a superset of requested results, which means that you receive some garbage on top of requested results. Sound algorithm is more conservative.
Statistician would probably say that sound algorithm is biased towrads type I errors (it does not accept the correct candidates), whereas complete algorithm is biased towards type II errors (to accept the false candidates).