CS21 Lab 8: Searching

Due Saturday, November 12, by 11:59pm

Please read through the entire lab before starting!

This is a one week lab. For the previous lab, you used a full week to practice the TDD component and a second week to implement your solution. Since the design process should be similar to the previous lab, you will be doing the design and implementation for this lab in a single week. If you found the open-ended nature of the last lab challenging, you will want to start this lab early.

Additionally, all the "standard" requirements from previous labs such as programming tips, function comments, etc. still apply; feel free to refer to previous lab pages as a reminder.

Goals

Write a program that uses linear search
Write a program that uses binary search
Continue practicing Top-Down Design (TDD)
Connect CS topics with real-world data

1. Searching a real-world data set

For this this assignment, we will be working with a real-world dataset from CORGIS (which is an acronym for: The Collection of Really Great, Interesting, Situated Datasets). We will be using a slightly modified version of this dataset that contains information about access to stores selling food (grocery stores, etc.) broken down by county. This data can be used to identify communities with significant "food deserts," but it also contains additional relevant information such as population, access to vehicles, income levels, etc.

In this lab we will focus on searching for records by county name, state, and population. A more interesting real-world application would likely allow the user to cross-reference the data and search for and/or display particular patterns or relationships in the data.

You will implement a program called search-food.py, which will allow the user to search through this dataset and find particular information.

1.1. Trigger Warning and notes about real-world data

While this data is provided as demographics (i.e. population numbers) and does not provide information on specific individuals, it is actual data collected about the real world relating to income inequality and hunger. If you are not comfortable working with this data, please reach out to one of the instructors about the possibility of completing an alternate version of this lab.

Even if you are not triggered by this data, it is worth being aware of what it represents, and the power that algorithms can give you. Technology is not value-neutral; even if the search algorithms you implement are mathematically indifferent to the meaning of the data, the data you are searching are produced by a world which is not. Thus, the results of the search will not be bias-free even if the search algorithm is "fair".

In addition to the unfairness explicitly being represented and highlighted in this data set (i.e. the unequal distribution of access to food), always keep in mind that data collected about the world is not a perfect representation of that world. The process of collecting and curating data is done by humans, and as a result the data we see typically have embedded biases that are difficult or impossible to identify simply from looking at the numbers.

In this lab, we’ll explore the use of algorithms that might help us use data to identify unfairness in the world, with the idea that doing so would be a first step towards trying to remedy the problem. Even with good intentions, however, it is important to keep in mind not only the strengths but also the limitations of your data and algorithms.

1.2. Program Requirements

Reads in stored data from a file, storing a list of records. The data is stored in the file:

/data/cs21/food_access/food_access.csv

Note: don’t copy this file to your labs/08 directory, just use "/data/cs21/food_access/food_access.csv" as the file name in your python program.

As you read in the data, each line of the file corresponds to one record, which your program should represent using a FoodAccessRecord object and store in a list.

Note that there are actually two versions of the data file; the complete one is: /data/cs21/food_access/food_access.csv but there’s also a copy that’s had most of the lines removed, which may be easier to use for testing your program, particularly in the early stages: /data/cs21/food_access/food_access_small.csv

Repeatedly presents a menu to the user with three choices: to search by county name, to search by state, or to quit. For example:
```
Please select one of the following choices:
(1) Find by County
(2) Find by State
(3) Find by Population
(0) Quit

Choice?
```
Depending on the user’s selection, prompt them for additional information and then do one of:
1. Search the dataset by county name, using binary search.
2. Search the dataset by state, using linear search.
3. Search the dataset by population threshold, using linear search.
4. Exit the program.
When searching for name or state, compares data in lowercase format (so that user input is case insensitive) but displays results with their original case.
Searches by prefix, meaning that if the name in the database is longer than the string typed, it counts as a match as long as they’re the same up to the point the typed string ends. For example, if the user enters "Ada", it should be a match for the database entry "Ada County". If the user just types "A", it should match all the county names that start with the letter A. (Note that this means if you search for an empty string, it should match the entire database)
When searching for population, compares data by numeric threshold, such that any records with a population larger than the specified value are returned.
Ensures that the user provides valid input (i.e. the program should not crash if the user enters something unexpected).
Uses formatted printing to show search results in a table format that fits in an 80-character wide terminal window.
- Note that this will require using methods to retrieve different pieces of information about each record; see the FoodAccessRecord object for a list of methods you can use.
Uses linear search to find matches by state and by population.
Uses binary search to find matches by county name.

