算法代写 | Java代写 | CS146 Assignment 3

本次加拿大CS代写之Java代写数据结构Data Structure算法的主要内容是使用希表和哈希函数来模拟社交网站.

Data Structures and Algorithms, CS146, Spring 2019 Programming Assignment 3: Micro Version of Facebook Due at 11:59pm, on May 14th (Tuesday), 2019

(No late submission! 0 for late submissions and email submissions!)

Warning:

This programming assignment is for individual work only. You are not allowed to use someone’s code or copy from internet, except for Web Crawler code provided. Code plagiarism checker tools (Jplag, MOSS, etc.) will be used to check the similarity of codes. You may be asked to demo and explain your code to the instructor or to the class. Cheating will not be tolerated and will be reported to University. Please check on the University Policies in the syllabus.

Read this instruction carefully before your design and implementation of your work.

Problem Statements

Facebook is a very popular web based social media application. In this programming assignment,

you will use Hash Table and Hashing Functions to design and implement a micro-version of

Facebook.

Specifically, your program must provide options (or GUI) for users to choose the following

operations:

1. Create a person record of the specified name. (You may assume that no two people have the

same name.)

2. Record a person as a new friend. (Make a friend.)

3. Remove a person from the friend list. (Unfriend)

4. Search a person’s name to list his/her friend list. (he/she may or may not be your friend.)

5. Enter two person’s names to check whether the two people are friends. (Print “Yes” or “No”)

Functional Requirements

1. (-20%) For this programming assignment, your job is to design and implement a micro

version of Facebook using Hash Table. The Hash table MUST contain minimum 10 slots

and maximum 15 slots. At least 50 distinct users must be stored in the table by using a

hash function. Other size of table and users will be considered violating functional

requirements and 0 point will be given.

2. (-30%) The following 50 distinct popular names must be used to test your program. You may

do your own way to make friendships for these people. (Remember that you have to convert

a name to a natural number for hashing purpose)

1/5 Rank

Male name

Female name

1

Liam

Emma

2

Noah

Olivia

3

William

Ava

4

James

Isabella

5

Logan

Sophia

6

Benjamin

Mia

7

Mason

Charlotte

8

Elijah

Amelia

9

Oliver

Evelyn

10

Jacob

Abigail

11

Lucas

Harper

12

Michael

Emily

13

Alexander

Elizabeth

14

Ethan

Avery

15

Daniel

Sofia

16

Matthew

Ella

17

Aiden

Madison

18

Henry

Scarlett

19

Joseph

Victoria

20

Jackson

Aria

21

Samuel

Grace

22

Sebastian

Chloe

23

David

Camila

24

Carter

Penelope

25

Wyatt

Riley

3. Using Hashing with Chaining (page 258 in textbook):

3.1 Design and implement your own Division Method Hash Function: (Must show and screenshot the content/result of hash table for each of the following functional requirements)

a) Define a “Person” class which has one field for the name and another field for the linked list of friends. (You may assume that no two people have the same name.) (-20%)

b) Store the friends of each person in a linked list. A linked list class must be created by yourself. (-20%)

c) Create a global hash table that indexes each Person object under the name and show the result of hash table. (-30%)

d) Record a person as a new friend. (Make a friend.)
(-20%)

i. Chained-Hash-Insert(T,x)

2/5 e) Remove a person from the friend list. (Unfriend) (-20%)

i. Chained-Hash-Delete(T,x)

f) Search a person’s name to list his/her friend list. (he/she may or may not be your friend.)
(-20%)

i. Chained-Hash-Search(T,k)

g) Enter two person’s names to check whether the two people are friends. (Print “Yes” or “No”) (-20%)

3.2 Design and implement your own Multiplication Method Hash Function: (Must show and screenshot the content/result of hash table for each of the following functional requirements)

a) Derive from 3.1.a

b) Derive from 3.1.b

c) Create a global hash table that indexes each Person object under the name and show the result of hash table. (-30%)

d) Record a person as a new friend. (Make a friend.)
(-20%)

i. Chained-Hash-Insert(T,x)

e) Remove a person from the friend list. (Unfriend) (-20%)

ii. Chained-Hash-Delete(T,x)

f) Search a person’s name to list his/her friend list. (he/she may or may not be your friend.)
(-20%)

iii. Chained-Hash-Search(T,k)

g) Enter two person’s names to check whether the two people are friends. (Print “Yes” or “No”) (-20%)

Programming Requirements

1. The program MUST be written in Java. (Any other codes will be treated as failing requirements and will receive 0 points.)

2. Each java file/class/subroutine/function call MUST contain a header comment at the beginning of each and make sure you have enough comments at the end of lines in your code. (-20 points if your code did not provide enough comments.)

3. You MUST write a professional/formal report in MS Word/PDF format with the following items included in the report: (You will receive 0 point for this assignment if a report is not provided.)

a) Cover Page – PA2 Title and your name (-10%)

3/5 b) Design and Implementation: (Ranging -20% ~ -40%) Briefly explain/illustrate how you design and implement your Hash Table and Hash Functions. such as diagram, graph, data structure, (Array, ArrayList, Linked List, Vector, etc.).

c) A list of classes/subroutines/function calls: (-30%) Explain purpose for each.

d) Self-testing screen shots: (ranging -50% ~ -100%) Provide enough screen shots for each function including inputs and outputs for each of function listed in “Functional Requirements” section. This is to verify your codes and to check to see if your codes match the functional requirements and run correctly by yourself. (You will receive 0 point if no self-testing screenshots provided. Points will be taken off if not enough self-testing screen shots provided.)

e) The procedure (step by step) of how to unzip your files, install your application, and run/test your codes. (-20% if not provided)

f) Problems encountered during the implementation: Describe all problems found/encountered during your implementation and how you resolved them. (-30% if not provided or too simple.)

g) Lessons Learned: Describe the concepts and skills you have learned from this programming assignment and any inspiration or motivation you got from this programming assignment. (-30% if not provided or too simple.) Submission Requirements:

1. Zip all your files including your formal report pdf file, all *.java files and a Java executable file (a jar file, so that I can run your code) into one zipped file with file name: PA3-Secion 8-Last_Name.zip, Any file with incorrect file name will not be accepted and 0 point will be given. [No jar file or your code is not runnable (test it before submission: java -jar filename.jar): -100 points]

2. The deadline to submit/upload your zip file to Canvas is before 11:59pm on Tuesday, 5/14/2019. After deadline, the submission link will be closed.

Warning: DO NOT wait until the last minute to upload your files to Canvas. It has been happening all the time that it took forever to upload files to Canvas during the last hour/minute. No excuse for late submission.

4/5 Grading Criteria Grading is based on the creative design, full functioning, completeness and clarity of codes and the professional report. Each grading policy is specifically listed after each functional item above. You should follow the functional requirements to avoid losing points. Extra bonus points will be given to additional/excellent work.

Note: Eclipse with JDK 8 under can export project into Runnable Jar, but not JDK 9.

If you jar file is not runnable when I click on it, it is OK as long as it can be runnable when I use commend window and type “java -jar name.jar”

5/5