B2.3 Programming constructs

Sequence, selection and iteration

A program is a list of instructions, but the processor does not always run them in the order they are written. The order in which statements execute is called the flow of control. A result from 1966 known as the structured program theorem shows that sequence, selection and iteration together are enough to express any algorithm, which is why every mainstream language provides all three.

Sequence is the default. Unless a selection or a loop changes the flow, the statement on line 5 runs after line 4 and before line 6, and every value it uses must already have been set by an earlier line.

Selection lets a program respond to its data: a ticket machine charges a child less than an adult, a thermostat switches the heating on only when the room is cold. Each run of the program follows one path through the selection and skips the others.

The three structures map directly onto flowchart symbols. Sequence is a column of process and input/output boxes joined by flowlines; selection is a decision symbol with two labelled exits; iteration is a decision whose flowline loops back to an earlier point.

All three structures depend on conditions. A condition is a Boolean expression: it evaluates to exactly one of two values, true or false.

Conditions are built from relational operators, which compare two values (<, <=, >, >=, ==, !=), and Boolean operators, which combine or invert conditions. The relational operators are written the same way in both course languages, but the Boolean operators are not.

Sequence: the order of instructions

In a sequence, each statement works on the state that the earlier statements left behind. Moving a statement up or down therefore changes which values it sees, and so changes the result, even though every individual line is still correct.

Input, process, output

The simplest correct order is input → process → output: a value must be obtained before it is used, and a result must be calculated before it is displayed. The program marks follows that order, matching the sequence flowchart in the figure of the three control structures.

The program prints the total and the average rounded to one decimal place.

The Java version divides by 3.0, not 3. Dividing two int values in Java performs integer division, so 220 / 3 would give 73; Python's / always gives a floating-point result. Placing average = total / 3 before the line that calculates total would fail completely: Python stops with a NameError because total does not exist yet, and the Java compiler refuses to compile a variable used before it is declared.

How reordering changes the result

Some ordering faults produce no error message at all, which makes them harder to find. These are logic errors: the program runs and prints something, but the output is wrong. Three patterns cause most of them.

1. Overwriting a value before it has been used. Swapping two variables with a = b then b = a loses the original value of a, because the first assignment overwrites it.

2. Initialising in the wrong place. A running total set to 0 inside a loop is reset on every pass, so only the last value survives.

3. Outputting before processing. Printing a result before the line that updates it shows the old value.

The program swap shows the first pattern. Both halves contain the same three kinds of statement; only their order and the extra variable temp differ.

A trace table of the correct swap records each variable after every line. The value 5 survives in temp while a is overwritten, so it can be copied into b at the end.

The wrong version prints 9 9. Python also allows a, b = b, a, which evaluates both values on the right before assigning either, so no temporary variable is needed; Java has no equivalent and always uses temp.

The program tax should add 20% tax to a price of 40 and print the total, but it prints 40 instead of 48.

Selection

Selection lets a program choose between blocks of code. In both course languages the chosen block is marked out clearly: Java wraps it in braces { }, and Python indents it under a line ending in a colon. Four shapes of selection appear in almost every program: single, two-way, multi-way and nested.

Single and two-way selection

A single selection (if on its own) runs a block when the condition is true and does nothing otherwise. A two-way selection (if … else) always runs exactly one of two blocks. The program temperature check uses both: the fever warning appears only for high readings, while the second statement always prints one of two messages.

For a reading of 38.4 the program prints two lines, Fever: see the school nurse and Outside the normal range. The second condition is a range check built from two relational comparisons joined by AND; Python also accepts the chained form 35.0 <= temperature <= 37.5, which Java does not.

Java needs brackets round every condition, and its blocks are only safe with braces. Without braces, a Java if controls just the one statement that follows it, whatever the indentation suggests. Python has no such trap, because its indentation is the block structure.

Multi-way selection with else-if

When there are more than two possible outcomes, a chain of conditions picks one of them. Python writes each extra test as elif; Java writes else if.

The function grade converts a mark out of 100 into a grade using a set of hypothetical school grade boundaries. Each test only runs if every test before it was false, so mark >= 68 effectively means "68 or more, and below 80".

The test values were chosen as boundary data: 80 sits exactly on a boundary and 79 just below it, so they show whether >= or > was used correctly.

