COMP2823
Assignment 1
S1 2023
Problem 1. (20 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 and that allocating the space for the matrix takes O(n
2
) time.
Your task is to
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. (40 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 elements currently stored in the data structure.
Your task is to:
a) Design a data structure that supports the required operations in the required 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. (40 points)
We would like to implement an ADT for keeping track of a collection of queues.
We would like to implement the following operations:
• init: Initialize the system having a single empty queue
• enqueue(Q, e): Q is a position specifying a given queue in the system, and e is the element to be enqueued into Q
• dequeue(Q, e): Q is a position specifying a given queue in the system, from which we could like to dequeue an element
• split(Q): Q is a position specifying a given queue in the system whose elements needs to be redistributed evenly into two new queues.
• iterate(): iterate over the queues stored in the system
Examples:
• given the state [⟨1, 5, 4⟩,⟨3, 7, 5, 2⟩,⟨10⟩] if we split the second queue the state should become [⟨1, 5, 4⟩,⟨3, 7⟩,⟨5, 2⟩,⟨10⟩],
• given [⟨1, 5, 4⟩,⟨3, 7, 5, 2⟩] if we dequeue from the first queue the state should become [⟨5, 4⟩,⟨3, 7, 5, 2⟩],
Design a data structures for the ADT such that enqueue, dequeue, and init run in O(1) time, and split runs in O(log m) amortised time, where m is the number of operations performed. Your data structure should take O(n) space, where n is the number of elements currently stored in the data structure.
Your task is to:
a) Design a data structure that supports the required operations in the required 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.
Written Assignment Guidelines
• Assignments should be typed and submitted as pdf (no pdf containing text as images, no handwriting).
• Start by typing your student ID at the top of the first page of your submission. Do not type your name.
• Submit only your answers to the questions. Do not copy the questions.
• When asked to give a plain English description, describe your algorithm as you would to a friend over the phone, such that you completely and unambiguously describe your algorithm, including all the important (i.e., non-trivial) details. It often helps to give a very short (1-2 sentence) description of the overall idea, then to describe each step in detail. At the end you can also include pseudocode, but this is optional.
• In particular, when designing an algorithm or data structure, it might help you (and us) if you briefly describe your general idea, and after that you might want to develop and elaborate on details. If we don’t see/understand your general idea, we cannot give you marks for it.
• Be careful with giving multiple or alternative answers. If you give multiple answers, then we will give you marks only for "your worst answer", as this indicates how well you understood the question.
• Some of the questions are very easy (with the help of the slides or book). You can use the material presented in the lecture or book without proving it. You do not need to write more than necessary (see comment above).
• When giving answers to questions, always prove/explain/motivate your answers.
• When giving an algorithm as an answer, the algorithm does not have to be given as (pseudo-)code.
• If you do give (pseudo-)code, then you still have to explain your code and your ideas in plain English.
• Unless otherwise stated, we always ask about worst-case analysis, worst case running times, etc.
• As done in the lecture, and as it is typical for an algorithms course, we are interested in the most efficient algorithms and data structures.
• If you use further resources (books, scientific papers, the internet,...) to formulate your answers, then add references to your sources and explain it in your own words. Only citing a source doesn’t show your understanding and will thus get you very few (if any) marks. Copying from any source without reference is considered plagiarism.