Data Structures, Testing and Debugging: Quick Revision

A brief note on Data Structures, Testing and Debugging. Read it before a test. Try each question at the end before you open its answer.

Data structures

• Stack or queue? Ask which item must come out next: the newest (a stack) or the oldest (a queue). stack[-1] looks at the top without removing it.
• Balanced brackets: push each opening bracket, match each closing one with the top, and the stack must be empty at the end.
• Linked list: each node holds a value and a link to the next; the last link is None. Walk it with current = current.next while current is not None. Save the next node before you change a link.
• Binary search tree: insert and search follow one path down, smaller to the left and bigger to the right. The in-order walk (left, node, right) gives the values sorted. Sorted input makes a chain, as slow as a list.
• Graph search: BFS uses a queue and finds the route with the fewest steps. DFS goes deep first and finds everything that can be reached. Both must remember the places already seen, or a loop runs for ever.

Testing

• A test compares the answer of the code with an answer worked out from the rules, never from the code.
• assert condition, "message" is silent when the condition is true, and stops with an AssertionError when it is false.
• A table of tests and a loop show every failure at once.
• Edge cases first: nothing, one, two, repeats, all equal, both sides of each limit, and strange values.
• In unittest, a class inherits from unittest.TestCase, and each method whose name starts with test is a test. setUp runs before each one.
• assertEqual, assertAlmostEqual for decimals, and assertRaises with with. In the report, . is a pass, F a failure and E an error.
• Random tests with a fixed seed, compared with a trusted answer, find bugs nobody thought of, and can be repeated.

Debugging

1. Reproduce the bug with a small input.
2. Locate it: read the traceback from the bottom, print values, or check each stage.
3. Explain the cause in one sentence before you change anything.
4. Fix one thing, then test again, and keep the test.

The usual causes: off by one, a wrong condition at an edge, a variable that is not what you think, and a list changed by accident.

A worked example

Six towns are joined by roads. BFS finds the route from Amberly to Fern with the fewest roads.

1. The queue takes the oldest town first, so every town one road away is visited before any town two roads away.
2. came_from marks each town as seen and records where it was reached from. When Cedar is taken, Dune is already in it, so Dune is not added again.
3. Walking back from Fern gives Fern, Dune, Brook, Amberly. Reversed, the route is ['Amberly', 'Brook', 'Dune', 'Fern']: 3 roads.

Practice with new numbers

A program to try

median should give the middle plant height. A table of tests, with answers worked out from the rule, shows that it has a bug.

Mistakes to avoid

• Popping from an empty stack or queue. [].pop() stops with IndexError: pop from empty list, and an empty deque gives IndexError: pop from an empty deque. Check first.
• list.pop(0) for a long queue. It is slow. Use deque and popleft.
• A town missing from the dictionary. roads["Fern"] stops with KeyError: 'Fern'. Every node needs an entry, even with an empty list.
• A search that does not remember what it has seen. In a graph with a loop, it goes round for ever.
• assertEqual for decimals. 0.1 + 0.2 is not exactly 0.3. Use assertAlmostEqual.
• Changing the tests to match the code. The tests come from the rules; the code changes to meet them.

Check yourself

1. A web browser keeps the pages that you visit, so that the Back button returns to the last one. Should it keep them in a stack or a queue?

2. A linked list holds 4, 9 and 2. To put a new node after the head, a student writes head.next = new and then new.next = head.next. What happens to 9 and 2?

3. Why does a binary search tree built from values that are already in order lose its speed?

4. A unittest report starts with the line .F.E. How many tests ran, and what happened to each?

5. A function gives 10 percent off on a bill of 1000 rupees or more. Which bills would you test first, and why?