BEST代写-线上编程学术专家

Best代写-最专业靠谱代写IT | CS | 留学生作业 | 编程代写Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代写

C++代写 | CSE 100 PA1: BST in C++

C++代写 | CSE 100 PA1: BST in C++

这个作业是用C++完成数据结构二叉搜索树

CSE 100 PA1: BST in C++

Checkpoint Deadline: Thursday, Jan. 16th, 11:59 pm

Final Deadline: Thursday, Jan. 23rd, 11:59 pm

Overview

  • In this project, you will be asked to implement some number of BST methods. This assignment is essentially a warmup on C++ programming in the STL. You should read these instructions carefully before you start writing code or post questions on piazza.
  • This is a Pair Programming project. You may ask Professors/TAs/Tutors for some guidance and help, but you can not copy code from anywhere including online sources such as Github. You may also discuss the assignment conceptually with your classmates, including bugs that you ran into and how you fixed them. However, do not look at or copy code, as this constitutes an Academic Integrity Violation. And you may not use other libraries’ implementations in your solutions.
  • For this assignment and the remainder of the course, you are expected to use Git to keep track of your code and Github to store your code. Make a private repository on Github, commit and push your code regularly as you go through the assignment.
  • There is a FAQ page for Docker and devcontainer setup issues please check this as well as existing Piazza posts before making your own post. Thank you!
  • Start early, submit early and often!

 

Pair Programming Partner Instructions

Academic Integrity and Honest Implementations

Retrieving Starter Code

Submitting Your PA

Style Requirement

Part 1 (Checkpoint): Implementing a Binary Search Tree in C++

Part 2 (Final Submission): Tree Balancing and Node Deletion

Part 3: Worksheet

Testing

Getting Help

Pair Programming Partner Instructions

If you wish to work with a partner, please be sure to read the guidelines for Pair Programming in the syllabus carefully.  Make sure to have both of the partners’ names on the headers of all files. Most importantly, make sure to submit your homework on Gradescope using only ONE of the accounts and do not forget to add the other teammate’s account into the submission.

https://sites.google.com/eng.ucsd.edu/100/programming-resources/pair-programming-guidelines

 

Academic Integrity and Honest Implementations

We will hand inspect all submissions and will use automated tools to look for plagiarism or deception.  Attempting to solve a problem by other than your own means will be treated as an Academic Integrity Violation.  This includes all the issues discussed in the Academic Integrity Agreement, but in addition, it covers deceptive implementations.  For example, if you use a library (create a library object and just reroute calls through that library object) rather than writing your own code, that’s seriously not okay and will be treated as dishonest work.

 

Retrieving Starter Code

To retrieve the starter code, go to this page. (If you have accidentally cloned starter code before Jan. 9th, make sure you re-download the latest starter code) :

https://github.com/CaoAssignments/cse100-wi20-pa1-bst-starter

 

Copy the git url of your repo from here after clicking “Clone or download” (make sure the URL you copied starts with https):

 

Then on your own machine or on ieng6 you can clone the repo like this:

git clone https://github.com/CaoAssignments/cse100-wi20-pa1-bst-starter

 

Now go back to GitHub and create your own private repository.

 

Now cd into the PA1 starter code repository you cloned earlier. Type “git remote -v”.

 

We’re going to remove the remote called origin, so we can then add your own GitHub repository as the new remote called origin: run “git remote remove origin”

 

If you now run “git remote -v” you should no longer see the remote called origin like you saw before. Now run the commands listed on your newly created git repo (be sure to replace the url in the screenshot below with the url to your repo).

 

(If your terminal did not ask you to log in upon executing this git clone command, double check that the repo is set to private.)

 

You should now see the PA1 starter code on your private GitHub repository. If you are working with a partner, add them as a collaborator on your private repository. First click the settings tab on your GitHub repository.

Then click Collaborators on the left and search for your partner’s github account.

Among the starter code files, only the following files are relevant to implementation and testing. You are required to only implement the underlined files, and you must leave all the other files unchanged, especially “main.cpp” and “mainInt.cpp”

 

In src/bst folder:

  • hpp
  • hpp
  • hpp

In test/bst folder:

  • cpp
  • cpp
  • cpp
  • cpp
  • cpp

In data/mainInput folder:

  • txt
  • txt
  • txt
  • txt
  • txt