1.3. Example Output

Here are some examples of searching:

1.4. Tips

1.4.1. Continue to use TDD

We strongly recommend that you create a top-down design with a fully fleshed out main and stubs for all other functions. However, you may not work with a partner on this lab. Also, you don’t need to get approval from an instructor for your design, though we’d be glad to review it with you in lab, office hours, or ninja sessions. You should only begin implementing the other functions after you have a clear plan in place for the structure of main.

1.4.2. Create modular, reusable functions

Avoid duplicating similar code in multiple places throughout the program. Think about how you could re-use the same function. For example, we are doing several types of searches (by county name, by state, and by population), but the results of those searches are displayed in exactly the same way. Consider having a function that takes in a list of search results and displays them. Then you could call this function for either type of search.

1.4.3. Displaying matches

We want the results of our searches to be nicely displayed in the terminal window. However, some fields in the data set are quite long. We can use slicing to truncate these strings to a fixed maximum length, allowing us to create an easy to read table format. This section of the online textbook explains how to slice a string. For instance, the following example using the REPL shows how to slice out the first 10 characters from a string:

>>> alphaString = "abcdefghijklmnopqrstuvwxyz"
>>> alphaString[0:10]
'abcdefghij'

Notice how this nicely works, even if we provide an upper bound that is longer than the string we’re trying to slice (unlike when dealing with lists):

>>> shortString = "xyz"
>>> shortString[0:10]
'xyz'

Recall also that you can specify the width of a field when printing, e.g. print("%10s" % ("hi")) will print "hi" with 8 spaces in front of it. You can also use the - flag to get left-justified printing (the default is right-justified), e.g. print("%-10s %10s" % ("hi", "there")) will print "hi" followed by 8 spaces, and then "there" with 5 spaces in front of it:

>>> print("|%-10s|=|%10s|" % ("hi", "there"))
|hi        |=|     there|

This type of formatting works with numbers the same way it does with strings, but remember that %s is used for strings, %d is used for integers, and %f is used for floats. Here’s an example using numeric types:

>>> print("|%-10d|=|%10.3f|" % (837, 45.345986))
|837        |=|     45.346|

By combining these methods, you can make your output look like a nice table where everything is aligned (as demonstrated in the example output). For instance, to get the header shown in the example output, try:

print("================================================================================")
print("| %15s | %12s |%9s| %7s| %6s | %6s | %7s|" % ( "County", "State", \
      "Total Pop", "LFA Pop", "Income", "Senior", "Vehicle" ) )
print("--------------------------------------------------------------------------------")

Note that several of the column labels shown here are abbreviations so it fits in 80 characters; "Total Pop" is the total population of the county, "LFA Pop" is the low food access population (i.e. the number of people too far from the nearest supermarket). Likewise, "Income", "Senior", and "Vehicle" are the counts for the various different groups that are too far from a market (see here for further details on how to get these numbers and what they represent).

1.4.4. Adapting linear search

The version of linear search that we discussed in class stops as soon as it finds the item it is looking for, and returns the index of that item or -1 if not found. For this problem, your linear search will need to accumulate a list of matching results and return that.

In addition, the basic version of linear search assumes that you are searching a flat list. We will be searching a list of objects, so will need to adapt linear search to use method syntax to get at the data within each object.

Finally, when searching for state names, make sure your search function uses the .startswith method (see here) rather than == so it doesn’t miss any partial matches (e.g. using "New" should match both "New York" and "New Mexico"). You’ll also want to use the .lower method (see here) to convert both the target and the candidate match to lower case.

1.4.5. Adapting binary search

Because the data is sorted by county name, we can use binary search to very quickly locate a particular county. However, names can be somewhat long, so we’ll want to be able to search by prefix rather than complete string. Additionally, the data may contain multiple county names with the same name prefix.

For example, there are six county names that start with the prefix "Allen":

