Department of Computing and Information Systems
COMP10002 Foundations of Algorithms
Semester 2, 2014
Assignment 2
Learning Outcomes
In this project you will demonstrate your understanding of dynamic memory and linked data structures.
You will also extend your skills in terms of program design, testing, and debugging.
Trees, Trees, Trees
The Binary Search Tree (BST) is a linked data structure that can be used to implement a dictionary data
structure. In this project you will write an “interpreter” that manipulates items in a BST, supporting a
small number of operations such as inserting and printing.
To get started, copy and study the program ass2-skel.c linked from the assignment FAQ page at
http://people.eng.unimelb.edu.au/ammoffat/teaching/10002/ass2/. The FAQ page is also
linked from the LMS. The skeleton program compiles cleanly, and provides the framework necessary for
a simple “language” for manipulating binary search trees.
Commands in this language are all one letter long, and have either zero or one string arguments
each. A stub function is provided for each type of command that is to be implemented; and the main
program and auxiliary functions are all complete and should not require any modification. Each stage of
the project requires that you implement one or more of the following commands:
• “i”, insert an item;
• “p”, generate a simple printout of the tree that has been built;
• “t”, tabulate some statistics about the tree that has been formed;
• “r”, rotate an item one level closer to the root;
• “s”, generate a snazzy printout of the tree that has been built; and
• “f”, free all of the space currently allocated to the tree, and restart from an empty tree.
The program can either take its input from stdin or from a file named on the command line. In the latter
case, the commands are echoed as they are read, to provide understandable output. The interpreter loop
ends, and the program exits, when end of file is encountered.
Stage 1 – Inserting and Printing (9/15 marks)
Complete the functions do insert() and do print s().
Insertion should follow the usual binary tree ordering, and youmay simply call strcmp() to establish
ordering. If a string is already present in the tree, and another insert command for that string is issued,
the tree should be left unchanged. That is, the tree should not contain duplicate strings. Note that there is
no use of polymorphism in this project, and you do not need to make use of function pointers or void*
pointers. That is, your code will be more like listops.c than treeops.c; and should all be in one file.
The function do print s() draws a simple picture of the tree as it stands at that point in time,
without changing the tree at all. The root of the tree should be against the left margin. The strings should
be reverse alphabetic down the page, with each node of the tree indented five more characters than its
1parent. Here is one possible sequence of inputs and outputs (turn the page 90 degrees clockwise to see
the tree):
> i mary
> i had
>ia
> i little
> i lamb
>p
mary
little
lamb
had
a
>
Stage 2 – Tree Size (11/15 marks)
Now add in the body of the do tabulate() function. It prints a small table reporting the number of
items in the tree, and the average and maximum depth in the tree of those items. The root of the tree is
at depth 1. Continuing on from the previous example, a “t” command would report:
>t
size : 5
avg depth: 2.60
max depth: 4
>
Stage 3 – Edge Rotations (13/15 marks)
Ok, now for something different. The diagram on the next page shows what is meant by an edge rotation
in a BST: starting with the tree on the left, a rotation at the node whose key is the string “d” results in the
tree on the right; conversely, starting with the tree on the right, an edge rotation at the node whose key
is “b” results in the tree on the left. Note how one of the subtrees is reassigned in a manner that ensures
that the post-rotation tree is still a binary search tree. A rotation alters the structure of a tree, but not
its contents. For example, if subtree E is larger than subtree A, the tree on the right will have a smaller
average node depth, and thus better average searching and insertion characteristics.
Write the body of the function do rotate() that identifies the location of its argument in the tree,
and then rotates the tree at that position. If the argument string is at the root of the tree, or if the
argument string does not appear anywhere in the tree, then the original tree should be returned unchanged.
Warning: there are a lot of pointers to be re-assigned, and multiple cases to be considered. Draw pictures
on paper first, before you try and write the code. Continuing the same example, we would have:
2b
b
b d
A
CA EC
E
rotate at
rotate at
d
d
Edge rotation in a Binary Search Tree. The lower node is “rotated” in to the position
previously occupied by its parent, then subtrees are rearranged and all pointers
updated so that the tree is still in alphabetic order.
> r had
>p
mary
little
lamb
had
a
>t
size : 5
avg depth: 2.40
max depth: 4
>
Stage 4 – Resetting the Tree (14/15 marks)
The “f” command frees up all space that has been allocated to the tree and its strings by making calls to
free(), and resets the tree back to an empty initial state:
>f
>t
size : 0
>
The tree should be freed up from the leaves back toward the root, so that you don’t end up with a memory
leak caused by unreachable data.
Stage 5 – Snazzy Printing (15/15 marks)
For one last mark, add the details of the second “snazzy” print command. For the same tree as before,
(after rotating “had”), the output would be
3>s
+--
+--mary
| | +--
| +--little
| | +--
| +--lamb
| +--
had
| +--
+--a
+--
>
There are more examples linked from the FAQ page.
Purely for Fun (and not for submission)
Implement a “d” command that deletes the indicated string from the tree. If the string is a leaf, deletion is
easy. If it is an internal node, locate the alphabetically next node and swap it in to the position occupied
by the string being deleted.
The boring stuff...
This project is worth 15% of your final mark. A rubric explaining the expectations that you will be
marked will be provided shortly via the LMS.
You need to submit your program for assessment; detailed instructions on how to do that will be
posted on the LMS once submissions are opened. Submission will not be done via the LMS; instead you
will need to log in to a Unix server and submit your files to a software system known as submit. You
can (and should) use submit both early and often – to get used to the way it works, and also to check
that your program compiles correctly on our test system, which has some different characteristics to the
lab machines. Only the last submission that you make before the deadline will be marked.
You may discuss your work during your workshop, and with others in the class, but what gets typed
into your program must be individual work, not copied from anyone else. So, do not give hard copy
or soft copy of your work to anyone; do not “lend” your “Uni backup” memory stick to others for any
reason at all; and do not ask others to give you their programs “just so that I can take a look and get
some ideas, I won’t copy, honest”. The best way to help your friends in this regard is to say a very
firm “no” when they ask for a copy of, or to see, your program, pointing out that your “no”, and their
acceptance of that decision, is the only thing that will preserve your friendship. A sophisticated program
that undertakes deep structural analysis of C code identifying regions of similarity will be run over all
submissions in “compare every pair” mode. Students whose programs are so identified will be referred
to the Student Center. See https://academichonesty.unimelb.edu.au for more information.
Deadline: Programs not submitted by 10:00am on Monday 20 October will lose penalty marks at
the rate of two marks per day or part day late. Students seeking extensions for medical or other “outside
my control” reasons should email Alistair, ammoffat@unimelb.edu.au as soon as possible after those
circumstances arise.
Marks and a sample solution will be available on the LMS by Monday 3 November.
And remember, algorithms are fun!
4