In data/mainIntInput folder:

  • txt
  • txt
  • txt
  • txt

In the top level folder:

  • solution-main.executable
  • solution-mainInt.executable

 

To complete the assignment, you will modify the files in the starter code to provide full definitions for methods marked with // TODO. To see all of the TODO tags, you can run the command “grep -r TODO .” in your PA1 directory.

We personally recommend using grep like this as you can manipulate the arguments after “A” and “B” to get a good snapshot of what is required: grep -r -A 5 -B 5 TODO *

To search in VSCode, you can also use Ctrl+Shift+F or Cmd+Shift+F on mac

 

You can find all the relevant information about compiling your code and running tests in the README.md file of the starter code.

Submitting Your PA

You will be submitting your code using Gradescope through the Github submission option. You should have gotten enrolled in Gradescope by now (if not, please add your name to the appropriate piazza post ).

 

Instructions to submit your PA on Gradescope:

  1. Be sure to test your code on ieng6 or in the devcontainer.  We will be grading your code on the same environment as ieng6 and the devcontainer. There may be issues with compilers/etc if you only tested your code on your personal machine outside of a devcontainer using self-installed dependencies.
  2. Be sure to push the final version of your code to your private Github repository. (That will be the code you will submit if you are submitting using Github)
  3. Go to gradescope and find PA1 checkpoint/final submission. You may use either Upload  or Github to submit.

Upload: In the root directory of your PA1, run ./create_submission_zip.sh. The script will create a zip file named submission.zip, then simply drag the zip file to gradescope to finish the submission. It is very important that you use the submission script to generate zip file rather than uploading the entire directory, as some PA will contain files that are quite large.

 

Github: You will be asked to authorize your GitHub account if you haven’t done so before. After authorizing your account, choose the repo you pushed your final version of PA1 code to and the correct branch.

 

  1. Check the feedback from the autograder and make sure no compile errors appeared.
  2. If you are submitting with a partner, make sure that the student who submits adds the other student to the assignment.
  3. You can submit as many times as you like before the deadline: only your last submission will be counted.

 

Checkpoint Submission (Due Thursday, Jan. 16th, 11:59 pm):

When you have completed all of the requirements for the checkpoint submission (Part 1, everything except rebalance and delete). You should go to gradescope and find PA1 checkpoint submission. Only the files in your src and test folders will be graded.

Make sure your code can compile (running ‘meson build’ and ‘ninja -C build’ in project directory gives no error)

 

Final Submission (Due Thursday, Jan. 23rd, 11:59 pm) :

When you have completed all of the requirements for the final submission (All the parts). You should go to gradescope and find PA1 final assignments: PA1 Final Submission and WorkSheet.

Only the files in your src and test folders will be graded.

Make sure your code can compile. (running ‘meson build’ and ‘ninja -C build’ in project directory gives no error)

Style Requirement

Please follow the style guidelines below on course website.

https://sites.google.com/eng.ucsd.edu/100/style-guidelines/style-guidelines

 

When grading the PAs, there won’t be points specifically allocated for style, but bad style will result in up to 10 points deduction from the points you get in the other parts. (Bad style includes magic numbers, missing method headers and lacking inline comments etc.)

 

You have an auto formatter available to you (check the Readme.md for details), use it!

Part 1 (Checkpoint): Implementing a Binary Search Tree in C++

In this part of the assignment, you will implement the fundamental BST operations using concepts from the C++ Standard Template Library, which includes writing an iterator for it.

 

  1. Understand the code and write unit tests

 

Your first task is to review the concepts about BST and understand the starter code. Do not attempt to start writing code until you have a firm grasp of what the provided code does and what you are supposed to do with it. You are required to implement all the methods with TODO in the header (except for the copy constructor and deleteNode method, which you will implement for the final submission), make sure you read the details of each method below (Part 1.2).

 

We will use the GoogleTest framework to perform unit tests. You should first read the README.md in the starter code to get introduced. Then make sure you can understand the provided incomplete test files in the test folder. (All the unit tests files have a prefix “test_”)

 

It is important that you add your own unit tests there before you start implementing any code of your own. Try to avoid “big bang development” where you first try to finish all the code and then find out nothing works as expected. Instead, try to locate the easiest unit of functionality you need to implement and start writing tests for its expected behavior. Then implement the expected behavior of that simple unit and verify it by running your tests. After you’ve confirmed it works as expected, make a git commit to save your changes and move on to the second simplest unit, and repeat the process.

 

