A Level Computer Science Paper 2 B: Algorithms and Programming

Everything that does not help plan a route, such as buildings, trees and the shape of the land, has been removed. Only the roads, the junctions and the distances between them are kept, which turns the real world into a much simpler problem the app can solve.

The list must already be sorted, and the target must be the same type as the items in the list, so that they can be compared.

A page in the cache is loaded from the computer's own storage rather than downloaded again, so it appears faster and less bandwidth is used. But if the page has changed since it was cached, the browser may show an out of date version.

Thinking concurrently means identifying the parts of the task that can happen at the same time. Each image can be requested and downloaded at the same time as the others, while the text of the page is being laid out. None of these tasks depends on the others, so overlapping them makes the page appear much sooner than doing them one after another.

Using a library subroutine saves the time it would take to write and test the code again, and because it has already been tested and used by many programmers it is likely to be reliable.

Inputs and outputs are thinking ahead, sub-procedures are thinking procedurally, decisions are thinking logically and simultaneous parts are thinking concurrently.

2 + mystery(47) = 2 + 7 + mystery(4) = 2 + 7 + 4 + mystery(0) = 13. The function adds up the digits.

mystery(472), mystery(47), mystery(4) and mystery(0): four calls.

Take the last digit with % 10, add it to a running total, and remove it with // 10, until no digits are left.

def mystery(n):
    total = 0
    while n > 0:
        total = total + n % 10
        n = n // 10
    return total

For a problem that is defined in terms of smaller versions of itself, such as visiting every node of a tree, a recursive solution is short and mirrors the structure of the data, so it is easier to write and follow. But every recursive call puts a new frame on the call stack, holding its parameters, local variables and return address, so recursion uses more memory and time than a loop, and very deep recursion can overflow the stack.

x is passed by value, so the procedure changes only its own copy and x stays 5. y is passed by reference, so the change to b changes y, which becomes 6.

Breakpoints pause, watches show values, stepping runs line by line, and highlighting colours the code.

Dog overrides the speak method it inherits, so the same call gives different behaviour depending on the object's class: polymorphism.

The attribute __name is private, so code outside the class cannot read or change it directly. The only way to get the name is through the public method getName, so the class controls how its data is used.

A class is the template, an object an instance of it, a method a subroutine in it, and inheritance builds a class on another.

Because any subroutine can change a global variable, an unexpected change is hard to trace back to its cause. Subroutines that depend on globals are also harder to test separately and reuse in other programs.

The base case is the empty tree, with 0 nodes. Any other tree has 1 node, its root, plus the nodes in its left and right subtrees.

def countNodes(tree):
    if tree is None:
        return 0
    left, value, right = tree
    return 1 + countNodes(left) + countNodes(right)

Binary search halves the list each time, bubble sort compares every pair, merge sort does n work on each of log n levels, and indexing is a single step.

The time taken by an O(n²) algorithm grows with the square of the number of items, so doubling the data quadruples the time. For a million items, n² is a million million steps while n log n is about 20 million, so the O(n log n) algorithm is many thousands of times faster.

Pass 1 inserts 3 before 7. Pass 2 leaves 9 where it is. Pass 3 moves 1 to the front. Pass 4 inserts 5 between 3 and 7.

If every pivot is the largest or smallest item, each partition removes only one item, giving O(n²).

C is 2. B is 3, through C (2 + 1), which beats the direct 4. D is 8, through B (3 + 5). E is 10, through D (8 + 2), which beats 12 through C. F is 12, through E (10 + 2), which beats 14 through D.

A, C, B, D, E, F, with a length of 12.

Dijkstra's algorithm always visits the unvisited node with the smallest distance from the start, so it spreads out in every direction and finds the shortest path to every node. A* adds a heuristic, an estimate of the remaining distance to the goal, and visits the node with the smallest total of distance so far plus estimate. That steers the search towards the goal, so it usually visits far fewer nodes to find a route to one destination.

Breadth-first visits each level in turn: A, then B and C, then D, E and F. Depth-first goes as deep as it can down the left first: A, B, D, E, then C and F.

A binary search works by jumping straight to the middle item, which needs direct access by position, as an array gives. A linked list can only be followed node by node from its start, so just reaching the middle takes as long as a linear search.

Push each opening bracket. For each closing bracket, the stack must not be empty and the bracket popped must be its partner. At the end, the stack must be empty.

def isBalanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for character in text:
        if character in "([{":
            stack.append(character)
        elif character in ")]}":
            if len(stack) == 0 or stack.pop() != pairs[character]:
                return False
    return len(stack) == 0

The base case is low > high: nothing is left to search. Otherwise compare the middle item and recurse on the half that could hold the target, moving low or high past the middle.

def binarySearch(items, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if items[mid] == target:
        return mid
    elif items[mid] < target:
        return binarySearch(items, target, mid + 1, high)
    else:
        return binarySearch(items, target, low, mid - 1)

Shift each larger item one place right, working back from position i - 1, then drop current into the gap.

def insertionSort(items):
    for i in range(1, len(items)):
        current = items[i]
        position = i
        while position > 0 and items[position - 1] > current:
            items[position] = items[position - 1]
            position = position - 1
        items[position] = current

Merge sort builds new lists as it splits the data and merges the sorted halves, so it needs extra memory in proportion to the number of items. Insertion sort works in place, moving items within the original list, so it needs only one extra variable.

The inner loop runs n times for each of the n passes of the outer loop: n x n steps.

n is halved each time round the loop, so it repeats about log2 n times.

A* explores the nodes with the smallest estimated total first. If the heuristic overestimates, a node on the genuinely shortest path can look more expensive than it is and be left unexplored, so the algorithm may reach the goal along a longer route first and stop there.

Check for a full or empty queue first. Move the pointer on with (pointer + 1) % size, which wraps from the last position back to 0, and keep count up to date.

class Queue:
    def __init__(self, size):
        self.items = [None] * size
        self.size = size
        self.front = 0
        self.rear = -1
        self.count = 0

    def isEmpty(self):
        return self.count == 0

    def isFull(self):
        return self.count == self.size

    def enqueue(self, item):
        if self.isFull():
            return False
        self.rear = (self.rear + 1) % self.size
        self.items[self.rear] = item
        self.count = self.count + 1
        return True

    def dequeue(self):
        if self.isEmpty():
            return None
        item = self.items[self.front]
        self.front = (self.front + 1) % self.size
        self.count = self.count - 1
        return item

In a linear queue the front pointer moves along the array as items are removed, so the positions behind it are never used again and the queue soon reports itself full. A circular queue wraps both pointers back to position 0, so the freed positions are reused.

Each player's name, their score and the tiles on their rack.

Convert the word to upper case, add up VALUES[letter] for each letter, then double the total if len(word) >= 7.

VALUES = {"A": 1, "B": 3, "C": 3, "D": 2, "E": 1, "F": 4, "G": 2, "H": 4, "I": 1,
          "J": 8, "K": 5, "L": 1, "M": 3, "N": 1, "O": 1, "P": 3, "Q": 10, "R": 1,
          "S": 1, "T": 1, "U": 1, "V": 4, "W": 4, "X": 8, "Y": 4, "Z": 10}


def wordScore(word):
    total = 0
    for letter in word.upper():
        total = total + VALUES[letter]
    if len(word) >= 7:
        total = total * 2
    return total

Copy the rack into a list of tiles and remove each letter of the word as it is used, so that a tile cannot be used twice. If a letter is not there, the word cannot be made.

VALUES = {"A": 1, "B": 3, "C": 3, "D": 2, "E": 1, "F": 4, "G": 2, "H": 4, "I": 1,
          "J": 8, "K": 5, "L": 1, "M": 3, "N": 1, "O": 1, "P": 3, "Q": 10, "R": 1,
          "S": 1, "T": 1, "U": 1, "V": 4, "W": 4, "X": 8, "Y": 4, "Z": 10}


def canMake(word, rack):
    tiles = list(rack)
    for letter in word.upper():
        if letter in tiles:
            tiles.remove(letter)
        else:
            return False
    return True

Keep the best word so far and its score, starting from an empty string and 0. Replace them only when a word can be made and scores strictly more, so the first of two equal words is kept.

VALUES = {"A": 1, "B": 3, "C": 3, "D": 2, "E": 1, "F": 4, "G": 2, "H": 4, "I": 1,
          "J": 8, "K": 5, "L": 1, "M": 3, "N": 1, "O": 1, "P": 3, "Q": 10, "R": 1,
          "S": 1, "T": 1, "U": 1, "V": 4, "W": 4, "X": 8, "Y": 4, "Z": 10}


def wordScore(word):
    total = 0
    for letter in word.upper():
        total = total + VALUES[letter]
    if len(word) >= 7:
        total = total * 2
    return total


def canMake(word, rack):
    tiles = list(rack)
    for letter in word.upper():
        if letter in tiles:
            tiles.remove(letter)
        else:
            return False
    return True


def bestWord(words, rack):
    best = ""
    bestScore = 0
    for word in words:
        if canMake(word, rack) and wordScore(word) > bestScore:
            best = word
            bestScore = wordScore(word)
    return best

A hash table calculates where a word would be stored from the word itself, so a lookup takes constant time, O(1), however many words there are. A linear search is O(n): a word near the end, or one that is not valid, means comparing it with all 270,000 words. Words are checked on every turn, so the hash table keeps the game responsive.

Two underscores make an attribute private in Python. addWord works out the word's score once, adds it to the running total and returns it.

VALUES = {"A": 1, "B": 3, "C": 3, "D": 2, "E": 1, "F": 4, "G": 2, "H": 4, "I": 1,
          "J": 8, "K": 5, "L": 1, "M": 3, "N": 1, "O": 1, "P": 3, "Q": 10, "R": 1,
          "S": 1, "T": 1, "U": 1, "V": 4, "W": 4, "X": 8, "Y": 4, "Z": 10}


def wordScore(word):
    total = 0
    for letter in word.upper():
        total = total + VALUES[letter]
    if len(word) >= 7:
        total = total * 2
    return total


class Player:
    def __init__(self, name):
        self.__name = name
        self.__score = 0

    def getName(self):
        return self.__name

    def getScore(self):
        return self.__score

    def addWord(self, word):
        points = wordScore(word)
        self.__score = self.__score + points
        return points

A list used as a queue: nextPlayer removes the player at the front and appends them to the back, so the order cycles. winner looks at every player in the queue, whatever order it is in.

VALUES = {"A": 1, "B": 3, "C": 3, "D": 2, "E": 1, "F": 4, "G": 2, "H": 4, "I": 1,
          "J": 8, "K": 5, "L": 1, "M": 3, "N": 1, "O": 1, "P": 3, "Q": 10, "R": 1,
          "S": 1, "T": 1, "U": 1, "V": 4, "W": 4, "X": 8, "Y": 4, "Z": 10}


def wordScore(word):
    total = 0
    for letter in word.upper():
        total = total + VALUES[letter]
    if len(word) >= 7:
        total = total * 2
    return total


class Player:
    def __init__(self, name):
        self.__name = name
        self.__score = 0

    def getName(self):
        return self.__name

    def getScore(self):
        return self.__score

    def addWord(self, word):
        points = wordScore(word)
        self.__score = self.__score + points
        return points


class Game:
    def __init__(self, players):
        self.__queue = list(players)

    def nextPlayer(self):
        player = self.__queue.pop(0)
        self.__queue.append(player)
        return player

    def winner(self):
        best = self.__queue[0]
        for player in self.__queue:
            if player.getScore() > best.getScore():
                best = player
        return best.getName()

Every time a word is played it is pushed onto a stack along with its score. Undo pops the top item, which is always the most recent word, subtracts its score from the player's total and puts its tiles back on the rack. Because a stack is last in, first out, pressing undo again removes the word before that, so the words are undone in the reverse order to the one they were played in.

Object-oriented programming suits the game because its design can mirror the problem: there are players, a game and a queue of turns, and each becomes a class. Encapsulation keeps each player's score private, so it can only change through addWord, which stops other parts of the program corrupting it. Any number of players can be created as instances of Player, each with its own name and score, without any extra code. The design is also easy to extend. A ComputerPlayer class could inherit everything from Player and override a method to choose its own word, and through polymorphism the Game class would treat it exactly like a human player. Because each class is self-contained it can be written and tested separately, so a team can share the work and later changes are less likely to break other parts. There are costs. The classes and their relationships need careful design before coding starts, and for a small program the classes add code and complexity. Parts of the game, such as wordScore and canMake, are simple calculations that are clearer as ordinary functions, as a procedural approach would write them. Overall an object-oriented approach is the better choice for the game as a whole, because it has several kinds of object with their own data and behaviour and is likely to grow, while small stateless calculations can stay as plain functions.