CS 683 Emerging Technologies: Embracing Change Spring Semester, 2001 Assignment 1
	Assignment Index         © 2001, All Rights Reserved, SDSU & Roger Whitney San Diego State University -- This page last updated 13-Feb-01

---

Assignment 1
Problem 1 & 2 are due Feb 20
Problem 3 is due Feb 27

1. A palindrome is a word or phrase that reads the same backward as forward. Add a method isPalindrome to the String class that returns true is the string is reads the same backward as forward. The method returns false if this is not the case.

2. A BankAccount class. Each BankAccount object is to have a name, balance and a history. You can make deposits and withdrawals on a BankAccount object. Each transaction is to be added in a history (just the amount). You can get the current balance. The BankAccount class is to have a do: method that enumerates over the history of the transactions.

3. Implement a ternary search tree with integer keys. A ternary search tree is like a binary search tree, except each node in the tree has up to two keys and three subtrees. Figure A below shows a node with keys 10 and 20. The subtree A contains keys with values less than 10, the subtree B contains keys with values between 10 and 20. The subtree C contains keys with values greater than 20. When you insert a key into an empty ternary tree, that key becomes a key in the root node. The second key inserted into the ternary tree becomes the second key in the root node. These two keys are kept in order. All subsequent keys are inserted using the same rules in the proper subtree of the root note. So if we were to insert the numbers 10, 40, 7, 20, 5, 6, 30, 15 we would get the tree in Figure B.

Your ternary tree needs to have the following methods:


at: anInteger put: anObject

Stores the key and object in the proper location in the tree as described above. If key is already in the tree, its value is changed to the new value.

at: anInteger

Returns the value stored in with the given key in the tree.

do: aBlock

Enumerates over the objects in the tree

includesKey: anInteger

Returns true if the tree contains the key.

includes: anObject

Returns true if the tree contains the object stored as a value.

printString

Implement printOn: so that printString defined in Object returns a string representation of the tree using the following recursive rule: for each node print "(" then left subtree, smallest key, middle subtree, largest key, right subtree ")". So toString() on the tree in figure B will result in

(( 5 (6) 7 ) 10 ( (15) 20 30) 40 )


Figure A

Figure B

Copyright ©, All rights reserved.
2001 SDSU & Roger Whitney, 5500 Campanile Drive, San Diego, CA 92182-7700 USA.
OpenContent license defines the copyright on this document.

---

    visitors since 13-Feb-01