闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

FIT3155 S2/2022: Assignment 3

Question 1: B-tree [5 Marks]

In this question you will be writing a program that implements an in-memory1 construction of a B-tree data structure, with supporting operations that you have learnt in your lecture (Week 8). Your program takes three arguments:

1. Minimum degree parameter t > 2 of the B-tree. (Only exemption to this minimum degree is the root node.)

2. An input text ﬁle (dictionary .txt) containing a list of distinct words in some random order. All words in this ﬁle are strings of ASCII characters, in one-word-per-line format (see example below).

3. Another input ﬁle (commands .txt) specifying a sequence of either insert <someword> or delete <someword> commands, which need to be applied on the constructed B-tree. (See example below.)

❼ That is, starting from the B-tree constructed on words in the input dictionary .txt,

these commands should be carried out on the current state of the B-tree, executed one-by-one in sequence they appear in commands .txt.

❼ Note, if any command asks you to either insert <someword> that is already in

a B-tree or delete <someword> not in the B-tree, your program should recognize these events and ignore them, by searching for that word in the current state of the B-tree (before deciding to execute any speciﬁed command.)

After executing the commands, your program has to traverse the ﬁnal state of the B-tree (after executing the sequence of commands) and output the sorted list of words contained in the B-tree (one word per line; see example below).

Strictly follow the speciﬁcation below to address this question:

Program name: btree .py

Arguments to your program: As enumerated above, the inputs are:

1. t (minimum B-tree node degree parameter)

2. dictionary.txt (containing list of distinct words (ASCII strings) in some random order, one per line; see example below).

3. commands.txt (sequence of insert/delete commands, one command per line; see example below).

Command line usage of your script:

btree <t> <dictionary .txt> <commands .txt>

Output ﬁle name: output btree .txt (containing sorted words derived by traversing the B- tree)

❼ Important: The sorted order of words is based on ASCII values of characters within

those words/strings. Internally, when constructing the B-tree, you will have to maintain the B-tree’s search order on the same criterion.

Examples

dictionary.txt commands.txt output btree.txt

schmaltzy	delete Ascension	Abstemious
replica	insert Abstemious	Addend
Ascension	delete syzygy	Capitalize
cascades	insert synchs	Libation
abscissas	delete slicks	Winch
replicate		abscissas
Capitalize		capital
capital		cascades
dairying		dairying
hearties		hearties
Winch		replica
Libation		replicate
summarize		schmaltzy
slicks		summarize
Addend		synchs
ventilated synchs		ventilated

Question 2: Yet another integer code [5 Marks]

Background: A full binary tree is a binary tree where each internal node has exactly two children. Full binary trees can be enumerated systematically in the increasing order of their number of internal nodes, as follows:

The number of full binary trees with 0 internal nodes is 1 (see ﬁrst row of the illustration above). The number of full binary trees with 1 internal node is also 1 (see second row). The number of full binary trees with 2 internal nodes is 2 (see third row). The number of full binary trees with 3 internal nodes is 5 (see fourth row). The number of full binary trees with 4 internal nodes is 14 (see ﬁfth row, which shows the ﬁrst 6 of 14). In general, the number of full binary trees with Ninternal internal nodes is given by the formula .

One could uniquely associate a variable-length bit string with each full binary tree, based on its pre-order traversal. In such a traversal, an internal node is associated with bit 0, and a leaf node is associated with bit 1. The illustration above gives the bit string underneath each tree corresponding to the pre-order traversal of that tree.

Furthermore, in the illustration above, in each row, notice that the bit strings corresponding to trees containing the same number of internal nodes are of the same length and appear in a lexicographically sorted order.

Based on this background, the goal of this exercise is as follows. Given some MAXNinternal , enumerate the full binary trees (represented by bit strings derived from their traversals) in the increasing order of their internal nodes in the range [0, MAXNinternal]. That is, for each Ninternal e [0, MAXNinternal], the bit strings (corresponding to full binary trees containing Ninternal ) are enumerated lexicographically. See example below.

Strictly follow the speciﬁcation below to address this question:

Program name: treecode .py

Argument to your program: MAXNinternal (Assume MAXNinternal < 10.)

Command line usage of your script:

treecode.py <MAXN internal>

Output ﬁle name: output treecode .txt

❼ Output format of each line of the output:

❼ Example output for MAXNinternal = 4 (meaning, we are enumerating trees lexico-

graphically with {0, 1, 2, 3, 4} internal nodes):