The flowchart of the grade chain shows why the order of the tests matters: the flow leaves the chain at the first "Yes" and never reaches the later decisions.

If the same four tests are written from the lowest boundary upwards (mark >= 42 first), a mark of 91 makes the first condition true and is given grade 4: every mark of 42 or more gets a 4. The rule for ordering is to test the most restrictive condition first, or to write each condition as a full range (mark >= 68 and mark < 80) so that order no longer matters.

Nested selection

A selection inside another selection's block is nested. The inner test only runs when the outer test has led into its block, so nesting expresses decisions that depend on earlier decisions.

The function ticket_price charges a fixed child price, and only for older visitors does it go on to ask whether they are members.

The calls print 4.0, 6.5 and 9.0. The same logic can be written without nesting as a three-way else-if chain (if age < 12:, then elif is_member:, then else:), because the elif is only reached when the age test has already failed; the flat chain is often easier to read. Deep nesting, three or more levels, is a sign that the logic should be simplified or split into a separate function.

Case study: Apple's "goto fail" bug

CVE-2014-1266, fixed by Apple in February 2014, was a flaw in SecureTransport, the library that Safari and many other Apple apps used to check that an HTTPS server really owned the certificate it presented. Apple's security note described it in a single sentence, and programmers outside the company traced the cause in the published source code. In a C function called SSLVerifySignedServerKeyExchange, a line had been duplicated.

Source: Apple's published source code, as quoted by Adam Langley, "Apple's SSL/TLS bug", ImperialViolet, 22 February 2014.

C, like Java, attaches only the first statement after an unbraced if to the condition. The first goto fail; was conditional; the second, despite its indentation, ran every time. It jumped to the end of the function with err still holding the "success" value from the previous step, so the final hash check and the signature check after it were never reached. Any server could send a valid certificate chain and sign the key exchange with the wrong private key, or not sign it at all, and the connection was still accepted. The flaw affected iOS before version 7.0.6 and OS X before 10.9.2.

The bug is a lesson in both sequence and selection. In sequence terms, an extra line inserted between two steps made every later step unreachable. In selection terms, the visible layout of the code (indentation) and its real structure (one statement per unbraced if) disagreed. The same trap exists in Java: the program Dangling sets cancelled to true even though there is enough money, because the second indented line is outside the if.

Both versions report the order as cancelled after the first if and not cancelled after the second. Three habits prevent this class of error. Always using braces in Java, even round a single statement, makes every block explicit. Automatic code formatters re-indent code to match its real structure, so a misleading indent becomes visible. Compilers can also warn about unreachable code: the Clang compiler, with every warning switched on (-Weverything), reports statements that can never run, which would have pointed straight at the skipped hash check.

Iteration: counted and conditional loops

A loop repeats a block, called the body, and each repetition is one iteration or pass. The choice of loop depends on two facts about the task: whether the number of repetitions is known before the loop starts, and whether the body must run at least once.

Counted loops

When the number of repetitions is known in advance (10 students, every element of a list, the numbers 1 to n), a counted loop is the right choice.

Python's for i in range(start, stop, step) gives i the values from start up to, but not including, stop. Java's for (int i = start; i < stop; i += step) packs the same three parts (initialise, test, update) into the loop header.

A counted loop over a collection can skip the index altogether: Python's for score in scores: and Java's enhanced for (int score : scores) give each element in turn. That form is shorter and avoids index mistakes, but it gives no position and cannot change the elements of a Java array.

Loops are often used to build up a result. Two kinds of variable appear in nearly every loop that processes data.

The program sum to n adds the numbers 1 to 5, printing the loop variable and the accumulator on each pass.

The trace table records the state at the end of each pass. The final total, 15, matches the formula $\frac{n(n+1)}{2} = \frac{5 \times 6}{2} = 15$, a useful check.

A counter is a special accumulator that always adds 1. Both must be initialised before the loop: a total set to 0 inside the body is reset on every pass. For the scores 12, 7, 9 and 15, a total reset inside the loop ends as 15 (only the last score) instead of 43.

Conditional loops

When the number of repetitions depends on what happens while the program runs (a user keeps entering data, a search continues until it finds a match), the loop must test a condition instead of counting.

