1. CS21 Lab 8: Searching a Dataset

Due Monday, November 16, before midnight


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 lab 8 in a single week. If you found the open-ended nature of the last lab challenging, you will want to start this lab early.

1.1. 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 data

1.2. Graduates Data

For this lab, we’ll be using data collected on college graduates from the United States. The dataset is a modified version from the CORGIS educational dataset archive, and it contains 518 entries. We have defined a Graduates class to represent one record from the data. To clarify, each record corresponds to all graduates from a specific major and year. Examples in the section below.

2. Introduction: Searching the Dataset

Your task is to write a program that:

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

/usr/local/doc/graduates.txt

Note: don’t copy this file to your 08 directory, just use "/usr/local/doc/graduates.txt" as the file name in your python program. Each line of the file corresponds to one record and contains the following fields (separated by commas):

  • The id (string)

  • The year (int)

  • The total number of graduates (int)

  • The major (string)

  • The mean salary of employed graduates (float)

  • The total number of employed graduates (int)

Here’s one example:

ELEC03,2003,828727,Electrical Engineering,83006.83,677605

Each line of data ends with a "newline" character, which causes the following text to start on the next line of the file. When you’re reading in data from the file, you can call the .strip() method on each line (prior to calling .split()) to remove any or newlines or other unnecessary spaces.

As you read in graduates data, each line of the file corresponds to one record, which your program should represent using a Graduates object, and store it in a list. Here is an example of using a Graduates constructor:

record = Graduates("ELEC03", 2003, 828727, "Electrical Engineering", 83006.83, 677605)

Notice how the order of the constructor arguments is in the same order as the data in the file. For more information on the Graduates class, go down to the Provided Library section. For tips on how to print such an object, head down to the Hints and Tips section.

  • Prompts the user with a menu of four choices:

Please select one of the following choices:
(1) Find by major
(2) Find by ID
(3) Find by mean salary
(4) Quit

Choice?

Depending on the user’s selection, you will prompt them for additional information and then do one of:

  1. Search the dataset by major, using linear search.

  2. Search the dataset by ID, using binary search.

  3. Search the dataset by minimum and maximum mean salaries, using linear search.

  4. Exit the program.

You program should continue prompting the user until they enter a valid choice and then perform the following queries listed below for each menu option. The program should exit if the user selects option 4 (Quit).

Please select one of the following choices:
(1) Find by major
(2) Find by ID
(3) Find by mean salary
(4) Quit

Choice? -4
Invalid choice. Please select a number choice from above
Choice? 0
Invalid choice. Please select a number choice from above
Choice? 4
Have a nice day!

3. Find by Major

For option 1 (find by major), you must:

  • Prompt the user for a major string.

  • Use linear search to find all the records for which the user-entered string appears in the major.

    You can use the in operator for strings to help you to determine whether or not the user-entered string appears in a record’s full major string as a substring. For example: "co" in "cold" and "old" in "cold" are both True, but "cld" in "cold" is False.

    You can use the .lower() method to make the matching case-insensitive.

  • Your matching should be case-insensitive. For example, if the user enters "BOT", your search should match records with "Botany", "botany", "Bot", etc.

  • Print the information for all matching records, one per line, if there were any matches.

  • If no records match the entered major, let the user know that you couldn’t find any.

Here are some examples:

$ python3 graduates.py
Please select one of the following choices:
(1) Find by major
(2) Find by ID
(3) Find by mean salary
(4) Quit

Choice? 1
Please enter which major to search for: Astronomy
11 found
PHYA01:Physics and Astronomy, 2001. Mean salary: $35980.71. Total graduates: 10937. Total employed graduates: 9648
PHYA03:Physics and Astronomy, 2003. Mean salary: $81201.21. Total graduates: 248495. Total employed graduates: 201406
PHYA06:Physics and Astronomy, 2006. Mean salary: $31212.45. Total graduates: 18980. Total employed graduates: 15643
PHYA08:Physics and Astronomy, 2008. Mean salary: $38101.3. Total graduates: 16430. Total employed graduates: 14547
PHYA10:Physics and Astronomy, 2010. Mean salary: $75886.38. Total graduates: 294337. Total employed graduates: 243215
PHYA13:Physics and Astronomy, 2013. Mean salary: $79512.6. Total graduates: 291317. Total employed graduates: 226861
PHYA15:Physics and Astronomy, 2015. Mean salary: $93267.1. Total graduates: 317500. Total employed graduates: 264694
PHYA93:Physics and Astronomy, 1993. Mean salary: $195036.54. Total graduates: 220883. Total employed graduates: 184918
PHYA95:Physics and Astronomy, 1995. Mean salary: $56423.7. Total graduates: 223931. Total employed graduates: 187318
PHYA97:Physics and Astronomy, 1997. Mean salary: $62580.77. Total graduates: 229955. Total employed graduates: 194449
PHYA99:Physics and Astronomy, 1999. Mean salary: $68603.82. Total graduates: 234861. Total employed graduates: 196611
Please select one of the following choices:
(1) Find by major
(2) Find by ID
(3) Find by mean salary
(4) Quit

