COP 5536编程代做、代写Java，C++，Python程序语言

日期：2021-03-24 10:38

COP 5536 Spring 2021

Programming Project

Due Date: Apr 6

th, 2021, 11:59 pm EST

1. General

Problem description

The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage

context — in particular, file systems. In this project, you’re asked to develop and test a small degree B+

tree used for internal-memory dictionaries (i.e. the entire tree resides in main memory). The data is

given in the form (key, value) with no duplicates, you are required to implement an m-way B+ tree to

store the data pairs. Note that in a B+ tree only leaf nodes contain the actual values, and the leaves

should be linked into a doubly linked list. Your implementation should support the following

operations:

1. Initialize (m): create a new m-way B+ tree

2. Insert (key, value)

3. Delete (key)

4. Search (key): returns the value associated with the key

5. Search (key1, key2): returns values such that in the range key1 <= key <= key2

Programming Environment

You may use either Java or C++ for this project. Your program will be tested using the Java or g++/gcc

compiler on the thunder.cise.ufl.edu server. So, you should verify that it compiles and runs as expected

on this server, which may be accessed via the Internet.

Your submission must include a makefile that creates an executable file named bplustree.

2. Input and Output Requirements

Your program should execute using the following

For C/C++:

$ ./ bplustree file_name

For Java:

$ java bplustree file_name

Where file_name is the name of the file that has the input test data.

Input Format

The first line in the input file Initialize(m) means creating a B+ tree with the order m (note: m may be

different depending on input file). Each of the remaining lines specifies a B+ tree operation. The

following is an example of an input file:

Initialize(3)

Insert(21, 0.3534)

Insert(108, 31.907)

Insert(56089, 3.26)

Insert(234, 121.56)

Insert(4325, -109.23)

Delete (108)

Search(234)

Insert(102, 39.56)

Insert(65, -3.95)

Delete (102)

Delete (21)

Insert(106, -3.91)

Insert(23, 3.55)

Search(23, 99)

Insert(32, 0.02)

Insert(220, 3.55)

Search(33)

Delete (234)

Search(65)

You can use integer as the type of the key and float/double as the type of the value.

Output Format

For Initialize, Insert and Delete query you should not produce any output.

For a Search query you should output the results on a single line using commas to separate values. The

output for each search query should be on a new line. All output should go to a file named

“output_file.txt”. If a search query does not return anything you should output “Null”.

The following is the output file for the above input file:

121.56

3.55,-3.95

Null

-3.95

3. Submission

Do not use nested directories. All your files must be in the first directory that appears after unzipping.

You must submit the following:

1. Makefile: You must design your makefile such that ‘make’ command compiles the

source code and produces executable file. (For java class files that can be

run with java command)

2. Source Program: Provide comments.

3. REPORT:

· The report should be in PDF format.

· The report should contain your basic info: Name, UFID and UF Email account

· Present function prototypes showing the structure of your programs. Include the structure of your

program.

To submit, please compress all your files together using a zip utility and submit to the

Canvas system. You should look for Assignment Project for the submission.

Your submission should be named LastName_FirstName.zip.

Please make sure the name you provided is the same as the same that appears on the

Canvas system. Please do not submit directly to a TA. All email submissions will be

ignored without further notification. Please note that the due day is a hard

deadline. No late submission will be allowed. Any submission after the deadline

will not be accepted.

4. Grading Policy

Grading will be based on the correctness and efficiency of algorithms. Below are some details of

the grading policy.

Correct implementation and execution: 60%

Note: Your program will be graded based on the produced output. You must make sure to produce the

correct output to get points. Besides the example input/output file in this project description, there are

two extra test cases for TAs to test your code. Each one of the test case contributes 20% to the final

grade. Your program will not be graded if it can not be compiled or executed.

You will get 0 point in this part if your implementation is not B+ tree.

Comments and readability: 15%

Report: 25%

You will get 10% points deducted if you do not follow the input/output or submission requirements

above. In addition, we may ask you to demonstrate your projects.

5. Miscellaneous

• Do not use complex data structures provided by programming languages. You have to

implement B+ tree data structures on your own using primitive data structures such as pointers.

You must not use any B tree / B+ tree related libraries.

• Your implementation should be your own. You have to work by yourself for this assignment

(discussion is allowed). Your submission will be checked for plagiarism.