We suggest you familiarize yourself with the GoogleTest framework by writing tests for methods and classes that are already completed in the starter code. It is also a good way to get to understand the workings of those methods and classes.

 

  1. Implement methods in BSTNode.hpp, BSTIterator.hpp, and BST.hpp

 

Please first read and understand the purpose of each member variable at the top of the file. Do not modify any public method signatures. You may modify the private helper methods or add any additional member variables if needed.

 

BSTNode.hpp:

 

BSTNode(const Data & d)

Constructor. Initialize a BSTNode with the given Data item, with no parent and no children

 

BSTNode<Data>* successor()

Return the successor of this BSTNode in a BST. The successor of this BSTNode should have the smallest element that is larger than this BSTNode. The BST should be unchanged after the function call. If there is no successor, return nullptr. This method is used in the BSTIterator’s ++ operators to advance the iterator.  Moving iterator from the first element till the end should give you sorted data in the BST.

Note: Try to analyze different cases of successor() by examining the successor of all the nodes in an arbitrary BST that you draw.

 

BSTIterator.hpp:

 

bool operator==(BSTIterator<Data> const& other) const

Equality test operator. Two iterators are equal to each other if they contain the same BSTNode pointer.

 

bool operator!=(BSTIterator<Data> const& other) const

Inequality test operator.

 

BST.hpp:

 

bool insert (const Data& item)

Given a reference to a Data item, insert a copy of it in this BST. Return true if the item was successfully added to this BST, false if an item equal to this one was already in this BST. This means the BST should not allow duplicate insertion. The average runtime of this function must be O(logn).

Note: This function should use only the ‘<‘ operator when comparing Data items. The reason for this is that some data types do not have the other operators (>, <=, >=, etc.) overloaded. For safety reasons, it’s best to only use < to compare. Remember: given an element, you need to check if it’s less than, greater than, or equal to element in the BST. How can you do that with just the < operator?

 

iterator find (const Data& item) const

Find a Data item in the BST. Return an iterator pointing to the given item, or pointing past

the last node in the BST (an iterator containing nullptr) if not found. The average runtime must be O(logn).

Note: This function should use only the ‘<‘ operator when comparing Data items for the same reason above.

 

unsigned int size() const

Return the number of items currently in the BST.

 

int height() const

Return the height of the BST. Note that empty BST has height -1 and BST with only one node has height 0.

 

bool empty() const

Return true if the BST is empty, else false.

 

iterator begin() const

Return an iterator pointing to the first item in the BST (the smallest element in current BST). Implement this method by completing the private helper method first(), which finds the first element of this BST.

 

vector<Data> inorder() const

Perform an inorder traversal of this BST to collect the data of each node in ascending order to a vector. Consider using a helper function to implement it. You should not use iterator or successor() in this function, we will manually check this in grading your PA.

 

~BST()

Default destructor. Delete every node in this BST. Implement this method by completing the private helper method deleteAll().

 

Please read the Testing part below to understand how to test your code. You can also find the point distribution of this PA on that section as well.

 

By the time you submit PA1 checkpoint, please complete the following two surveys with each of them worth 1 point towards your PA1 checkpoint grade

  1. Pre-class survey: https://forms.gle/mjUPy353xXKGQroP6
  2. Week 1 reflection survey: https://forms.gle/LufA7BcPBe6YwSY68

Part 2 (Final Submission): Tree Balancing and Node Deletion

In this part of the assignment, you will extend your binary search tree implementation to add a few additional operations. The first is to balance a given BST, the second is to delete a single element from the BST.

  1. Understand the code and write tests first

First, read the requirements of each method below write unit tests to define and understand the expected behavior of the required functions.

  1. Implement methods in BST.hpp

Please do not modify any public method signatures. You may modify the private helper methods or add any additional member variables if needed.

BST.hpp:

BST(const BST<Data>& bst)

A copy constructor that creates a valid balanced BST with all the data in the given bst. This constructor should take one other BST, copy all its data and create a new set of BSTNodes to build a balanced version of that given BST. You may assume the current BST is empty (root is null) before the function call. The given BST should be left unchanged after the function call. You should implement this function by finishing the helper function buildSubtree().

