Lab Assignment 3- Develop algorithms to find solutions to business problems in a timely manner; developing faster algorithms using low runtime complexity.


Lab Assignment 3/Lab Assessment 3.docx
Objectives

· Prepare a suitable data structure for a video hosting website.

· Prepare a suitable data structure for items with multiple properties.

· Implement binary search trees for searching data structure.

· Develop algorithms to find solutions to business problems in a timely manner; developing faster algorithms using low runtime complexity.

· Develop readable and documented algorithms for business applications.

· Develop video suggestion methods for video hosting websites.

Scenario

Your team is working on a video hosting website, similar to the likes of YouTube, Dailymotion, and so on, that has grown over time. The website had hundreds of videos and registered users earlier, but now has millions of videos and users. Due to its exponential growth, some of the solutions used for the problems of the past are the cause of the websites’s problems today. To solve these problems, the founders of the website have hired your team.

One of the issues is with the login system of the website, which uses an email address as the login id and a password. Although the website is available publicly, users are urged to register on the website so that they can use the extra features. With the growth in the number of registered users, login authentication has started to take more time. It has been discovered that most members are willing to accept some wait time while registering on the website, but they do not want to wait for the login process.

To overcome this problem, the founders need a faster data structure that will get the password from the data for a given login id (registered email address). They want this new data structure to be at least 10 times faster than the current data structure in terms of finding the password for the given login id.

You are also required to develop an algorithm that can find the member most similar to the logged-in member based on the videos watched by both of them. The company plans to use this data to offer video suggestions to the logged-in member.

What you need to know

You have been provided with the website’s old code files, which are MemberAccountOld.java and MemberDataOld.java, in your project folder. The old data structure contains two classes: MemberAccountOld and MemberDataOld. TheMemberAccountOld class contains information about each member, while the MemberDataOld class contains account details of all members in an array list structure. Inspect these classes for further detail. Your data structure and methods will be similar to these ones but much faster.

The video hosting website uses a 0-1 structure to keep track of the videos watched (0 for unwatched and 1 for watched videos) and linked lists to keep track of members who’ve watched that video.

For this project, arrays cannot be used due to increasing dimensions; members and videos. Stack and queue are not acceptable since you need to search over and over again to get any member record. So you should use list or search trees.

Time Complexity (Worst)

Access

Search

Insertion

Deletion

Singly-Linked List

O(n)

O(n)

O(1)

O(1)

Doubly-Linked List

O(n)

-O(n)

O(1)

O(1)

Hash Table

N/A

O(n)

O(n)

O(n)

Binary Search Tree

O(n)

O(n)

O(n)

O(n)

Red-Black Tree

O(log(n))

O(log(n))

O(log(n))

O(log(n))

Table 3.1

From the above time complexity table, your team has decided to use a red-black tree structure for both member data and the watched video data of each member. This structure will have an advantage over arrays and lists since members care about login and page load times; to achieve these goals you need to focus on the search performance of the data structure.

To find the most similar member, you need to calculate similarity between customers. In this project, you cannot use a matrix structure because its dimensions will expand exponentially, and the matrix will be sparse (containing a few “1” and mostly “0” values). Also, since only watched video ids are stored, a simple counter can be used as the similarity criteria as all data will be either 0 or 1.

However, you need to remember that, “0” values in the high-dimensional data should not be taken into account when evaluating the similarity between two members. This is because there will be millions of videos that the members would not have watched, and taking “0” values into account will base the similarity on what the two customers did not do in common, instead of what they did in common, thereby affecting the accuracy of the similarity method.

Taking all these considerations into account, your team has decided to use a simple counter, which will count the number of watched videos by two members, as the similarity criteria. This method is expected to meet the performance needs of the website.

Best Practices

· Find a suitable binary search API (a Red-black tree API, if possible) for Java or you can use TreeMap API. Search the Javadocs of the API and become familiar with its methods.

· Develop the methods similar to old classes providing appropriate java docs and algorithmic step explanations within the code.

· For easy readability, use full variable names instead of short 2-3 character abbreviation. For code reusability, develop separate methods when available.

