COMP 251 Algorithms and Data Structures

Exercise 2 (50 points). Building a Disjoint Set

We want to implement a disjoint set data structure with union and find operations.

template for this program is available on the course website and named DisjointSets. java.

Copyright By cscodehelp代写 加微信 cscodehelp

In this question, we model a partition of n elements with distinct integers ranging from O to n

(i.e. each element is represented by an integer in 0, •.

,n – 1,, and each integer in 0, • •• , n

represent one element). We choose to represent the disjoint sets with trees, and to implement the

forest of trees with an array named par. More precisely, the value stored in par [i] is parent of

the element i, and par li]==i when i is the root of the tree and thus the representative of the

disjoint set.

You will implement union by rank and the path compression technique seen in class. The rank is

an integer associated with each node. Initially (i.e. when the set contains one single object) its

value is O. Union operations link the root of the tree with smaller rank to the root of the tree

with larger rank. In the case where the rank of both trees is the same, the rank of the new root

increases by 1. You can implement the rank with a specific array (called rank) that has been

added to the template, or use the array par (this is tricky). Note that path compression does not

change the rank of a node.

Download the file DisjointSets. java, and complete the methods find(int i) as well as

union (int i, int j). The constructor takes one argument n (a strictly positive integer) that

indicates the number of elements in the partition, and initializes it by assigning a separate set to

each element.

The method find (int i) will return the representative of the disjoint set that contains i (do not

forget to implement path compression here!). The method union (int i,

int j) will merge the

set with smaller rank (for instance i) in the disjoint set with larger rank (in that case j). In that

case, the root of the tree containing i will become a child of the root of the tree containing j),

and return the representative (as an integer) of the new merged set. Do not forget to update the

ranks. In the case where the ranks are identical, you will merge i into j.

Once completed, compile and run the file DisjointSets. java. It should produce the output

available in the file unionfind. txt available on MyCourses.

Exercise 3 (90 points). Improving our discussion board

The teaching staff in Comp251 is really happy of how our discussion board (Ed) is working;

however, we believe there is one function missing. This function will allow us to identify important

topics (discussed in Ed) by filtering key words. In particular, given a list of messages posted in

Ed, we want a function that reports the words used by every single user on the discussion board.

This list must be sorted from most to least used word (i.e., the word with the highest frequency

must be the first one). In case of a frequency tie, the word needs to be sorted in alphabetical

Let’s see now some features of the discussion board posts. The list of post will be provided to

you as an array of strings (String[]), where every slot in the array will contain a message.

messages will have the following characteristics.

Each message is represented in Java as a String

Each message begins with a user’s name of no more than 20 characters.

After the name, each message continues with the content of that user’s post all in lower case.

The total number of characters across all messages, including spaces, will not exceed 2 * 106

Let’s see now two examples to make sure that everything is clear. Given the following list of

David no no no no nobody never

Jennifer why ever not

Parham no not never nobody

Shishir no never know nobody

Alvin why no nobody

Alvin nobody never know why nobody

David never no nobody

Jennifer never never nobody no

Your algorithm must return the array [no, nobody, never] (exactly in that order). Those

three words were used by every single user of our discussion board and they are reported in order

of frequency (i.e., “no” is the most frequent used word). In case of a tie, the order was decided

lexicographically.

Now, if the following list of post is given to you:

David comp

Maria music

Your algorithm must return an empty array [] given that any of the words in the post was

used by every single user.

For this question, you must implement your solution in the function Discussion _Board(String{]

posts) which is inside the class/ file A1_Q3. java. Please notice that for this question the correct-

ness and efficiency of your algorithm will be tested, then it is of your interest to code your solution

using the right algorithms and data-structures. Please notice that for this question, it is forbid-

den to create new classes.

程序代写 CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com