Note: For a given set of data, there may be multiple valid balanced BST. However, for testing and grading purposes, your balanced BST from a given BST must be unique which follows the rule below:

For any subtree of the balanced BST, if the number of nodes in that subtree is even, there can be two median node within the subtree. In this case, you must pick the node with larger median data to be the root of the subtree. For example, if the given BST contains data 2,3,4,5, then the resulting BST should be:

It is important that you follow the rule above in your program to pass the tests in autograder. This means when given one arbitrary set of data, your balanced BST should be unique. If your function produce different balanced BST, you will not receive credits for this function.

BSTNode<Data>* buildSubtree(vector<Data>& data, int start, int end, int depth)

The helper function that recursively builds a balanced BST with the given data.

data: a vector of data used in building BST

start: the start index (inclusive) of the vector used to build the subtree

end: the end index (exclusive) of the vector used to build the subtree

Depth: the depth of recursion, used to update height

bool deleteNode(const Data& item)

Given a reference to a Data item, delete the copy of it in this BST. After the deletion, the BST should still be valid. Return true if the item was successfully deleted from this BST, false if an item equal to this one does not exist in this BST.

Note: There might be multiple correct ways to delete a node from a BST. However, for testing and grading purposes, your node deletion must follow the rules below in each case:

  1. Node to delete is a leaf node: Directly delete the node and no further modification of BST is needed.
  2. Node to delete has exactly one child: Connect the parent node to the child node and delete the current node.
  3. Node to delete has two children: Replace the current node’s data with its successor node’s data, and delete the successor node to avoid duplication.

It is important that you follow the rule above in your program to pass the tests in autograder. This means when deleting some elements in the BST, your resulting BST must be unique.

This function and all its helper functions should use only the ‘<‘ operator when comparing Data items for the same reason mentioned in insert() above.

Please read the Testing part below to understand how to test your code. You can also find the point distribution of this PA on that section as well.

When you submit your PA1 final submission, please complete this survey for your weekly reflection 2: https://forms.gle/CGB5t4hB9TBUtV7w7 . This survey is worth 1 point towards your PA1 final submission grade.

Part 3: Worksheet

Please print and complete the worksheet linked below. It will be submitted in pdf format as a separate assignment on gradescope. The worksheet is worth 5 points.

 

Note that the worksheet is an individual assignment, this means if you are working with a partner, you should not collaborate with your partner to finish the worksheet.

PA1 Worksheet

Testing

You will want to be sure to test your code at every step.  You should write your own tester (extend the provided testers based on the example).  Be sure to test every method, no matter how simple it is. Always start with simple cases in unit tests, as unit tests are extremely helpful for catching missed edge cases and any unintentional mistakes.  Use larger test cases only after your program passed on small and simple test cases.

Make good use of the provided tools, such as debugger and GDB. Try out the different tools in Readme.md to see how they can help you to test the program.

Additionally, make sure that your program has no memory leaks, as this will also lose points.  Be sure to remove any debugging output from your program before submitting as I/O is expensive and could make your program inefficient that might timeout the autograder.

  1. Unit tests and code coverage:

After you implemented each function, run your unit tests to see if you can pass your own tests. Make sure your unit tests cover all different cases of each function This includes edge cases like empty BST has height -1 or inserting an element into an empty BST. For information on how to compile and run the unit tests, you may refer to the README.md in the starter code.

 

In this PA, a small amount of extra credit will be added for you coverage report (you may refer to the Readme.md for how to generate the report). A code coverage report essentially measures the percentage of your code being executed in the test. You should be able to see your code coverage report similar to below:

Line Coverage: the percentage of lines of code executed in your tests

Functions: the percentage of functions executed in your tests

Branches: the percentage of branches (such as “if” and “else if “) executed in your tests

For checkpoint submission, the line coverage above (functions and branches won’t be graded) in bst directory should be at least 80% to get 1 extra point for coverage report.

For final submission, the line coverage in bst directory should be at least 90% to get 1 extra point for coverage report.

  1. Diffing outputs:

Important:

While the unit tests can verify the correctness of your program, passing comprehensive unit tests only means the outputs of your methods are more likely to be correct. In the autograder, all the tests will use the standard output of executables (such as main.cpp and mainInt.cpp) that are compiled using your solution code. Therefore, if you have any irrelevant cout or cerr statements that you added for debugging, they will mess up the autograder and you will receive 0 points!

