Part: Programming Questions:
The Canadian Real Estate Association (CREA). Operates on multiple lists of n properties where each property is identified by a unique ULS code of 8 digits (e.g. # ULS: 20942894), some of the lists are local for cities and areas, where n counts few hundred properties. Others are at the provincial level, that is n counts tens of thousands or more. CREA needs your help to design a smart "real estate listing" data structure called SmartULS. Keys of SmartULS entries are integers of 8 digits, and one can retrieve the key of a SmartULS or access a single element by its key. Furthermore, similar to sequences, given a SmartULS element one can access its predecessor or successor (if it exists). SmartULS adapts to their usage and keep the balance between memory and runtime requirements. For instance, if a smart ULS contains only a small number of entries (e.g., few hundreds), it might use less memory overhead but slower (sorting) algorithms. On the other hand, if the number of contained entries is large (greater than 1000 or even in the range of tens of thousands of elements), it might have a higher memory requirement but faster (sorting) algorithms. SmartULS might be almost constant in size or might grow and/or shrink dynamically. Ideally, operations applicable to a single SmartULS entry should be 0(1) but never worse than 0(n). Operations applicable to a complete SmartULS should not exceed 0(n2).
You have been asked to design and implement a SmartULS, a smart data structure which automatically adapts to the dynamic content that it operates on. In other words, it accepts the size (total number of properties 71 identified by their 8 digits ULS number as a key) as a parameter and uses an appropriate (set of) data structure(s) from the one(s) studied in class in order to perform the operations below efficientlyl.
The SmartULS must implement the following methods:
- setSmartThresholdULS(Size): where 100 s Threshold s -500,000 is an integer number that defines when the list size should be implemented with a data structure such as a Tree, Hash Table, AVL tree, binary tree, or sequence, if its size is greater than or equal to value of Threshold.
- generate0: randomly generates new non-existing key of 8 digits
- allKeys(SmartULS): return all keys in SmartULS as a sorted sequence
- add(SmartULS,key,value2): add an entry for the given key and value
- remove(SmartULS,key): remove the entry for the given key
- getValues(SmartULS,key): return the values of the given key
- nextKey(SmartULS,key): return the key for the successor of key
- prevKey(SmartULS,key): return the key for the predecessor of key
- rangeKey(keyl, key2): returns the number of keys that are within the specified range of the two keys keyl and key2.
1. Write the pseudo code for each of the methods above.
2. Write the java code that implements the methods above.
3. Discuss how both the time and space complexity change for each of the methods above if the underlying structure of your SmartULS is an array or a linked list?
You have to submit the following deliverables:
a) A detailed report about your design decisions and specification of your SmartULS ADT including a rationale and comments about assumptions and semantics.
b) Well-formatted and documented Java source code and the corresponding class files with the implemented algorithms.
c) Demonstrate the functionality of your SmartULS by documenting at least 5 different but representative data sets. These examples should demonstrate all cases of your SmartULS ADT functionality (e.g., all operations of your ADT for different sizes).
You have to additionally test your implementation with benchmark files