Both languages provide a while loop. Its condition is tested before each pass, which makes it a pre-condition loop.

Java also has a do … while loop, whose condition comes after the body.

The flowcharts of the two loop types place the decision at different points. In the pre-condition loop the input appears twice: once before the loop (so the first test has a value to check) and once at the end of the body. In the post-condition loop the input appears once, inside the body.

The rating program asks for a value from 1 to 5 and keeps asking until it gets one. Python has no do … while, so the post-condition form is written as while True: with a break once the value is valid.

With the inputs 0, 9 and 4, each version rejects the first two and accepts 4. The pre-condition version prints Out of range twice; the post-condition version simply asks again. The do … while condition describes when to repeat (the value is invalid), which is the opposite of the condition in the Python if that leaves the loop (the value is valid): one is the NOT of the other, rewritten with De Morgan's laws.

Sentinel values

A common way to end a conditional loop that reads data is to agree on a special value that cannot be real data. When the program reads that value, it stops.

The program average with sentinel reads marks until −1 and prints their average. It reads the first mark before the loop and the next mark as the last line of the body, so the sentinel is tested before it can be added to the total. It also guards against dividing by zero when the first input is the sentinel.

Conditions that govern loops

A loop condition can combine several tests with Boolean operators, so the loop stops for whichever reason comes first. The program find negative searches a list of sensor readings for the first negative value; the loop continues while there are readings left and no negative value has been found.

The trace table includes a column for each part of the condition, which shows exactly which part ends the loop.

The output is First negative reading at index 2. This shape is the basis of linear search. The order of the two tests matters. Python's and and Java's && use short-circuit evaluation: if the left side is false, the right side is not evaluated at all. Putting i < len(readings) first means that when i reaches 5 the condition stops before readings[5] is read; written the other way round, a list with no negative values makes the program crash with an IndexError (Java: ArrayIndexOutOfBoundsException).

The same task can be written with a for loop and a break statement, which leaves the loop immediately.

The program prints First negative reading at index 2 and Total of valid readings: 17.6, because continue skips −1.0 and adds the other four readings (4.2 + 3.9 + 5.1 + 4.4). break and continue make short loops concise, but a loop with several exits is harder to trace, because the reason for stopping is hidden in the body instead of stated in the condition. For anything longer than a few lines, a flag in the loop condition is usually clearer.

Validation loops

A program that accepts input from people must assume that some of it will be wrong. Checking input before using it, and asking again until it is acceptable, is one of the most common uses of a conditional loop.

The function read_age combines three checks. A presence check rejects empty input; a type check uses exception handling to catch text that is not a whole number; a range check rejects numbers outside 11 to 19. The loop only ends through the return, once all three checks pass.

Testing the function with one input of each kind (an empty line, fifteen, 23, then 16) exercises every branch. The run shows each check failing in turn before the valid value is accepted.

Validation reduces errors but has limits. It cannot detect a value that is valid but wrong (a student typing 15 instead of 16), so data that must be exact is also checked by verification, such as typing a password twice. Validation also protects security: unchecked input passed straight into a database query is how SQL injection attacks work, a topic for HL students in subtopic A2.4, Network security.

Nested loops

A loop inside the body of another loop runs completely for every single pass of the outer loop. Nested loops process two-dimensional data (rows and columns of a 2D array, every pair of items, a times table).

The program triangle prints a triangle of products: row 1 has one value, row 2 two, row 3 three, because the inner loop's range depends on the outer loop variable.

The number of passes in nested loops grows quickly. Two loops that each run n times execute the inner body $n \times n = n^2$ times, so doubling the data makes the work four times larger; subtopic B2.4, Programming algorithms, measures this with Big O notation. Repetition can also be written without a loop, as recursion (a subprogram that calls itself); the Computerphile video on loops and recursion sets the two approaches side by side.

Avoiding infinite loops, deadlock and incorrect output

Programs that compile and run can still fail in three ways related to the order and control of their instructions: they never finish, they stop making progress while waiting for each other, or they finish with the wrong answer.

Infinite loops

A loop ends only when its condition changes. If nothing in the body can make the condition false, the loop runs for ever.