Evaluate the existing data structure (MemberAccountOld.java and MemberDataOld.java), and develop variables and methods (including constructors, getters, and setters) for MemberDataNew.java and MemberAccountNew.java files similar to the old classes. Implement a red-black tree structure to ensure low runtime complexity.

Use the MemberDataTest.java file for runtime performance comparison. It will evaluate performances for two sets. The second test focuses on creating an unbalanced tree by using emails which have similar char sequences. Your structure needs to be at least 10 times faster to complete the project.

Task

Improve the speed of the existing login algorithm

Use the SimilarMember.java class method for calculating similarity and finding a similar member.

Create a getSimilarMember(MemberDataNew, String) method as the main method. Prepare variables for the getSimilarMember(MemberDataNew, MemberAccountNew) method and return the result.

Develop the getSimilarMember(MemberDataNew, MemberAccountNew) method to find the most similar member from the member list by comparing the given member account and list of all members. Use the findSimilarityIndex() method to calculate similarity.

Develop the findSimilarityIndex() method to find the similarity index, which is the number of the videos watched by both of them.

Task

Find the member most similar to the logged-in member.

Your customer wants you to develop a method that will find similar videos to a given video. They want it as a list or an array, ordered from the most similar video id to the least similar video id. Those videos will be used to provide suggestions for guest users and to suggest what to watch next on the website.

Lab Assignment 3/Provided Code/MemberAccountNew.java
Lab Assignment 3/Provided Code/MemberAccountNew.java
public class MemberAccountNew {
// Write your code here

}
Lab Assignment 3/Provided Code/MemberAccountOld.java
Lab Assignment 3/Provided Code/MemberAccountOld.java
import java . util . LinkedList ;

public class MemberAccountOld {

private String loginEmail ;
private String password ;
private long memberID ;
private LinkedList watchedList ; //will contained id of watched videos

public MemberAccountOld ( String loginEmail , String password , long memberID ) {
super ();
this . loginEmail = loginEmail ;
this . password = password ;
this . memberID = memberID ;
this . watchedList = new LinkedList ();
}

public String getLoginEmail () {
return loginEmail ;
}

public void setLoginEmail ( String loginEmail ) {
this . loginEmail = loginEmail ;
}

public String getPassword () {
return password ;
}

public void setPassword ( String password ) {
this . password = password ;
}

public long getMemberID () {
return memberID ;
}

public LinkedList getWatchedList () {
return watchedList ;
}

public void addWatchedVideo ( Long watchedVideoID ) {
watchedList . add ( watchedVideoID );
}

}
Lab Assignment 3/Provided Code/MemberDataNew.java
Lab Assignment 3/Provided Code/MemberDataNew.java
public class MemberDataNew {
// Write your code here

}
Lab Assignment 3/Provided Code/MemberDataOld.java
Lab Assignment 3/Provided Code/MemberDataOld.java
import java . util . ArrayList ;

public class MemberDataOld {

private ArrayList accountsList ;
private ArrayList emailList ;

public MemberDataOld () {
super ();
accountsList = new ArrayList ();
emailList = new ArrayList ();
}

public void addAccount ( MemberAccountOld account ) {
this . accountsList . add ( account );
this . emailList . add ( account . getLoginEmail ());
}

public MemberAccountOld getAccount ( String email ) {
int index = emailList . indexOf ( email );
return accountsList . get ( index );
}

}



This essay is written by:

Prof. SirMojo Verified writer

Finished papers: 435

Proficient in:

English, History, Business and Entrepreneurship, Nursing, Psychology, Management

You can get writing help to write an essay on these topics
100% plagiarism-free

Hire This Writer
© 2017 theacademicessays. All Rights Reserved. Design & Developed by theacademicessays.
How to Avoid Plagiarism
  • Use multiple resourses when assembling your essay
  • Use Plagiarism Checker to double check your essay
  • Get help from professional writers when not sure you can do it yourself
  • Do not copy and paste free to download essays
Get plagiarism free essay
Need Help? Chat with us
Loading...