IB Computer Science Topic B2.3.1: Constructing Programs That Implement the Correct Sequence of Code Instructions Notes

Instruction Order: Sequence Decides Whether a Program Works

1. Statements execute in the order they are written, one after another, unless a selection or looping construct redirects the flow.
2. Put two correct statements in the wrong order and the program often still runs, but it produces the wrong answer.
3. Sequence is one of the three control constructs, alongside selection and iteration.

Dependencies: What Has to Happen First

1. Before writing a line, ask what that line depends on.
2. Three dependencies cause most sequencing bugs:
   1. A variable must be declared and initialised before anything reads it.
   2. A running total must be reset to zero before the loop that adds to it, never after.
   3. A file must be opened before it is read and closed after the last read.

Three Errors That Correct Sequencing Prevents

1. Incorrect output: every line is valid, but they run in an order that computes the wrong value.
2. Infinite loop: the statement that would end the loop never runs, so the program never stops.
3. Deadlock: two tasks each wait for a resource the other is holding, so neither can continue.

Incorrect Output: The Bug That Compiles Cleanly

1. A logic error breaks no syntax rule, so no compiler or interpreter will warn you about it.
2. The usual cause is reading a value before the line that updates it has run.
3. You find it by checking the output against a value you worked out by hand, not by rereading the code.

Infinite Loops: When the Exit Condition Never Arrives

1. Cause: the loop condition stays true because the variable it tests is never changed inside the loop.
2. Sequencing version of the same bug: the update statement exists but sits after the loop instead of inside it.
3. Fix: check that every path through the loop body moves the tested variable toward the exit condition.

Deadlock: Two Tasks Each Waiting on the Other

1. Deadlock happens when two tasks each hold a resource the other needs and neither will release what it has.
2. In a booking system, two payment routines might each need the customer record and the seat record:
   1. Routine A locks the customer record, then asks for the seat record.
   2. Routine B locks the seat record, then asks for the customer record.
   3. Each now waits on a lock the other holds, and the booking never completes.
3. The fix is a sequencing rule: every routine claims the resources in the same agreed order, so one routine always gets both.
4. Releasing each resource as soon as the task is finished with it shortens the window in which a deadlock can form.

Planning the Sequence Before You Write Code

1. Draw the order as a flowchart or write it as pseudocode, so the dependencies are visible before any syntax gets in the way.
2. Run a trace table over the first few iterations and compare each variable against the value you expect at that point.
3. Split the program into functions, so each one has a short, checkable sequence of its own.
4. Test with normal, boundary and invalid input, because an ordering bug often shows up only on the first or last item.

Sequencing in the Exam: Name the Order, Then the Consequence

1. A question that asks you to correct an algorithm usually hides one moved line, so read for order before you read for syntax.
2. State which statement has to move and what the program produces until it does, because the second half is where the second mark sits.