Choice? 1
Please enter which major to search for: ASTRO
11 found
PHYA01:Physics and Astronomy, 2001. Mean salary: $35980.71. Total graduates: 10937. Total employed graduates: 9648
PHYA03:Physics and Astronomy, 2003. Mean salary: $81201.21. Total graduates: 248495. Total employed graduates: 201406
PHYA06:Physics and Astronomy, 2006. Mean salary: $31212.45. Total graduates: 18980. Total employed graduates: 15643
PHYA08:Physics and Astronomy, 2008. Mean salary: $38101.3. Total graduates: 16430. Total employed graduates: 14547
PHYA10:Physics and Astronomy, 2010. Mean salary: $75886.38. Total graduates: 294337. Total employed graduates: 243215
PHYA13:Physics and Astronomy, 2013. Mean salary: $79512.6. Total graduates: 291317. Total employed graduates: 226861
PHYA15:Physics and Astronomy, 2015. Mean salary: $93267.1. Total graduates: 317500. Total employed graduates: 264694
PHYA93:Physics and Astronomy, 1993. Mean salary: $195036.54. Total graduates: 220883. Total employed graduates: 184918
PHYA95:Physics and Astronomy, 1995. Mean salary: $56423.7. Total graduates: 223931. Total employed graduates: 187318
PHYA97:Physics and Astronomy, 1997. Mean salary: $62580.77. Total graduates: 229955. Total employed graduates: 194449
PHYA99:Physics and Astronomy, 1999. Mean salary: $68603.82. Total graduates: 234861. Total employed graduates: 196611
Please select one of the following choices:
(1) Find by major
(2) Find by ID
(3) Find by mean salary
(4) Quit

Choice? 1
Please enter which major to search for: ehfeufheuh
Record not found.
Please select one of the following choices:
(1) Find by major
(2) Find by ID
(3) Find by mean salary
(4) Quit

Choice? 4
Have a nice day!

4. Find by ID

For option 2 (find by id), you must:

  • Prompt the user to enter an ID.

  • Use binary search to find the ID in your list of records. The data file provided lists each graduate’s record in increasing order by ID.

  • Print the information for the record matching the user-entered ID, if there is one.

  • If the ID that was not in the list let the user know you couldn’t find it.

Here are some examples (input bolded):

$ python3 graduates.py
Please select one of the following choices:
(1) Find by major
(2) Find by ID
(3) Find by mean salary
(4) Quit

Choice? 2
Please enter which ID to search for: PSYC15
1 found
PSYC15:Psychology, 2015. Mean salary: $63618.92. Total graduates: 3355678. Total employed graduates: 2593450
Please select one of the following choices:
(1) Find by major
(2) Find by ID
(3) Find by mean salary
(4) Quit

Choice? 2
Please enter which ID to search for: MAT123
Record not found.
Please select one of the following choices:
(1) Find by major
(2) Find by ID
(3) Find by mean salary
(4) Quit

Choice? 4
Have a nice day!

5. Find by Mean Salary

For option 3 (find by mean salary), you must:

  • Use linear search to find all the records that have a mean salary that is between a user entered minimum salary and a user entered maximum salary.

  • Prompt the user for a minimum salary. You must verify that the user input is a valid float, to do this, you can use the is_float() function we created for you, detailed in the Validating Floats section. You need to ensure that the user enters a number that is greater than or equal to 0. If not, continue to prompt until they do.

  • Prompt the user for a maximum salary. You must verify that the user input is a valid float, to do this, you can use the is_float() function we created for you, detailed in the Validating Floats section. You need to ensure that the maximum salary entered is be greater than or equal to the minimum salary. If not, continue to prompt until they do.

  • Print the information for the records that have a mean salary less than or equal to the maximum salary and greater than or equal to the minimum salary.

  • If no records with that mean salary range are found, let the user know.

Here are some examples:

$ python3 graduates.py

Please select one of the following choices:
(1) Find by major
(2) Find by ID
(3) Find by mean salary
(4) Quit

