Data Structures and Algorithms. Computer Engineering Charles III
University of Madrid
Lab Case. COURSE 2018-2019
Creating a social network at the university.
The University has a project to create a new social network for University students by integrating social networks existing managed by departments and faculties.
The aim of the current exercise is to define and implement the different data structures and algorithms that support the social network according to the requirements specified in each of the following phases.
Phase 1
Given that, in a first stage, the social network will include users existing social networks, it is considered that these networks can be represent doubly linked list. The following are provided two classes ( which can not be modified or extended ).
● A Student class that stores information about each student. Their attributes are:
or e-mail : this is the email to the student network
Social. Each email is unique. That is, it can not have different students with the same email.
or city: city of residence.
or campus: (GETAFE, LEGANES, COLMENAREJO). It has been enum type one
defined, Campus within class Student.
or blocks : Students in the network can block other
forbid students to communicate with them. East attribute stores the number of times that this student has It has been blocked by other users.
or date_sign_in : The date on which the user is registered on the network Social. We have used the java.time.LocalDate class for
one Tutorial for creation of a enum type:
https://docs.oracle.com/javase/tutorial/java/javaOO/enum.html
two https://docs.oracle.com/javase/8/docs/api/java/time/LocalDate.html
two
represent data. This class does not store or represents one hour or time zone. Only
stores the year, month and day of a date.
● A StudentsList class that implements the IList interface. It contains all students registered in
a social network. The social network should not contain repeated students. For this reason, you
can see that methods addLast , addFirst and insertAt Always check if the student It exists or not, before adding it to the list. In this phase, you must implement a new class, ManageNetworkList, with
the following methods (these methods are also described in the interface IManageNetwork that has been provided):
1. Create a method called Union , linking two social networks
a single social network. That is, the method takes as input two objects the StudentsList and returns a new list containing first the Students from the first list, followed by students second list.
2. Create a method getCampusCity which takes as input a network
social (ie, an object of the class StudentsList) and an integer as opc parameter such that:
● If opc = 1: the method must return an object StudentsList contains all students residing in the same city the campus where they are studying.
● If you opt = 2: the method must return an object StudentsList contains all students residing in different cities the campus in studying.
Note: The order in the resulting list should be the same as in the list of entry.
3. Create a method locateByCity taking a social network (ie,
StudentsList object of the class) and a city name as input, and returns a list containing all
students (ie a StudentsList object of the class) living in that city. Note: The order in the resulting list should be the same as in the list of
entry.
4. Create a method orderBy that takes as input a social network (
Note 1.
ie, an object of the class StudentsList) and an integer parameter such opc what:
● If opt = 1, the method returns a new list of student (s ie, an object of the class StudentsList) sorted by order ascending by email.
● If OPC = 2, the method returns a new list of student (s ie, an object of the class StudentsList) sorted by order Descending by email.
You should implement a proprietary method based classification some of the sorted
algorithms (such as bubble sort).
3 http://www.java2novice.com/java-sorting-algorithms/
3
Note 2: Remember that you can not modify or extend the StudentsList class.
Therefore, if a helper method that help is needed to order list, including the method in ManageNetwork
class. Note 3.
The entry list can not be modified. The method must return a new list where students are ordered.
5. Create a method getStudentsByDateInterval , which takes as
Input a social network (an object of class StudentsList) and two dates (Start and end, which should be defined as objects java.time.LocalDate class) and returns a list of all students in the entry list whose record dates are in this date range. Please note the following comments:
to. start <= end.
b. Both dates are included in the range.
c. The order in the resulting list should be the same as in the list of
entry.
6. Create a table with the Big-O functions for each method
ManageNetwork class . A brief explanation of each method. Phase 2
As the number of students, the access time student searches by username increases limits unacceptable. To improve access time, a tree is provided binary search StudentsTree students to store a network Social determined ( you can not change! ) and BSTNode class with methods for working with nodes of binary search. The StudentsTree
class implements the interface iTree .
Create a class, ManageNetworkTree , including the following methods:
1. Create a method, copySocialNetwork , that takes as input a
StudentsTree object of the class and one object of the class StudentsList (Phase 1) and insert the list in the tree. The method must not return nothing.
2. Create a method getOrderedList, which takes as input an object of
the StudentsTree class and returns an object of class that StudentsList It contains all students
ordered by email in the tree. For get this list, you can not use any sorting algorithm (Such as bubble, etc.), you must traverse the tree recursively. Tip: You can use an assistant and recursive method that takes as input
BSTNode an object and an object of StudentsList, and return the students (ordered by email)
of this subtree.
3. Create a method deleteByNumberOfBlocks taking as input a
StudentsTree object and an integer n. The method should eliminate all students who have a number of blocks equal to or greater than n.
Tip can be used and an auxiliary recursive method, which takes as
one BSTNode input object and an integer n. In addition, you can use the remove the StudentsTree method to remove nodes.
4. The members of the social network also can be searched by their
logon date. It is the StudentsTree class structure Efficient Data for this type of search engines ?. Explain your answer. Yes is considered inefficient, describe a data structure more efficient to support this type of search engine.
Phase 3
One of the capabilities of social networking is to allow users to follow friends or people who share interesting content. There is need to provide a data structure that supports this capacity. As one might imagine, the most appropriate data structure is a graph. At this stage it is to provide an implementation of the social network based on a graph data structure. This should be called as
StudentGraph . To simplify the exercise, the graph only has to store emails from students (see Note). It should be borne in mind that University has more than 20 thousand students.
1. What kind of representation of graph is most suitable for so large number of potential users? Explain your answer.
2. Create a builder StudentGraph for taking as input a
array with emails of students enrolled in the social network. When an object of class StudentGraph is created, there will be no relationship between students. In other words, the method of constructor only stores the emails of students in the graph, without create any relationship between them.
3. Create a method addStuden t take as input an email and adds to the social network.
4. Create a method areFriends take as input two students
(Emails) and create a friendship between them. Be aware that the friendship is a symmetrical relationship.
5. Create a method getDirectFriends that as a student (email)
as input, returns an object of LinkedList
6. Create a method suggestedFriends such that, as a student (email)
as input, returns an object of LinkedList
Tip: Some of the graph traversal algorithms can be useful to implement the solution.
Note : In phase 3, strongly recommended that classes use is recommended Java Collections Framework (eg LinkedList), instead of using implementations arrays or lists. It’s a good opportunity to expand knowledge. Thus, for example, if it finally decides to implement a graph
based on adjacency lists, you could use a LinkedList of LinkedLists !, in Instead of using an array of LinkedList (as we have seen in our classes theory). Ask your teacher for help.
General instructions:
1. The lab should be performed by a team of two
students (which must belong to the same group of laboratory). In any case, teams with more than two members will be allowed. If not you have no partner to carry out the laboratory case, SE You MUST NOTIFY THE TEACHER AS SOON AS LABORATORY POSSIBLE.
2. A Java project is provided with various interfaces and classes implemented to They CAN NOT BE MODIFIED :
to. Phase 1:
■ interfaces: IList ( interface for a list of students).
IManageNetworkList , which defines a set of
methods what there is what implement in the ManageNetworkList class.
■ Classes: Studen t class containing the information the student in a social network. The DNode Y StudentsList classes , which implement a dual node and a list doubly linked storing objects students.
■ JUnit Test: ManageNetworkListTest, which helps validate whether your solution is correct.
b. Phase 2:
■ interfaces: IBSTNode , IBSTree interfaces for nodes and
tree binary search respectively. The IManageNetworkTre and interface contains a set of methods
what there is what implement in the ManageNetworkTree class .
■ Classes: BSTNode , StudentsTre e, which are classes for a node and a binary search tree Students stores.
■ JUnit Test: ManageNetworkTreeTest , It helps validate If your solution is correct.
c. Phase 3:
■ Interface: IManageNetworkGraph , which defines a
set of methods that must be implemented in the
ManageNetworkGraph class.
■ Classes: adjacent , It is an auxiliary class that stores the vertex index.
■ JUnit Test: ManageNetworkGraphTest , It helps validate If your solution is correct.
3. ONLY HAVE TO COMPLETE SE following classes: to. Phase 1: ManageNetworkList .
b. Phase 2: ManageNetworkTree .
c. Phase 3: ManageNetworkGraph.
4. Deliver before May 6 at am through the platform AulaGlobal. Upload a zip with the following files:
to. The lessons: ManageNetworkList.java, ManageNetworkTree.java, ManageNetworkGraph.java.
b. A document with answers to questions. Also I know
You may include those comments deemed necessary on its solution.
c. The name of the zip should be the concatenation of the NIA student group (eg “10002354_10004532.zip”).
5. JUnit test classes are important. The solution practice
You must pass these tests junit. Therefore, you must implement classes Given these test ( that can never be changed !!!). Solutions that do not take into account the conditions and restrictions JUnit tests, will not be evaluated .
6. Only one team member will be responsible for uploading the zip file
the AulaGlobal platform (in the created task called “Lab Case Submission “).
7. It is mandatory the two members of the group to attend a session
defense practice, which is scheduled for the week of 6 to 13 May (to be confirmed through AulaGlobal). For this reason, professor of laboratory test solution using students JUnit test (similar to test Junit provided). A method correct only consider if your JUnit test does not fail. In addition, teacher laboratory may ask about some details of implementation practice. Both members of the group should be involved in implementation of all phases and have a thorough knowledge of they.