CM1035 Algorithms and Data Structures I Examination Instructions 2025 | UoL

Rationale for the Module

Algorithms and data structures are essential components of the field of computer science. Knowledge of a range of algorithms and data structures will allow you to solve common programming problems more rapidly. Within the programme, this module provides an introductory treatment of algorithms and data structures, preparing students for more advanced coverage later in the programme.

Aims of the Module

This module aims to help you develop your analytical and problem-solving skills, particularly concerning thinking algorithmically. The module will encourage you to start thinking about how to use computers to solve problems. You will develop skills in thinking algorithmically and learn the central concepts of algorithms and data structures. You will learn about linear data structures such as arrays, vectors and lists, and a unifying framework for considering such data structures as collections. You will learn how algorithms can be expressed as flowcharts and pseudocode, and how to convert these expressions into running programs. You will learn specific algorithms used for sorting and searching, and how to express repetition as iteration and recursion. You will learn a simple model for the execution of computation and how to describe computational problems and their solutions. The model will allow you to compare algorithms regarding their correctness and efficiency.

Instructions to Candidates: 

Part A of this assessment consists of a set of TEN multiple-choice questions (MCQs). You should attempt to answer ALL the questions in Part A. The maximum mark for Part A is 40. 

Candidates must answer TWO out of the THREE questions in Part B. The maximum mark for Part B is 60. 

Part A and Part B will be completed online together on the Inspera exam platform. You may choose to access either part first upon entering the test area, but you must complete both parts within 4 hours of doing so. 

Calculators are not permitted in this examination. Credit will only be given if all workings are shown. 

Do not write your name anywhere in your answers.

Part A 

Candidates should answer the TEN Multiple Choice Questions (MCQs) in Part A of the test area. 

Part B 

Candidates should answer any TWO questions in Part B. 

Question 1 

This question concerns computational complexity. 

In this question, the perfect square problem is the problem of determining if a positive integer, 𝑛𝑛, is a perfect square i.e. if 𝑛𝑛=𝑥𝑥2 where 𝑥𝑥is a positive integer. 

(a) The following decision algorithm, 𝐴𝐴, is proposed for the perfect square problem: 

Compute 𝑥𝑥2for integer 𝑥𝑥starting at 𝑥𝑥= 1until 𝑥𝑥2 either equals or exceeds 𝑛𝑛. 𝑛𝑛is accepted in the former case and rejected otherwise. 

Based on 𝐴𝐴, what is the complexity class of the perfect square problem? Show your reasoning. [4 marks] 

(b) What is Heron's algorithm for finding the square root of a number? [4 marks] 

(c) Given that Heron's algorithm always overestimates the square root, explain how Heron's algorithm can be adapted into a decision algorithm for the perfect square problem. [4 marks] 

(d) Based on the Heron-adapted algorithm, what is the complexity class of the perfect square problem? Show your reasoning. [4 marks] 

(e) Propose a binary search algorithm, 𝐵𝐵, that decides the perfect square problem. [4 marks] 

(f) Based on 𝐵𝐵, what is the complexity of the perfect square problem? [4 marks] 

(g) Compare the complexity results from analysis of algorithms 𝐴𝐴,𝑩𝑩and adapted- Heron. You should explain why the analysis produces identical or different classes. [6 marks] 

Question 2 

This question concerns data structures. 

A queue will be represented <𝑎𝑎,𝑏𝑏,𝑐𝑐,𝑑𝑑>. The queue head is the left-most element.

(a) A vector data structure has the following operations: 

new Vector v(L) creates data structure with L elements set to a default value select(i) returns the i'th element of v. 
store(v, i, a) sets the i'th element of v to a 

Suppose we require a vector but we only have access to a queue. 

Write a pseudocode function with headerselect(q, index)that returns a copy of the element in positionindexof the queueq. For example, select(<𝑎𝑎,𝑏𝑏,𝑐𝑐,𝑑𝑑>,3)returns a copy of 𝑐𝑐. You can assume there is a function copy(𝑒𝑒)which makes a copy of element 𝑒𝑒. The queue should remain unchanged upon return. [4 marks] 

(b) Write a pseudocode function with headerstore(q, index, value)that overwrites the element at position index of the queue,q, with value. qshould remain unchanged otherwise. [4 marks] 

(c) Tokenisation and postfix arithmetic. A token is either a number or one of the operators +,−,×,÷. An arithmetical expression can be tokenised into a queue of arithmetical tokens. So, for example, 1 + 2 × 3becomes < 1, +, 2,×, 3 >. A postfix arithmetical expression is written with the operator after the operands. For example, postfix notation for (1 + 2) is (1 2 +). 

The input to Postfix is a queue of arithmetical tokens. 

function to Post Fix(input) 
new Queue queue 
new Stack stack 

while!empty(input) 
token = dequeue(input) 
If the token is a number 
enqueue(token, queue)
 else push(token, stack) 

while!empty(stack) 
enqueue(pop(stack), queue) 

return queue 

What is returned for input < 1, +, 2,×, 3 >? [4 marks] 

(d)Eval(input)evaluates a postfix expression. 

functionEval(input) 
new Stack stack 
while !empty(input) 
token = dequeue(input)
 If the token is a number 
push(token, stack) 
else 
a = pop(stack)
 b = pop(stack) 
c = Op(a, b, token) push(c, stack) 

return pop(s) 
Op(a, b, op) performs the calculation (a b op). For example, Op(2, 3, ×)returns 6. 

What is Eval (to Post Fix(< 3, +, 4,×, 5 >))? [4 marks] 
(e) What is Eval (to Post Fix(< 3,×, 4, + 5 >))? [4 marks] 
(f) Comment on (d) and (e) above. [4 marks] 
(g) Amend to Post Fix(input)so that Eval computes correctly. [6 marks]

Question 3 

This question concerns the following sorting algorithm: 

1.functionSORT(A) 
2. for i = 1 to length(A) - 1 
3. for j = length(A) down to i + 1 
4. if A[j] < A[j - 1] 
5. swap A[j] and A[j-1] 
6. print(A) 

(a) What is printed when SORT is run on A = [5, 4, 3, 2, 1]? The first element of the list is rightmost: A[1] = 5. [6 marks] 

(b) Consider the operation of SORT on a list of length N. How many comparisons in line 4 take place when i = 1 and when i = N - 1? [4 marks] 

(c) How many comparisons take place in total? Show your working. You may use the result1 + 2 +⋯+𝑛𝑛=𝑛𝑛 �𝑛𝑛+1 2 �. [4 marks] 

(d) Based on the analysis above, or otherwise, what is the worst, best and average-case time complexity of SORT? Explain your answer. [4 marks] 

(e) What is SORT's space complexity? Explain your answer. [4 marks] 

(f) Complete the table below. Does SORT have any advantages over QUICKSORT? [8 marks]