Exam practice

• Stack: last in, first out. Example: a pile of plates; the plate put on last is taken first. Operations: push (put on top), pop (take from the top), peek (look at the top), is empty.
• Queue: first in, first out. Example: the token queue at a bank; the first to take a token is served first. Operations: enqueue (join at the back), dequeue (leave from the front), front (look at the front), is empty.
• Priority queue: the item with the highest priority leaves first, whenever it came. Example: an emergency department, where the most urgent patient is seen next. Operations: add an item with its priority, take the item of highest priority.

It fails at the last ]: the most recently opened bracket is {, which must be closed before the [ can be. balanced() returns False there.

pop(0) takes the front item out of a Python list, and every item after it moves one place forward, so each pop is O(n) and the whole search does quadratic work in moving items alone. A deque adds and removes at both ends without moving anything:

from collections import deque to_visit = deque([start])          # instead of to_visit = [start]place = to_visit.popleft()         # instead of to_visit.pop(0)

to_visit.append(...) stays the same. Each step is now O(1), and the search is linear in the size of the graph again.

class Node:    def __init__(self, value, next=None):        self.value = value        self.next = next  class LinkedStack:    def __init__(self):        self._top = None               # the head of the chain is the top     def push(self, value):        self._top = Node(value, self._top)     def pop(self):        if self._top is None:            raise IndexError("pop from an empty stack")        value = self._top.value        self._top = self._top.next        return value     def peek(self):        if self._top is None:            raise IndexError("peek at an empty stack")        return self._top.value     def is_empty(self):        return self._top is None  s = LinkedStack()for n in [1, 2, 3]:    s.push(n)print(s.pop(), s.pop(), s.pop(), s.is_empty())

3 2 1 True

Push and pop each change only the head reference, so both are O(1), and no item ever moves.

Dawa: 68 + 97 + 119 + 97 = 381, and 381 % 8 = 5 (8 × 47 = 376, remainder 5). Bucket 5.
Asha: 65 + 115 + 104 + 97 = 381, and 381 % 8 = 5. Bucket 5 too.

The two names collide, because their letters’ codes happen to add up to the same total, 381. Any two words made of the same letters in a different order (like “meat” and “team”) always collide under this hash, because adding doesn’t care about order. A better hash function also uses each letter’s position, for example by multiplying the total so far by a number before adding the next code; Python’s own string hash mixes the bits far more thoroughly.

            50          /    \        30      70       /  \    /  \     20   40  60   80         /       35

35: compare with 50 (go left), 30 (go right), 40 (go left), 35 (found): 4 looks.
65: compare with 50 (go right), 70 (go left), 60 (go right): there is no right child, so 65 isn’t in the tree, after 3 looks.

Each name added in alphabetical order is later than every name already in the tree, so the search for its place goes right at every node and it becomes the right child of the last name. The tree turns into a single chain, as high as the number of names, and a search must walk down it like a linked list: O(n) instead of O(log n).

What to do: (1) use a balanced search tree (such as an AVL tree), which rotates nodes after each insertion to keep its height near log₂ n whatever the order; (2) add the names in a random order (shuffle them first), which makes a lopsided tree very unlikely when all the names are known at the start. (If the program needs only exact look-ups and no order, a dictionary avoids the problem altogether.)

(i) Position 0 is the root, 2; its children (positions 1 and 2) are 5 and 3; 5’s children (positions 3 and 4) are 9 and 6; 3’s child (position 5) is 4.

          2        /   \       5     3      / \   /     9   6 4

(ii) 1 goes in at position 6, the next place, as 3’s right child. Its parent, (6 − 1) // 2 = position 2, holds 3: 1 is smaller, so swap. Now 1 is at position 2; its parent, position 0, holds 2: 1 is smaller, swap again. Now 1 is at the root, and it stops.

(iii) [1, 5, 2, 9, 6, 4, 3]. Every parent is still smaller than its children: 1 over 5 and 2; 5 over 9 and 6; 2 over 4 and 3.

1. A stack (or a list used as one), with a limit on its size: the newest emoji used goes on top and is shown first. (An emoji used again is taken from where it was and put back on top.)
2. A queue (a deque): first come, first served. Enqueue as each person joins, dequeue at the counter, both O(1).
3. A set (or a dictionary), a hash table: “is this username taken?” is an exact look-up, O(1) on average among two million; a list would need up to two million comparisons.
4. A dictionary from player to runs, updated in O(1) as each run is scored, plus heapq.nlargest(10, …) (a heap) or a sort when the top 10 is shown; with very many players and constant updates, a balanced search tree ordered by runs keeps the order all the time. Either answer is fine with a reason.
5. A sorted structure: a sorted list searched with binary search, or a search tree, because words starting with the same letters are next to each other in alphabetical order. A dictionary can’t find “every word starting with pa” without looking at all of them.

Not always. A dictionary is faster for finding an exact key, but:

• When the keys are needed in order: listing a phone book alphabetically, or finding all the names between Pa and Pe, all day long. A search tree gives its keys in order by an in-order traversal, and finds a range by walking down to its start; a dictionary must sort or check every key each time.
• When “the smallest” or “the next bigger” is asked often: the next bus after 10:15 among a day’s departures, or the cheapest flight. A tree finds them in O(log n); a dictionary must look at every key.
• (Also good: a dictionary’s worst case, with many collisions, is O(n); a balanced tree’s worst case is still O(log n).)

Neither: when the program needs the most urgent item next and keeps adding new ones (a heap), or the oldest first (a queue), or just the items in the order they were added, by position (a list).

• The kitchen’s orders: a priority queue (a heap) of tuples (priority, order number, order), priority 1 for a waiting takeaway and 2 for the rest. The order number breaks ties, so orders of the same priority are cooked in the order they came. Operations: add an order (heappush), take the next to cook (heappop), O(log n) each. (A simpler design, just as good: two queues, one for waiting takeaways and one for the rest, always serving the first queue while it isn’t empty.)
• The bills: a dictionary from table number to that table’s Bill object, found in O(1) when the cashier asks. A table’s items are a list inside its Bill.
• Undo: a stack of changes (“added 2 plates of buff momo to table 4”); undo pops the last and does its opposite.

Tests: an empty kitchen (taking the next order must say there is none, not crash); two takeaways and three table orders arriving mixed (the takeaways first, each group in arrival order); a bill for a table with no orders; an undo with nothing to undo; and a busy evening’s worth of orders, timed, to check nothing slows down.

from collections import deque def reverse_words(sentence):    stack = []    for word in sentence.split():        stack.append(word)    out = []    while stack:        out.append(stack.pop())        # the last word pushed comes off first    return " ".join(out) def same_both_ways(word):    stack = []    queue = deque()    for ch in word:        stack.append(ch)        queue.append(ch)    while stack:        if stack.pop() != queue.popleft():   # from the end, and from the start            return False    return True print(reverse_words("the bus leaves at seven"))print(same_both_ways("malayalam"), same_both_ways("momo"))

seven at leaves bus theTrue False

The stack gives the letters back from the last, the queue from the first, so comparing them pair by pair compares the word with itself reversed.

(i) Pre-order: 50, 30, 20, 40, 35, 70, 60, 80. Post-order: 20, 35, 40, 30, 60, 80, 70, 50. (In-order, for comparison, is 20, 30, 35, 40, 50, 60, 70, 80.)

(ii)

class Node:    def __init__(self, key):        self.key = key        self.left = None        self.right = None  def put(root, key):    """Adds a key to the tree under root; gives back the root."""    if root is None:        return Node(key)    if key < root.key:        root.left = put(root.left, key)    else:        root.right = put(root.right, key)    return root  def pre_order(node, out):    if node is not None:        out.append(node.key)            # the node first        pre_order(node.left, out)        pre_order(node.right, out)    return out  def post_order(node, out):    if node is not None:        post_order(node.left, out)        post_order(node.right, out)        out.append(node.key)            # the node last    return out  root = Nonefor key in [50, 30, 70, 20, 40, 60, 80, 35]:    root = put(root, key)print("pre-order: ", pre_order(root, []))print("post-order:", post_order(root, [])) copy = Nonefor key in pre_order(root, []):    copy = put(copy, key)print("copy, pre-order:", pre_order(copy, []))

pre-order:  [50, 30, 20, 40, 35, 70, 60, 80]post-order: [20, 35, 40, 30, 60, 80, 70, 50]copy, pre-order: [50, 30, 20, 40, 35, 70, 60, 80]

The three functions differ only in where the line that visits the node goes: first, between the two subtrees, or last.

(iii) In pre-order, every node comes before every node below it. So when a key is added to the copy, the nodes above it in the original are already there, in the same places, and its search falls off at the same spot: it becomes the same child of the same parent. The last line of the output shows the copy has the same shape.

(iv) Post-order deals with everything below a node before the node itself. Uses: adding up the space a folder takes on a disk (each folder’s total needs its subfolders’ totals first); deleting a tree, children before their parent; and working out a sum written as a tree, such as (3 + 4) × 5, where each operation needs its two numbers first. Grade 12 meets the last again: the post-order of a sum’s tree, 3 4 + 5 ×, is its Reverse Polish notation.

(i)

import heapqimport random  def selection_sort(items):    """Sorts the list in place, smallest first. Gives back the comparisons made."""    compared = 0    for i in range(len(items) - 1):        smallest = i        for j in range(i + 1, len(items)):      # look through the rest for the smallest            compared += 1            if items[j] < items[smallest]:                smallest = j        items[i], items[smallest] = items[smallest], items[i]    return compared  def heap_sort(items):    """The same idea, with a heap to find the smallest each time."""    heap = list(items)    heapq.heapify(heap)    return [heapq.heappop(heap) for i in range(len(heap))]  marks = [64, 81, 47, 92, 58, 73]print(selection_sort(marks), "comparisons:", marks)random.seed(1)for n in [100, 1000, 3000]:    data = [random.randint(1, 100000) for i in range(n)]    print(f"{n:>5} items: {selection_sort(list(data)):>9,} comparisons;",          heap_sort(data) == sorted(data))

15 comparisons: [47, 58, 64, 73, 81, 92]  100 items:     4,950 comparisons; True 1000 items:   499,500 comparisons; True 3000 items: 4,498,500 comparisons; True

(heapq.heapify turns a list into a heap in place. True shows that heap_sort sorted each list correctly.)

(ii) The first pass compares n − 1 items, the next n − 2, and so on down to 1: (n − 1) + (n − 2) + … + 1 = n(n − 1) ÷ 2 comparisons, always, however the list starts (6 marks: 15; 1,000 items: 499,500). That is **O(n²)**: ten times the items, about a hundred times the work.

(iii) Both sorts do the same thing n times: take the smallest item still left and put it next in the answer. Selection sort finds that smallest by looking through every item left, O(n) each time, so O(n²) in all. Heapsort keeps the items left in a heap, where the smallest is always at the top, and taking it out costs only a sift down, O(log n). n takes at O(log n) each make O(n log n): for 3,000 items, roughly 3,000 × 12 = 36,000 steps instead of about 4.5 million. (The classic heapsort sorts in place inside the list, with the largest at the top of the heap, moving it to the end of the list each time; the idea is the same.)