Three causes account for most infinite loops: the loop variable is never updated; it is updated in the wrong direction (count = count - 1 in a loop waiting for count > 10); or the condition tests for an exact value that the variable jumps over. Deliberate infinite loops do exist (a server or a game waits for events in while True:), but they always contain a break or return that ends them.

The program odd numbers should print the odd numbers below 10, but it never stops.

A real infinite loop stopped thousands of devices at once. On 31 December 2008, many first-generation Microsoft Zune 30 music players froze; Microsoft blamed the clock driver supplied by Freescale and its handling of leap years, and the players recovered by themselves the next day. Analysis of the published driver code showed a year-counting loop that could not finish on the 366th day of a leap year.

Sources: Microsoft's statement as reported in "Zune", Wikipedia; Dr. Drang, "Leap year and the Zune", And now it's all this, January 2009.

The function year_from_day is a simplified Python version of that loop. It counts days from 1 January 1980 (day 1) and subtracts a year's worth of days at a time until fewer than a year's worth remain.

Day 10592 is 30 December 2008, and the call prints 2008. Day 10593, 31 December 2008, never returns.

A corrected function makes every pass subtract a year, and compares days with the length of the current year in the loop condition itself.

The test days are chosen at the boundaries: the first and last days of 1980 (a leap year), the first day of 1981, and the last days of 2008 and first of 2009.

Deadlock

Deadlock arises when programs share resources such as files, printers or database records. A program that needs two resources usually takes, or locks, them one at a time so that no other program can change them while it works. If two programs lock the same two resources in opposite orders, each can end up holding one and waiting for the other.

The deadlock diagram shows a booking app and a report app sharing a seat file and a payment file. The booking app has locked the seat file and is waiting for the payment file; the report app has locked the payment file and is waiting for the seat file. Neither will release what it holds until it gets what it is waiting for, so both wait for ever.

A deadlock differs from an infinite loop. In an infinite loop the program is busy doing the same work again and again; in a deadlock the programs are idle, each blocked and waiting, and the processor may have nothing to do. Deadlock is also different from a fault in one program: each program on its own is correct, and the error only appears when their steps happen in a particular order.

Ordering is the most common way to prevent deadlock. If every program that needs both files agrees to lock the seat file first and the payment file second, the cycle in the diagram cannot form: whichever program gets the seat file first will also get the payment file, finish, and release both. Other approaches are to request all resources at once, to give up held resources after waiting for a set time (a timeout) and try again later, and to hold locks for as short a time as possible.

A related fault is the race condition, in which nothing stops, but the result depends on timing.

Two tills selling the last ticket for a concert show the problem. Each till reads the number of tickets left, subtracts one and writes the new value back. If both tills read before either writes, both sell the same ticket.

The stored value ends at 0, but two tickets have been sold. On 14 August 2003 a race condition in General Electric's XA/21 energy management system stalled the alarm system in FirstEnergy's control room for over an hour; the operators lost both the audio and the visual alerts that should have warned them of changes in the grid, and the blackout that followed affected about 55 million people in eight US states and Ontario. The usual fix uses the same locks that make deadlock possible: each till locks the stored value before reading it and releases the lock after writing, so the read–update–write sequence acts as a single step that the other till cannot interrupt.

Source: "Northeast blackout of 2003", Wikipedia.

Incorrect output

Most incorrect output comes from logic errors that a careful order of design steps would catch. Common sources are statements in the wrong order, conditions using < where <= is needed, uninitialised or wrongly initialised variables, and output placed inside a loop instead of after it (or the reverse). A short design routine prevents most of these faults:

1. Plan before coding. Write the steps as a flowchart or numbered list, and check that every value is set before it is used.

2. Initialise before use. Set accumulators, counters and flags on the line before the loop that updates them.

3. Make every loop progress. Check that each path through a loop body changes the value its condition depends on.

4. Trace by hand. Follow the code with a trace table for a small input, recording each change.

5. Test with planned data. Use normal, boundary and erroneous data, and compare the actual output with the expected output worked out beforehand.

Functions and modularisation

As programs grow, the same steps are needed in several places: reading a validated number, calculating an average, printing a heading. Copying those lines each time makes the program longer and creates several copies to fix whenever a fault is found. Subprograms solve this by giving a block of code a name, so it is written once and called wherever it is needed.

