Algorithm Design and Problem Solving: notes

An algorithm is a set of clear steps that solves a problem. It must finish and give the right answer.

Tools

• Flowcharts use shapes: oval for start and stop, parallelogram for input and output, rectangle for a process, diamond for a decision.
• Pseudocode is structured English, close to a program but not tied to one language. Example: INPUT mark, then IF mark >= 50 THEN OUTPUT "Pass".

The three constructs

• Sequence: steps run one after another.
• Selection: a choice: IF...THEN...ELSE, or CASE.
• Iteration (loops): repeat steps. FOR (a fixed number of times), WHILE (test at the start, may run zero times), REPEAT...UNTIL (test at the end, runs at least once).

Dry runs and trace tables

A dry run works through an algorithm by hand. A trace table has one column per variable and one row per step, so you can see each value change and spot errors.

Testing data

• Normal: sensible values that should be accepted.
• Extreme (boundary): values at the edge of the range, such as 0 and 100 for a percentage.
• Erroneous: values that should be rejected, such as -5 or "abc".

Searching

• Linear search: check each item in turn from the start. Works on any list but is slow for long ones.
• Binary search: the list must be sorted. Check the middle item, then throw away the half that cannot hold the target. Much faster on large lists.

Sorting

• Bubble sort: compare neighbours and swap if in the wrong order; repeat passes until no swaps happen.
• Insertion sort: take each item and insert it into the correct place in the sorted part.