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 |
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:
-
Search the dataset by major, using linear search.
-
Search the dataset by ID, using binary search.
-
Search the dataset by minimum and maximum mean salaries, using linear search.
-
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
inoperator 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 bothTrue, but "cld" in "cold" isFalse.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
Graduatesclass, you can callprint()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:
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:
|
-
When reading the input data file, process the file once and store all the records as a list of
Graduatesobjects. Reading the file once will make it faster to process later. -
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.
-
Validate your minimum and maximum search inputs when searching by salary.
-
For Search by Major and Search by Mean Salary, all matching records should be printed (if they exist).
-
Search by ID must use binary search to find the matching record (if one exists). If the matching record exists, it should be printed.
-
For all searches, if no records are found, the user should be notified.
-
Write one function that prints a list of Graduate objects. See the hint above on how you can print a Graduates object.
-
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 (
) 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
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!