06 — Algorithms and Correctness Free Online FlashCards

What is an algorithm?

An algorithm is a precise, finite sequence of steps for solving a problem or computing a result.

How do a specification and implementation differ?

A specification states what an algorithm must achieve; an implementation explains how to achieve it.

What are linear search’s key properties?

Linear search examines elements from left to right and takes O(n) time in the worst case. It does not require sorted data.

What condition and complexity characterize binary search?

Binary search requires sorted data, repeatedly halves the remaining range, and runs in O(log n) time.

How does insertion sort build a sorted list?

Insertion sort builds a sorted prefix by taking each next unsorted element and inserting it into its proper position.

When is insertion sort especially useful?

Insertion sort uses O(1) extra space and has O(n²) worst-case time. It is often effective for small or nearly sorted lists.

What is merge sort’s divide-and-conquer process?

Merge sort divides the list, recursively sorts both parts, and merges the sorted parts. It runs in O(n log n) time and usually uses O(n) extra space.

What is a loop invariant?

A loop invariant is a statement that remains true at a particular point during every loop iteration.

What are the three parts of a loop-invariant proof?

The three parts are initialization, maintenance, and termination: establish the invariant, preserve it, then use it with the stopping condition to prove the postcondition.

What makes a recursive algorithm correct?

A recursive algorithm needs a base case, a recursive case that reduces the problem, progress toward the base case, and a way to combine results.

What is the recursive definition of factorial?

The factorial base case is 0! = 1; for n > 0, n! = n × (n−1)! .

What is a termination variant?

A termination variant is a nonnegative quantity that strictly decreases on every iteration or recursive call.