B215 Practical exercises – Week 7
ICT283 Assessed exercise 2
Objectives:
To learn
· BST concepts
· To construct a simple BST
· Understand recursion
· Preparation for assignment 2
It is very important not to fall behind with these exercises.
Internal students demonstrate exercise b to their tutor during the next lab session.
Externals students submit via LMS once the submission area is available. Only exercise b is needed.
Exercises (assessed)
Use recursive routines for dealing with the tree. See lecture notes. The textbook uses non-recursive (iterative) routines but for the lab, you need to write recursive routines. You may want to use the unit reference book Introduction to Algorithms by Cormen et al.
In the assignment, you would normally be asked to provide a rational for your data structures. In this video for BST justification one particular example is used. https://www.youtube.com/watch?v=9Jry5-82I68&index=5&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb. In the video, the tree algorithm is modified to cater for a new requirement. This approach is not acceptable – see Open Closed Principle. Think of a better solution. Other than that, the video explains the BST and its use very **well**.
a. (Homework, before you start on exercise b)
Implement a simple (non-templated) Binary Search Tree (BST) class called Bst, which stores integers. Provide the following recursive operations: Insert, Delete tree, Search, inOrder traversal, preOrder traversal, postOrder traversal. You should go through the lecture notes and the videos related to BST found at the end of the BST lecture note.
Processing a node simply involves printing out the contents of the node, which in this case is the integer being stored in the node.
Data should come from a data file containing integers. You decide on the format. The main program should open the data file and insert into the tree and demonstrate other tree operations.
The point of this exercise is to demonstrate that you understand the BST. There is no need to go overboard with it and put in operations not asked for.
To use your BST in your test program, you will have the following declaration in main.
Bst intTree; // declaration of non-templated integer tree
// other code follows the above:
// insert various integer values
// test the tree methods
b.** (submitting or demonstrating in class – start work on it at home)
Complete exercise a above before attempting this exercise for assessment. Recursive operations are needed.
This exercise is preparation for assignment 2. It does not mean what follows is how a BST is going to be used in your assignment. The purpose of this exercise is to get you started with the template Binary Search Tree needed for the assignment. You should go through the lecture notes and the videos related to BST found at the end of the BST lecture note.
Convert your BST from exercise a above into a template Binary Search Tree (BST). Note that recursive operations are required for this assessed work. You may use non-recursive versions in assignment 2 but you must know the recursive versions as well so that you understand pros/cons of iterative vs recursive algorithms.
So, your Bst.h file will now have:
template
class Bst{…
// declaration of methods and data members of class Bst
};
// rest of the code in Bst.h
As this is a template class, there is no Bst.cpp.
As Node stores the data, Node will also be implemented as a template.
Test your template BST with the integer data file from exercise a. Change the declaration in your test program from exercise a above to:
Bst
// rest of the code is the same as exercise a.
Use your data file from assignment 1 and test your template BST by inserting just the Date values.
Bst
Make sure you test all the BST operations on the dateTree
Would the Date class from assignment 1 work, or do you need to modify the Date class or provide additional routines? What else is needed and why?
Not assessed in this lab.
What would you have to do if the user (client) of your tree data structure would like to do something else instead of just printing the values? See textbook section on “Binary Tree Traversal and Functions as Parameters.” See the code file funcPtr.cpp.
Further practice with Recursion
1. Fibonacci sequence
Fibonacci numbers are a series of numbers defined as shown below.
· F(1) = 1
// first number
· F(2) = 2
// second number
· F(n) = F(n-1) + F(n-2)
// subsequent numbers
These numbers have been used in Mathematics and Computer Science, and some have argued that these numbers represent some patterns in nature (https://en.wikipedia.org/wiki/Patterns_in_nature). For a quick background to these numbers and their applications, see https://en.wikipedia.org/wiki/Fibonacci_number. The unit textbook, like most Computer Science texts, covers Fibonacci numbers. The reference book Introduction to Algorithms has good coverage of algorithms and various issues including parallel algorithm versions of Fibonacci.
For this exercise, implement two versions of routine F.
The first version of the routine is iterative (uses loops).
The second version of the routine is recursive.
i. Compare the algorithms of each version. Which version of the algorithm best matches the definition of Fibonacci numbers as given above? Review their algorithmic performance.
ii. Compare the runtime performance of each routine F, when n is large.
2. Tower of Brahma (aka Tower of Hanoi)
Edouard Lucas, who is said to have coined the term “Fibonacci sequence”, introduced a legend and invented an associated puzzle in 1883. The legend goes as follows:
“In the great temple of Brahma in Benares, on a brass plate under the dome that marks the center of the world, there are 64 disks of pure gold that the priests carry one at a time between these diamond needles according to Brahma’s immutable law: no disk may be placed on a smaller disk. In the beginning of the world, all 64 disks formed the Tower of Brahma on one needle. Now, however, the process of transfer of the tower from one needle to another is in mid-course. When the last disk is finally in place, once again forming the Tower of Brahma but on a different needle, then the end of the world will come and all will turn to dust.” (Reproduced from an exercise in Algorithms and Data Structures: The Basic Toolbox
by Mehlhorn and Sanders). This puzzle got mathematicians, and later computer scientists very interested. Consequently algorithms for solving this puzzle have been widely studied.
The following can be done after you completed the BST, or after completing assignment 2.
· Create the puzzle using everyday items (buttons, bottle caps, …etc.) as described at https://www.scientificamerican.com/article/the-tower-of-hanoi/ and work out an algorithm for solving the puzzle. Use the rules as described in the legend above.
· Compare your algorithm with the worked example in the unit textbook (chapter on Recursion)
· Implement the algorithm in C++ and try solving the puzzle for a few disks.
· If the priests in the legend had a computer such as yours and attempted to solve the problem in simulation, how long would it take to transfer all 64 disks from one needle to one of the other needles?
· What can you say about the complexity of the problem? Would it be a polynomial time problem?
� It is a good book.
PAGE
1
LabExc-2-ass.doc