compX123 Assignment 1 s2 2024
This assignment is due on August 18 and should be submitted on Grade-
scope. All submitted work must be done individually without consulting someone
else’s solutions in accordance with the University’s “Academic Dishonesty and
Plagiarism” 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)
Consider the following algorithm that given an array A of length n produces an
array B where B[i] is the sum of the 16 elements of A following A[i].
1: function algorithm(A)
2: n← length of A
3: B← new array of size n− 16
4: for i ∈ [0 : n− 16] do
5: B[i]← 0
6: for j ∈ [0 : 16] do
7: B[i]← B[i] + A[i+ j+ 1]
8: return B
Use O-notation to upperbound the running time of the algorithm.
Problem 2. (25 points)
We want to build a queue for integer elements that in addition to the operations
we saw during the lecture, also supports a difference() operation that on a
given queue holding the elements Q1, . . . ,Qn returns the difference between the
sum of the first half of the elements and the sum of the second half of the
elements:
⌈n/2⌉
∑
i=1
Qi −
n
∑
i=⌈n/2⌉+1
Qi.
All operations should run in O(1) time. 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:
Design a data structure that supports the required operations in the re-
quired time and space.
a)
Briefly argue the correctness of your data structure and operations.b)
Analyse the running time of your operations and space of your data structure.c)
1
compX123 Assignment 1 s2 2024
Problem 3. (25 points)
In robotics, a common problem is figuring out what type of configuration a set
of robots is in using very limited information. Here, we look at a small example
of this.
You’re given n robots (each robot is uniquely identified simply using an in-
teger between 1 and n) and you’re told that we know that the n robots are on a
line (say the x-axis), but we don’t know the order of the robots along this line.
Unfortunately, the robots don’t have GPS, so they can’t tell you their coordinate
along the line. What you do have is a function adjacent(a,b) which takes two
robots (i.e., integers) a and b as input and returns whether robot a and robot b
are adjacent. You can assume that a single call to this function runs in O(1) time.
You’re asked to design an algorithm that outputs the order of the robots along
the line. You can output the robots from left to right, or from right to left. For
full marks, your algorithm should run in O(n2) time.
Example:
If we have three robots 1, 2, and 3 and the (unknown) order along the line from
left to right is 2, 3, 1, your algorithm should return either 2, 3, 1 (the left to right
order) or 1, 3, 2 (the right to left order). Returning any order other than these
two is incorrect. In this example adjacent(1,2) would return false, since robot 1
and robot 2 aren’t adjacent on the line. adjacent(1,3) would return true, since
robot 1 and robot 3 are adjacent.
Remember to:
describe your algorithm in plain English,a)
argue its correctness, andb)
analyze its time complexity.c)
2
compX123 Assignment 1 s2 2024
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.