Choice? 3
Enter minimum mean salary: -5
Salary must be 0 or greater.
Enter minimum mean salary: puppy
Invalid input. Please try again.
Enter minimum mean salary: 15000
Enter maximum mean salary: -5
Max salary must be greater than minimum salary.
Enter maximum mean salary: 30000
2 found
BIOL01:Biological Sciences, 2001. Mean salary: $28335.21. Total graduates: 121173. Total employed graduates: 92858
PSYC01:Psychology, 2001. Mean salary: $27500.55. Total graduates: 173766. Total employed graduates: 149937
Please select one of the following choices:
(1) Find by major
(2) Find by ID
(3) Find by mean salary
(4) Quit

Choice? 4
Have a nice day!

6. Provided Library

The graduates_lab library has some helpful tools for managing graduate records in your program.

6.1. Graduates Class

The library provides an Graduates class, which encapsulates all the information you’ll need to keep track of one record. You can create an instance object of this class by calling the Graduates() constructor with each field of information from one row of the graduates.txt file passed in as separate parameters. You may use any of these methods in your solution, but you may not need to use all of them.

You can call the following methods on an Graduates object to retrieve information about it:

  • get_id(): Get the id field. (string)

  • get_year(): Get the year field. (int)

  • get_total(): Get the total graduates from that record. (int)

  • get_major(): Get the major field. (string)

  • get_sal(): Get the mean salary field. (float)

  • get_employed(): Get the total employed field. (int)

For example:

>>> from graduates_lab import *
>>> record = Graduates("BIOL01", 2001, 121173, "Biological Sciences", 28335.21, 92858)
>>> print(record.get_id())
BIOL01
>>> print(record.get_employed())
92858
>>> print(record.get_major())
Biological Sciences
>>> print(record)
BIOL01:Biological Sciences, 2001. Mean salary: $28335.21. Total graduates: 121173. Total employed graduates: 92858

6.2. Validating Floats

For option 3, you’ll prompt the user to enter a minimum and maximum salary, which needs to be a float. The library provides an is_float function that you can call on a string that will return a Boolean, where True means the string can safely be converted with float:

>>> from graduates_lab import *
>>> is_float("3.1")
True
>>> is_float("3.1.5")
False
>>> is_float("big")
False

7. Hints and Tips

  • You should practice good top-down design, incrementally implement and test your solution, and document your code with comments. Start with the main menu and get a skeleton of your code working first. Then add each option from the menu one at a time (start with quit as it is easy and will allow you to exit your program when you are testing it). While much of the design is up to you, the requirements below are designed to avoid some headaches in the initial design.

  • To print an instance object of the Graduates class, you can call print() directly on the object:

record = Graduates("CHEM93", 1993, 148872, "Chemistry", 507616.0, 406585)
print(record)

The class knows how to format itself into a string, so you can avoid writing nasty formatting strings.

  • Validate menu selections. If the user doesn’t enter a valid number (1-4), let the user know it wasn’t a valid selection and prompt them again for a new menu item.

  • When reading file input, split() only generates a list of strings. Some of the strings will need to be converted to integers (year, total graduates, employed) and salary should be converted to float.

8. Requirements

The code you submit for labs is expected to follow good style practices, and to meet one of the course standards, you’ll need to demonstrate good style on six or more of the lab assignments across the semester. To meet the good style expectations, you should:

  • Write a comment that describes the program as a whole using a comment at the top of the file.

  • All programs should have a main() function.

  • Use descriptive variable names.

  • Write code with readable line length, avoiding writing any lines of code that exceed 80 columns.

  • Add comments to explain complex code segments (as applicable).

  • Write a comment for each function (except main) that describes its purpose, parameters and return value.

In addition, you’ll need to demonstrate good top-down design practices on two or more lab assignments across the semester. To meet the top-down design expectations, you should:

  • Have a main() function that serves as an outline for your program.

  • Your main() function should call other functions that implement subtasks.

  • The functions that are called by main() should be well-named and have good comments explaining their purpose, parameters (including their types), and return value (including its type).

  1. When reading the input data file, process the file once and store all the records as a list of Graduates objects. Reading the file once will make it faster to process later.

  2. Validate menu selections. If the user doesn’t enter a valid number (1-4), let the user know it wasn’t a valid selection and prompt them again for a new menu item.

  3. Validate your minimum and maximum search inputs when searching by salary.

  4. For Search by Major and Search by Mean Salary, all matching records should be printed (if they exist).

  5. Search by ID must use binary search to find the matching record (if one exists). If the matching record exists, it should be printed.

  6. For all searches, if no records are found, the user should be notified.

  7. Write one function that prints a list of Graduate objects. See the hint above on how you can print a Graduates object.

  8. After each search, your program must return to the main menu and allow the user to perform another search or quit the program.

Answer the Questionnaire

After each lab, please complete the short Google Forms questionnaire. Please select the right lab number (Lab 08) from the dropdown menu on the first question.

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, including your vscode editor, the browser and the terminal. Then click on the logout icon (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!