Paper 2: Algorithms and programming

Explain what abstraction is and how it is used in a map of a train network.

Explain how decomposition could help develop a school timetable program.

Explain what is meant by caching and one disadvantage of it.

Explain one benefit and one drawback of designing a game so that tasks run concurrently.

procedure change(byVal a, byRef b)    a = a * 2    b = b + aendprocedure x = 3y = 4change(x, y)print(x)print(y)

State the outputs and explain the difference between passing by value and by reference.

function power(base, exp)    if exp == 0 then        return 1    else        return base * power(base, exp - 1)    endifendfunction

Rewrite power as an iterative function and compare the two versions.

Write a function validPassword(pw) that returns true only if the password is at least 10 characters long, contains at least one digit and at least one upper-case letter, and contains no spaces.

Write a class Account with private attributes accountNumber and balance, a constructor, a getBalance method and a withdraw(amount) method that only allows withdrawals that do not make the balance negative. Then write a subclass SavingsAccount that adds an interestRate attribute and an addInterest method.

Describe four features of an IDE that help programmers to find and fix errors.

Explain the difference between local and global variables and why local variables are preferred.

Show the steps of a binary search for 40 in the list [3, 9, 14, 21, 27, 33, 40, 48, 52].

Show each pass of an insertion sort on [5, 2, 8, 1, 9].

Describe how merge sort works and state its time complexity.

Explain the meaning of O(1), O(n), O(n²) and O(2ⁿ), giving an example of each.

Explain how A* search differs from Dijkstra's algorithm.

Write pseudocode for push(item) and pop() for a stack stored in an array of size 10 with a pointer top (initially −1), including checks for overflow and underflow.

Describe how a new node is inserted into an ordered linked list.

The values 50, 30, 70, 20, 40, 60, 80 are inserted into a binary search tree in that order. Describe where 65 would be inserted and why.

A graph has edges A–B, A–C, B–D, C–D, C–E, D–F. Give the order of a breadth-first traversal from A (visit neighbours alphabetically) and name the data structure used.

Section B — A cinema chain wants a seat-booking system. Each screen has rows A–M with 20 seats per row. Customers choose a film, a time and the number of seats, and the system suggests seats together. Identify the inputs, outputs and stored data, and one abstraction the designers could make.

Describe a suitable data structure to store seat availability for one screening.

Write a function findSeats(row, n) that returns the index of the first seat of the first block of n adjacent free seats in the given row, or −1 if there is none.

Describe a test plan for findSeats, including normal, boundary and erroneous data.

Tickets cost £12 for adults and £8 for children; screenings before 5pm are 25% cheaper; a group of 6 or more people gets £1 off each ticket. Write an algorithm to calculate the total price for a booking.

The chain wants to allocate seats so that groups are kept together and as few single seats as possible are left empty. Discuss how backtracking or heuristic methods could be used to solve this problem.

Evaluate the use of an object-oriented approach for developing the cinema booking system.