CONFIDENTIAL EXAM PAPER

This paper is not to be removed from the exam venue.

Computer Science

EXAMINATION

Semester 1– Main, 2021 comp2123 Data Structures and Algorithms

EXAM WRITING TIME: 2 hours

READING TIME: 10 minutes

EXAM CONDITIONS:

This is a OPEN book examination.

All submitted work must be done individually without consulting someone else’s help, in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.

MATERIALS PERMITTED IN THE EXAM VENUE: MATERIALS TO BE SUPPLIED TO STUDENTS:

INSTRUCTIONS TO STUDENTS:

Type your answers in your text editor (Latex, Word, etc.) and convert it into a pdf file.

Submit this pdf file via Canvas. No other file format will be accepted. Hand- written responses will not be accepted.

Start by typing you 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.

Do not copy any text from the permitted materials. Always write your answers in your own words.

For examiner use only:

Problem	1	2	3	4	Total
Marks
Out of	10	10	20	20	60

Problem 1.

1. Suppose we have a priority queue PQ, implemented as a min-heap, containing

   n keys and some integer x.

   [5 marks]

   1: def foo(x)

   2:

   3:

   4:

   5:

   6:

   result ← 0

   while PQ.min() < x2 do temp ← PQ.remove_min() result ← result + temp2

   return result

   Analyze the time complexity of running foo.

2. We are given a set of items I = {i1, …, in} and sets S1, …, Sm containing subsets of these items, i.e., Sk ⊆ I for all 1 ≤ k ≤ m. The sets don’t have to contain the same number of items and an item may occur in multiple sets. We need to find the smallest set T ⊆ I of items such that we have at least one element from each set Sk (1 ≤ k ≤ m).

Example:

I = {i1, …, i6}

S1 = {i1, i2, i6}

S2 = {i2, i4, i5, i6}

S3 = {i2, i4}

In the example above, we can return T = {i2} as the smallest set of items such that we have at least one element from each set, since i2 is part of all three sets S1, S2, and S3. The set T = {i1, i4} also contains an element from each of the three sets, but it isn’t the smallest set with this property, as it contains two elements and {i2} contains only one.

Construct a counterexample to show that the following algorithm doesn’t com- pute the smallest set T: Sort the items by the number of sets that contain them (for ease of writing, we use |ij| to write the number of sets that contains the item ij) in decreasing order. For every item ij, if ij occurs in some Sk and no item in T is an element of Sk, we add ij to T.

[5 marks]

Problem 2. Consider the following edge weighted undirected graph:

A

3

B

9

C

3

D

15

16

4

16

6

11

7

E

1

F

6

G

5

H

Your task is to:

1. Compute the shortest path tree T of the graph starting from A. List the edges in

   T.

   [7 marks]

2. Indicate the order in which the edges are added by Dijkstra’s algorithm starting from A.

   (You do not have to explain your answer.)

   [3 marks]

   Problem 3. Recall that a forest is a graph where every connected component is a tree. We want to design a data structure for a fixed set of n vertices that allows us to add and remove edges, as well as efficiently answer the query: “Are vertex i and vertex j part of the same tree?” You can assume that we identify the vertices by their number and that each vertex has a unique number in the range 0 to n − 1 (or 1 to n if that’s easier for you).

   Your data structure should support the following operations:

   • initialize(n): construct the data structure for the n vertices without any edges. This method is called exactly once and only as the first operation in any execu- tion.

   • insert–edge(i, j): insert an undirected edge between vertex i and vertex j, if adding this edge doesn’t create cycles (otherwise, don’t add the edge)

   • remove–edge(i, j): remove the edge between vertex i and vertex j, if it exists

   • in–same–tree(i, j): return True if vertex i and vertex j are part of the same tree, and False otherwise (do not modify the data structure)

Example:

initialize(10) – creates the data structure for 10 vertices

in–same–tree(9,2) – returns False

insert–edge(2,6) – adds the edge between vertex 2 and vertex 6 insert–edge(9,6) – adds the edge between vertex 9 and vertex 6 insert–edge(9,2) – doesn’t do anything as this would create a cycle in–same–tree(9,2) – returns True

remove–edge(6,2) – removes the edge between vertex 6 and vertex 2 in–same–tree(9,2) – returns False

Your task is to come up with a data structure that uses O(n2) space. The ini– tialize, insert–edge, and remove–edge operations should run in O(n2) time. The in–same–tree operation should run in O(1) time. Remember to:

1. Describe your data structure implementation in plain English. [8 marks]

2. Prove the correctness of your data structure. [7 marks]

3. Analyze the time and space complexity of your data structure. [5 marks]

Problem 4. Silbo Gomero is a whistling language used in the border region of France and Spain by shepherds to communicate with each other. We want to determine the number of pairs of shepherds that can communicate using this language. More specifically, we are given the locations of the shepherds in an array A, where every location is represented by a distinct positive integer. For simplicity you can assume

that every shepherd whistles equally loudly and thus can cover the same distance d. Shepherds i and j can communicate with each other if |A[i] − A[j]| ≤ d, i.e., if the absolute difference between their locations is at most the distance they can cover by whistling. Recall that |x| equals x when x ≥ 0 and |x| equals −x if x < 0. You need to determine how many pairs of shepherds can communicate with each other.

Example:

When A = [4, 2, 12, 7] and d = 3, you should return 2, since |4 − 2| = 2 ≤ d and

|4 − 7| = 3 ≤ d and no other pair is at distance at most d from each other.

Your task is to give a divide and conquer algorithm for this problem that runs in

O(n log n) time. Remember to:

1. Describe your algorithm in plain English. [8 marks]

2. Prove the correctness of your algorithm. [7 marks]

3. Analyze the time complexity of your algorithm. [5 marks]

(Disclaimer: Silbo Gomero is an actual language and the background information given in the question is mostly accurate.)