Suppose we want to create an address book which contains names, phone numbers, e

Question

Suppose we want to create an address book which contains names, phone numbers, emails, and other personal information. In the questions below, give support to your answers based on the typical operations (for example, finding a person by his/her email) you might use. Explain why the algorithm and/or data structure you use gives a good tradeoff between memory use and runtime complexity. Some of the questions below could require nested data structures (for example, a Map which has values that are Sets).

a) Which data structures should you use for the address book in general to store the class Person? Give reasoning for your answer.

b) Suppose you have friends who live in various different cities. What data structure could be useful to find these friends efficiently. You can suppose that each friend has a city field associated with them. Give reasoning to your answer. Think about search engines for this question.

c) Suppose you want to check that there are no people with the same email address. Which algorithm(s)/data structure(s) might you use to do this? Give reasoning for your answer.

d) Suppose in you know which of the people in you address book are friends which each other. Now suppose you take yourself out of the graph. Which algorithm(s)/data structure(s) would help you determine the number of unrelated groups of friends you have? Give reasoning for your answer.

e) Suppose you want to list your friends who have March birthdays in order of date. What algorithm(s)/data structure(s) whould you use to accomplish this. You may assume that you have a birthday field which has a Date class that contains date and month member variables. Declare any other assumptions you make and give reasoning for your answer.

Explanation / Answer

(a) The purpose of an address book is to usually quickly provide us the details of a person we search for. So, a good data structure for address book is a hash map with the person's name being the key field.

(b) A graph data structure can be used. The people represent the vertices. And links can be created between the vertices which have the same "city" field.

(c) We can use a hash map with key being the email address. This way whenever there already exists another person with the same email address, we get notified about it as soon as new person is added to the address book. So, time complexity of this method is O(1).

(d) We can use a graph for this. The people represent the vertices. When two persons are friends, there is a link between them. So when we take ourself out of the graph, the compnent of the graph which contained us gets broken down into several smaller components. The number of new components formed gives the number of unrelated group of friends.

(e) We can use a map where the key is a month and the value is a set of people whose birthdays are in that month.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.