1 - Algorithms, Proofs, Debugging, and Big-O Notation

Question 1

What is an abstraction? Explain how a function is a form of abstraction.

Answer 1

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.

Question 2

What is an algorithm?

Answer 2

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).

Question 3

What is the relationship between an algorithm and a function?

Answer 3

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.

Question 4

Give an example of an input condition that cannot be specified using only a type.

Answer 4

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.

Question 5

What are two different techniques used to specify the input conditions for an algorithm?

Answer 5

1. Argument types (will make sure that the arguments passed are of the correct type)
2. Run-time checking (e.g. range restriction)

Question 6

What are some ways used to describe the outcome, or result, of executing an algorithm?

Answer 6

1. The result type

2. Documentation (comments)

Question 7

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?

Answer 7

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.

Question 8

In considering the execution time of algorithms, what are two general types of questions one can ask?

Answer 8

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?

Question 9

What are some situations in which termination of an algorithm would not be immediately obvious?

Answer 9

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;

Question 10

What are the three properties a value must possess in order to be used to prove termination of an algorithm?

Answer 10

1. The property or value can be placed into a correspondence with integer values
2. The property is nonnegative
3. The property or value decreases steadily as the algorithm executes.

Question 11

What is a recursive algorithm? What are the two sections of a recursive algorithm?

Answer 11

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.

Question 12

What does it mean to say you are debugging a function?

Answer 12

Systematic testing of the program to uncover errors.

Question 13

What are some useful hints to help you debug a function or program?

Answer 13

1. Test small sections at a time
2. Once found, find the simplest input that produces the same error
3. Simulate execution of the test input
4. Use print statements to view the state of the computation in the middle
5. Don’t assume that handling one thing right means it’s always right.

Question 14

What is an assertion?

Answer 14

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 */.

Question 15

What is an invariant?

Answer 15

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

Question 16

Once you have identified assertions and invariants, how do you create a proof of correctness?

Answer 16

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.

Question 17

How is an assertion different from an assertion statement?

Answer 17

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 */...}

Question 18

What is unit testing?

Answer 18

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.

Question 19

What is a test harness?

Answer 19

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;
}

Question 20

What is boundary testing?

Answer 20

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.

Question 21

What is a test suite?

Answer 21

A collection of test cases.

Question 22

What is integration testing?

Answer 22

Once your individual functions are working correctly, you should combine calls on functions into more complex programs.

Question 23

What is regression testing and why is it performed?

Answer 23

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.

Question 24

What is black box testing?

Answer 24

Testing that considers only the structure of the input and output value, and ignores the algorithm used to produce the result.

Question 25

What is white box testing?

Answer 25

Testing that also considers the structure of the function (that every statement is executed and that every condition is evaluated both true and false).

Question 26

Give an informal description in English (not code) explaining how the bubble sort algorithm operates.

Answer 26

The bubble sort algorithm goes through each consecutive element in an array and swaps it with the one above it if it is larger. Once the bubble sort has traversed the array, it has completed a “pass” and the largest element in the array is at the end. Then, it continues to do “passes” through the array minus the last element, which will have been the largest of that subset.

Question 27

Give a similar description of the selection sorting algorithm.

Answer 27

The selection sort algorithm swaps the smallest element with the first element in the array. Then, it traverses the rest of the array for the second smallest element to put in the second position, etc.

Question 28

Suppose an algorithm is O(n), where n is the input size. If the size of the input is doubled, how will the execution time change?

Answer 28

It would double because it would take 2*n, or twice as long.

Question 29

Suppose an algorithm is O(log n), where n is the input size. If the size of the input is doubled, how will the execution time change?

Answer 29

It’s only one more comparison! If you originally do log n comparisons, then when you do log (2n) steps, that’s log 2 + log n, which is log n + 1.

Question 30

Suppose an algorithm is O(n^2), where n is the input size. If the size of the input is doubled, how will the execution time change?

Answer 30

(2n)^2 = 4*n^2, so it should take four times as long to execute.

Question 31

What does it mean to say that one function dominates another when discussing algorithmic execution times?

Answer 31

Essentially, when you look at a function as n approaches infinity, the function will act more like the one with the largest power.

Question 32

Explain in your own words why any sorting algorithm that only exchanges values with a neighbor must be in the worst case O(n^2).

Answer 32

In the worst case, the first value must travel all the way to the very end, which requires n steps. The next case will travel n-1 steps, and so on. When added up, this is approximately n^2 steps.

Question 33

Explain how the shell sort algorithm gets around the limitation of sorting algorithms that only exchange values with a neighbor.

Answer 33

Rather than moving elements one by one, the outer loop can perform an insertion sort every gap steps, allowing elements to move much farther, with O(n) complexity, even with 3 nested loops!

Question 34

How does the merge sort algorithm work?

Answer 34

It breaks an array into two smaller arrays, and then sorts the smaller arrays by calling itself on those arrays, then figuring out whether an element is bigger than the halfway point or smaller.

Because it compares n elements using log n recursive calls, it has O(n log n) complexity.

Question 35

What is the biggest advantage of merge sort over selection sort or insertion sort? What is the biggest disadvantage of merge sort?

Answer 35

Merge sort is significantly faster than selection sort and insertion sort.

However, unfortunately, merge sort uses extra memory!

Question 36

Explain the process of forming a partition.

Answer 36

First, the pivot is swapped to the start of the array. You have three sections: the left is lower than the pivot, the right is higher or equal to the pivot, and the middle is unknown.

The lowest of the middle region (i) is compared with the highest (j) and swapped if neither is true. If j is true, then the j position is decremented, and if i is true, then the i position is decremented.

Question 37

Explain how the quick sort algorithm works.

Answer 37

Quick sort picks a pivot, then arranges every element above or before it. Then, it picks a new partition within each sub-array, and sorts according to that pivot.

Question 38

Why is the pivot swapped to the start of the array in quick sort? Why not just leave it where it is? Give an example where this would lead to trouble.

Answer 38

It is swapped out of the way of the partition step. Otherwise, you could end up comparing the pivot against itself.

Question 39

In what ways is quick sort similar to merge sort? In what ways are they different?

Answer 39

Both quick sort and merge sort are recursive functions that sort quickly. Their main difference is that merge sort takes an extra step to merge the arrays together, but quick sort can be incredibly inefficient with imbalanced sub-arrays, leading to a much worse Big-0 time complexity of 0(n^2) as opposed to merge sort’s O(n log n).

Question 40

Suppose you selected the first element in the section being sorted as the pivot. What advantage would this have? What input would make this a very bad idea? What would be the big-O complexity in this case?

Answer 40

The advantage is that this avoids the initial swap, but it leads to O(n^2) performance in the common case where the input is already sorted.

Question 41

What does the quick sort algorithm do if all elements in an array are equal? What is the big-Oh execution time in this case?

Answer 41

If all the elements in the array are equal, then no swaps will take place because the elements on the unknown range will be in their proper position in the pivot.