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

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

C语言数据结构代写|Exercise 2

C语言数据结构代写|Exercise 2

本次英国代写是一个C语言数据结构的assignment

This exercise has total 15 points. Each point amounts to one percent of the total module
mark. You are not allowed to use any external library in your code. We might ask you to
explain your code.

All assessment deadlines in this module are strict. Late submissions will get a mark of 0. All
submissions must work on the virtual machine as specified.

This exercise addresses the challenges in concurrent programming. It will use the Binary
Search Tree (BST) data structure that you have implemented in Exercise1. Multiple
concurrent threads will perform read/write operations on the BST data structure.

Before you start Ubuntu, please set the number of processors to 2 from VM

VirtualBox Manager–>Settings–>System–>Processor.

If you are using UTM, right-click on your virtual machine edit->system->show
advanced settings and set CPU cores to 2.

After this change, if you run the ‘lscpu’ command from a terminal, it should show the
number of CPUs = 2.

Part 1:

Use your BST code (bst.c file) from Exercise1 and add the following new functionalities.
Please, not that the header file has changed in this assignment, and you may need to adapt
your code. You may add helper functions to the bst.c file.

Task 1.1 Node* balanceTree(Node* root);

This function creates a new balanced BST from an input BST. Note that the BST in Exercise1
is unbalanced. See the tips section on how to create a balanced BST in page 5.

Task 1.2 int sumSubtree(Node *N);

This function returns the sum of all the nodes. For example, if you pass the root of a BST, the
function will return the sum of all nodes that are present in the tree. The algorithm for this
function will be somewhat similar to printSubtree() as both functions perform complete tree
traversal; printSubtree() prints the node-values whereas sumSubtree() accumulates the
node values.

Inside the main() function in test_bst.c file, sums of an unbalanced BST and its equivalent
balanced BST are computed. If the implementation is correct, both sums will be equal.

[Optional: Observe the clock cycle counts for the two sum calculations in main(). In both
cases, sumSubtree() visits the same number of nodes. So, in ‘theory’, both sum calculations
should roughly consume the same number of cycles. In ‘practice’, do you see any difference
in the cycle counts? If you see a difference, what could be the reason? You do not have to
submit your answers for this optional question. (run “make cycle” to do this experiment)]

Part 2:

Assume that a server machine manages a BST data structure. During the day-time, many
clients perform operations on the BST. Each client sends its BST-commands in the form of a
command- file to the server.

Valid commands that can be executed by the clients are:

(1) insertNode <some unsigned int value>
The server will insert the node with the specified value in the tree. Note that this operation
modifies the BST.

The server also prints a log using printf() in the format of

“[ClientName]insertNode <SomeNumber>\n”

(2) deleteNode <some unsigned int value>

The server will delete the node with the specified value from the tree. Note that this
operation modifies the BST.

The server also prints a log using printf() in the format of

“[ClientName]deleteNode <SomeNumber>\n”

(3) countNodes

The server will count the current number of nodes in the BST and print the number on the
display. Note that this operation does not modify the BST.

The server also prints a log using printf() in the format of

“[ClientName]countNodes = <SomeNumber>\n”

(4) sumSubtree

The server will compute the sum of all the nodes that are present in the BST and print the
sum on the display. Note that this operation does not modify the BST.

The server also prints a log using printf() in the format of “[ClientName]sumSubtree =
<SomeNumber>\n”

bestdaixie

评论已关闭。