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 3-9, 2016). (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); -
After Supplemental Problem 1, global variables may not be used in solutions to any supplemental problem.
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 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.
-
Computing a Babysitter's Fee
A baby sitter charges $2.75 per hour until 9:00 pm (while the kids are still up), $1.75 per hour between 9:00 pm and midnight, and $2.25 per hour after midnight (since late night baby sitting interferes with morning classes).
Write a program that reads four integer values (the sitter's starting time in hours and minutes and the ending time in hours and minutes) and computes the sitter's fee. Assume all times are between 6:00 pm and 6:00 am, and hours should be specified as being between 0 and 12 (inclusive). Hours outside the range of 0 to 12 should be considered invalid.
- The hour 6 should be considered as 6:00 pm, when it is entered as a starting time.
- The hour 6 should be considered as 6:00 am, when it is entered as an ending time.
The following table may clarify allowed time values for this problem.
Starting Starting Ending Ending Starting Ending Hour Minutes Hour Minutes Time time 8 0 3 30 8:00pm 3:30am 6 0 0 45 6:00pm 12:45am 12 0 6 0 12:00am (midnight) 6:00am Programming Note: You may NOT use loops or recursion in this program.
-
Computing a Polynomial
A polynomial function has the form
p(x) = anxn + an-1xn-1 + ... + a2x2 + a1x + a0
Write a function compute_poly that takes three parameters:
- an x value,
- an integer n which gives the largest power of x with a non-zero coefficient, and
- an array a of n+1 coefficients (a0, a1, ..., an-1, an).
and returns the value of the polynomial p(x).
Notes:
- compute_poly should make only one pass through the list of coefficients.
- Both the number x and the elements of the array a should be real numbers (e.g., of type double) rather than integers.
- The number x may be used in a multiplication operation no more than n times in the entire computation. (Thus, recomputing xi from scratch for each of the n terms is not acceptable for this problem.)
- Since the pow function in the math.h library requires many multiplication operations, use of pow in this problem would violate the condition that no more than n multiplications are allowed in the entire solution to this problem. (To be specific, use of pow in this program will yield an automatic score of 0 for this program.)
- As a hint, you may want to search for discussion of Horner's Rule either in a book on numerical analysis or on the Web.
- Be sure that the array element a[n] is used as the coefficient of xn (not the coefficient of x0).
- You will need to include compute_poly in a main program for testing.
- Be sure your testing covers an appropriate range of cases.
- compute_poly should return the result of the computation, not print the result. (Any printf statement in compute_poly is subject to a 12 point penalty!)
-
Grading Passwords
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 6 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 2 points for passwords that contain less than 6 characters
- passwords of 6, 7, or 8 characters have no point deductions or additions
- add a point for passwords that contain 9, 10, or 11 characters
- add 2 points for passwords that contain 12, 13, 14, or 15 characters
- add 4 points for passwords than contain more than 15 characters
-
Assign a letter grade to the password by applying the sum of the points
above to the following.
- 9 or more points: A
- 7 or 8 points: B
- 5 or 6 points: C
- 3 or 4 points: D
- 0 or 1 or 2 points: F
Note: Use of globals is expressly forbidden on this problem.
- -10 for declaration of first global variable
- 0 points total on problem if 2 or more global variables.
-
A Simple Route Cipher
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:
-
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 -
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 -
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:
- Read rectangle size and create rectangle(s) of the appropriate dimensions to process a single block.
-
Continue until all input is processed
- Read one block
- Process characters for the one block
- 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.
-
Singly-linked-list Processing
Program namelist-2016-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:
Then the new list after duplicate would have 6 nodes:
-
For each node on the list,
Programming Hints:
- In Program namelist-2016-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).
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%.
-
Unusual Canceling
The fraction 64/16 has the unusual property that its reduced value of 4 may be obtained by "canceling" the 6 in the numerator with that in the denominator. Write a program to find the other fractions whose numerators and denominators are two-digit numbers and whose values remain unchanged after "canceling."
Of course, some fractions trivially have this property. For example, when numerator and denominator are multiples of 10, such as 20/30, one can always "cancel" the zeroes. Similarly, cancellation is always possible when the numerator and denominator are equal, as in 22/22. Your program should omit these obvious cases.
Note: An extensivie discussion of this problem may be found at Lucky fractions: Where bad arithmetic gives the correct answer by Tom Osler, Rowan University.
-
Alphabetizing Numbers
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.)
-
Common Letters
Write a program that reads two strings and counts how many letters the strings have in common. To determine common letters, each letter of one word should be matched with exactly one letter of the second word. the case of the letters (upper case versus lower case) should be ignored.)
Examples:
- "room" and "tool" have two letters in common (each "o" in "room" is matched with a separate "o" in "tool").
- "fewer" and "red" have two letters in common (the "e" in "red" matches one of the "e"s in "fewer" and both words contain one "r").
- "Mississippi" and "Iowa" has just one letter in common (the "I" of Iowa matches one of the "i"s in "Mississippi").
-
Printing Cross Words
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.
-
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. The required work for this problem involves three C procedures, combined within a main program.
- Procedure turn simulates one turn of a player; that is, it takes a number init_cherries as parameter, and adjusts the number of cherries on the tree appropriately — using C's rand function to determine the outcome of the spinner.
- Procedure playGame has players, the number of players, as input parameter, and returns the number of rounds taken until some player wins.
- Procedure playNGames has two parameters: players, the number of players in a game, and games, the number of games to be simulated. playNGames returns a list with the maximum, minimum, and average number of rounds taken by the players over the full number of games.
Hints: Although you are free to approach this problem however you want, the following pieces might help.
- Write a procedure init_games that takes a number of players as parameter and generates a list of that number of 10's (the initial number of cherries on the trees for each of those players).
- Write a procedure play_round that takes a list of tree-cherry numbers as parameter, plays one round for each player, and returns a list of new totals for the number of cherries for each player.
- Write a procedure check_win that takes a list of tree-cherry numbers as parameter and checks if any of the players has won.
-
Directing a Robot to Follow a Tape
Assume that tape has been place on the floor, and suppose that the color of the tape is significantly different (i.e., darker or lighter) than the floor. This problem asks you to write a program that will control the robot to follow the tape for at least a minute or two.
Some programming notes:
- In the lab on two-dimensional arrays, one exercise asks to locate an area of the brightest light in a picture. In this problem, use a similar approach to find the edge of a piece of tape on the floor. Since the color of the tape contrasts with the floor, one should scan a picture from the robot to determine where the color changes substantially from light to dark or dark to light.
- If the color change is approximately straight ahead, the robot might go forward a short distance before taking another picture.
- If the color change on the left side of the picture, the right motor might be directed to move more quickly than the left motor, so the robot will move somewhat to the left. The farther the color change is to the left, the more the difference between the right and left motors. After moving a short distance, the robot might stop and take another picture.
- If the color change is to the right, the right motor might be directed to move less quickly than the left motor, so the robot will move somewhat to the right. The farther the color change is to the left, the more the difference between the right and left motors. After moving a short distance, the robot might stop and take another picture.
Overall, the robot should follow a tape that winds left and right around the floor for at 10 or more feet.
-
Elementary Text Analysis
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
-
-
Filtering and Reporting Data
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:
-
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).
-
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).
-
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.
-
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.
-
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.
-
Hardness often is measured on the (nonlinear) Mohs Scale, which associates a hardness number to each mineral, from 1 (softest) to 10 (hardest):
- Talc
- Gypsum
- Calcite
- Fluorite
- Apatite
- Orthoclase
- Quartz
- Topaz
- Corundum
- 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.62To 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.75Another 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.75As 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.
-
-
Parenthesis Checking
Write a program that reads a line of text from the terminal and checks if the parentheses in the line are balanced.
Notes
- The program should distinguish among three types of parentheses, { }, [ ], ( ).
- Parentheses checking should involve working from the inside of nested parentheses to the outside.
- In each case, the appropriate right parenthesis should be matched with a left parenthesis of the same type.
Examples
- ( these { parentheses[] match } perfectly ) !!!
- (the {right [parentheses ) on } this line ] are in the wrong order.
- this ( line { is missing } one (round ) right parenthesis.
Comments on a solution to the problem: This problem can be solved reasonably easily using a single left-to-right scan of a line, if left parentheses are placed on a stack as they are encountered. Then, when a right parenthesis is found, the stack can be popped and one can check if the right parenthesis has the same type as the left one.
Programming Note: Your program should use a self-contained Stack library package, following the program management concepts described in the reading on program management.
