﻿ comp2123|学霸联盟

# 一站式論文代寫,英国、美国、澳洲留学生Essay代寫—FreePass代写

comp2123

### 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 }

Problem 2. 一站式論文代寫,英国、美国、澳洲留学生Essay代寫—FreePass代写Consider the following edge weighted undirected graph: 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.

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

? remove-edge ( i, j ) : remove the edge between vertex i and vertex j, if it exists

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

insert-edge(2,6) - adds the edge between vertex 2 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:

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.

a)  Describe your algorithm in plain English.

b) Prove the correctness of your algorithm.

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

#### 在線客服  Essay_Cheery  