COMP2123
Assignment 1
S1 2025
Problem 1. (10 points)
Given an array A consisting of n integers, we want to compute a matrix B where for any 0 → i < j < n we have
B[i][j] = f([A[i], A[i + 1], ..., A[j ↑ 1]])
Consider the following algorithm for computing B:
Algorithm 1 Range Function Computation
1: function RangeFunc(A)
2: B ← new n × n matrix
3: for i ← 0 to n – 1 do
4: for j ← i + 1 to n – 1 do
5: C ← make a copy of A[i : j]
6: B[i][j] ← f(C)
7: return B
Assume that f(C) runs in Θ(log |C|) time.
a) Using O-notation, upperbound the running time of RangeFunc. Explain your answer with a detailed line by line analysis.
b) Using Ω-notation, lowerbound the running time of RangeFunc. Explain your answer.
Problem 2. (25 points)
We would like to design an augmented queue data structure. In addition to the usual enqueue and dequeue operations, you need to support the even-diff operation, which when run on a queue Q = <q0, q1, q2,..., qn-1> returns
Examples:
• even-diff([1, 3, 50, 48]) returns 4,
• even-diff([1, 3, 50, 48, 30]) returns 4,
• even-diff([3, 50, 48, 30]) returns 65.
We are to design an implementation of the methods enqueue, dequeue, and even-diff so that all operations run in O(1) time. You can assume that the data structure always starts from the empty queue.
Your data structure should take O(n) space, where n is the number of ele-ments currently stored in the data structure.
Your task is to:
a) Design a data structure that supports the required operations in the re-quired time and space.
b) Briefly argue the correctness of your data structure and operations.
c) Analyse the running time of your operations and space of your data structure.
Problem 3. (25 points)
A skyline is defined by an array of n distinct integers A = [h0, h1, h2, h3, h4, ...., hn-1] representing the heights of buildings in a one-dimensional city, given in the or-der they appear from left to right. Suppose you are standing on the rooftop of one of these buildings. You want to determine the closest taller building to your left and the closest taller building to your right. The goal is to find an efficient algorithm to compute this for ALL n buildings.
Specifically, for every building x ∈ [0, n – 1], compute the two closest indices i and j to x such that:
i < x, j > x, A[i] > A[x] and A[j] > A[x].
Your algorithm should return two arrays of length n:
L[0...n – 1] where L[x] denotes the index (i) of the nearest taller building to the left of building x (or None if no such building exists).
R[0...n – 1] where R[x] denotes the index (j) of the nearest taller building to the right of building x (or None if no such building exists).
Note:
• A[*] denotes the element at index ⇐ in the array.
• Indices start at 0.
Examples:
Input: A=[7,3,9,12,2,6,5,15]
Output:
L=[None, 0, None, None, 3, 3, 5, None]
R=[2, 2, 3, 7, 5, 7, 7, None]
Input: A=[6,2,4,1,10,7,8,11]
Output:
L=[None, 0, 0, 2, None, 4, 4, None]
R=[4, 2, 4, 4, 7, 6, 7, None]
Input: A=[10,3,2]
Output:
L=[None, 0, 1]
R=[None, None, None]
a) Design an algorithm to solve this problem in O(n) time.
b) Prove your algorithm is correct.
c) Analyse the running time of your algorithm.