How both the time and space complexity change

Reference no: EM131293170

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(n²).

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 n 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 efficiently.

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 that will be posted soon here:

Attachment:- Assignment 3 and 4.zip

Reference no: EM131293170

Questions Cloud

Construction of a new hospital in home country : In November of 2009 the Chelsea football (soccer) player, Didier Drogba, pledged 3 million pounds to the construction of a new hospital in his home country of Cote d'Ivoire. Suppose the hospital has been constructed

Analyse the current financial state of anthonys orchard : Analyse the current financial state of Anthony's Orchard and evaluate the impact of a major customer cancelling their expected order.

Prepare a comprehensive strategy for training new employees : Develop a comprehensive strategy for training new employees. Focusing on the role of the new employees within the organization. Propose two to four training strategies aimed at motivating the employees to learn key aspects about their new jobs.

Explain friedman methodology of positive economics : Briefly write and explain Friedman's methodology of "Positive Economics". Do you think the discrimination of economics as "normative" and "positive" is a logical move in building theory?

How both the time and space complexity change : Write the java code that implements the methods and 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?

Determine average federal and overall effective tax rate : Workman Tools reported a TI of $90,000 last year. If the state income tax rate is 7%, determine the (a) average federal tax rate, (b) overall effective tax rate, (c) total taxes to be paid based on the effective tax rate, and (d) total taxes paid to ..

Pandemic disease due to its continued existence : HIV/AIDS is still considered a pandemic disease due to its continued existence throughout the various populations in the world. How does malaria and TB figure into this dilemma?

Describe the factors that influence reputation : Describe the factors that influence reputation. Then, define risk and describe what makes up sustainability risks. What risks has your organization taken lately?

Demand for columbia brother coffee : Suppose that the price of flavored milk is increased by 5 %. What impact will this have on the demand for Columbia Brother's coffee?

User Account

All Pages