IN C PROGRAMMING Sample Cumulative Question #8 Note: The following problem is ex
ID: 3716549 • Letter: I
Question
IN C PROGRAMMING
Sample Cumulative Question #8 Note: The following problem is excerpted from the final exam I gave in Summer 2013. The actual exam afforded more space for their written responses. There are at least two equally great solutions to this one (Data Structures) Suppose you need to write a program that processes all the 7-digit phone numbers that are in use in the United States. In particular, you need to choose a data structure that will facilitate the following operations: 3. (a) Insertion. You should be able to insert a phone number into the data structure very quickly. It might be associated with some metadata that's wrapped up in a struct along with the phone number, but you'll always use the phone itself to insert, retrieve, and update those records. The phone number serves as your point of entry to any record. (b) Retrieval. You should be able to retrieve a phone number very quickly. The organization you're coding this program up for loooooves to access metadata associated with people's phone numbers, so you need this operation to be fast and efficient. (c) Area code listing. You should be able to list all the numbers in your data structure that start with a particular area code, and you should be able to do that very quickly. Special consideration: The organization you're coding this program for wants to be able to run the program on all kinds of tiny little devices that have limited memory, so it can spyhave access to its hoard of metadata on the road and on the run, everywhere it goes. So, try not to waste memory with your program unnecessarily (a) What data structure (perhaps with a slight modification) have we studied this semester that you would use for this program, and why? (There are at least two really great, full-credit answers to this question.) (b) With your data structure, what are the Big-Oh runtimes for each of the operations listed above? Briefly ustify your answers. Insertion.: Retrieval: Area code listing: (c) Choose any one other data structure we have discussed in class that you think would be a poor choice for this problem, and briefly explain why your choice is better than that other data structure. Key considerations here are runtime efficiency and space (memory) efficiencyExplanation / Answer
a) There are various data structures that offer low time complexity for given operation. Linked list offers good low time complexity for inserting but not good for retrieval and look up. Heap offers average time complexity for all the required operations. A good choice for the above situation could be the hash table.
Since we need a data structure that is good at inserting, retrieval hash table is a very good option. For area code listing, we need to retrieve the phone number with the area code and display the result so again we will be retrieving the phone number.
b) Time complexities:
Insertion: O(1) insertion in a hash table can be performed in constant time. We just need to find the key for phone numberwhich can be done in constant time and store the number at position specfied by the key.
Retrieval: O(1) Again, to retrieve a phone number from the table, we just need to go to the specified position with the help of the key and get the element
Area Code Listig: O(n) This operation would take O(n) time on any type of data structure as it is possible that all the phone numbers belong to a single area.
c) Array would be a poor choisce for the given problem. As for array, time complexity for inseting is O(n), time complexity for searching a phone number is O(n) and for listing phone numbers of a given area code, it would take O(n) time. Out data structure beats the arra in terms of time complexity of insertion and retrieval.