Dear Students!
Graded Discussion Board (GDB) will launch on Thursday, July 24, 2014 and it will close on Friday, July 25, 2014.
GDB Scenario:
Consider V Mart shopping mall where lot of customers comes to shop different products and pay their bills on daily basis. Quantities of products are changing regularly, incremented as they are stocked, searched and decremented (deleted) as they are sold. It is observed that insertion, deletion and search is in balanced form, as all modifications to the data need to be completed as soon as the items are sold to the customers or stocked in the store or searched.
The shopping mall also has registered customers. Number of new customers visit the shopping mall and get registered. The shopping Mall can renew registration, update status, and quit registration of the customers. Large number of customers gets registered on daily basis instead of get quitting registration. It is observed that insertion of new customers is greater than deletion and search operations.
GDB Questions:
Your job is to choose appropriate data structure for each of the above data (i.e. Products and Customers) keeping in view their given usage pattern. justify your choice with solid arguments.
Hint:
Scenario 1 - As number of insertion, searching and deletion operation (of products) are same so you can choose either binary tree or hash function for its implementation.
Scenario 2 – As number of insertion is greater than searching and deletion (of customers) so you can choose either singly or doubly linked list for its implementation.
Instructions:
A concise, coherent and to the point answer is preferred over lengthy comment having irrelevant details. Answers, posted on regular Lesson's MDB or sent through email will NOT be considered in any case.
Idea Solution
Graded Discussion Board (GDB) will launch on Thursday, July 24, 2014 and it will close on Friday, July 25, 2014.
GDB Scenario:
Consider V Mart shopping mall where lot of customers comes to shop different products and pay their bills on daily basis. Quantities of products are changing regularly, incremented as they are stocked, searched and decremented (deleted) as they are sold. It is observed that insertion, deletion and search is in balanced form, as all modifications to the data need to be completed as soon as the items are sold to the customers or stocked in the store or searched.
The shopping mall also has registered customers. Number of new customers visit the shopping mall and get registered. The shopping Mall can renew registration, update status, and quit registration of the customers. Large number of customers gets registered on daily basis instead of get quitting registration. It is observed that insertion of new customers is greater than deletion and search operations.
GDB Questions:
Your job is to choose appropriate data structure for each of the above data (i.e. Products and Customers) keeping in view their given usage pattern. justify your choice with solid arguments.
Hint:
Scenario 1 - As number of insertion, searching and deletion operation (of products) are same so you can choose either binary tree or hash function for its implementation.
Scenario 2 – As number of insertion is greater than searching and deletion (of customers) so you can choose either singly or doubly linked list for its implementation.
Instructions:
A concise, coherent and to the point answer is preferred over lengthy comment having irrelevant details. Answers, posted on regular Lesson's MDB or sent through email will NOT be considered in any case.
Idea Solution
I think either a bst or avl tree will work fine for this scenario. This can be seen from requirements
Requirements:
List of criminal should be loaded faster with the possibility to identify one as quickly as possible.
The trees can load the data faster because they preserve some order as compare to link list, queue or stack in which for each value we may need to find its right place and then rearrange whole thing. The other benefits of using tree is that the one offender can be found easily as we know that it takes nlog(n) to search in tree as compare to O(n) in link list, queue or stack.
Add/Remove Offenders:
The trees are faster to add data in them because we know that it will goes to its right place without the need of traversing the whole tree and usually requires nlog(n) to insert data. This is oppose to linked list, queue or stack in which we first have to search its right place and it can be worst to transverse whole data structure, so for them it can be O(1) but also O(n).
Deleting the offender from stack, queue and link list usually requires much time it can be O(1) if last but it can also be O(n) if it is first as compare to tree which is usually takes nlog(n).
Merging two offenders list:
The merging of two offenders list in linked list, stack and queue takes O(n + m) times where n & m are offender in two list. But in case of tree with appropriate use of algorithm it can O(n log n).
Read more at http://vustudents.ning.com/group/cs301datastructures/forum/topics/3783342:Topic:4433151?xg_source=activity#AcYqxvwvDy6l5j01.99
Requirements:
List of criminal should be loaded faster with the possibility to identify one as quickly as possible.
The trees can load the data faster because they preserve some order as compare to link list, queue or stack in which for each value we may need to find its right place and then rearrange whole thing. The other benefits of using tree is that the one offender can be found easily as we know that it takes nlog(n) to search in tree as compare to O(n) in link list, queue or stack.
Add/Remove Offenders:
The trees are faster to add data in them because we know that it will goes to its right place without the need of traversing the whole tree and usually requires nlog(n) to insert data. This is oppose to linked list, queue or stack in which we first have to search its right place and it can be worst to transverse whole data structure, so for them it can be O(1) but also O(n).
Deleting the offender from stack, queue and link list usually requires much time it can be O(1) if last but it can also be O(n) if it is first as compare to tree which is usually takes nlog(n).
Merging two offenders list:
The merging of two offenders list in linked list, stack and queue takes O(n + m) times where n & m are offender in two list. But in case of tree with appropriate use of algorithm it can O(n log n).
Read more at http://vustudents.ning.com/group/cs301datastructures/forum/topics/3783342:Topic:4433151?xg_source=activity#AcYqxvwvDy6l5j01.99