Since your submission will ultimately be graded using the output of the executables, it is necessary that you compare your output to that of the reference solution. We’ve provided information on diffing outputs for checkpoint and final submission below.

Diffing outputs of your program and the reference program is exactly how we grade your assignment. Therefore, DO NOT CHANGE main.cpp and mainInt.cpp or you’ll not get any credit!

How to diff outputs using executable (checkpoint and final):

The main.cpp in test/bst folder is a program that takes an optional flag and two files: input and query file. The input file contains strings to insert in BST, and the query file contains strings to search in the BST. When the optional flag “-p” is entered, the program will additionally print the inorder traversal and iterator traversal of the data in BST.

Note that the flag “-p” should only be set when the input file is relatively small: as the program will print all the data in the input file, large file like “actors.txt” might make your program overflow the stdout.

First run the reference solution main with and without the flag to see the difference of the outputs:

./solution-main.executable -p data/mainInput/smallActors.txt data/mainInput/queryActors.txt

./solution-main.executable data/mainInput/actors.txt data/mainInput/queryActors.txt

(You should understand what the program is testing behind the scenes. Reading the main.cpp in the starter code is quite helpful. )

To compare your output to that of the reference solution, you should first run both programs on the same input and capture their output. For instance, without using the print flag “-p”, to get the output of reference solution for the BST program, you can run:

./solution-main.executable data/mainInput/actors.txt data/mainInput/queryActors.txt > ref-output.txt

For your own solution, after compiling your code, you can run:

./build/test/bst/main.cpp.executable data/mainInput/actors.txt data/mainInput/queryActors.txt > my-output.txt

To compare the outputs, you can use the diff command to see any differences.

diff ref-output.txt my-output.txt

Then you should diff the outputs with the print flag enabled to see any differences. You can try to mimic the provided input files to come up with your own test files.

In order to obtain points, your output should match exactly that of the reference solution, so be sure to address any differences you find! (As an extra security measure you can search for all occurrences of “cout” in your program)

How to diff outputs using executable (final):

The mainInt.cpp in test/bst folder is a program that can be used as an interactive console program. When you directly run the executable without any command line arguments, the program is in interactive mode as following (text marked in black are your inputs and text marked in blue are the program printouts):

./solution-mainInt.executable

GREETINGS! TYPE COMMANDS TO VISUALIZE YOUR BST.

INSERT 1

Insert: Successfully inserted value 1

INSERT 3

Insert: Successfully inserted value 3

INSERT 5

Insert: Successfully inserted value 5

FIND 2

Find: Value 2 not found!

EMPTY

Empty: false

BEGIN

Iterator: 1

NEXT

Iterator: 3

NEXT

Iterator: 5

NEXT

Iterator: Hit end of tree

NEXT

Iterator: Cannot traverse to next; hit end of tree

PRINT

Printing BST Structure

1

X               3

X       X       X       5

BALANCE

BST balanced

PRINT

Printing BST Structure

3

1       5

HEIGHT

Height: 1

SIZE

Size: 3

DELETE 5

Delete: Successfully deleted value 5

PRINT

Printing BST Structure

3

1       X

EXIT

mainInt.cpp.executable can also takes two files: input and output file. The input file contains commands you want to execute (text in black in the above example), and the program will output the program printouts (text in blue in the above example) to the output file.

Note: this program provides useful tools for visualization of small BST. When the PRINT command is given, the program will print the structure of BST. You should interpret the printouts as follows:

the element directly under current element: left child of current element

the element to the right of the left child: right child of current element

null child: represented as ‘X’

For example, the tree above will be represented as:

4

3            5

2     X     X     X

 

First run the reference solution mainInt to get the reference output file:

./solution-mainInt.executable data/mainIntInput/mainIntExample.txt ref-output.txt

 

Then, for your own solution, after compiling your code, you can run:

./build/test/bst/mainInt.cpp.executable data/mainIntInput/mainIntExample.txt my-output.txt

 

To compare the outputs, you can use the diff command to see any differences.

diff ref-output.txt my-output.txt

Then you should diff the outputs to see any differences. You can try to mimic the provided input files to come up with your own test files.

In order to obtain points, your output should match exactly that of the reference solution, so be sure to address any differences you find! (As an extra security measure you can search for all occurrences of “cout” in your program)

 

bestdaixie