Computer Science EXAMINATION Semester 1- Main, 2021 comp2123 Data Structures and Algorithms

EXAM WRITING TIME: 2 hours READING TIME: 10 minutes

Problem 1.

       a）Suppose we have a priority queue PQ, implemented as a min-heap, containing n keys and some integer x. 1: def foo(x) 2: result ← 0 3: while PQ.min() < x 2 do 4: temp ← PQ.remove_min() 5: result ← result + temp 2 6: return result Analyze the time complexity of running foo.

        b）We are given a set of items I = { i 1 ,...,i n } and sets S 1 ,...,S m containing subsets of these items, i.e., S k ⊆ 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 S k (1 ≤ k ≤ m).

Example:

I = { i 1 ,...,i 6 } 

S 1 = { i 1 ,i 2 ,i 6 } 

S 2 = { i 2 ,i 4 ,i 5 ,i 6}

In the example above, we can return T = { i 2 } as the smallest set of items such that we have at least one element from each set, since i 2 is part of all three sets S 1 , S 2 , and S 3 . The set T = { i 1 ,i 4 } 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 { i 2 } 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 | i j | to write the number of sets that contains the item i j ) in decreasing order. For every item i j , if i j occurs in some S k and no item in T is an element of S k , we add i j to T.

1: def SmallestSet(S 1 ,...,S m , I) 2: T ← [ ] 3: Sort I by the number of sets that contains each item in decreasing order and renumber such that | i 1 | ≥ | i 2 | ≥ ... ≥ | i n | 4: for j ← 1; j ≤ n; j++ do 5: if i j is part of some S k and no other item in T is part of S k then 6: T ← T ∪ i j 7: return T

Problem 2. Consider the following edge weighted undirected graph:

Your task is to:

Compute the shortest path tree T of the graph starting from A. List the edges in T. a) [3marks] Indicate the order in which the edges are added by Dijkstra’s algorithm starting from A.

 b) (You do not have to explain your answer.)

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 ( n 2 ) space. The ini- tialize, insert-edge, and remove-edge operations should run in O ( n 2 ) time. The in-same-tree operation should run in O ( 1 ) time. Remember to:

a) Describe your data structure implementation in plain English. 

b) Prove the correctness of your data structure.

 c)Analyze the time and space complexity of your data structure.

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 ( nlogn ) time. Remember to: 

a)  Describe your algorithm in plain English. 

b) Prove the correctness of your algorithm. 

c) Analyze the time complexity of your algorithm. 

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