...
Allegheny County     <- this has a different prefix
Allen County
Allen County
Allen County
Allen County         <- suppose binary search finds this one
Allen Parish
Allendale County
Alpena County        <- this has a different prefix
...

Finding the first match

First write a binary search function that searches for a partial match to a county name and returns the index of the first match that it finds (or -1 otherwise).

Once again, make sure your search function uses the .startswith method (see here) rather than == so it doesn’t miss any partial matches (e.g. using "Ada" to match on "Ada County"). You’ll also want to use the .lower method (see here) to convert both the target and the candidate match to lower case.

Finding additional matches

There might be more matches that are just before or just after that initial index you locate. So next you’ll need to search in the vicinity of that location to find all of the other potential matches.

Fortunately, you can use the provided library function for this.

1.5. Food Access Data Set

For this lab, we’ll be focusing on just a few of these features. Much of the work of parsing the file will be done for you by objects by the provided FoodAccessRecord object type, but it’s worth understanding how the data file is set up anyway.

The data is stored in CSV (Comma Separated Value) format and is located on our systems at:

/data/cs21/food_access/food_access.csv

The data file has one "record" per line (where each record contains the data for a particular county). Here are the first three lines and the last three lines from the file:

Abbeville County,25417,South Carolina,901,9990,559,912,116,0,4249,5262,601,0,7585,9784,1567,0,18958,23281,2647,0,3068,3836,456,0
Acadia Parish,61773,Louisiana,1050,22841,480,1002,6,0,8615,12008,15,0,10500,16733,28,0,31316,43547,70,0,3466,5190,16,0
Accomack County,33164,Virginia,428,13798,1274,1397,226,0,5731,6482,135,0,11970,13236,298,0,27105,30794,727,0,5089,5812,156,0
...
Zapata County,14018,Texas,30,4297,157,234,40,0,1931,3354,447,1,3569,5989,962,2,5828,9704,1548,3,688,994,200,1
Zavala County,11677,Texas,409,3573,308,442,229,101,1539,2819,1017,310,3389,5531,2311,787,5053,8811,3139,1000,527,986,335,101
Ziebach County,2801,South Dakota,0,836,67,75,45,32,626,739,387,281,1110,1272,701,509,1706,1949,1050,735,148,153,94,58

Notice that the file is sorted alphabetically by county name.

Each line contains 25 fields separated by commas:

Table 1. Features of Food Access Data Set
Feature index	Type	Description
0	string	County name
1	int	Population of the county
2	string	State name
3	int	Residents in group quarters
4	int	Total housing units
5…24	int	Access to food markets for different groups

After the first 5 lines, the remainder of the file is made up of five blocks, each containing four numbers. Each block describes food access based on a particular demographic group: those lacking vehicles, children, low-income individuals, all individuals, and seniors. Within a block, the four numbers refer to different distances (1/2 mile, 1 mile, 10 miles, 20 miles), and are counts of how many individuals in that demographic live further than the specified distance from the nearest supermarket.

A full description of the file format can be found here: Data set description link

2. Provided Library

The lab comes with a food_access_lab library that gives you several helpful tools intended to make this lab easier:

2.1. FoodAccessRecord Class

The library provides a FoodAccessRecord class, which encapsulates all the features needed to store one "record." You can create an object of this class by calling the `FoodAccessRecord()`constructor, which takes as its input a string containing a record (i.e. one line of the file).

In order to create the objects, you’ll need to read in the file, split it into lines, and then create an object from each line. For example, to make a record from line 37 of the file, you could do like this:

file_obj = open("/data/cs21/food_access/food_access.csv", "r")
raw_data = file_obj.read()
lines = raw_data.splitlines()
one_line = lines[36]

record = FoodAccessRecord(one_line)

After this, the variable record will refer to the newly created object. For your program, you’ll need to create an object for each line of the file, then assemble them into a list of records which you can pass around.

Once you have a FoodAccessRecord object, you can use various getter methods to retrieve information about it:

