Algorithm design and problem-solving flashcards

Topic 7: Algorithm design and problem-solving

What are abstraction, decomposition and pattern recognition?

Abstraction: keep only the details that matter. Decomposition: split a problem into smaller sub-problems. Pattern recognition: spot similarities so a solution can be reused or a task put in a loop.

What do the flowchart symbols mean?

Rounded terminator: start or end. Parallelogram: input or output. Rectangle: process. Diamond: decision, with labelled yes/no exits. Arrows show the order.

How do totalling and counting work in an algorithm?

Totalling: set Total ← 0 before the loop, then Total ← Total + Value inside it. Counting: set Count ← 0, then Count ← Count + 1 each time the condition is met.

How does a linear search work?

Check each item in turn from the start until the target is found or the end of the list is reached. It works on unsorted data but can be slow, as every item may need checking.

How does a bubble sort work?

Compare adjacent items and swap them if they are in the wrong order, working through the list. After each pass the largest unsorted item is in place. Stop when a pass makes no swaps.

Why does a swap in a bubble sort need a temporary variable?

To hold one value while the other is copied over it. Without Temp, one of the two values would be overwritten and lost.

Validation vs verification

Validation: an automatic check that data is reasonable and allowed (range, length, type, presence, format, check digit); it cannot prove data is correct. Verification: checks data was entered or copied accurately (double entry, visual check).

Normal, boundary and abnormal test data for whole numbers 1 to 10

Normal: e.g. 5 (accepted). Boundary: 1 and 10 (accepted) and 0 and 11, the first values outside the range (rejected). Abnormal (erroneous): e.g. "ten" (rejected).

What is a trace table used for?

Recording the value of each variable, and any output, step by step as an algorithm runs, to work out what it does or find a logic error.