关于算法:求解COP-5536

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:
2. Initialize (m): create a new m-way B+ tree
3. Insert (key, value)
4. Delete (key)
5. Search (key): returns the value associated with the key
6. 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.
7. 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
8. Submission
   Do not use nested directories. All your files must be in the first directory that appears after unzipping.
   You must submit the following:
9. 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)
10. Source Program: Provide comments.
11. 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.
12. 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.
13. 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.