A subprogram has two parts: its definition, which states its name, its inputs and the code it runs, and the places where it is called. Defining a subprogram does not run it; the code inside runs only when it is called.

Parameters, arguments and return values

A subprogram becomes reusable when it works on different values each time it is called. The values are passed in through parameters.

A subprogram can send one result back to the caller with a return statement. The call then acts as an expression whose value is the result, so it can be stored, printed or used in a calculation.

The program rooms defines one subprogram that returns a value and one that only performs an action.

Both versions print the same report.

The wall area is rounded because $4.5 \times 2.4$ is stored as 10.799999999999999 in floating point. The subprogram call diagram follows the first call step by step.

The two languages differ in how much they make explicit. A Java method must sit inside a class, declares the data type of every parameter, and declares its return type before its name (double rectangleArea(...)); programs without objects mark their methods static. A Python function declares no types, and if it reaches the end without a return it returns the special value None. A Python function can also return several values at once as a tuple (return low, high); a Java method returns exactly one value.

Older terminology calls a subprogram that returns a value a function and one that does not a procedure. In Python both are written with def, and in Java both are methods, distinguished only by whether the return type is void.

Passing arguments by value

When a subprogram is called, each argument is copied into its parameter. The parameter is a separate variable, so changing it inside the subprogram does not change the caller's variable.

The program bonus shows both sides of this rule. Adding 10 to the parameter score has no effect on mark outside, but changing the elements of a list or array passed in does change the caller's list, because the copy is a reference to the same list.

The output confirms that mark is unchanged while the list's elements have changed.

Java always passes by value: a primitive such as int is copied, and for an array, ArrayList or other object the reference is copied, so the method and the caller share one object. Python passes a reference to every object; because integers and strings are immutable, "changing" one inside a function creates a new object and the caller's variable is untouched, while a list is mutable and can be changed in place. In practice the two languages behave the same way. Some other languages, such as C++, also offer pass by reference, in which the parameter becomes another name for the caller's variable; neither course language has it, so a subprogram that must give back a new number or string returns it.

Scope of parameters and variables

Every variable has a scope: the part of the program in which it can be used. Parameters and variables created inside a subprogram are local variables: they are created when the subprogram is called and destroyed when it returns, and no other subprogram can see them. Variables created outside every subprogram are global variables, visible throughout the program.

The program prints Local visits: 99 and then Global visits: 2. Python needs the keyword global before a function can assign to a global variable; without it, visits = visits + 1 creates a local visits and fails with UnboundLocalError, because the local variable is read before it has a value. Java has no true global variables: the nearest equivalent is a static variable declared in the class, outside every method. In both languages, the local visits in show_message hides the global one of the same name, which is shadowing.

Scope differs inside loops too. A Java variable declared inside a loop or if block exists only within that block's braces, so it cannot be used after the loop. A Python variable created inside a loop is local to the whole function and still exists after the loop ends.

Global variables are convenient but make programs harder to maintain. Any subprogram can change a global, so when its value is wrong, every subprogram is a suspect; a subprogram that relies on a global also cannot be reused in another program without bringing the global with it. Passing values in as arguments and sending results back with return keeps each subprogram self-contained. Constants, values that never change, such as PASS_MARK = 42, are the accepted exception, because no subprogram is meant to change them. Java enforces this with final; Python relies on the convention that a name in capitals is not reassigned.

The program points uses the same name for a global variable and a local one.

Constructing subprograms

Writing a subprogram to a specification follows a fixed routine: decide its inputs (the parameters), its output (the return value, or void), and the steps between them; then test it with calls that cover normal, boundary and erroneous cases. Selection, a loop, a flag and a return value combine in a short password checker.

Modularisation

Splitting a program into subprograms is the first step of a wider idea: organising the whole program as separate, independent parts.

Groups of related subprograms are stored together in a module, which other programs can then load.

The module structure diagram shows two programs sharing one module of mark-processing functions, while one of them also uses the standard maths library.

The module grade_tools holds the reusable code; the main program report imports it and calls its functions through the module's name.

The main program contains no calculation of its own, only calls. Python names a function from a module as module.function; Java names a static method as Class.method.

The program prints Average: 59.2, Rounded up: 60 and Passes: 3 (58, 72 and 90 reach the pass mark; 41 misses it by one).

