Data Structure and Algorithms- Tasks to be completed
SIT221-Practical Task 8.1.pdf
SIT221 Data Structures and Algorithms Trimester 2, 2019
1
Practical Task 8.1 (Pass Task)
Submission deadline: 10:00am Monday, September 16 Discussion deadline: 10:00am Saturday, September 28
General Instructions
In this task, answer all the following questions and complement each answer with a detailed explanation.
1. Given a graph ⟨ , ⟩, what is to be the running time of the depth‐first search algorithm, as a function of the number of nodes | | and edges | |, if the input graph is represented by an adjacency matrix instead of an adjacency list?
2. Kolade is at a train station in a foreign town. He wants to select a hotel that has the maximum number of shortest paths from the train station. He thinks that this should reduce the risk of getting lost. Suppose he gives you a city map represented via a graph ⟨ , ⟩ with | | locations and | | edges connecting the locations. Each edge connecting a pair of directly connected locations has a unit distance, say 1. Help Kolade to find a proper hotel by designing a runtime algorithm that finds the number of shortest paths between the train station, located at node and every hotel on the map. Note that Kolade expects you to convince him that your algorithm is correct and it does find all possible shortest paths. Your solution can be in the form of a pseudocode.
3. A communication network, such as the Internet, can be modelled as an undirected graph ⟨ , ⟩. Here, the vertices are the computers on the network, and the edge set consists of one edge for each pair of computers that are directly connected. We assume that the edges of are undirected, that is, if there is a direct connection from computer to computer , then there is also a direct connection from computer to computer .
It is highly desirable for a communication network graph to be connected, so that every computer on the network can communicate, possibly through a series of relays, with any other computer. But networks can change, with some computers failing and other computers being added to the network. It is useful to have a testing algorithm that collects information about the current network graph (vertices and edges) at designated times, and determines properties related to connectivity.
Describe, in words and pseudocode, a testing algorithm that given an undirected graph ⟨ , ⟩ representing the current network decides whether or not the network is connected. A graph (network) is connected if there is a path from any node to any other node in the graph. You may assume that is given in adjacency list format. Your algorithm must run in time, where | | is the number of computers on the network, and | | is the number of connecting edges.
Further Notes
You will learn how to complete this task by reading the relevant sections of chapters 14.1‐14.3 of the course book “Data Structures and Algorithms in Java” by Michael T. Goodrich, Irvine Roberto Tamassia, and Michael H. Goldwasser (2014). You may access the book on‐line for free from the reading list
application in CloudDeakin available in Resources Additional Course Resources Resources on Algorithms and Data Structures Course Book: Data structures and algorithms in Java.
SIT221 Data Structures and Algorithms Trimester 2, 2019
2
Marking Process and Discussion
To get this task completed, you must finish the following steps strictly on time:
Submit your answers to the task via OnTrack submission system. You may submit a hand‐written and then scanned document, but ensure that the text and figures are very clear to read. Note that this is a theoretical task, thus we do not expect you to write any program code.
Meet with your marking tutor to explain your solutions. When the solutions are hand‐written, do not forget to bring them with you. Cloud students must record a short video explaining their work and use a sort of white‐board, e.g. a graphical editor, or a scanned document with the answers.
Answer all additional (theoretical) questions that your tutor may ask you. Questions are likely to cover lecture notes, so attending (or watching) lectures should help you with this compulsory interview part. Please, come prepared so that the class time is used efficiently and fairly for all the students in it. You should start your interview as soon as possible as if your answers are wrong, you may have to pass another interview, still before the deadline. Use available attempts properly.
Note that we will not check your solution after the submission deadline and will not discuss it after the discussion deadline. If you fail one of the deadlines, you fail the task and this reduces the chance to pass the unit. Unless extended for all students, the deadlines are strict to guarantee smooth and on‐time work through the unit.
Remember that this is your responsibility to keep track of your progress in the unit that includes checking which tasks have been marked as completed in the OnTrack system by your marking tutor, and which are still to be finalised. When marking you at the end of the unit, we will solely rely on the records of the OnTrack system and feedback provided by your tutor about your overall progress and quality of your solutions.
SIT221-Practical Task 7.1.pdf
SIT221 Data Structures and Algorithms Trimester 2, 2019
1
Practical Task 7.1 (Pass Task)
Submission deadline: 10:00am Monday, September 9 Discussion deadline: 10:00am Saturday, September 28
General Instructions
In this task, answer all the following questions and complement each answer with a detailed explanation.
1. Draw a series of figures demonstrating the insertion of the values
20, 9, 3, 7, 5, 8, 25, 30, 15, 6, 17
into an initially empty AVL tree. Insert the values in the order they appear in the given sequence. You must:
‐ Show the resulting AVL tree immediately before and after each insertion step that causes the tree’s rebalancing.
‐ Calculate the balance degree (as the difference between the heights of the left and the right subtrees rooted at a node) and label each node of the AVL tree before and after the necessary rebalancing.
‐ Clearly indicate the node(s) at which rotation is performed. Here, let be the first node you encounter in going up from the newly added node, say , toward the root of the AVL tree such that is unbalanced. And let denote the child of with greater height (and note that must be an
ancestor of ). Determine whether the subtree of rooted at is right or left heavy. Similarly, specify whether the subtree of rooted at is right or left heavy.
‐ Performing a single or a double rotation as the rebalancing (repairing) operation on the AVL tree, specify the type of the rotation that you apply: Single Left Rotation, Single Right Rotation, Left‐Right Rotation, or Right‐Left Rotation.
‐ Each time a new value has been inserted, ensure that both the Binary Search Tree Property and the Height‐Balance (AVL Tree) Property are maintained.
2. Now, draw a series of figures showing the deletion of the values:
20, 15, 8, 25, 30, 9, 17, 5, 6, 3, 7
from the AVL tree built in the previous part of the task. Delete the values in the order they appear in the given sequence. Draw the AVL tree after each deletion and rotation (if any), and complement each of the figures with all the aforementioned details.
When you delete a node with two children, you must always replace it with the largest element smaller than the key of the deleted node (as opposed to another possible rule: the smallest element larger than the key of the deleted node). Following this rule is important to let us check your solution quickly.
3. What order should we insert the elements 1,2,…,7 into an empty AVL tree so that we do not have to perform any rotations on it?
Further Notes
The lecture notes of weeks 6 and 7 should be a good starting point outlining the topic of AVL and binary search trees.
You will learn how to complete this task by reading sections 11.1.1, 11.1.2, and 11.3.1 of the course book “Data Structures and Algorithms in Java” by Michael T. Goodrich, Irvine Roberto Tamassia, and Michael H. Goldwasser (2014). You may access the book on‐line for free from the reading list application in
SIT221 Data Structures and Algorithms Trimester 2, 2019
2
CloudDeakin available in Resources Additional Course Resources Resources on Algorithms and Data Structures Course Book: Data structures and algorithms in Java.
You may find the attached tutorial on the AVL tree rotations useful to clarify how different rotations work and when each of them must be applied for the purpose of rebalancing.
Marking Process and Discussion
To get this task completed, you must finish the following steps strictly on time:
Submit your answers to the task via OnTrack submission system. You may submit a hand‐written and then scanned document, but ensure that the text and figures are very clear to read. Note that this is a theoretical task, thus we do not expect you to write any program code.
Meet with your marking tutor to explain your solutions. When the solutions are hand‐written, do not forget to bring them with you. Cloud students must record a short video explaining their work and use a sort of white‐board, e.g. a graphical editor, or a scanned document with the answers.
Answer all additional (theoretical) questions that your tutor may ask you. Questions are likely to cover lecture notes, so attending (or watching) lectures should help you with this compulsory interview part. Please, come prepared so that the class time is used efficiently and fairly for all the students in it. You should start your interview as soon as possible as if your answers are wrong, you may have to pass another interview, still before the deadline. Use available attempts properly.
Note that we will not check your solution after the submission deadline and will not discuss it after the discussion deadline. If you fail one of the deadlines, you fail the task and this reduces the chance to pass the unit. Unless extended for all students, the deadlines are strict to guarantee smooth and on‐time work through the unit.
Remember that this is your responsibility to keep track of your progress in the unit that includes checking which tasks have been marked as completed in the OnTrack system by your marking tutor, and which are still to be finalised. When marking you at the end of the unit, we will solely rely on the records of the OnTrack system and feedback provided by your tutor about your overall progress and quality of your solutions.
The AVL Tree Rotations Tutorial By John Hargrove Version 1.0.1, Updated Mar-22-2007
Abstract I wrote this document in an effort to cover what I consider to be a dark area of the AVL Tree concept. When presented with the task of writing an AVL tree class in Java, I was left scouring the web for useful information on how this all works. There was a lot of useful information on the wikipedia pages for AVL tree and Tree rotation. You can find links to these pages in section 4. The tree rotation page on wikipedia is lacking, I feel. The AVL tree page needs work as well, but this page is hurting badly, and at some point in the future, I will likely integrate most of this document into that page. This document covers both types of rotations, and all 4 applications of them. There is also a small section on deciding which rotations to use in different situations.
1. Rotations: How they work A tree rotation can be an imtimidating concept at first. You end up in a situation where you're juggling nodes, and these nodes have trees attached to them, and it can all become confusing very fast. I find it helps to block out what's going on with any of the subtrees which are attached to the nodes you're fumbling with, but that can be hard. Left Rotation (LL) Imagine we have this situation: Figure 1-1
a
\
b
\
c
To fix this, we must perform a left rotation, rooted at A. This is done in the following steps: b becomes the new root. a takes ownership of b's left child as its right child, or in this case, null. b takes ownership of a as its left child. The tree now looks like this: Figure 1-2
b
/ \
a c
Right Rotation (RR) A right rotation is a mirror of the left rotation operation described above. Imagine we have this situation: Figure 1-3
c
/
b
/
a
To fix this, we will perform a single right rotation, rooted at C. This is done in the following steps: b becomes the new root. c takes ownership of b's right child, as its left child. In this case, that value is null. b takes ownership of c, as it's right child. The resulting tree: Figure 1-4
b
/ \
a c
Left-Right Rotation (LR) or "Double left" Sometimes a single left rotation is not sufficient to balance an unbalanced tree. Take this situation: Figure 1-5
a
\
c
Perfect. It's balanced. Let's insert 'b'. Figure 1-6
a
\
c
/
b
Our initial reaction here is to do a single left rotation. Let's try that. Figure 1-7
c
/
a
\
b
Our left rotation has completed, and we're stuck in the same situation. If we were to do a single right rotation in this situation, we would be right back where we started. What's causing this? The answer is that this is a result of the right subtree having a negative balance. In other words, because the right subtree was left heavy, our rotation was not sufficient. What can we do? The answer is to perform a right rotation on the right subtree. Read that again. We will perform a right rotation on the right subtree. We are not rotating on our current root. We are rotating on our right child. Think of our right subtree, isolated from our main tree, and perform a right rotation on it: Before:
Figure 1-8
c
/
b
After: Figure 1-9
b
\
c
After performing a rotation on our right subtree, we have prepared our root to be rotated left. Here is our tree now: Figure 1-10
a
\
b
\
c
Looks like we're ready for a left rotation. Let's do that: Figure 1-11
b
/ \
a c
Voila. Problem solved. Right-Left Rotiation (RL) or "Double right" A double right rotation, or right-left rotation, or simply RL, is a rotation that must be performed when attempting to balance a tree which has a left subtree, that is right heavy. This is a mirror operation of what was illustrated in the section on Left-Right Rotations, or double left rotations. Let's look at an example of a situation where we need to perform a Right-Left rotation. Figure 1-12
c
/
a
\
b
In this situation, we have a tree that is unbalanced. The left subtree has a height of 2, and the right subtree has a height of 0. This makes the balance factor of our root node, c, equal to -2. What do we do? Some kind of right rotation is clearly necessary, but a single right rotation will not solve our problem. Let's try it: Figure 1-13
a
\
c
/
b
Looks like that didn't work. Now we have a tree that has a balance of 2. It would appear that we did not accomplish much. That is true. What do we do? Well, let's go back to the original tree, before we did our pointless right rotation: Figure 1-14
c
/
a
\
b
The reason our right rotation did not work, is because the left subtree, or 'a', has a positive balance factor, and is thus right heavy. Performing a right rotation on a tree that has a left subtree that is right heavy will result in the problem we just witnessed. What do we do? The answer is to make our left subtree left-heavy. We do this by performing a left rotation our left subtree. Doing so leaves us with this situation: Figure 1-15
c
/
b
/
a
This is a tree which can now be balanced using a single right rotation. We can now perform our right rotation rooted at C. The result: Figure 1-16
b
/ \
a c
Balance at last.
2. Rotations, When to Use Them and Why How to decide when you need a tree rotation is usually easy, but determining which type of rotation you need requires a little thought. A tree rotation is necessary when you have inserted or deleted a node which leaves the tree in an unbalanced state. An unbalanced state is defined as a state in which any subtree has a balance factor of greater than 1, or less than -1. That is, any tree with a difference between the heights of its two subtrees greater than 1, is considered unbalanced. This is a balanced tree: Figure 2-1
1
/ \
2 3
This is an unbalanced tree: Figure 2-2
1
\
2
\
3
This tree is considered unbalanced because the root node has a balance factor of 2. That is, the right subtree of 1 has a height of 2, and the height of 1's left subtree is 0. Remember that balance factor of a tree with a left subtree A and a right subtree B is B - A Simple. In figure 2-2, we see that the tree has a balance of 2. This means that the tree is considered "right heavy". We can correct this by performing what is called a "left rotation". How we determine which rotation to use follows a few basic rules. See psuedo code: IF tree is right heavy
{
IF tree's right subtree is left heavy
{
Perform Double Left rotation
}
ELSE
{
Perform Single Left rotation
}
}
ELSE IF tree is left heavy
{
IF tree's left subtree is right heavy
{
Perform Double Right rotation
}
ELSE
{
Perform Single Right rotation
}
}
As you can see, there is a situation where we need to perform a "double rotation". A single rotation in the situations described in the pseudo code leave the tree in an unbalanced state. Follow these rules, and you should be able to balance an AVL tree following an insert or delete every time.
3. Summary It’s important to understand that the examples above were on very small trees to keep the concepts clear. In theory, however, if you develop an application which uses AVL trees, programming for the situations shown above while using the rules provided should scale just fine. If you have comments, questions or criticisms, feel free to e-mail me at castorvx@gmail.com
4. Further Reading - Tree rotation page on Wikipedia, http://en.wikipedia.org/wiki/Tree_rotation - AVL tree page on Wikipedia, http://en.wikipedia.org/wiki/AVL_tree - Animated AVL Tree Java applet, http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm - AVL Trees: Tutorial and C++ Implementation, http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html