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 PowCoder代写 加微信 powcoder
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代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com