Benefits of modularisation

Modular programs are easier to build and to keep working, and two qualities sum up why.

The benefits depend on the scenario.

Modularisation has costs. Designing the interfaces between modules takes time, a very small program gains little from being split up, and calling a subprogram has a small overhead compared with running the same lines in place. Its benefits all concern writing, testing and maintaining the program, while running speed stays the same or becomes very slightly worse.

Exam focus

Programming constructs are examined in Paper 2, in the language of your paper (Python or Java), and they underpin almost every question on it. The statements use the command term construct, so expect to write working code: a selection that classifies values, a loop that reads data until a sentinel, a validation loop, or a complete function with parameters and a return value, usually for 3–6 marks. Trace questions (2–6 marks) give code with selection, loops or nested loops and ask for a trace table or the output; identify and explain questions ask why a loop never terminates, why a condition gives the wrong result, or why one loop type suits a task better than another. Questions may forbid built-in functions such as len, max or sum, so practise the hand-written loop versions. The no-code algorithmic-thinking question may present the same constructs as a flowchart to trace.

The code for the exam-style question finds the best day and counts the days with at least 10,000 steps in a week of step counts.

A construct answer is marked on features of the code, not on perfect syntax: the correct initialisation, loop bounds, condition, update and return or output each earn a mark. A missing colon or semicolon is usually not penalised if the logic is clear, but a wrong index, a wrong comparison (> for >=) or an accumulator reset inside the loop loses the mark for that feature.

Explain questions on loops reward a reason tied to the task. To answer "why is a while loop more appropriate than a for loop here?", state that the number of repetitions is not known in advance, then name what controls the loop in this program (the sentinel, a valid input, finding the item).

Practice questions

1. State the three control structures from which every program can be built. [1]

2. Distinguish between a parameter and an argument. [2]

3. Outline the difference between a pre-condition loop and a post-condition loop, giving one situation suited to each. [3]

4. Identify the output of for i in range(3, 12, 4): print(i) (Java: for (int i = 3; i < 12; i += 4) System.out.println(i);). [1]

5. A program uses if mark >= 50: result = "Pass" followed by if mark >= 80: result = "Distinction" and else: result = "Fail" (the else belongs to the second if). Explain why a mark of 60 is given "Fail", and construct a corrected selection. [4]

6. Construct a program that reads temperatures until the sentinel 999 is entered, then outputs the highest temperature entered, or "No data" if none were entered. Do not use the built-in max. [6]

7. Trace the following code and state its output. [4]

8. Explain how a deadlock can occur between two programs that each need the same two files, and outline one way to prevent it. [4]

9. Explain two benefits of modularisation for a team developing a school timetable system. [4]

10. Explain why the following Python function causes an error when called, and suggest two ways to fix it. [3]

Summary

• Every program is built from sequence, selection and iteration; a condition is a Boolean expression built from relational operators (<, <=, >, >=, ==, !=) and Boolean operators (and/&&, or/||, not/!).

• Instruction order decides the result: values must be set before they are used, accumulators initialised before the loop, and outputs placed after the processing they report.

• Selection can be single (if), two-way (if–else), multi-way (elif in Python, else if in Java; only the first true branch runs, so the most restrictive test goes first) or nested; Java blocks need braces to avoid statements falling outside the if, as in Apple's goto fail bug.

• A counted loop (for) repeats a known number of times; a conditional loop (while) repeats while a condition holds. A pre-condition loop may run zero times; a post-condition loop (Java do … while; Python while True with break) runs at least once.

• Loops use accumulators, counters, flags and sentinel values; validation loops repeat until input passes presence, type and range checks; nested loops run the inner loop fully for each outer pass.

• An infinite loop happens when no path through the body makes the condition false; deadlock happens when programs each hold a resource another needs; a race condition makes results depend on timing. Planning, tracing, consistent lock ordering and boundary testing prevent them.

• A subprogram (Python function, Java method) receives arguments in its parameters and may send back a return value; a void method returns nothing. Arguments are passed by value, but a list or array passed in can have its elements changed.

• Parameters and variables created in a subprogram are local; globals (Python global, Java static fields) are visible everywhere but harm maintainability.

