Supplemental Problems
Supplemental Problems extend the range of problems considered in the course and help sharpen problemsolving skills. To support this objective, all Supplemental Problems are to be done individually.
 You may ask the instructor about any part of the course (including any Supplemental Problem) at any time.
 You should not discuss any Supplemental Problem with other students (e.g., students from the class, CS majors, or other students).
 Help from assistants in the lab is limited. See The Role of Tutors For Computer Science 161 for details.
Problems numbered 6 or higher may be turned in for extra credit. However, no more than 2 extracredit problems may be turned in during the last week of classes (December 713, 2019). (If more than 2 extracredit supplemental problems are submitted during the last week of classes, only the first two submitted will be graded.)
Quick links: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
Submission Details
Use the link, Detailed Coursework Instructions, to find specific instructions regarding code, submission, and testing of supplemental problems.
Some Grading Notes:

Since every programming task should yield readable and carefully tested code,
the grading of all programs for this course will begin with the following
algorithm (expressed in C format):
if ((no_comments)  (missing pre or postconditions)  (formatting_does_not_show_structure)  (long_procedures_not_divided_into_sections_with_clarifying_comments)  (no_evidence_of_compilation)  (no_test_plan,__no_listing_of_circumstances__OR__no_listing_of_test_cases)  (no_test_runs)  (no_commentary_on_correctness)  (no_signed_certification_regarding_sources_and_help)  (use of Bubble Sort or nonapproved sorting algorithm) return (no_grade);

Global constants (identifiers declared with const) may be used in any supplemental problems. As an example, any solution to a supplemental problem may include scalenotes.h, which includes declarations, such as
const int pitchA0 = 27;
However, except for Suppemental Problllem 1, use of global variabless is expressly forbidden for any problem numbered 2 or higher.
 10 for declaration of first global variable
 0 points total on problem if 2 or more global variables.

When a program and its output are submitted according to the above instructions, it should be understood that any output was generated by the program as given, unless explicit comments indicate changes that might have been made. Discrepancies between a program and an output file may raise questions of academic dishonesty; and, by College policy, any evidence of academic dishonesty must be turned over to the Academic Standing Committee for action.

Grading for each required supplemental problem will involve two parts:
 A general feedback form that highlights common characteristics of good programming practice.
 A problemspecific form tailored to the individual problem.
Problem Statements

Parking Lot Charges
A downtown parking lot charges $1.25 per hour for parking between 7:00 am and 5:00 pm, $2.40 per hour between 5:00 pm and midnight (high demand for people seeking entertainment), and $3.00 between midnight and 7:00 am (since late night requires an attendant to be paid time and a half and a security team is needed).
In this problem, we consider cars parked for 24 hours or less; to avoid the parking lot becoming a dumping ground, cars may NOT be parked continuously in the lot for more than a day. Further, for reasons of security, cars are not allowed to enter the facility between midnight and 7:00 am.
By widelyused convention, midnight is considered 12:00 am, and noon is considered 12:00 pm.
Write a program that first reads from the user the starting and ending times for a car, as follows:
 starting hour: hour car entered lot (int 1..12)
 starting minute: minute car entered lot (int ≥ 0)
 start before or after noon: char 'a' for am or char 'p' for pm
 ending hour: hour car left lot (int 1..12)
 ending minute: minute car left lot (int ≥ 0)
 end before or after noon: char 'a' for am or char 'p' for pm
The program then should use these six times read to compute the parking fee charged for the car. The following cases illustrate some possible values for user input.

Car parked 24 hours from 12 midnight one day to 12 midnight the next.
start_hour: 12 start_minute: 0 start_ampm: 'a' end_hour: 12 end_minute: 0 end_ampm: 'a'

Car parked from 8:10 am to 10:47 pm
start_hour: 8 start_minute: 10 start_ampm: 'a'; end_hour: 10; end_minute: 47; end_ampm: 'p';

Another representation for a car parked from 8:10 am to 10:47 pm
start_hour: 7; start_minute: 70; start_ampm: 'a'; end_hour: 8 end_minute: 167 end_ampm: 'p'

Car parked from 5:15 pm to noon the next day
start_hour: 5 start_minute: 15 start_ampm: 'p' end_hour: 12 end_minute: 0 end_ampm: 'p'

Another representation for a car parked from 5:15 pm to noon the next day
start_hour: 5 start_minute: 15 start_ampm: 'p' end_hour: 10 end_minute: 120 end_ampm: 'a'
Programming Notes:
 You may NOT use loops or recursion in this program.
 Rather than work with hours, minutes and am/pm separately throughout the program, you may want an internal variable (e.g., starttime and endtime) that works with a 24hour clock—possibly extending over 2 days (e.g., 0..48). Presumably, the values of these internal variables would be computed based on the six variables read.
 If the starting time read is between midnight and 7:00 am, or if an hour entered is not between 1 and 12 (inclusive), the program should report an error and quit without further processing. Similarly, the program should report an error and terminate, if a value read for minutes is negative.
Grading Forms
 A general feedback form that highlights common characteristics of good programming practice.
 Problemspecific grading form for Supplemental Problem 1
Note: In addition to the program, a separate page should indicate what cases should be considered in the testing of this program, what test data have been identified to test the program in each of the cases, and what the program printed for each of the tests.

Making Early Loan Payments
When investigating a loan, a customer typically states the amount of money (loanAmount) and specifies the loan's length (number of months N). A bank or other lender proposes an annual interest rate (annRate) for the loan. (The annual rate should be specified as a percentage, such as 4.59%—entered by a user as 4.59.) With this information, the monthly payment for the loan is given by the formulae:
monthlyRate = annRate / 1200.0
payment = loanAmount * monthlyRate / (1.0  (1 + monthlyRate)^{(N)})For example, a loan to improve a house might involve $26,000 for 25 years (300 months) at an annual rate of 8.75%, yielding a monthly payment of $213.76.
The expectation is that the customer will pay this amount (in dollars and cents) each month, although a slight adjustment may be needed the last month to make up for any rounding in the computation.
The expected payment notwithstanding, the terms of many loans allow the customer to pay an additional amount for one or more months in order to shorten the length of the loan and possibly save some interest charges. This problem investigates the consequences of paying twice the required amount for the first few months.
More specifically, the program should have these characteristics:
 The beginning of the program should read from the terminal the values of the loan amount, length (in months), and annual interest rate.

The program should compute the normal loan payment using at least two
functions:

double compute_neg_power (double value, int n)
that returns 1 / (value)^{n}.
(In the computation, the function should use successive multiplications. Use of the more general, but much less efficient function pow in th C library will yield a 10point penalty.) 
double compute_payment (double annRate, int months, double amt)
that returns the monthly payment for the given parameters.  compute_payment should call compute_neg_power.

double compute_neg_power (double value, int n)

The main procedure should determine the actual length of the loan
and the total amount paid assuming each of three payment options:
 The customer pays exactly the expected amount each month (except that the last month may be smaller, if appropriate)..
 The customer pays twice the expected amount the first month and then the expected amount each subsequent month (except that the last month may be smaller, if appropriate).
 The customer pays twice the expected amount each month in the first year and then the expected amount each subsequent month (except that the last month may be smaller, if appropriate).

Some programming constraints:
 No global variables may be used in this program.
 When using functions, all relevant values must be passed as parameters.
 Values may be returned from functions either through a return statement or via parameters (with addresses).
 No printf statements are allowed in any final function except main. (printf may be used in functions for testing, but these should be commented out for any final runs.) In particular, neither function compute_neg_power nor function compute_payment should print anything.

Computations of actual payments and the cost of the loan should be given
to the nearest cent. Note that if double value is a real number,
then
 ((int)(value * 100.0)) / 100.0 truncates value to two decimal places, and
 ((int)(value * 100.0 + 0.5)) / 100.0 rounds value to two decimal places.
 In addition to computing the cost of the loan for the three payment plans, the program should indicate the additional costs (if any) of each of the first two payment options over the third.
Grading Forms
 A general feedback form that highlights common characteristics of good programming practice.
 Problemspecific grading form for Supplemental Problem 2

Emergency Telephones
[This problem is inspired by Problem 3 on the 1985 Advanced Placement Computer Science Examination; folklore now sometimes refers to this exercise as "The Dreaded TelLocs Problem".]
The arrangement of streets in many midwestern cities resembles a 2dimensional grid. If emergency telephones are placed at the intersection of streets, then their location can be modeled by a 2dimensional array:
#define north_south_size 20 #define east_west_size 25 int tel_locs [north_south_size] [east_west_size];
For this array, the location tel_locs[0][0] is considered to be in the southwestern corner of the grid; and the location tel_locs[1][2] has the location that is north 1 block and east 2 blocks of the southwestern corner of the grid.
Within this array, tel_locs[i][j] is 1 if an emergency telephone is located at intersection of streets i and j, and tel_locs[i][j] is 0 otherwise.
In a certain city, intersection [r][s] is considered "safe" if the [r][s] is within 2 blocks of an emergency telephone — moving north or west. Thus, (ignoring the edge of the array), [r][s] is "safe" if there is an emergency telephone at [r][s], [r+1][s], [r+2][s], [r][s1], [r][s2], or [r+1][s1]. (Due to oneway streets, the notion of "safe" does not consider emergency telephones located to the south or east of intersections.)
Write a C program that analyzes a proposed placement of emergency telephones in a city to determine if all intersections in the city can be considered "safe". The program should have these characteristics:
 The array tel_locs should be declared and initialized as part of the program. (You should not read in the placement of telephones; the program will have to be edited for each proposed telephone placement.)
 A function safe should take a location and a tel_locs array as parameters and return 1 or 0 if the location is "safe" or not (respectively).
 The program should print the coordinates of any intersection that is not "safe".
 The end of the program should indicate "all safe" if all intersections in the city are "safe" or "unsafe intersections exist" if there is at least one intersection that is not "safe".
Grading Forms
 A general feedback form that highlights common characteristics of good programming practice.
 Problemspecific grading form for Supplemental Problem 3

Histogram of Letters
When given a number of data elements, it sometimes is convenient to visualize how many times each outcome occurs. For example, in reviewing text, we might count the number of times each letter occurs (ignoring case), and then print this number of asterisks (*) for each letter. The resulting diagram is called a histogram. As an illustration, the following diagram shows a histogram for the letter counts in this paragraph.
Histogram follows: * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * a b c d e f g h i j k l m n o p q r s t u v w x y z
Programming Notes:
 This program should allow any number of characters to be entered before a # character is typed, and the input may be on one or more lines.
 Separate variables, countA, countB, ..., countZ, is tedious, inefficient, and error prone, so should not be used. Rather use an array for the counts (e.g., count[0], ..., count[25] or count ['a'], ..., count ['z']).
 In this histogram of letters, all nonletters should be ignored.
 Use of C functions, tolower and isalpha, within the ctype.h library is encouraged.
 In order to determine the number of lines in the histogram, the program will need to determine the maximum count for any letter. For letters with this maximum count, the histogram will have a column of asterisks that goes from the top row to the bottom (just before the row of printed letters).
Grading Forms
 A general feedback form that highlights common characteristics of good programming practice.
 Problemspecific grading form for Supplemental Problem 4

Creating and Summing SinglyLinked Lists
In this problem, singlylinked lists containing doubles will use the following types:
typedef struct Node * listType; typedef struct Node { double value; listType next; } listNode;
This problem asks you to create two procedures for lists of doubles, and include those procedures within a program that performs rigorous testing. Specification of the two required procedures follows.
/* procedure to create a list of n nodes @param n: a nonnegative integer @param f: a defined function of one variable @param newList: when processing is completed, newList * is a newlycreated list of n nodes @precondition: newList may or may not be initialized @postcondition: the value stored in the ith node is f(i) */ void createList (int n, double f(double x), listType * newList); /* procedure to create and return a new list, where the ith node in the new list is the sum of the values in the first i nodes of an original list @param oldList: points to a valid singlylinked list @returns: a pointer to a list of doubles @postcondition: the returned list has the same number of nodes as the old list @postcondition: the value stored in the ith node of the new list is the sum of the values in the first i nodes of oldList */ listType accumulatingSeq (listType oldList);
Examples (using Scheme notation for lists
 Example 1: Suppose sqr(x) = x*x. Then
createList (7, sqr, &lst) sets lst to(1.0 4.0 9.0 16.0 25.0 36.0 49.0)
 Example 2: createList (4, sqrt, &lst) sets lst to
(1.000 1.414 1.732 2.000)
 Example 3: Suppose g(x) = 2*x1. Then
createList (7, g, &lst) sets lst to(1.0 3.0 5.0 7.0 9.0 11.0 13.0)
 Example 4: Suppose lst1 is the list (1.0 2.0 3.0 4.0 5.0 6.0 7.0)
Then accumulatingSeq (lst1) returns the list(1.0 3.0 6.0 10.0 15.0 21.0 28.0)
 Example 5: Suppose ls2 is the result of Example 3.
Then accumulatingSeq (lst2) returns the result of Example 1 above.
Function sqrt
Tthe square root function sqrt is available in C's math library math.h. As a reminder, the following paragraphs are copied from the lab on Functions Parameters and Arrays, Program Correctness, and Testing.
C's math library math.h
The header file math.h for C's math library can be used in the same way as other C libraries, and compiling a program that includes math.h can proceeds without trouble. That is, the translation of a C program using the math library follows the same steps as programs using other libraries.
However, by default, the gcc compiler does not link compiled programs with the math library. (The math library is large and thus is not added to an executable program, unless needed.) To instruct the computer to link your program to the math library, you need to use the lm option when compiling:
gcc lm ...
Grading Forms
 A general feedback form that highlights common characteristics of good programming practice.
 Problemspecific grading form for Supplemental Problem 5
 Example 1: Suppose sqr(x) = x*x. Then
Any of the following problems may be done for extra credit. As noted in the course syllabus, however, a student's overall problems' average may not exceed 120%.

Currency Conversion
[approximately 10 points]
In the United Kingdom and some British Crown dependencies, modern currency is based on the pound sterling, often identified simply as the pound or by the abbreviation GBP. Further, the pound may be subdivided into 100 pence. (The singular form of pence is penny.) When this problem was updated in June, 2019,
1.00 GBP = $1.26843 (United States dollars)
Write a program that reads a quantity using British currency, such as the following:
int pounds; double pence; scanf ("%d %lf", £s &pence
The program then should compute the corresponding amount in United States dollars and cents. This amount should then be specified in one, five, ten, and twentydollar bills, and pennies. Your computation should use the fewest number of bills. Also, fractions of a cent should be ignored — that is, you should not round up fractions of a penny.
For example, if a user enters 23 for pounds and 18.97 for pence, the program might print the following:
23 pounds 19.27 pence translates to $29.41 This may be paid as 1 twentydollar bill 1 fivedollar bill 4 onedollar bills 41 cents in change
Notes:
 23 pounds 19.27 pence actually translates to $29.4183. Since fractions of a cent are ignored (no rounding as currency exchanges never give more), the customer would receive $29.41.
 Do NOT try to compute how many of each coin type should be given to the customer (pennies, nickels, dimes, and quarters).
 In translating this amount to dollars and cents, note that only bills actually used are printed. (No tendollar bill is listed in the above output.)
 When one bill of a given type is mentioned, the output uses the singular form "bill" (e.g., "1 twentydollar bill"); but when multiple bills of a given type are needed, then the plural form is given (e.g., "4 onedollar bills").
 If no pennies are needed, the "cents" line should not be printed. If only one penny is needed, then the singular form, "1 cent in change", should be printed.
 The program should not use loops to compute bills or change. Rather, use integer division (/) and remainder (%) in computations. Also, multiplication should not be used in computing a remainder. For example, if usd is the amount of dollars involved (as an int), then usd / 20 will compute the number of twentydollar bills required, and usd % 20 is the amount of money needed in smaller bills.

Shopping Bargains
[approximately 10 points]
A store has two policies to encourage shoppers to buy as many goods as possible:
 The purchase of 1 item is full price, but the cost of a second identical item is 10% off, the cost of a third identical item is 20% off, etc., although no item is sold for less that 10% of its original price.

The shop offers a global discount for high spenders:
 If a shopper's overall bill is between $100 and $200 (inclusive), then the shopper is given a 15% discount (beyond any reduction for purchases of multiple identical items).
 If a shopper's overall bill is over $200 (i.e., $200.01 or higher), then the shopper is given a 25% discount (beyond any reduction for purchases of multiple identical items).
Write a program that reads a sequence of original item costs as input and computes the total charge a customer will pay after discounts. Reading should continue on one or more lines until the user enters a cost of 0.00. For this exercise, assume that the costs of identical items will be grouped together, and all consecutive equal costs relate to identical items. To illustrate, consider this sequence of costs:
1.25 8.73 5.55 5.55 5.55 12.84 5.55 5.55 20.30 20.30 20.30 20.30 0.00
Here, we assume first item purchases costs $1.25 and the second costs $8.73. The third, fourth, and fifth items have the same cost, so we assume they are identical items (the cost of these items after multipleitem discount will be 5.55 + 0.9*5.55 + 0.8*5.55). The sixth item costs 12.84. The next two items again cost 5.55, but these must represent a different item than the earlier ones of the same price, since these costs are not contiguous with the previous run of 5.55 prices. Thus, the cost of the seventh and eighth items is 5.55 + 0.9*5.55. The last four items again are considered identical, with costs 20.30 + 0.9*20.30 + 0.8*20.30 * 0.7*20.30. The number 0.00 at the end signifies the end of the input.
Notes:
 Processing should make one pass only through the initial list of costs.
 The program may utilize any helper functions that seem convenient, although the user interface must be as prescribed. (However, even with helper functions, processing should not make multiple passes through the data.)
 The program should print a cost of 0.00 if the initial sequence of costs is empty.
 The program should produce an error message, if any of the prices is a nonnumber or if any of the items are negative numbers.
Some Clarifications
 Reading data in one loop and then going back through the data in a second loop would involve two passes through the data and thus be inconsistent with the requirement of only one pass through the data.

The use of arrays in this problem will yield very few points.
 Since allocation of space to an array requires knowledge of the size required, use of a [statoc] declared array to store costs will not allow any number of elements to be entered—imposing a constraint not imposed by the problem.
 If dynamic arrays were used, then data would need to be copied from one array to another from time to time, also violating the requirement that only one pass be made through the data.

Classifying SAT and ACT Scores
[approximately 10 points]
Each fall, the Departments of Computer Science and Mathematics and Statistics provide recommended placements for incoming students in first courses in computer science, mathematics, and statistics. Overall, the process involves about 125 rules within a reasonably complex system.
One of the early steps in this process involves the classification of standardized scores, based on student scores on the SAT and/or ACT. The following edited table suggests the basic framework for a classification.
Category SAT Range ACT Range Superior 700– 31– Excellent 640–690 28–30 Strong 600–630 26–27 Good 550–590 24–25 Adequate 480–540 20–23 Participating –470 –19 Although this table provides a starting point, students scores sometimes differ substantially from one test to another. This leads to the following rules for determining the actual category for a student' standardized scores.
 If a student takes the SAT several times, only the best SAT score is considered.
 If a student takes the ACM several times, only the best ACT score is considered.
 If a student takes the SAT or the ACT, but not both, then the above table provides the classification.

If a student takes both the SAT and ACT,
 the student's classification is the higher of the two categories from the above table, EXCEPT
 if the categories differ by three or more levels, then the top category is lowered by one.
 If a student has not taken either the SAT or ACT, the category is specified as "Unknown".
Examples:
 A student with a 650 SAT or 28 ACT (or both) would be placed in category "Excellent" for standardized scores.
 A student with a 650 SAT and 24 ACT would be placed in category "Excellent", based on the 650 SAT. (The 24 ACT is two categories lower than the 650 SAT, and two categories is not enough to lower the classification.)
 A student with a 650 SAT and a 23 ACT would be placed in category "Strong". (The "Excellent" category from the SAT would be lowered by one, since the 23 ACT is three categories lower.)
Write a program that computes the appropriate category for a specified SAT and ACT score. Rather than read SAT or ACT scores from the keyboard, the program should assign an SAT and ACT score to variables at the very beginning of the program. If the student has not taken an SAT or an ACT test, then the variable for that test should be set to 0.
A Clarification
 Since only the best SAT score is used and only the best ACT score is used in this problem, the program should expect that only these maximum scores are included in processing. For example, the program need not review a sequence of SAT scores to determine the best, but rather can use a single variable (not an array) to record the best SAT score.
A Simplified Eliza Program
[approximately 12 points]
One of the early, wellknown programs within the field of artificial intelligence was called Eliza, a program by Joseph Weizenbaum. The idea was to simulate conversation between a patient and psychotherapist, based on a series of patterns and corresponding responses. Although the original program had an extensive sequence of patterns, this assignment focuses on the following five rules:
Pattern Response Template _{1} my singleWord _{2} me _{3} tell me about your singleWord _{1} i am _{2} i am sorry to hear you are _{2} _{1} am i _{2} do you believe you are _{2} _{1} you _{2} me _{ 3 } why do you think i _{2} you _{1} in what way In this table, the blank spaces in a pattern, denoted by subscripted dashes, can be filled in with any sequence of words. Similarly, singleWord represents exactly one word in a sentence. For example, these patterns might generate the following "conversation," where the responses are indented and in italics:
Sample Dialogue:
well my friend made me come here
tell me about your friend
he says i am depressed
i am sorry to hear you are depressed
i think i need help
in what way
i wonder if you would help me learning to program Scheme
why do you think i would help you
when i registered for the course i wondered am i crazy
do you believe you are crazyEach of these statements and responses follows the template/response patterns given. For example, in the first statement:
well my friend made me come here
the presence of the word
my
near the start of the sentence with the wordme
later on corresponds to the first pattern, with the following matches:Pattern Element Words from this Sentence _{1} well my my singleWord friend _{2} made me me _{3} come here After identifying these pattern elements for the first pattern, the Eliza program uses the corresponding response template. In this case, the program prints "Tell me about your friend". The first four of these words come directly from the template. For the final word, singleWord in the template was matched with the word "friend" in the above analysis.
Historical Note
Although this approach may seem simple today, Joseph Weizenbaum used this approach as the basis for his widely heralded Eliza in 1966. In 1976, Weizenbaum noted he "was startled to see how quickly and how deeply people conversing with [ Eliza] became emotionally involved" in the conversation. People shared their hopes and secrets, and they became annoyed if other people looked over their shoulders or otherwise interrupted. Even when they knew Eliza was a program, they often talked as if it were a close personal friend.
Exercise
Write a C program to solve this Elizabased patternmatching problem. For example, if you entered the successive dialog strings from the "Sample Dialog" above, the program would respond as the example indicates. The program should continue to read user input until the user types "quit".

Assigning Lab Partners
[approximately 12 points]
In CSC 161 and numerous other courses, students may work on labs or projects (sometimes other assignments) in small groups (usually pairs). These groups are assigned by the instructor, and groups are changed frequently. This problem seeks a program to determine these assigned groups. (Currently, the assignments are done manually, with a laborintensive process.) The basic requirements follow:
 Suppose there are N students in the class (where N is between 24 and 38). For the purposes of this problem, the students are numbered 1, ..., N.
 Early in the semester, students are given the option of indicating which students they do NOT to work with during the semester.
 Following past history, for this problem, we assume no more than 6 students indicate which people they do not want to work with. (Usually the number is just 2 or 3.)
 Groups of 2 are preferred for an assignment, but a group of 3 is needed if N is odd.
 To the extent possible, students should be working with someone different with each assignment.
 During the semester, a student should not be asked to work in a group of three more than once.
 Sometimes during the semester (but not often), a student drops the course. That is, the student may be assigned a group for the first several weeks, but the student should not be assigned a partner after a designated week.
Write a program that identifies and prints up to 14 assignments of students (i.e., up to one new assignment of pairs each week). The program should have the following features:
 The program is deterministic. That is, the program makes the same assignments every time it is run. (This allows the program to be run several times during the semester, if a few people drop.)
 The program provides the option that up to 8 students may drop the course after varying assignments. (In practice, there are rarely more than 2 drops, so allowing 8 is intended to be safe.)
 Under varying circumstances, it may not be possible to make different assignments each week. However, in all cases, a student should never have to work with someone they explicitly wanted to avoid. Also, the resulting assignments should have as few repeated pairs of students as possible.
 If a group of 3 is required (e.g., the number of students in the class is odd), then the students in the group of 3 should change from week to week as much as possible.

Trip Planning
[approximately 15 points]
In planning a trip by automobile, several routes might be considered. Some roads may be direct, but speed limits vary according to the type of road. Further, travel through cities may take longer than routes that avoid driving through city centers. This problem considers finding routes in Iowa that will take the least amount of time from one city to another. For reference, the Iowa Department of Transportation posts a map of the main routes in Iowa. Most highways run northsouth or eastwest; interstate highways run through the middle of the state, US highways and some state roads run in some areas with reasonably high speed, and rural or county roads connect many smaller towns.
In this problem, we consider the main interstates, US highways, state roads, and county roads. We do not consider small connecting roads, improved gravel roads, or rough gravel streets intended for lowspeed farm travel. Further, all routes start at a designated starting city, go from one city to an adjacent city, until a destination city is reached.
The following table identifies the time (in minutes) for direct travel from one city to another within the northeastern quadrant of Iowa. (Data from Google maps, accessed January 2, 2015.) A dash or blank indicates there is not a direct highway between cities, so a traveler must follow a path through intermediate cities on the way.
Ames Cedar Rapids Charles City Clinton Davenport Decorah Des Moines Dubuque Grinnell 10Iowa City 11Iowa Falls 12Manchester 13Maquoketa 14Marshalltown 15Mason City 16Nevada 17New Hampton 18Waterloo 19Webster City Ames — 35 min 50 min. 14 min 44 min Cedar Rapids — 98 min. 141 min. 77 min. 74 min. 32 min. 54 min. 70 min. 76 min. 51 min. Charles City — 78 min. 39 min 22 min. 48 min Clinton 98 min. — 47 min. 43 min. Davenport 47 min. — 74 min. 59 min. 44 min. Decorah 141 min. — 115 min. 90 min. 48 min. Des Moines 35 min — 51 min. 54 min. Dubuque 77 min. 74 min. 115 min. — 89 min. 47 min. 33 min. 87 min. Grinnell 74 min. 51 min. — 63 min. 92 min. 38 min. 80 min. Iowa City 32 min. 59 min. 89 min. 63 min. — 77 min. Iowa Falls 50 min. 78 min. 92 min. — 57 min. 58 min. 51 min. 54 min. 35 min. Manchester 54 min. 44 min. 90 min. 47 min. 77 min. — 68 min. 48 min. Maquoketa 70 min. 43 min 33 min. 68 min. — Marshalltown 76 min. 54 min. 38 min. 57 min. — 36 min. 64 min. Mason City 39 min. 58 min. — 91 min. 70 min. Nevada 14 min. 51 min. 36 min. 91 min. — 78 min. New Hampton 22 min. 48 min. — 44 min. Waterloo 51 min. 48 min. 87 min. 80 min. 54 min. 48 min. 64 min. 44 min. — Webster City 44 min. 35 min. 70 min. 78 min. — Write a program that reads two cities and determines the path with the least driving time between them. The program should print both the list of cities on the path and the total time for the overall route.

Distance to Fire Hydrants
[approximately 12 points]
Within cities, rates for property insurance often depend upon the distance between a house and the nearest fire hydrant. This problem outlines a simple version of this rathergeneral problem.
Here are some details. We suppose that a city is organized as a grid of streets, and that fire hydrants are located near selected street intersections. The best insurance rates (category A) are available to houses who are at an intersection where there is also a fire hydrant. The second best insurance rates (category B) are available to houses at an intersection where the nearest fire hydrant is 1 block away (there is no fire hydrant at the house's intersection, but there is a fire hydrant 1 block away). The third best insurance rates (category C) are available to houses at an intersection where the nearest fire hydrant is 2 blocks away. The worst insurance rates (category D) are applied to houses for which there is no fire hydrant within 2 blocks (all hydrants are 3 or more blocks away).
Of course, this problem is not unrelated to the Emergency Telephone problem (supplemental problem 3), with telephones replaced by fire hydrants and with searching possible in any direction. However, in this case, the issue is how close the nearest fire hydrant might be. Also, for this problem, the fire hydrant information will be located in a file.
Additional details follow:

Fire hydrant information will be stored in a file, organized as follows:
 The first line of the file will contain the city name (up to 40 characters).
 The second line of the file will contain two integers: the northsouth size of the city grid and the eastwest size of the city grid.
 A line of 0's and 1's for the fire hydrants at successive intersections (west to east) for a row of the grid; a 0 indicates no hydrant at that intersection, and a 1 indicates there is a hydrant. The 0's and 1's are separated by one or more spaces.
 Each successive lines of 0's and 1's represents an eastwest street in the town, going from north to south.
 The program is to read the file name from the command line.
 The program is to print the name of the city, followed by a table of intersections, with the category rating (A, B, C, or D) for each intersection. The table of intersection ratings will be the same size and organization as the city grid specified in the file.

For example, file onehydrant contains
the following data:
one hydrant city 3 5 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
For this data, the program should print the following:one hydrant city C B A B C D C B C D D D C D D
 You should test your program on various files, including

Fire hydrant information will be stored in a file, organized as follows:
Processing a GroceryStore Order
[approximately 12 points]
File groceryitems.txt contains an abbreviated inventory of grocery items in the Pacific northwest in February, 2019. The first seven lines of the file follow:
item unit number name category price unit 0000000001111111111222222222233333333334444444444555555555566666666667 column 1234567890123456789012345678901234567890123456789012345678901234567890 numbers 100 Pacific Rose Apples fruit 0.99 pound 101 Navel Oranges fruit 1.69 pound 102 Honeycrips Apples fruit 2.99 pound 103 Anjou Pears fruit 1.49 pound
This excerpt indicates the content and format of the file:

The first two lines provide titles for the various columns.

The third and fourth lines specify the numbers of the each character in a line (01, 02, 03, ... ).
 Columns 118 contain the serial number of a grocery item (using 1based indexing).
 Columns 1945 contain the title of the item.
 Columns 4656 contain a category for the item, such as fruit, vegetable, dairy, etc.
 Columns 5763 contain the item's price per unit.
 Columns 64 and following specify the type of unit, such as pound, gallon, bag, package
Problem Overview
This problem asks you to write a program to use this groceryitem information, together with a person's ordering information, to create a full report for the order.
Problem Details
A user is to enter a sequence of item numbers, with the amount desired for each item. (The user should enter item number 0 (no quantity needed) to signal the end of the order.) The program then will print those items (from the file), where each line contains two additional columns: the quantity wanted for that item and the total cost for that item. The bottom of the report also should contain the total cost of the order.
For example, if the user types
101 5.25 103 .8 0
Then the program should print
item unit quantity order number name category price unit desired cost 101 Navel Oranges fruit 1.69 pound 5.25 8.87 103 Anjou Pears fruit 1.49 pound 0.8 1.19 Total Cost of Order: 10.06
Some processing details related to processing efficiency.
 After the user data are entered, they should be sorted by item number, so within the program the order information is in the same order as the grocery items in the file.
 Sorting should be performed by an insertion sort—either using an insertitem procedure as each item is entered or a full insertion sort after data entry. (Use of any sorting algorithm other than an insertion sort requires explicit instructor permission. Use of an unauthorized sorting algorithm may yield a total score of 10 on this entire supplemental problem—that is, you may lose points on your supplementalproblem grade.)
 The file should be read only once, and each item read should be processed as it is read.
 Note that an array cannot be used to store all grocery items from the file. Not only would such an array be an unnecessary waste of space, but this program should work for any groceryitem file (not just the one given), and thus the number of grocery items in the file cannot be known ahead of time.


A C Version of Scheme's MAP Procedure
[approximately 12 points]
In Scheme, recall that the map procedure takes a procedure and one or more list(s) as parameters and returns the list obtained by applying the procedure parameter to the list(s). This problem asks you to write a basic version of map in C.
In particular, write a C procedure map with the following signature:
struct node * map (int f (int), node * lst)
where node is a list node defined as:
struct node { int data; struct node * next; };
and where f is a function that can be applied to an integer to obtain another integer.
Notes:
 The parameter lst points to the first node of a singlylinked list of integers.
 The list designated by lst is not changed by map.
 map returns a pointer to the first element of a new list.
 The resulting singlylinked list has the same length as the list lst and the elements on this new list should have values obtained by applying f to the integers stored in lst (and in the same order).
 Testing of this procedure is essential. It is suggested that you embed this procedure in a linkedlist program (perhaps from one of the laboratory exercises related to linked lists in Modules 101 or 110).
This problem may be solved either iteratively or recursively. Credit may be obtained for either the interactive or recursive solution. Additional credit is possible for two versions of this procedure, one iterative and the other recursive.
created 28 June 2019 (based on past years' work) by Henry M. Walker revised June 2019 by Henry M. Walker 

For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. 