锐客网

  1. 首页 > it技术 > >

求解COP 5536

算法

【求解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.

    推荐阅读


    上一篇：数据库|logstash同步mysql数据至elastic

    下一篇：对象、数组的遍历方法总结