• Modularisation splits a program into subprograms and modules, giving reuse, easier testing and debugging, teamwork, readability and maintainability, but not faster execution.

Self-check

• To do:

  I can identify sequence, selection and iteration in code and in a flowchart.

• To do:

  I can explain how moving one line (an initialisation, a calculation or an output) changes a program's result.

• To do:

  I can swap two variables correctly in Python and Java.

• To do:

  I can write a condition using relational and Boolean operators in both languages, including a range check.

• To do:

  I can construct an if–elif–else (Java if–else if–else) chain and order its conditions correctly.

• To do:

  I can trace a nested selection for given values, including values on a boundary.

• To do:

  I can choose between a counted, a pre-condition and a post-condition loop and justify the choice.

• To do:

  I can write the Python range and the Java for header for any start, stop and step.

• To do:

  I can construct a sentinel loop and a validation loop that use a counter, an accumulator or a flag.

• To do:

  I can trace a loop and a nested loop with a trace table, one row per pass.

• To do:

  I can identify why a loop never terminates and correct it.

• To do:

  I can explain deadlock and a race condition with an example, and give a way to prevent each.

• To do:

  I can construct a function or method with parameters and a return value, and say when a void method is appropriate.

• To do:

  I can predict the output of a program in which a local variable has the same name as a global one.

• To do:

  I can explain the benefits of modularisation in a given scenario, without claiming it makes programs faster.

1. (a)

   State the value returned when ids holds [12, 7, 33, 7].

   [1]1 mark

   Markscheme (a)

   True / true;

2. (b)

   Calculate the number of times the comparison ids[i] == ids[j] is made, in the worst case, for a playlist of 6 songs.

   [2]2 marks

   Markscheme (b)

   Award [1] for the method and [1] for the answer.
   $5 + 4 + 3 + 2 + 1$ / $\frac{6 \times 5}{2}$;
   15;

   Note: Award [2] for 15 with no working.

3. (c)

   Deduce the worst-case time complexity of has_duplicate / hasDuplicate, explaining your answer.

   [3]3 marks

   Markscheme (c)

   Award [1] per point, up to [3 max].
   In the worst case (no duplicates) every pair is compared once;
   the number of comparisons is $\frac{n(n-1)}{2}$ / $\frac{n^2}{2} - \frac{n}{2}$

4. (d)

   Describe the best case for this function/method and state its time complexity.

   [2]2 marks

   Markscheme (d)

   Award [1] for the description and [1] for the complexity.
   The first two songs (ids[0] and ids[1]) are the same, so it returns after one comparison;
   $O(1)$;

5. (e)

   The service now keeps every playlist sorted by ID.

   Construct, in Python or Java, a function/method has_duplicate_sorted / hasDuplicateSorted that returns whether a sorted playlist contains a repeated ID, using a single loop. For example, [7, 12, 12, 33] returns true and [7, 12, 33] returns false.

   [4]4 marks

   Markscheme (e)

   Award [1] per point, up to [4 max].
   header with a list/array parameter (and boolean return type in Java);
   loop over the positions from the first to the second-last element;
   compares each element with the next (adjacent) element;
   returns true as soon as two adjacent elements are equal;
   returns false after the loop has finished;

   Note: Accept a loop from 1 to n − 1 that compares with the previous element. Do not award the bounds mark if the code reads past the end of the list/array.

   Example answer (Python):

   PythonCopy

   def has_duplicate_sorted(ids):
       for i in range(len(ids) - 1):
           if ids[i] == ids[i + 1]:
               return True
       return False

   Example answer (Java):

   JavaCopy

   public static   {
        (   ; i < ids.length - ; i++) {
            (ids[i] == ids[i + ]) {
                ;
           }
       }
        ;
   }

6. (f)

   State the time complexity of your solution to part (e) and outline why it scales better than has_duplicate / hasDuplicate for long playlists.

   [2]2 marks

   Markscheme (f)

   Award [1] for the complexity and [1] for the outline.
   $O(n)$;
   because equal IDs are next to each other in a sorted list, each element is compared once with its neighbour rather than with every other element, so the work grows linearly instead of with $n^2$;

   Note: Allow FT from part (e).

Note: Award [1 max] for $O(n^2)$ with no explanation.

[2]2 marks