Lab 04

Introduction

• The goal of this lab is to implement:
  • linear search in a unsorted data structure
  • binary search in a sorted data structure

Download pricebook_tester.py

Big-O requirements

The six required functions are:

• is_sorted(pricebook) \(O(N)\)
• price_average(pricebook) \(O(N)\)
• unsorted_get(pricebook, name) \(O(N)\)
• unsorted_put(pricebook, name, price) \(O(N)\)
• sorted_get(pricebook, name) \(O(\log N)\)
• sorted_put(pricebook, name, price) \(O(N)\)

Data Structure

Lists of Tuples: pricebook representation

prices = [(80.0, 'Lego'),
          (690.0, 'Laptop'),
          (300.0, 'Camera'),
          (5.9, 'Knife'),
          (194.4, 'Headphone')]

First item (at index zero) is the price, second item (at index 1) is name

Avoid nested for loops

There’s no need for nested for loops when you know the first position of each tuple (index zero) is price and the second position (index one) is product name.

You can index the tuple in a for loop to get each price or name:

for i in range(1, len(pricebook)):
  # do something with pricebook[i][1] (each product name)
  
for product in pricebook:
  # do something with product[1] (each product name)

How to check if a list in unsorted?

• Compare each value with the next (or the previous) value
• If any two adjacent values are out of order, list is not sorted

How to replace a tuple?

• Remember that tuples are not mutable (cannot change them)
• If your unsorted_put is asked to change a price of an existing product name, you need to remove the existing tuple from the list of products, and append a new tuple with the new price for that existing product name.

Document your Code!

• Add docstrings to every function
• Add at least one in-line comment in each function