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) and 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) and 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) and 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.