A. Programming Concepts and Skills · Algorithm Design and Analysis

Algorithm Design and Analysis: Unit Review

A3.2 A3.3 A3.4 A3.5 A3.6 A4.2 C2.1 C2.2 C2.3 C2.4About 40 minutes

Learning goals

I can design, trace and analyse searching, sorting, 2-D array and recursive algorithms.
I can compare algorithms using run times and Big-O, and state their preconditions and postconditions.
I can test algorithms with a formal test plan.

Words to know

precondition / postcondition
What must be true before an algorithm runs / what it guarantees when it finishes.

Big-O
The growth rate of an algorithm's work as n grows, keeping only the fastest-growing term.

base case
The input a recursive function answers directly, which stops the recursion.

regression testing
Rerunning all tests after every change.

Let's review!

In this unit you learned to specify algorithms with preconditions, postconditions and loop invariants, and to measure them with run times, step counts and Big-O. You wrote linear and binary search and compared them, built subprograms to insert and delete array elements, wrote insertion sort and compared the sorts, processed 2-D arrays (including matrices and image pixels), designed recursive algorithms (factorial, fast power, numbers to words, fractals, XML, merge sort) and learned their pitfalls, and finished with formal test plans.

This review has a few questions from every lesson. Try each one on paper or in Python first, then press Show answer. Where a question shows code, type it in to check your prediction.

The unit at a glance. The numbers are the lessons, in order; the review sections below follow the same order.

How to use this review

Do two or three sections at a time. For tracing questions, write a trace table (variables in columns, one row per pass or call) instead of working in your head. For Big-O questions, ask "what happens when n doubles?" For each question you miss, write down why (off-by-one? wrong case? forgot the precondition?) and go back to the lesson named in the section title. Finish with the 10-question quiz.

Specifying Algorithms: Preconditions, Postconditions and Loop Invariants

State a precondition and a postcondition for def first_char(s): return s[0].

Give a loop invariant for a loop that finds the smallest element of a, starting with best = a[0] and running i from 1.

When should you use raise ValueError instead of assert?

Measuring Efficiency: Run Times, Counting Steps and Big-O

Give the Big-O: (a) 6n + 40 (b) n² ÷ 2 + 5n (c) 3 log₂ n + 8

An O(n²) program takes 5 s for n = 20 000. Estimate the time for n = 60 000.

How many times does the body run? for i in range(n): for j in range(i + 1, n): with n = 9.

Linear Search in Depth: Records, Variations and Analysis

Average comparisons for a successful linear search of 49 elements?

How many comparisons does an unsuccessful linear search make on n elements?

Write the loop header to search a list from the last index down to index 0.

Binary Search: Halving the Problem

Trace binary search for 31 in [3, 8, 12, 19, 23, 31, 38]: give low, high, mid each pass.

Why must the loop be while low <= high and not <?

What does bisect.bisect_left([2, 5, 5, 9], 5) return?

Linear versus Binary Search: Run Times and Complexity

Worst-case comparisons for n = 4000: linear and binary?

An unsorted list of a million items will be searched 3 times. Sort first?

Times of 1 ms, 1.3 ms, 1.7 ms for n = 10⁴, 10⁵, 10⁶ suggest which growth?

Subprograms to Insert and Delete Array Elements

An array has size 12. How many moves to insert at index 4? To delete at index 4?

Why must insertion shift from right to left?

Which is O(1): a.pop(), a.pop(0), a.insert(0, x)?

Insertion Sort

Show the list after each pass of insertion sort on [6, 2, 5, 1].

How many shifts does insertion sort make on [3, 2, 1]?

Why is insertion sort stable?

Comparing Sorting Algorithms: Counting and Timing

Which simple sort makes the same number of comparisons on every input of size n?

Which sort would you choose for a nearly sorted list, and why?

Why must each sort in an experiment get a copy of the same data?

