闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

DSC 30 Final Project

General Requirements

1

. Office hours through Autograder and Zoom: You are only allowed to submit at most 2

tickets for debugging questions on the final project (autograder errors will not count).

We will count your opportunity as used if you asked any questions about the final

project in a session.

2

. Piazza: You can submit unlimited amounts of clarification questions in public posts

only. Private posts about the final project will not be answered. You are not allowed to

post your final project code in a piazza post unless being told to do so by an instructor.

Since all clarification questions are public posts, you are encouraged to search your

potential questions first before you make a new post.

3

. Others: You are not allowed to request help on the final project through other

approaches, including sending email to the instructors, or reaching the instructors

through social networks.

Note that these policies will only apply to the final project related questions. If you need help

from us for other reasons, feel free to contact us in the usual approach you prefer.

START EARLY!

Style Requirements

You will be graded on your code’s style according to the Style Guide.

IntelliJ has a great plugin to check your style automatically. Use it!

There are style considerations beyond indentation and such.

●

Choose names for test methods and for variables that are descriptive and useful when

you see them in the test output.

●

Consider writing helper methods if you repeatedly use the same set of statements.

Use Javadoc comments for descriptions of your methods and classes and inline

comments if the logic of your program is not captured by your variable names and the

natural flow of code.

Testing Requirements

For the final project, you are not required to submit any test cases, including JUnit test files

and main methods. However, we strongly recommend you to test your code thoroughly.

Think about the butterfly effect: a small mistake in one method will lead to a major failure of

the project.

Part 0: Setup

Starter Code

Our starter code will be distributed from the course GitHub repository.

Please follow the same procedures as before to get your starter code and set up IntelliJ.

Project Quiz

The final project quiz is a part of PA 10, thus its grade will be a part of PA 10 grade. Please

read the write-up of PA 10 for more details.

Part 1: Project Overview

In this project, you will implement a hybrid data structure (called FADAF, Part 4) that stores

key-data pairs with support of duplicate keys.

The goal of creating this new data structure is to achieve optimal time complexity for every

operation it supports by sacrificing space complexity. To achieve this goal, we will use a

combination of data structures we learned from this class as the backed structures. This new

data structure will be primarily backed by (thus you must use) a hash table (Chaining, Part 2),

and a binary search tree that supports duplicates (DAFTree, Part 3). If you want to use other

data structures for optimization, feel free to use the built-in ones (import from java.util.*

package), but you must implement Part 2 and 3, and use these two structures to implement

Part 4. This is an open-ended project, meaning that there are multiple valid implementations

for many methods. You should enhance the time complexity of all methods as best as you

can.

Note that the backed data structures in Part 2 and Part 3 are considered as helper classes.

Therefore, you will find that many methods will give access to the raw implementation details

(

such as tree nodes) publicly. With the same reasoning, you are allowed to add helper

methods with ANY access modifier (not confined to private anymore) in these two data

structures. However, the hybrid data structure in Part 4 will still NOT allow any public

exposure of implementation details, just like the usual data structures you have implemented

before.

You may reuse the codes from your previous PAs, readings, lectures, and exams to

save you some time. Make sure you have done the necessary modifications to fit

these codes in this assignment.

Part 2: Hash Table (Chaining)

Introduction

In PA 8, you have implemented a hash table that applies cuckoo hashing as the strategy to

address collisions. In this section, you will implement a hash table that applies the chaining

to resolve collisions. You may refer to the course materials for the specific algorithms of

chaining. For this implementation, we will use the LinkedList API from Java.util to express the

chain, and an array of LinkedList to express the table.

Another key difference between this hash table and the hash table in PA 8 is that our hash

table now supports Generics (<T>). In order to calculate the hash value for an unknown

generic type, we will use the hashCode() method in our hash function. The hashCode()

method is declared in the Java.lang.Object (parent class of ALL class by default), and

implemented in all common concrete classes (such as Integer, String, etc.). This method

returns the hash value of the given object that Java’s built-in hash tables can use. If you want

to use Java’s built-in hash tables for your self-defined classes or the instructed hash table

described below, these classes must overwrite the hashCode() method. You may read the

method descriptions below for how you should apply this method to this implementation.

Debugging Tip: Create a HashTable that stores Integer to test, since the hashCode of an

integer is just the integer itself which is easy to keep track of.

Implementation

All implementations of this part should be done in HashTable.java, and you must

complete all the following constructor and methods.

public HashTable(int capacity)

A constructor that initializes a hash table with specified capacity.

@

throws IllegalArgumentException if capacityis less than the minimum threshold (10)

public boolean insert(T value)

A method that inserts the value in the hash table. This method returns true if the value

is inserted, and false if the value is already present in the hash table. Before insertion,

this method checks if the load factor is greater than ⅔, and invokes rehash() if the

condition satisfies.

@

throws NullPointerException if the value is null

public boolean delete(T value)

A method that deletes the value from the hash table. This method returns true if the

value was in the hash table before deletion, and false if the value was not found.

@

throws NullPointerException if the value is null

public boolean lookup(T value)

A method that checks if the value is stored in the hash table. This method returns true

if the value is in the hash table, and false otherwise.

@

throws NullPointerException if the value is null

public int size()

A method that returns the total number of elements stored in the hash table.

public int capacity()

A method that returns the total capacity of the hash table.

private int hashValue(T value)

A method that calculates the hash value (expected index) of the value in the hash

table. This method calls the hashCode() of the value and mod by the capacity of the

hash table.

private void rehash()

A method that performs rehash when the condition is met. This method doubles the

capacity of the original table, and re-insert all values (not the chained list) present in

the old table by iterating through the old table.

You can add more helper methods with ANY access modifiers if you think they are

necessary for your implementation.

COMP3760/6760: Enterprise Systems Integration