CSC 161 Grinnell College Fall–Term 1, 2020
 
CSC 161
 
Imperative Problem Solving and Data Structures
 


Notes:


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.

Problems numbered 4 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 (5:00 pm CDT 9 October through 5:00 pm CDT 16 October 2020). (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

Submission Details

Each problem submission (whether submitted as a regular assignment or for extra credit) must include

Each program for a supplemental problem must begin with the following academic honesty certification:

    /***********************************************************************
     * Name:                                                               *
     * email address                                                       *
     * Sup. Problem Title and Number                                       *
     *      (25% off if title/number does not match assignment)            *
     * Assignment for                                            *
     ***********************************************************************/

    /* *********************************************************************
     * Academic honesty certification:                                     *
     *   Written/online sources used:                                      *
     *     [include textbook(s), CSC 161 labs or readings;                 *
     *       complete citations for Web or other written sources           *
     *      write "none" if no sources used]                               *
     *   Help obtained                                                     *
     *     [indicate name of instructor, if consulted}                     *
     *     [help from others is NOT allowed, so this section should        *
     *      explicitly certify that others have not been consulted]        *    
     *   My signature below confirms that the above list of sources        *
     *   is complete AND that I have not talked to anyone else             *
     *   (e.g., CSC 161 students) about the solution to this problem       *
     *                                                                     *
     *   Signature:                                                        *
     **********************************************************************/
    

Some Grading Notes:

Problem Statements

  1. Status of Loan Balance

    The wording of this problem is slightly edited from Problem 9 in Section 3.2 of "Problems for Computer Solutions Using BASIC" by Henry M. Walker, Winthrop Publishers, 1980.

    If $387.46 for an airline ticket is charged on a credit card, the company may specify a minimum monthly payment of $15.00 each month until the loan is paid off. This problem asks you to investigate the "cost" of making only the minimum payment. Interest might be charged at the rate of 1.5% of the outstanding balance at the end of a month. The balance for the next month is computed by the formula:

    new balance = old balance + interest - payment

    Write a program that reads from the terminal window the initial balance of a loan, the monthly interest rate, and the constant monthly payment. Have the program print a labeled table showing the month number and the balance at the beginning of that month (the balance at the beginning of the month 1 is the amount borrowed). Continue printing until a payment would cause the balance to drop to zero or below. Also print the final payment necessary to close the loan, the total amount made in payments, and the "cost" of the loan (total payments - loan).

  1. Simulation of Hi Ho! Cherry-O

    This problem explores statistics for the game of Hi Ho! Cherry-O. For our purposes, we will follow the description of the game as described in Wikipedia. Note, however, that the number of cherries on a player's tree is always between 0 and 10. If one spins a bird or dog and the number of cherries on the tree is 8 or fewer, then the number of cherries on the tree goes up by 2. However, if one spins a bird or dog and the number of cherries on the tree is 9 or 10, then the number of cherries on the tree goes to 10 (not higher).

    The game progresses in rounds, during which each player in turn spins a game spinner that has seven outcomes (as described in the Wikipedia article). In our simulations, we will assume that each outcome of the spinner arises randomly with equal probability.

    Within this framework, the specific purpose of this supplemental problem is general statistics on how many rounds the game is likely to continue, based on the number of people playing the game. In particular,

    • Write a program that reads the number of players who will be playing and the number of games they will play, and returns the average number of rounds played until a game is won.
    • For this simulation, the following 3 C procedures must be used (in addition to the main procedure).
      • Function turn simulates one turn of a player and has the following signature:
          /* function that uses the rand function to determine number
             outcome of a spinner to adjust the number of cherries in a player's bucket
             @param   init_cherries:  the number of cherries originally in the bucket
             @returns the number of cherries in the bucket, based on the value of a simulated spinner
           */
           int turn (int init_cherries)
                  
      • Function playGame simulates an entire game with a designated number of players and has the following signature:
          /* function that simulates an entire game of Hi Ho Cherrio
             @param    players   the number of players in the game  
             @returns  the number of rounds taken until some player wins
           */
           int playGame (int players)
                
      • Function playNGames simulates the playing of several games of Hi Ho Cherrio and has the followingn signature:
          /* function that plays several games of Hi Ho Cherrio and computes basic game statistics
             @param  players: the number of players in a game
             @param  games: the number of games to be simulated.
             @param  avg:   the address for the average number of turns in a game
             @param  max:   the address for the maximum number of turns in a game
             @param  min:   the address for the minimum number of turns in a game
             post-conditions:
                  the function has controlled the playing of the Hi Ho Cherrio games and stored the
                      average, maximum, and minimum number of turns in a game in the last 3 addresses
                  no printing is done in this function or in functions called by it
          */
            void playNGames (int players, int games, double* avg, int* max, int* min)
                

    Hints: Although you are free to approach this problem however you want, the following pieces might help.

    • A procedure play_round that
      • takes as parameters the number of players and an array of the cherries on their trees,
      • plays one round for each player, and
      • updates the array entries with the new totals for the number of cherries for each player.
    • A function check_win that takes the number of players ad an array of tree-cherry numbers as parameters and returns whether any of the players has won.

    Problem-specific grading form for Supplemental Problem 2

  1. Singly-linked-list Processing

    Program namelist-2020-fa.c contains a simple framework for maintaining a singly-linked list of names (with no more than 20 characters). The program has these features:

    • A singly-linked-list structure is defined.
    • The list is initially null.
    • A basic menu identifies several processing options, the program reads a user option, and the program calls a procedure for that option.
    • Procedure addName allows names to be added anywhere on the list.
    • Procedure print allows current names to be printed from the first to the last.

    This problem asks you to implement two additional functions within this program.

    • Function removeDuplicates removes duplicate nodes from the current list:

      • The first copy of a name on the list is retained.
      • All copies of a name after the first are deleted.
      • In the final list, the first copies of the names of the original list should be in the same order as at the start.

      In this processing,

      • Duplicate nodes should be removed and space deallocated, but no new nodes should be created.
      • Adjustments should be made on the original list; a new list should not be created separately and then transferred to the original list.
    • Function duplicate adds a duplicate of each node after the node on the current list:

      • For each node on the list,
        • A new is created.
        • The name from the existing node is copied to the new node
        • The new node is inserted into the list after the existing node.

        In this processing for duplicate,

        • Duplicate nodes should be added, but no nodes should be removed or deallocated.
        • Adjustments should be made on the original list; a new list should not be created separately and then transferred to the original list.

        For example, if the original list had 3 nodes:

        original list

        Then the new list after duplicate would have 6 nodes:

        revised list

    Programming Hints:

    • In Program namelist-2020-fa.c, code for addName and print should not be changed in any way.
    • Program namelist-2016-fa.c also contains stubs for the new operations, but the bodies of these procedures only print a message that the operations are not implemented. This problem asks you to expand these stubs to working procedures.
    • Although code within the existing addName procedure itself should not be changed, parts of that code could be copied, modified, and streamlined in another procedure.
    • In identifying duplicate names, it is up to the programmer to decide whether or not names with letters in different cases (upper case and lower case) are considered as the same name. Names with the same string of characters (with the same case) should be considered the same, but names with the same characters in different cases may or may not be considered the same (at programmer's discretion).

    Problem-specific grading form for Supplemental Problem 3


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%.

  1. Grading Passwords

    [8 points possible]

    Since many modern computer systems use passwords as a means to provide protection and security for users, a major issue can be the identification of appropriate passwords. The main point should be to choose passwords that are not easily guessed, but which the user has a chance of remembering. For example, passwords related to birthdays, anniversaries, family names, or common words are all easily guessed and should be avoided.

    Some common guidelines suggest that a password should contain at least 12 characters and include characters from at least three of the following categories:

    • uppercase letters
    • lowercase letters
    • digits
    • punctuation (considered to be anything not a letter or a digit)

    Other guidelines indicate that elements of passwords should be pronounceable. One simple measure of this guideline suggests that any group of letters in a password should contain both vowels and consonants.

    This supplemental problem asks you to write and test a function

    
       char gradePassword (char * password)
    

    that assigns a grade to the given password, as follows:

    • Starting at 0, add 1 point for each of the following elements in the password:
      • password contains at least 1 vowel
      • password contains at least 1 consonant
      • password contains at least 1 upper-case letter
      • password contains at least 1 lower-case letter
      • password contains at least 1 numeric character
      • password contains at least 1 punctuation mark
    • Adjust points based on the length of the password:
      • deduct 4 points for passwords that contain 6 or fewer characters
      • deduct 3 points for passwords that contain 7, 8 or 9 characters
      • deduct 2 points for passwords that contain 10 or 11 characters
      • passwords of 12, 13, or 14 characters have no point deductions or additions
      • add a point for passwords that contain 15, 16, or 17 characters
      • add 2 points for passwords than contain 18 or more characters
    • Assign a letter grade to the password by applying the sum of the points above to the following.
      • 8 or more points: A
      • 6 or 7 points: B
      • 4 or 5 points: C
      • 2 or 3 points: D
      • 1 or fewer points: F

    Note: Use of globals is expressly forbidden on this problem.

    • 0 points total on problem if any global variables used.
  1. Anagrams or Common Letters

    [10 points possible for doing one of part a or part b]
    [no additional points will be given for doing both parts a and b]

    Extra credit is available for doing one of the following two problems. Further credit is NOT given for doing both parts a and b.

    1. Anagrams

      Sometimes one can simplify a problem by removing the parts that don't matter, and then looking at what's left.

      For instance if you wanted to figure out if two collections of "stuff" were the same, you might remove matching items from each collection until you see if there are items left over. If you have leftover items, the collections were different, and if both collections become empty at the same time, they are identical.

      Use this technique to write a program which will determine whether or not two strings are anagrams of each other.

      Test it by deciding whether or not "one PLUS twelve" is an anagram of "eleven PLUS two", among other test cases. (Note that spaces should match as well as letters.)

      Note: Two programs, one iterative and one recursive, might be eligible for bonus points.

    2. Computing Store Discounts

      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. For this exercise, assume that the costs of identical items will be grouped together on the list, and all consecutive equal costs relate to identical items. To illustrate, suppose the program reads the following 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
      

      Here, we assume the 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.

      Notes:

      • The program should allow successive numbers to be typed on one or multiple lines.
      • The program should continue processing numbers until a cost of $0.00 is read.
      • The program should consider negative costs as errors. If a negative is encountered in input, the program should print an error message and stop.
      • Processing should make one pass only through the initial list of costs.
      • The program may utilize any functions that seem convenient. However, even with multiple functions, processing should not make multiple passes through the data.
      • The use of arrays on this problem is actively discouraged and will likely lose credit.
  1. A Simple Route Cipher

    [12 points possible]

    When sending a message from one place to another, it is common for the sender to encode the message before it is sent with the understanding that the receiver would know how to decode the message. With this encoding process, anyone intercepting the message in transit would not be able read the text.

    For encoding, one approach is a substitution cipher, in which each letter in original message is replaced by another letter. (For example, each "a" in the message might be replaced by "d" and each "t" might be replaced by "w". This type of cipher is commonly used in many word puzzles in newspapers and puzzle books.

    A second approach for encoding is called transposition, in which the characters of the original message are rearranged in a different order. This problem implements a simple type of transition cipher, called a route cipher. (Historically, the Union forces in the American Civil War used a variation of a route cipher, called the Union Route Cipher.)

    Encoding: In a simple route cipher, letters of a message are placed into a rectangular table. As an example, suppose the cipher is based on a table of 5 rows and 9 columns, and suppose we wish to encode the text "this short example illustrates a route cipher". The first step of a route cipher is to insert the message row-by-row into the table, on character at a time.

    t h i s   s h o r
    t   e x a m p l e
      i l l u s t r a
    t e s   a   r o u
    t e   c i p h e r

    With this arrangement, the encoded message is obtained by retrieving the letters according a designated path or route from the rectangle. For this problem, we will retrieve the letters from the table column by column. For example, reading column-by-column from the above table, we obtain the coded message "tt tth ieeiels sxl c auaisms phptrholroereaur".

    Decoding: Given an encoded message, the receiver places the text character-by-character into the rectangle according the prescribed path (e.g., column by column). With the letters in the rectangle, the original message can be restored by reading the rectangle row-by-row.

    Extensions: In the basic encoding approach, the original message is placed in a rectangle of a designated size. If the rectangle has r rows and c columns, this approach works well if the message has length r*c, the size of the rectangle. Extensions are needed if the original message has length other than r*c characters.

    • If the original message has less than r*c characters, additional characters might be added to get the needed number. For example, we might add letters of the alphabet a, b, c, d, e, ... at the end of message as needed to fill the rectangle.
    • If the original message has more than r*c characters, the message is divided into blocks of r*c characters, and each block is encoded separately.

    As another example, suppose the rectangle is specified with 3 rows and 4 columns, and suppose we want to encode the message "this extended example shows the full algorithm".

    Encoding follows these steps:

    1. Divide the message into blocks of 3*4 = 12 characters. The last block would have only 10 characters, so "a" and "b" have been added to complete the block.

      t h i s   e x t e n d e
      d   e x a m p l e   s h
      o w s   t h e f u l l
        a l g o r i t h m a b
    2. Place each block into a rectangle, row-by-row:
      t h i s       d   e x       o w s           a l g
        e x t       a m p l       t h e       o r i t
      e n d e       e   s h       f u l l       h m a b
    3. Read characters from each block, column-by-column:
      "t ehenixdste"   "dae m epsxlh"   "otfwhusel  l"   " oharmliagtb"

      Combining the encoded blocks gives:
      "t ehenixdstedae m epsxlhotfwhusel  l oharmliagtb"

    Problem:

    • Write a program that reads the rectangle size (a row and a column) and the text of a message and prints the encoded message.
    • Explain how the above program can also be used for decoding and illustrate your explanation with an example.

    Programming Notes:

    • Although conceptually the first encoding step reads the entire message and then divides it into pieces, in practice, the program should read and process one block at a time:
      1. Read rectangle size and create rectangle(s) of the appropriate dimensions to process a single block.
      2. Continue until all input is processed
        1. Read one block
        2. Process characters for the one block
        3. Print encoded characters for that block
    • C allows arrays to be declared of a length that is determined during run time. See Arrays of Variable Length for details.

    Reference: A nice treatment of transposition ciphers may be found in Abraham Sinkov, "Elementary Cryptanalysis: A Mathematical Approach", The New Mathematical Library, Random House and the Mathematical Association of America, 1968, Chapter 5. A revised edition of the book is available in Abraham Sinkov and Todd Feil, "Elementary Cryptanalysis Second Edition", The New Mathematical Library, Mathematical Association of America, 2009.

  1. Alphabetizing Numbers

    [10 points possible]

    Write a C program that generates the names of the numbers from zero to two hundred and prints them in alphabetical order.

    Notes:

    • All numbers should be written as lower-case names.
    • The program should be as compact as possible and utilize logic rather than brute force. (For example, a program consisting of 200 printf statements will earn very little credit.)
    • The program should run efficiently. (For example, few points will be given for a program utilizing a bubble sort; rather, an insertion sort is suggested.)
  1. Printing Cross Words

    [10 points possible]

    Consider the problem of printing two words, the first word vertically (one letter per line) and the second word horizontally, so the words cross at a common letter. For example, if the first word is FUNCTIONAL and the second is SCHEME, then the desired output is:

    
     F
     U
     N
    SCHEME
     T
     I
     O
     N
     A 
     L
    
    

    In this problem, you are to write a program that reads two words from a terminal window and prints them in the crossed pattern shown above (assuming they have a letter in common). If the words have more than one letter in common, then they may be printed with the crossing at any common letter. If the words have no letters in common, then the program should print an error message.

  1. Elementary Text Analysis

    [14 points possible]

    Write a C program that takes the name of a file as a command-line argument, opens the file, reads through it to determine the number of words in each sentence, displays the total number of words and sentences, and computes the average number of words per sentence. The results should be printed in a table (at standard output), such as shown below:

    
         This program counts words and sentences in file "comp.text ".
    
         Sentence:  1    Words: 29
         Sentence:  2    Words: 41
         Sentence:  3    Words: 16
         Sentence:  4    Words: 22
         Sentence:  5    Words: 44
         Sentence:  6    Words: 14
         Sentence:  7    Words: 32
    
         File "comp.text" contains 198 words words in 7 sentences
         for an average of 28.3 words per sentence.
    

    Notes for this problem:

    • A word is defined as any contiguous sequence of letters. Apostrophes at the beginning or the end of a word should be ignored. Apostrophes with letters immediately before and after are considered part of a word. For example, "O'Henry", "I've", "you're", "friend's" and "friends'" should each be considered as one word.

    • A sentence is defined as any sequence of words that ends with a period, exclamation point, or question mark, except a period after a single capital letter (e.g., an initial) or embedded within digits (e.g., a real number) should not be counted as being the end of a sentence.

    • Digits and punctuation (other than apostrophes, periods, explanation points, and question marks) should be considered the same as white space. Thus,

         After they walked, talked, and ate, the first person said, "I'd like 
         to swim: crawl, side stroke, and butterfly."
      

      Should be considered the same as

         After they walked  talked  and ate  the first person said   I'd like 
         to swim  crawl  side stroke  and butterfly
      
    • White space (e.g., spaces, tabs, line feeds, and return characters) are considered as equivalent. Multiple white space characters are considered the same as one space character. Thus, the above passage would equivalent to the following:

      After they walked talked and ate the first person said I'd like to swim crawl side stroke and butterfly
      
  1. Filtering and Reporting Data

    [14 points possible]

    Gemstones are attractive forms of rock crystal, commonly used for decoration and in jewelry. Gemstones also have interesting mineral properties. Gemstones may be classified in a variety of ways, including chemical composition, crystal structure, color, specific gravity, refractive index, and hardness:

    1. Chemical Composition: While some gemstones are primarily composed of atoms of one element (e.g., diamonds are mostly carbon, with coloring coming from traces of other elements), other gemstones are made up of atoms of several atoms (e.g., mica molecules include oxygen, hydrogen, silicon, aluminum, iron, and/or many others). On-line sources of information include general references (e.g., Common Mineral Groups) and references to specific minerals (e.g., micas).

    2. Color may be classified informally (e.g., red, yellow, etc.) or more formally by viewing thin slices of mineral crystals through the microscope, using polarized light (see, for example, Minerals under the Microscope).

    3. Specific Gravity is a measure of the density of a mineral. More precisely, specific gravity is the ratio of the weight of the mineral in air to its weight in an equal volume of water. More details are available from various on-line sources (see, for example, the Mineral and Gemstone Kingdom's glossary for specific gravity.

    4. Refractive Index provides a measure of how much light bends within a crystal. The higher the refractive index, the more bending and the more brilliant a crystal is likely to appear. For more information, see various on-line sources, such as Refractive Index.

    5. Crystal Structure: Crystals typically have one of several standard shapes or structures, including cubic, tetragonal, orthorhombic, hexagonal, monoclinic, and triclinic. While the details of such structures are beyond the scope of this problem, the World Wide Web contains many useful references, including crystal forms (at the macro-level.

    6. Hardness often is measured on the (nonlinear) Mohs Scale, which associates a hardness number to each mineral, from 1 (softest) to 10 (hardest):

      1. Talc
      2. Gypsum
      3. Calcite
      4. Fluorite
      5. Apatite
      6. Orthoclase
      7. Quartz
      8. Topaz
      9. Corundum
      10. Diamond

      As a comparison, a fingernail has hardness 2.5, glass has hardness 5.5, and a steel file has hardness 6.5. Minerals of the same hardness should not scratch each other, but a mineral of one hardness will scratch minerals with a lower hardness number.

    File /home/walker/151s/labs/gems.txt contains information on several gemstones, including color, hardness, specific gravity, and refractive index. Within the file, each line contains information about a specific gemstone.

    Here are a couple of sample lines, and a character 'ruler' to show how wide the fields are:

              11111111112222222222333333333344444444445555555555666666666677777
    012345678901234567890123456789012345678901234567890123456789012345678901234
    
                    Zircon        RED           7.5         4.50         1.95
                     Topaz     YELLOW             8         3.53         1.62
    

    To clarify, the names of the gemstones come first in a line and are right-justified in a column. The colors come next, followed by hardness (on a scale 1 to 10), then specific gravity, and finally refractive index (generally between 1.3 and 2.5).

    Write a program print-by-color that will let you select the gemstones of a certain color and print the information about those gemstones, where the resulting table is in alphabetical order by gemstone name and where the columns are labeled.

    For example, if this procedure is invoked with the statement

    
    (print-by-color "GREY")
    
    the procedure should return a table, such as the following:
    
                                                          Specific   Refractive
                  Gemstone       Color       Hardness      Gravity      Index
    
                 Alabaster       GREY             2         2.32         1.53
                  Bakelite       GREY           2.5         1.28         1.65
                   Calcite       GREY             3          2.7         2.71
                    Casein       GREY           2.5         1.33         1.55
                  Celluoid       GREY             2         1.35         1.50
                Chalcedony       GREY             7         2.62         1.53
                  Corundum       GREY             9         3.99         3.99
                   Diamond       GREY            10         3.52         3.52
                  Hematite       GREY             6         5.10         5.05
                     Ivory       GREY           2.5         1.80         1.54
                   Jadeite       GREY             7         3.34         3.33
               Labradorite       GREY             6          2.7         2.70
                    Marble       GREY             3         2.71         1.50
                Meerschaum       GREY             2         1.50         1.53
                  Nephrite       GREY           3.5         3.00         2.96
                      Opal       GREY             6         2.10         2.10
                    Quartz       GREY             7         2.65         1.55
                    Quartz       GREY             7         3.33         2.65
                      Talc       GREY             1         2.70         2.75
    
    Another possible format might be:
    
                                           Specific   Refractive
    Gemstone Name       Color    Hardness   Gravity      Index
    
    Alabaster            GREY       2         2.32        1.53
    Bakelite             GREY       2.5       1.28        1.65
    Calcite              GREY       3         2.70        2.71
    Casein               GREY       2.5       1.33        1.55
    Celluoid             GREY       2         1.35        1.50
    Chalcedony           GREY       7         2.62        1.53
    Corundum             GREY       9         3.99        3.99
    Diamond              GREY      10         3.52        3.52
    Hematite             GREY       6         5.10        5.05
    Ivory                GREY       2.5       1.80        1.54
    Jadeite              GREY       7         3.34        3.33
    Labradorite          GREY       6         2.70        2.70
    Marble               GREY       3         2.71        1.50
    Meerschaum           GREY       2         1.50        1.53
    Nephrite             GREY       3.5       3.00        2.96
    Opal                 GREY       6         2.10        2.10
    Quartz               GREY       7         2.65        1.55
    Quartz               GREY       7         3.33        2.65
    Talc                 GREY       1         2.70        2.75
    

    As shown in each example, the gemstone names and properties must appear in labeled columns. Gemstone names may be either left-justified or right-justified.

    Note that some gemstones, such as Quartz above, appear several times in the table, since variations of a gemstone may have different properties.