Table 2. Features of Food Access Data with Getter Methods
Getter Method	Return Type	Description
`get_county()`	string	County name (i.e. the county the rest of the data pertains to)
`get_state()`	string	State the county is located in
`get_population()`	int	Total population (of the county)
`get_housing_total()`	int	Total housing units
`get_housing_group()`	int	Group housing units
`get_people(distance)`	int	Low Food Access population: Total number of people living beyond the given destance from nearest supermarket
`get_children(distance)`	int	Low Food Access children: Children living beyond the given destance from nearest supermarket
`get_seniors(distance)`	int	Low Food Access seniors: Seniors living beyond the given destance from nearest supermarket
`get_low_income(distance)`	int	Low Food Access low income population: Low income people living beyond the given destance from nearest supermarket
`get_vehicle_access(distance)`	int	Low Food Access no-vehicle households: Households with no vehicle (car/truck/etc.) beyond the given destance from nearest supermarket

Note that many of these methods take a distance parameter; this is the radius at which the number is recorded. For instance, .get_low_income(0.5) would return the number of low-income individuals for who live more than half a mile from the nearest supermarket; .get_children(10) would return the number of children who live more than 10 miles from the nearest supermarket. The data set contains entries for the distance values 0.5, 1, 10, and 20.

For your program, it’s fine to just use the value 1 all the time unless you’re implementing the related optional extension.

2.2. Finding nearby matches

We have conveniently provided you with a function to help with finding nearby matches based on an initial seed. This is called lookForwardBackward() and you can import it from the food_access_lab library. This function takes four parameters and returns a list of matching items that it found looking either forward or backwards. Those parameters are:

A list of record objects to search over
An integer where the search should start from (this is the index that your "binary search" function will return)
The partial match (string) that the function should be searching for (e.g. "Ada" in the above example)
A search direction. This is an integer which should have the value 1 (to search forward) or -1 (to search backwards)

A call to the lookForwardBackward() function might look something like this:

backwardMatches = lookForwardBackward(currData, currIndex, name, -1)

You will need to import the function at the top of the program (from food_access_lab import *) and call it twice for each binary search (once to get the forward matches and again to get the backward matches). You’ll then need to return a single list containing the match found as well as the forward and backward matches in the correct order.

3. Extra Challenges

Here are some optional extensions! These are NOT required, but they might be fun and rewarding, and allow you to get closer to how we might like to use this data in the real world.

If you implement extensions, please do so in a copy of your program called search-food-ext.py

3.1. Optional: Adjustable range

Right now, the distance parameter is always set to 1 mile. Add a menu option to let the user set a different distance threshold (in miles) which you will then pass to the getter functions.

3.2. Optional: Find counties with "food deserts"

Prompt the user for a number of individuals with poor access to food, then use linear search to find all counties where the "distant population" is greater than the number given.

For even more challenge, try searching for counties that pass a specified ratio threshold (i.e. find counties where more than a given percentage of the population has poor access to food).

Note that you can do this for other numeric columns if you want.

3.3. Optional: Extending your own binary search

Rather than importing the provided lookForwardBackward function, try writing your own. This should work the same way as the provided version: it will look linearly forwards or linearly backwards based on an initial seed index that it takes as a parameter. The function will also need to take the search string as an input parameter (as well as potentially other information depending on your design). This function should return a list of all the partial matches based on that initial seed index.

The program can then add that list together with the entry at the initial seed to compute the total list of partial matches which are then displayed to the user.

Answer the Questionnaire

Each lab will have a short questionnaire at the end. Please edit the Questions-08.txt file in your cs21/labs/08 directory and answer the questions in that file.

Once you’re done with that, you should run handin21 again.

Submitting lab assignments

Remember to run handin21 to turn in your lab files! You may run handin21 as many times as you want. Each time it will turn in any new work. We recommend running handin21 after you complete each program or after you complete significant work on any one program.

Logging out

When you’re done working in the lab, you should log out of the computer you’re using.

First quit any applications you are running, like the browser and the terminal. Then click on the logout icon ( or other logout icon ) and choose "log out".

If you plan to leave the lab for just a few minutes, you do not need to log out. It is, however, a good idea to lock your machine while you are gone. You can lock your screen by clicking on the lock xlock icon. PLEASE do not leave a session locked for a long period of time. Power may go out, someone might reboot the machine, etc. You don’t want to lose any work!