comp2123代做、代写c/c++，Python设计编程

日期：2025-03-28 10:55

comp2123 Assignment 1 s1 2025

This assignment is due on March 25 and should be submitted on Gradescope.

All submitted work must be done individually without consulting someone else’s

solutions in accordance with the University’s “Academic Dishonesty and Plagia rism” policies.

Before you read any further, go to the last page of this document and read

the Written Assignment Guidelines section.

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.

Using O-notation, upperbound the running time of RangeFunc. Explain

your answer with a detailed line by line analysis.

a)

Using Ω-notation, lowerbound the running time of RangeFunc. Explain

your answer.

b)

1

comp2123 Assignment 1 s1 2025

Problem 2. (25 points)

We would like to design an augmented queue data structure. In addition to

the usual ❡♥q✉❡✉❡ and ❞❡q✉❡✉❡ operations, you need to support the ❡✈❡♥✲❞✐❢❢

operation, which when run on a queue Q = ⟨q0, q1, q2, . . . , qn−1⟩ returns

∑

0≤i<n−1 s.t. i is even

|qi − qi+1

|.

Examples:

• ❡✈❡♥✲❞✐❢❢([1, 3, 50, 48]) returns 4,

• ❡✈❡♥✲❞✐❢❢([1, 3, 50, 48, 30]) returns 4,

• ❡✈❡♥✲❞✐❢❢([3, 50, 48, 30]) returns 65.

We are to design an implementation of the methods ❡♥q✉❡✉❡, ❞❡q✉❡✉❡, and

❡✈❡♥✲❞✐❢❢ 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:

Design a data structure that supports the required operations in the re quired time and space.

a)

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.

2

comp2123 Assignment 1 s1 2025

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 ◆♦♥❡ 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 ◆♦♥❡ 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]

Design an algorithm to solve this problem in O( n2) time. a)

b) Prove your algorithm is correct.

c) Analyse the running time of your algorithm.

3

comp2123 Assignment 1 s1 2025

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 submis sion. 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) de scription 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/under stand 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, though

slower solutions may receive partial marks.

• 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.

4