CSC 212 Recommending Friends on Social Networks Project

You must deliver:1. Source code submission to Web-CAT. You have to upload the following classes (and anyother classes you need) in a zipped file:• ArrayPQK.java• BSTMap.java• BSTSet.java• MGraph.java• Recommender.javaNotice that you should not upload the interfaces and classes given to you.The submission deadline is: 17/05/2021.You have to read and follow the following rules:1. The specification given in the assignment (class and interface names, and methodsignatures) must not be modified. Any change to the specification results in compilationerrors and consequently the mark zero.2. All data structures used in this assignment must be implemented by the student. Theuse of Java collections or any other data structures library is strictly forbidden. 3. The submitted software will be evaluated automatically using Web-Cat. 4. All submitted code will be automatically checked for similarity, and if plagiarism is confirmed penalties will apply.7. You may be selected for discussing your code with an examiner at the discretion of theteaching team. If the examiner concludes plagiarism has taken place, penalties will apply

note: i think I have more then 10 tries so we can still adjuest the answer till i get full marks

}
}
// Remove all keys from the set.
void clear();
// Search for the key k and return true if it ezists, false otherwise.
boolean exists (K k);
}
// Insert a new key if does not exist and return true. If k already
ezists, return false.
boolean insert (K k);
// Remove the key k if it exists and return true. If the key does not
ezist return false.
boolean remove (K k);
// Return an iterator that points to the minimum key. The iterator
moves according to the order of the keys.
Iterator minIt ();
public class BSTS et implements Set {
public BSTS et Node root; // Do not change this
// Return an iterator that points to the minimum key. The iterator
moves according to the order of the keys.
Iterator maxIt ();
public class BSTSetNode {
public X key;
public BSTSetNode left, right, next, prev;
public BSTSetNode (K key) {
this key
key;
left
right next prev= null;
}
3
Representing the social network
To represent the friendship graph, we use the following interface:
public interface Graph {
// Add a node to the graph if it does not exist and return true. If the
node already exists, return false.
boolean addNode (K 1);
// Check if i is a mode
boolean isNode (K 1);
// Add an edge to the graph if it does not exist and return true. If i
or do not exist or the edge (i, j) already exists, return false.
boolean addEdge (K i, K j);
// Check if (1, 3) is an edge.
CSC 212
Projectboolean isEdge (K 1. K j):
// Return the set of neighbors of node i. If i does not exist, the
method returns null.
Set neighb (K i);
// Return the degree (the number of neighbors) of mode i. If i does not
exist, the method returns -1.
int deg (K 1);
// Return an iterator over nodes in increasing order starting with the
smallest node.
Iterator nodes It ();
Instead of using an array of lists to represent the graph (adjacency list representation), we
use a map of sets. Each element in the map represents the set of neighbors of a node. Write
the class MGraph that implements the interface Graph using this representation:
public class MGraph implements Graph {
public Set nodes; // Do not change this
public Map adj; // Do not change this
4 The friends recommender
Write the class Recommender that implements the three friends recommendation methods dis-
cussed above:
public class Recommender {
// Read graph from file. The file is a test file where each line
contains an edge. The end and start of the
are separated
space (s) or tabs (see graph. tat).
public static Graph read (String filelane) {
return null;
}
// Return the top k recommended friends for user i using the popular
users method. If i does not exist, return null. In case of a tie,
users with the lowest id are selected.
public static PQK recommendDeg(
Graph g. Ki, int k) (
return null;
}
// Return the top k recommended friends for user using common
neighbors method. If i does not exist, return null. In case of a tie
users with the lowest id are selected.
public static PQK recommendCN (
Graph g. K i, int k) {
return null;
}
// Return the top k recommended friends for user using weighted
common neighbors method. If i does not exist, return null. In case
of a tie, users with the lowest id are selected.
CSC 212
Projectpublic static PQK recommend WCN (
Graph g. Ki, int k) {
return null;
}
5 Deliverable and rules
You must deliver:
1. Source code submission to Web-CAT. You have to upload the following classes (and any
other classes you need) in a zipped file:
• ArrayPQK.java
• BSTMap.java
• BSTSet.java
• MGraph.java
• Recommender.java
Notice that you should not upload the interfaces and classes given to you.
The submission deadline is: 17/05/2021.
You have to read and follow the following rules:
7
1. The specification given in the assignment (class and interface names, and method
signatures) must not be modified. Any change to the specification results in compilation
errors and consequently the mark zero.
2. All data structures used in this assignment must be implemented by the student. The
use of Java collections or any other data structures library is strictly forbidden.
3. This assignment is an individual assignment. Sharing code with other students will result
in harsh penalties.
4. Posting the code of the assignment or a link to it on public servers, social platforms or
any communication media including but not limited to Facebook, Twitter or WhatsApp
will result in disciplinary measures against any involved parties.
5. The submitted software will be evaluated automatically using Web-Cat.
6. All submitted code will be automatically checked for similarity, and if plagiarism is con-
firmed penalties will apply.
7. You may be selected for discussing your code with an examiner at the discretion of the
teaching team. If the examiner concludes plagiarism has taken place, penalties will apply.
CSC 212
ProjectCSC 212 Project
Recommending friends on social networks
Due date: 17/05/2022
Guidelines:
This is an individual assignment.
The assignment must be submitted to Web-CAT
1 Introduction
One of the main functionalities offered by online social platforms such as Facebook and Twitter
is the recommendation of new friends. This is achieved by utilizing various information about
the users, but the main factor used for recommending a new friend to a user is how well these
two users are connected. A social network such as Facebook can be represented as undirected
graph such as the one shown in Figure 1. We can use the information contained in the graph
to select the top candidate friends for a given user. There are many ways to do this, but we
will focus on three methods:
1. Popular users: In this method, we recommend the most popular users in the graph,
that is nodes with the highest degrees (number of neighbors).
Example 1. If we want to recommend 4 new friends for user 3 using the popular users
method, we recommend:
(a) User 8, which has degree 7.
(b) User 12, which has degree 5.
(c) User 4, which has degree 3.
(d) User 6, which has degree 3 (we break ties according to user ID).
2. Common neighbors: In this method, we recommend users who have the most common
friends with the user.
Example 2. If we want to recommend 4 new friends for user 3 using the common neigh-
bors method, we recommend:
(a) User 4, which has 2 common neighbors with 3, nodes 1 and 5.
(b) User 6, which has 2 common neighbors with 3, nodes 2 and 5.
(c) User 12, which has 1 common neighbor with 3, node 1.
(d) User 8, which has 0 common neighbors with 3 (we break ties according to user ID).CSC 212 Project
Recommending friends on social networks
Due date: 17/05/2022
Guidelines:
This is an individual assignment.
The assignment must be submitted to Web-CAT
1 Introduction
One of the main functionalities offered by online social platforms such as Facebook and Twitter
is the recommendation of new friends. This is achieved by utilizing various information about
the users, but the main factor used for recommending a new friend to a user is how well these
two users are connected. A social network such as Facebook can be represented as undirected
graph such as the one shown in Figure 1. We can use the information contained in the graph
to select the top candidate friends for a given user. There are many ways to do this, but we
will focus on three methods:
1. Popular users: In this method, we recommend the most popular users in the graph,
that is nodes with the highest degrees (number of neighbors).
Example 1. If we want to recommend 4 new friends for user 3 using the popular users
method, we recommend:
(a) User 8, which has degree 7.
(b) User 12, which has degree 5.
(c) User 4, which has degree 3.
(d) User 6, which has degree 3 (we break ties according to user ID).
2. Common neighbors: In this method, we recommend users who have the most common
friends with the user.
Example 2. If we want to recommend 4 new friends for user 3 using the common neigh-
bors method, we recommend:
(a) User 4, which has 2 common neighbors with 3, nodes 1 and 5.
(b) User 6, which has 2 common neighbors with 3, nodes 2 and 5.
(c) User 12, which has 1 common neighbor with 3, node 1.
(d) User 8, which has 0 common neighbors with 3 (we break ties according to user ID).3. Weighted common neighbors: This is similar to common neighbors, but we give less
weight to famous common neighbors. Namely, to each common neighbor, we assign the
weight 1/degree and then sum all weights.
Example 3. If we want to recommend 4 new friends for user 3 using the common neigh-
bors method, we recommend:
(a) User 6, which has weight 0.75 = 1/2 + 1/4.
(b) User 4, which has weight 0.50 = 1/4 + 1/4.
(c) User 12, which has weight 0.25 = 1/4.
(d) User 8, which has weight 0 (we break ties according to user ID).
Figure 1: Example of a graph representing a social network.
In this assignment, your are going to create data structures to represent graphs and use
them to implement these friend recommendation methods.
2 The data structures
In this section, we present the data structures necessary for this assignment.
2.1 Implementing a top k priority queue
To recommend top k users, we use a priority queue that keeps only the top k elements and
serves them in decreasing order of priority. For this, write the class ArrayPQK that implements
the interface PQK below.
public interface PQK {
// Return the length of the queue
int length();
// Enqueue a new element. The queue keeps the k elements with the
highest priority.
void enqueue (P pr, Te);
// Serve the element with the highest priority. In case of a tie apply
FIFO.
CSC 212
Project2.2 Implementing a map and a set
Pair serve ();
The class ArrayPQK takes the parameter k as parameter in the constructor:
public class ArrayPQK implements PQK {
public ArrayPQK (int k) {
}
2.2
Implementing a map and a set
In this step, you write a BST implementation of a map and a set. The Map interface is as follows:
public interface Map {
// Return the size of the map.
int size();
// Return true if the map is full.
boolean full();
// Remove all elements from the map.
void clear();
// Update the data of the key k if it exists and return true. If k does
not exist, the method returns false.
boolean update (K k, T e);
// Search for element with key k and returns a pair containing true and
its data if it exists. If k does not exist, the method returns
false and null.
Pair retrieve (K k);
// Insert a new element if does not exist and return true. If k already
exists, return false.
boolean insert (K k, T a);
// Remove the element with key k if it exists and return true. If the
element does not exist return false.
boolean remove (K k);
// Return an iterator that points to the minimum key. The iterator
moves according to the order of the keys.
Iterator minIt ();
// Return an iterator that points to the maximum key. The iterator
moves according to the order of the keys.
Iterator maxIt ();
Notice that this interface does not have a current element. The interface Iterator returned by
the methods minIt and maxIt allows to iterate over the elements of the map:
public interface Iterator {
// Returns true if the iterator is valid (points to an element), false
otherwise.
boolean isValid ();
CSC 212
Project2.2 Implementing a map and a set
|}
// Returns the current element and moves forward. This method can only
be called if the iterator is valid. If the iterator points to the
last element, it becomes invalid after the call.
T next();
// Returns the current element and moves backwards. This method can
only be called if the iterator is valid. If the iterator points to
the first element, it becomes invalid after the call.
T prev ();
Example 4. The following code shows how to use the iterator returned by minit and mazit to
print the elements of a map in increasing and decreasing order:
// Print in increasing
order
Iterator it1 = map.minit ();
while (st1.isValid ()) {
Pair pit1.next();
System.out.println (p. first + “\t” + p.second);
}
// Print in decreasing order
Iterator it2 = map.mazit ();
while (it.isValid ()) {
Pair p = 112.prev();
System.out.println (p.first + “\t” + p.second);
Write the class BSTMap that implements the interface Map:
public class BSTMap implements Map {
public BSTMap Node root; // Do not change this
The class node used inside BSTMap is as follows:
public class BSTMap Node {
public X key;
public T data;
public BSTMap Node left, right, next, prev;
public BSTMapMode (K key, T data) {
this key
this data
left right next prev= null;
key;
data;
The pointer next and prev point to the inorder following and preceding nodes respectively (that
is the keys immediately greater and immediately smaller).
The interface Set is similar to Map, except that it contains no data.
public interface Set {
// Return the size of the set.
int size();
CSC 212
// Return true if the set is full.
boolean full();
Project