DS&A

Exercises: Algorithm Design

Before attempting these exercises, you should read the posts on algorithm strategies and choosing data types.

Scenario

You are developing a website where users can search for and compare mobile phones. The user chooses the two criteria (e.g. screen size and battery capacity), and a database query returns a list of phone models.

This list contains tuples of three values; the first value is the model name, and the second and third values are the user’s criteria. For example:

search_results = [
    ("Samsung Galaxy S8", 5.8, 3000),
    ("Samsung Galaxy S7", 5.1, 3000),
    ("Samsung Galaxy A5 2017", 5.2, 3000),
    ("Apple iPhone 8", 4.7, 1820),
    ("Huawei Honor View 10", 5.99, 3750),
    ("Apple iPhone X", 5.8, 2716),
    ("Samsung Galaxy S8 Plus", 6.2, 3500),
    ("Samsung Galaxy J5 2017", 5.2, 3000),
    ("Huawei Mate 10 Pro", 6, 4000),
    ("Apple iPhone 7", 4.7, 1960),
    ("Motorola Moto G5S Plus", 5.5, 3000),
    ("Apple iPhone 8 Plus", 5.5, 2670),
    ("Google Pixel 2 XL", 6, 3520),
    ("Huawei P Smart", 5.65, 3000),
    ("OnePlus 5T", 6, 3300)
]

The format for each tuple is (name, screen_size, battery_capacity).

Since there may be many search results, it is your task to narrow down this list. The rule for doing this is:

• One phone “dominates” another phone if it is better on one criterion, and at least as good on the other criterion.
• A phone should only be shown to the user if it is not “dominated” by any other phone.

We assume that larger numbers are better — i.e. the user prefers a bigger screen, more battery capacity, and so on.(1) For example:

• "Samsung Galaxy S8" dominates "Samsung Galaxy S7" because it has a bigger screen and the same battery capacity.
• "Apple iPhone X" has a bigger screen but a smaller battery capacity than "Motorola Moto G5S Plus", so neither dominates the other.

When solving the exercises, use the small list above and the longer list in the following file to test your functions:

• phone_models.py — test data (2223 phones).

In the small list, the phones not dominated by another phone are:

Samsung Galaxy S8 Plus
Huawei Mate 10 Pro

Exercises

1. Is any of these phones dominated by all other phones?
2. Write a function def dominates(phone1, phone2): which returns a Boolean indicating whether phone1 dominates phone2.
3. Write a function def is_dominated(phone, lst): which returns a Boolean indicating whether phone is dominated by any other phone in lst.
4. Write a function def show_best_results(lst): which prints the names of the phones that aren’t dominated. What strategy does your algorithm use?
5. Write a function which sorts search_results in-place by screen size, from largest to smallest. Phones with the same screen size should be ordered by battery capacity, from largest to smallest.
   You may use the built-in sort() method, or implement an in-place sorting algorithm of your choice.
6. Using the sorted list, write a function which prints the names of the phones that aren’t dominated. Your algorithm must only iterate over the list once.
   (Hint: keep track of the best battery capacity so far.)

Footnotes

1. If the user prefers e.g. a smaller screen or a lower price, we could make those numbers negative to avoid complicating the algorithm.

• Tags: 
• algorithms, algorithm strategies, exercises