# Python算法设计代写 | FIT2004 S1/2021: Assignment 3 – Tries and Trees

This assignment achieves the Learning Outcomes of:

1) Analyse general problem solving strategies and algorithmic paradigms, and apply them
to solving new problems;

2) Prove correctness of programs, analyse their space and time complexities;

4) Develop and implement algorithms to solve computational problems.
In addition, you will develop the following employability skills:

Text comprehension

Designing test cases

In order to be successful in this assessment, the following steps are provided as a suggestion.
This is an approach which will be useful to you both in future units, and in industry.

1. Read the assignment speciﬁcation as soon as possible and write out a list of questions

2. Clarify these questions. You can go to a consultation, talk to your tutor, discuss the tasks
with friends or ask in the forums.

3. As soon as possible, start thinking about the problems in the assignment.

It is strongly recommended that you do not write code until you have a solid feeling
for how the problem works and how you will solve it.

4. Writing down small examples and solving them by hand is an excellent tool for coming
to a better understanding of the problem.

As you are doing this, you will also get a feel for the kinds of edge cases your code
will have to deal with.

5. Write down a high level description of the algorithm you will use.

6. Determine the complexity of your algorithm idea, ensuring it meets the requirements.

1. Think of test cases that you can use to check if your algorithm works.

Use the edge cases you found during the previous phase to inspire your test cases.
It is also a good idea to generate large random test cases.
Sharing test cases is allowed, as it is not helping solve the assignment.

2. Code up your algorithm, (remember decomposition and comments) and test it on the
tests you have thought of.

3. Try to break your code. Think of what kinds of inputs you could be presented with which
your code might not be able to handle.

Large inputs
Small inputs
Inputs with strange properties
What if everything is the same?
What if everything is diﬀerent?
etc…

Make sure that the input/output format of your code matches the speciﬁcation.
Make sure your ﬁlenames match the speciﬁcation.
Make sure your functions are named correctly and take the correct inputs.
Make sure you zip your ﬁles correctly (if required)

For this assignment (and all assignments in this unit) you are required to document and com-
ment your code appropriately. This documentation/commenting must consist of (but is not
limited to)

For each function, high level description of that function. This should be a one or two
sentence explanation of what this function does. One good way of presenting this infor-
mation is by specifying what the input to the function is, and what output the function
produces (if appropriate)

For each function, the Big-O complexity of that function, in terms of the input. Make
sure you specify what the variables involved in your complexity refer to. Remember that
the complexity of a function includes the complexity of any function calls it makes.

Within functions, comments where appropriate. Generally speaking, you would comment
complicated lines of code (which you should try to minimise) or a large block of code
which performs a clear and distinct task (often blocks like this are good candidates to be
their own functions!).

Consider the problem of determining how many words in a text appear lexicographically later
than a given word. To solve this problem, you will write a function lex_pos(text, queries).

text is an unsorted list of strings. Each string contains only lowercase a-z characters. text
can contain duplicates.
queries is a list of strings consisting only of lowercase a-z characters. Each string in queries
is a preﬁx of some string in text (note that a string is a preﬁx of itself).

lex_pos outputs a list of numbers. The i
th number in this list is the number of words in text
which are lexicographically greater than the i
th element of queries

text = [“aaa”,”bab”,”aba”,”baa”,”baa”,”aab”,”bab”]
queries = [“”, “a”, “b”, “aab”]
lex_pos(text, queries)
>>> [7, 7, 4, 5]

Remember that string comparison is not considered O(1) in this unit.
lex_pos should run in O(T + Q) time, where
 T is the sum of the number of characters in all strings in text
 Q is the total number of characters in queries

Suppose we have two lookup tables (stored as AVL trees). We want to create a new lookup
table which contains all the data from both, except we have discovered that some data in one
of the tables are corrupted, and we want to exclude those from the result. The number of
corrupted items is very small relative to the total number of items in either table.

Importantly, all the keys in one of the tables are lesser than all the keys in the other. Corrupted
items only appear in the table with lesser keys.

Nathan has ﬁgured out a way to solve the problem using the normal AVL tree insert and delete
operations:

For each corrupted element, delete it from the corrupted table. Once all the corrupted elements
have been removed from this table, insert each remaining element into the other table.

Your task is to come up with a more eﬃcient way to solve this problem. You will be given code
for an AVLtree class, with the methods insert(key) and delete(key) already implemented.
You need to implement a method of the AVLTree class, uncorrupted_merge(self, other,
corrupted) which solves this problem.

other is an instance of AVLTree. Note that since this is a method of AVLTree, self is also an
instance of AVLTree.

corrupted is a list of keys. Every item in corrupted appears in other. The number of items
in corrupted is much smaller than the number of items in other and self

uncorrupted_merge modiﬁes self so that it contains all the elements it originally contained,
as well as all the elements in other which are not in corrupted. At the end, it must still be a
valid AVL tree.

Download the AVL tree implementation found here. You may not modify any of the existing
methods, but you may add new methods (in addition to the required uncorrupted_merge).
You must submit a modiﬁed version of this ﬁle as your avl_tree.py.

To test your code, we will create two instances of AVLTree from avl_tree.py, and then call
uncorrupted_merge.

It is important that your implementation not rely on modifying the existing code in the AVL
tree implementation, since we need to know how to access the internals of the tree for testing
purposes.