Supplemental Problems

Supplemental Problems extend the range of problems considered in the course and help sharpen problem-solving 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 extra-credit problems may be turned in during the last week of classes (December 7-13, 2019). (If more than 2 extra-credit 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 post-conditions)
        || (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 non-approved 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 scale-notes.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 problem-specific 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 widely-used 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 24-hour 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.
- Problem-specific 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)ⁿ.
    (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 10-point 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.
- 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.
- Problem-specific 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 2-dimensional grid. If emergency telephones are placed at the intersection of streets, then their location can be modeled by a 2-dimensional 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][s-1], [r][s-2], or [r+1][s-1]. (Due to one-way 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:
1. 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.)
2. 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).
3. The program should print the coordinates of any intersection that is not "safe".
4. 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.
- Problem-specific 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 non-letters 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.
Problem-specific grading form for Supplemental Problem 4

Creating and Summing Singly-Linked Lists

In this problem, singly-linked 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 non-negative integer
     @param f: a defined function of one variable
     @param newList:  when processing is completed,
         newList * is a newly-created list of n nodes
     @pre-condition:  newList may or may not be initialized
     @post-condition: 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 singly-linked list
     @returns:  a pointer to a list of doubles
     @post-condition:  the returned list has the same number of nodes
        as the old list
     @post-condition:  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*x-1. 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.
- Problem-specific grading form for Supplemental Problem 5

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", &pounds &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 twenty-dollar 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 twenty-dollar bill
   1 five-dollar bill
   4 one-dollar 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 ten-dollar 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 twenty-dollar bill"); but when multiple bills of a given type are needed, then the plural form is given (e.g., "4 one-dollar 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 twenty-dollar 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:
1. 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.
2. 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 multiple-item 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 non-number 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, well-known 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 psycho-therapist, 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
---₁ my singleWord ---₂ me ---₃		tell me about your singleWord
---₁ i am ---₂		i am sorry to hear you are ---₂
---₁ am i ---₂		do you believe you are ---₂
---₁ you ---₂ me ---₃		why do you think i ---₂ you
---₁		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 crazy

Each 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 word me later on corresponds to the first pattern, with the following matches:

Pattern Element	Words from this Sentence
---₁	well
my	my
singleWord	friend
---₂	made
me	me
---₃	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 Eliza-based pattern-matching 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 labor-intensive 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 north-south or east-west; 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 low-speed 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 rather-general 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 north-south size of the city grid and the east-west 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 east-west 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 one-hydrant 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

Processing a Grocery-Store Order

[approximately 12 points]

File grocery-items.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 1-18 contain the serial number of a grocery item (using 1-based indexing).
  - Columns 19-45 contain the title of the item.
  - Columns 46-56 contain a category for the item, such as fruit, vegetable, dairy, etc.
  - Columns 57-63 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 grocery-item 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 insert-item 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 supplemental-problem 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 grocery-item 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 singly-linked 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 singly-linked 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 linked-list 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.

CSC 161.01	Grinnell College	Fall 2019
	CSC 161.01: Imperative Problem Solving with Lab

Notes:

Supplemental Problems

Submission Details

Some Grading Notes:

Problem Statements

Parking Lot Charges

Making Early Loan Payments

Emergency Telephones

Histogram of Letters

Creating and Summing Singly-Linked Lists

Function `sqrt`

C's math library `math.h`

Currency Conversion

Shopping Bargains

Classifying SAT and ACT Scores

A Simplified Eliza Program

Sample Dialogue:

Historical Note

Exercise

Assigning Lab Partners

Trip Planning

Distance to Fire Hydrants

Processing a Grocery-Store Order

Problem Overview

Problem Details

A C Version of Scheme's MAP Procedure

Notes:

Supplemental Problems

Submission Details

Some Grading Notes:

Problem Statements

Parking Lot Charges

Making Early Loan Payments

Emergency Telephones

Histogram of Letters

Creating and Summing Singly-Linked Lists

Function sqrt

C's math library math.h

Currency Conversion

Shopping Bargains

Classifying SAT and ACT Scores

A Simplified Eliza Program

Sample Dialogue:

Historical Note

Exercise

Assigning Lab Partners

Trip Planning

Distance to Fire Hydrants

Processing a Grocery-Store Order

Problem Overview

Problem Details

A C Version of Scheme's MAP Procedure

Function `sqrt`

C's math library `math.h`