Two-Dimensional Arrays: Rows, Columns and Traversals

For g = [[2, 7], [9, 4], [6, 1]], give len(g), len(g[0]) and g[2][0].

Write code to create a 3 × 4 grid of zeros correctly.

Transpose [[1, 2, 3], [4, 5, 6]].

2-D Array Algorithms: Matrix Multiplication and Image Pixels

Compute [[1, 0], [2, 3]] × [[4, 5], [6, 7]].

How many multiplications to multiply two 50 × 50 matrices with the triple loop?

Invert the pixel row [0, 100, 255].

Thinking Recursively: Base Cases and the Call Stack

Write a recursive count_down(n) that prints n, n − 1, …, 1.

How many calls does fast_power(x, 20) make? (n = 20, 10, 5, 2, 1, 0)

Predict the output of def f(n): return 1 if n == 1 else n + f(n - 1) for f(4).

Recursive Algorithms: Numbers to Words, Fractals and XML

What does words(3_050) return?

How many lines does ruler(6) print?

Why do recursive functions suit XML?

Recursion Pitfalls: Infinite Recursion and Exponential Growth

Why does def g(n): return 0 if n == 10 else g(n + 3) fail for g(0)?

How many calls does naive fib(8) make?

Name two ways to make Fibonacci O(n).

Merge Sort: Divide and Conquer

Merge [1, 4, 9] and [2, 3, 10]. How many comparisons?

Why is merge sort O(n log n)?

What extra cost does merge sort have that insertion sort does not?

Formal Test Plans for Algorithms: Unit, Integration and Regression Testing

List five test targets for binary search on a sorted list of 10 numbers.

What is the difference between unit and integration testing?

A bug is reported. What should you write first?

Just for fun

Review riddle: what is the time complexity of finishing this unit review?

O(1) per question, O(n) for the whole review, and O(coffee) for the person helping you.

Check your understanding

Quiz

Which pair is a precondition and a postcondition for binary search?

Which Big-O is the worst case of binary search?

Insertion sort on an already sorted list of n elements makes how many comparisons?

How many moves does deleting index 0 from an array of size n take, keeping the order?

After g = [[0] * 3 for r in range(2)] and g[1][2] = 5, what is g?

A is 2 × 4 and B is 4 × 3. What size is A × B?

What does factorial(0) return in the lesson's function, and why does it matter?

Why is naive recursive Fibonacci exponential?

What is the worst-case Big-O of merge sort?

10.

What is regression testing?

For parents and teachers

How to use the results: Use the section where your teen struggled to choose a lesson to revisit.

Contracts, invariants, "what must be true": revisit Specifying Algorithms: Preconditions, Postconditions and Loop Invariants.
Big-O, step counts, timing estimates ("what if n doubles?"): Measuring Efficiency: Run Times, Counting Steps and Big-O.
Search traces and off-by-one errors in low/high/mid: Binary Search: Halving the Problem; for averages and record searches, Linear Search in Depth; for choosing between them, Linear versus Binary Search.
Shifting in the wrong direction or wrong move counts: Subprograms to Insert and Delete Array Elements.
Sort traces, inversions and stability: Insertion Sort; for choosing a sort and timing experiments, Comparing Sorting Algorithms; for O(n log n) and merging, Merge Sort: Divide and Conquer.
Row/column mix-ups, aliasing, transposes: Two-Dimensional Arrays; matrix products and pixel algorithms: 2-D Array Algorithms: Matrix Multiplication and Image Pixels.
Base cases and tracing calls: Thinking Recursively; for numbers to words, fractals and XML, Recursive Algorithms; for infinite recursion and exponential growth, Recursion Pitfalls.
Choosing test cases and using unittest: Formal Test Plans for Algorithms.

A good final check: ask your teen to explain, without notes, why binary search needs sorted data, why merge sort beats insertion sort for large lists, and what a base case is. Those three ideas carry straight into first-year university computer science.