1 - Algorithms, Proofs, Debugging, and Big-O Notation Flashcards
(41 cards)
What is an abstraction? Explain how a function is a form of abstraction.
From the POV of the person calling the function, they only need to know the name of the action specified.
For example, for a function, you do not need to know the internal details.
What is an algorithm?
A description of how a specific problem can be solved, written at a level of detail that can be followed by the reader. (e.g. Newton’s method of a series of guesses to find the square root of a number).
What is the relationship between an algorithm and a function?
A function is a set of instructions written in a particular programming language. Although the function embodies the algorithm, the details of the algorithm are the same no matter the language used.
Give an example of an input condition that cannot be specified using only a type.
Types are function type signatures. For example, a minimum function written in integers will make sure that only integers are inputted.
However, a range restriction is not a type. For example, the square root program only works for positive numbers. Therefore, programs must check the range of the input at run-time.
What are two different techniques used to specify the input conditions for an algorithm?
- Argument types (will make sure that the arguments passed are of the correct type)
- Run-time checking (e.g. range restriction)
What are some ways used to describe the outcome, or result, of executing an algorithm?
- The result type
2. Documentation (comments)
In what way does the precision of instructions needed to convey an algorithm to another human being differ from that needed to convey an algorithm to a computer?
To explain algorithms in pseudo-code, we need only to emphasize the important properties of the algorithm, and downplay incidental details that do nothing to assist in the understanding of the procedure.
In considering the execution time of algorithms, what are two general types of questions one can ask?
First, will the algorithm terminate for all legal input values?
Second, is there a more accurate characterization of the amount of time it will execute?
What are some situations in which termination of an algorithm would not be immediately obvious?
For example, in Euclid’s GCD algorithm, there is no definite limit on iterations, but either n or m becomes smaller on each iteration. That means m+n satisfies the three conditions!
while (m !=n)
{ if (n > m)
n = n - m;
else m = m - n;
}
return n;
What are the three properties a value must possess in order to be used to prove termination of an algorithm?
- The property or value can be placed into a correspondence with integer values
- The property is nonnegative
- The property or value decreases steadily as the algorithm executes.
What is a recursive algorithm? What are the two sections of a recursive algorithm?
A recursive algorithm calls a version of itself.
There must be a base case, which does not have a recursive call, and the recursive/inductive case, which does have this recursive call.
What does it mean to say you are debugging a function?
Systematic testing of the program to uncover errors.
What are some useful hints to help you debug a function or program?
- Test small sections at a time
- Once found, find the simplest input that produces the same error
- Simulate execution of the test input
- Use print statements to view the state of the computation in the middle
- Don’t assume that handling one thing right means it’s always right.
What is an assertion?
A comment that explains what you know to be true when execution reaches a specific point in the program.
For example, if you have a series of if statements, then you could say that if it goes down one branch, that /* we know a == b / and else / we know a != b */.
What is an invariant?
An assertion inside a loop, since it must describe a condition that does not vary during the course of executing the loop.
For example, assertion 2 is an invariant, because before the assignment, s is only the partial sum of whatever loops executed before:
double s = 0.0; /* 1. s is the sum of an empty array */ for (int i = 0; i
Once you have identified assertions and invariants, how do you create a proof of correctness?
A proof of correctness is an informal argument that explains why you believe the code is correct.
You can use a series of small arguments that moves from one invariant to the next, and know how the value of the variables change as the execution progresses.
How is an assertion different from an assertion statement?
An assertion is written as comments and is not executed by the program.
An assertion statement takes an expression as an argument and will halt execution and print an error message if the statement is not true. For example, to verify the input range in the square root function, you could say:
double sqrt (double val)
{ assert (val >=0); /* halt execution if value is not legal */...}
What is unit testing?
When you test individual functions before you have a working application. To perform this test, you need a main method that will be different from that eventually used for your program.
What is a test harness?
A special main method used in testing. It will feed one or more values in the function under test, and check the result.
For example, this is a test harness for a summation program:
int main() {
double dataSetOne[] = {1.0, 2.0, 3.0, 4.0, 5.0};
double sum = sum(dataSetOne, 5);
println("result 1 should be 15, is: %g ", sm);
return 0;
}
What is boundary testing?
If there are limits to the data, exercise values that are just at the edge of the limits. For example, if the program uses conditional statements, then use some data values that evaluate true and others that evaluate false.
What is a test suite?
A collection of test cases.
What is integration testing?
Once your individual functions are working correctly, you should combine calls on functions into more complex programs.
What is regression testing and why is it performed?
Once you’ve fixed the errors from the integration testing, go back and re-execute the earlier test harness to ensure the changes have not inadvertently introduced any new errors.
What is black box testing?
Testing that considers only the structure of the input and output value, and ignores the algorithm used to produce the result.
