path file: suppl-prob-main-body.php Imperative Problem Solving and Memory Management
CSC 161.02 Grinnell College Fall 2018
Scribbler 2
CSC 161.02:
Imperative Problem Solving and Memory Management
Scribbler 2
Course Home References Course Details: Syllabus, Schedule, Deadlines, Topic organization MyroC Documentation Project Scope/
Acknowledgments

Note: Although this course is well-developed and tested, be prepared for adjustments in some details as the semester progresses.

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 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. (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, 15

Submission Details

Use the link, Detailed Coursework Instructions, to find specific instructions regarding code, submission, and testing of supplemental problems.

Some Grading Notes:

Problem Statements

Problem 1: Ticket Pricing

You've been asked by a local community theater to write a small program to calculate the price of a ticket for the box office staff. The problem is that the price of a ticket depends upon several factors:

The price schedule for tickets is:

Location Matinee Evening
Main floor - middle section $20.00 $25.00
Main floor - sides $15.00 $20.00
Balcony $10.00 $15.00

Assume the age of the ticket holder will be between 0 and 100 (inclusive). Children under 5 are free (ticket price should be $0.00 regardless of location). Senior citizens (age 55 and older) receive a $2.00 discount.

Students receive a 5% discount, and military veterans receive a 10% discount. The discount is applied after applying the discount for age (senior citizen), if applicable.  Discounts can stack!

You may use '0' (zero) and '1' to signal "no" and "yes" when getting input from the user and '1', '2', and '3' when asking what section the purchaser wants.

Be sure when testing to try input that is out of bounds (age > 100, for instance) since the box office is often a very busy place, and users will often make mistakes in typing responses to questions on the screen. Ensure that the program gives useful error messages in those cases.

The General Grading Form applies to this program project.

Also, see the specific criteria for Supplemental Problem 1

And I am providing you an example testing sheet to use for this programming assignment.

Problem 2: Credit Card Comparison

You're looking forward to traveling over your next break, and you plan to use a credit card to manage expenses during the trip. The problem is that there are two different cards that you are considering: 1) charges a lower interest rate but has an annual fee versus 2) one that has no annual or service fee but charges a substantially higher interest rate.

Write a program that will accept input from the user for both cards and generate a comparison to help you choose the best option. Assume that interest will be compounded monthly, the annual fee (if any) is charged as soon as you apply for the card and then every 12 months after that, and that both companies have the same minimum monthly payment, which is what you plan to pay every month.

Your program should prompt for:

Note: users will enter the annual interest rate (which is the typical way to describe the interest rate for a credit card or a loan). However, to calculate the monthly interest, first divide the annual interest rate by 12 to get the percentage to use to calculate the interest on the current balance each month. Also, be consistent in how you handle the percentages. If you enter the percentages as whole numbers (i.e. 15.0 for 15%), you need to divide that value by 100 before using it to calculate interest! (If you seem to have an infinite loop, check this.)

For each month, the new monthly balance should be calculated by the formula:

new balance = old balance + interest - payment

Output should be in a table with a line for each month (while the current balance of either card is positive). Each line should show the current balances of both cards, with a summary at the end stating the total cost for each card (initial balance + annual fees (if any) + interest paid) with a statement about which card is the better deal in this case. You can also think of this as the total of all payments made for each card. The output should look something like this:

Run several tests, keeping in mind that credit card companies often charge 20% (annual rate) and more on outstanding balances. Play around to see what percentage rate would make the annual fee "worth it". Use the script command to save your input and output to a text file. Submit both your code and testing file as attachements in an email to the grading account.

The General Grading Form applies to this program project.

Also, see the specific criteria and grading form for Supplemental Problem #2

Problem 3: The Caesar Cipher

This problem is an introduction to using computers in cryptography. This particular assignment presents a type of cipher that is very easy to crack (simple substitution) - and should never be used to encrypt anything important. However, it is of historical interest, having been ascribed to Caesar, who is said to have used it to protect confidential correspondence, and it still has use as a component in more complex encoding systems. You can read more about the Caesar Cipher on Wikipedia.

Caesar's cipher shifts each letter in the plain text (the message to be encrypted) a given number of steps to the right in alphabetical order. If the shift would take you past the end of the alphabet, you just return to the beginning and keep counting. As an example:

Original alphabet:     abcdefghijklmnopqrstuvwxyz
Alphabet shifted + 3 : defghijklmnopqrstuvwxyzabc

For this assignment, your program should accept three lines of input from the user:

  1. The number of characters in the message to be encrypted
  2. The number of steps to shift each letter (also called "rotating")
  3. The original message to be encrypted. This message may include upper or lowercase letters, spaces, punctuation, and other symbols from the keyboard. It will not have to handle control characters, tabs, or newlines.

You should output to the screen:

  1. repeat the original message
  2. print the encrypted message

NOTE: only letters (upper or lowercase) should be encrypted. Spaces, punctuation, and other symbols should be left as entered. Case of letters (upper or lower case) needs to be maintained in both the original message and the encrypted one.

Assumptions:

This problem is a modification of a practice item at Hacker Rank (by Vatsal Chanana) and is also found in our textbook on page 181, where you will find a very useful hint.

The General Grading Form applies to this program project.

Also, see the specific grading form for Supplemental Problem #3

Problem 4 - Favorite Movies Listing

This project asks you to write a program that will first create an array of length n that will contain information about your favorite movies: movie title, year published, and your rating (from 0.0 to 4.0).

Your program should first ask for the number of movies to include (n). And then your program should read in those n movies, one per line. I strongly suggest that you enclose your titles in double quotes (which are NOT stored in the array). Just as when you want to specify a search phrase when searching the internet, double quotes let you use spaces in your search term while seeking to match the term exactly. After the title, read in the year released and the initial rating. I used floats for the ratings so that I could use decimals, but you could use integers if you prefer.

So, an example of an input line would be:

"A Princess Bride" 1987 4.0

Then, your program should present the user with a list of options: 1) Change a rating, 2) Print the array sorted by title, 3) Print the array sorted by rating, or 4) Quit.

Your program should:

  1. Ask for the number of movies n to enter into the array
  2. Read in title, year, and rating for n movies, one per line
  3. Switch to asking the user for choice of what to do next
  4. Update a rating or print the array (properly sorted), based on the entered option
  5. Continue asking for the user's option until the user selects the option to end the program

Note: if the user asks to update a movie but the title doesn't match anything in the array, you need to give an error message and return to presenting the user options.

Each movie in the array should be a struct such as:

struct movie {
char title[50];
int year;
float rating; // assuming you might want to rate something 3.5, for instance
};

To change the rating, you will need to request the title of the movie from the user. You can require double quotes again, although this time, you can simply read a whole line and store it in the string without the double quotes. Obviously, you will also need to read in the new rating value as well.

Sort the array using an insertion sort algorithm (see reading and lab for November 5th), sorting in ascending order for both the title and the rating. You may write two different functions for sorting, or you can write one sorting procedure and pass in a function that determines which struct is greater than the other.

The General Grading Form applies to the programming project.

Also, see the specific grading form for Supplemental Problem #4.

Problem 5: Palindromes

A palindrome is a word, phrase, or any other sequence of characters that read the same backwards as well as forwards. Most often, they are seen as single words, such as "racecar" or "madam," but they can also be much longer if you allow for variations in capitalization and ignore whitespace. Palindromes also do not have to be composed of only words. Musical notes or numbers can be used to create palidromes, and they appear in mathematics and biologic structures. To read more about palindromes, check out the Wikipedia article.

In the meantime, you are going to write a program that will read in a string (which may contain spaces or punctuation) and determine whether or not it is a palindrome. Any spaces or punctuation should be ignored when doing the comparison work, but you will want to keep the string as entered to include in the message to the user on the status of the test. The program should ignore capitalization when deciding if a word is a palindrome. "Madam", for instance, should pass the test.

There is an elegant and simple way to do this, using functions from the string.h library. We are not going to take the easy route, however. I am going to ask you to use what you know of queues and stacks to solve this particular problem.

Your program should read in a string for evaluation. This will consist of letters (lower and upper case), whitespace, and punctuation. There should be no special, control characters or numbers in the input. You may assume that the string will not be longer than 50 characters total.

Your program should:

  1. Read in the string. For this program, it might be easier to read it in character by character rather than as a whole line of input.
  2. Take each character in the string, and if it is a letter, push it onto a stack and also enqueue it onto a queue.
  3. Once whole string has been processed: dequeue a letter from the queue, pop a letter from the stack and compare them. (Remember that upper and lower case versions of a letter should match.) If they match, continue working through the stack and queue in the same way, character by character, until either the characters don't match or the queue and stack are empty.
  4. If the characters matched throughout the process, then the string is a palindrome. If there was a mismatch, then it is not a palindrome.
  5. Print the original string plus a message stating whether or not it was a palindrome.

You may use either linked lists or arrays (or a combination of both) for your data structures.

For testing, you can use this list of palindromes for examples that should pass. Remember to also try examples that should fail.

The General Grading Form applies to this problem.

See the specific guidelines for scoring Supplemental Problem #5.


Optional/Extra Credit Problems

These problems will be accepted as extra credit points and can be used for practice or to increase your grade. Some are harder than others, and points for each problem will reflect their estimated difficulty.

Problem 6: Calculating Factorials

If you do not remember what factorials are, Wikipedia has a good entry. This problem is frequently solved using a recursive approach, although it could be tackled (inefficiently) by a loop. See King, section 9.6 for a discussion of how to handle recursive functions in C.

Write a program that reads a positive integer from user. You can assume that the input will be between 2 and 12 (inclusive). Your program should then print out the resulting factorial, N! -- keeping in mind that 12! will be a very large number.

For full points, you must use the recursive function calls approach, but you do not need to worry about how to calculate large factorials. 12! should compute correctly on a 32-bit computer.

This problem is slightly adapted from one given on the Hacker Rank site, created by Abhimanya Singh.

This assignment will be worth up to 15 points. Remember that this and all problems below are optional and may be done for extra credit.

Guidelines for grading this problem include the general grading form and a specific grading form.

Problem 7: Decimal Numbers to Binary

Write a program that accepts a decimal number (an integer) between 1 and 1000000, inclusive.

Your program should convert the decimal number to its binary representation, which it will print out, and it should count the maximum number of 1's that appear consecutively.

For instance, if you input the digit 7, your program should calculate and print out 111 as the binary representation, and on a new line, type the digit 3, because there are three consecutive 1's. If, however, the input was 5, then your program should print the binary equivalent of 101 and on a new line print 1 because there is only a single 1 in a row.

This problem is a modification of a practice problem from Hacker Rank, the original was created by Abhimanya Singh.

This assignment will be worth up to 15 points.

Problem 8: Random Walk

This project comes from the King textbook, Chapter 8 (Arrays). It is project #9, found on page 179.

Write a program that generates a "random walk" across a 10 x 10 array of characters. This type of activity may be found in two-dimensional games in which non-playing characters (NPC) wander around a map, potentially triggering an interaction with the player if the player and the NPC happen to occupy the same space at the same time. In more serious simulations, this can also be used to model movements of an organism in an environment.

The array will initially contain all '.' (periods) in every cell. Your program should randomly pick a cell in the array as its starting point for the random walk. At that starting point, the program should change the '.' to an 'A'. It should then continue by randomly choosing to move one space in one of four directions: up, right, down, or left from its current location. Each time it moves, it should pick the next letter of the English alphabet (A through Z) to enter into the cell before choosing a direction again. If the cell it picks for its next move is already occupied (i.e., it does not contain '.'), it should choose another location. If the cell it picks is outside of the boundaries of the array, it should also pick another location.

The program should stop if all of the cells around its current position are already occupied by a letter or are outside of the array OR if it successfully reaches the end of the alphabet ('Z'). See King page 179 - 180 for examples of how the array will look in both successful and early termination cases.

Use srand and rand functions to generate random numbers. After generating a number, use its remainder when divided by 4 to choose the next direction to move. You will need to check bounds to be sure that the program does not attempt to move off the array/game board.

Your program should print out the 10 x 10 array showing the placement of the letters as well as the spaces that still contain periods '.' in them.

This assignment will be worth up to 15 points.

Problem 9: Hourglasses

This project will deal with a two-dimensional array of integers (although it would be pretty easy to extend this to an arbitrary sized array). The program will traverse the two-dimensional array, A, calculating the sums of numbers located in a particular pattern (the hourglass, defined below) surrounding each location A[i][j] and reporting the greatest sum that is found.

This sort of array traversal and calculation may be found in a variety of situations, such as reporting and updating the status of the squares surrounding characters in a map-based videogame or in managing a simulation of bacteria.

For this assignment, we will stick with a 6 x 6 array of integers. The integers may range from -9 to 9, including 0.

For instance, let A be an array such as:

1 0 0 0 0 0
2 1 0 0 0 0
3 2 1 0 0 0
4 3 2 1 0 0
5 4 3 2 1 0
6 5 4 3 2 1

An hourglass is defined to be all the values in this pattern:

a b c
  d  
e f g

An hourglass sum is the result of adding all of the integers (a through g) in each hourglass. In a 6 x 6 array, there are 16 hourglasses, and hence, there are 16 sums to calculate.

Your assignment is to calculate the hourglass sums of a 6 x 6 array read in from stdin, calculate the hourglass sums, and print out the greatest of the sums. The input should be in 6 lines of data, each line containing 6 integers separated by spaces. The integers should be in the range -9 to 9, inclusive.

The program should output a single value: the largest of the hourglass sums. For the example array above, your output might look like:

The largest hourglass sum is: 28

Test your program with both positive and negative values.

This problem comes from Hacker Rank as part of the 30 Days of Code challenge. It was written by Shafaet Ashraf. If you are having difficulty envisioning what an hourglass is, take a look at the explanation at the botton of the original page.

This assignment will be worth up to 12 points.

Problem 10: Word Sort

(This is Programming Project #5 in Chapter 17 of the King textbook.)

Write a program that sorts a series of words entered by the user.

Assume that each word is no longer than 20 ASCII characters long (and contains no spaces or control characters). Stop reading new words when the user presses "Enter" without typing a word.

Store each word in a dynamically allocated string, using an array of pointers to keep track of the strings. After all the words have been read, sort the array and then use a loop to print the words in sorted order. You should use the insertion sort algorithm to sort the strings. Note that you can sort the array as you add the words to the array (see King, page 418).

This assignment will be worth up to 12 points.

Problem 11: Tech Support Ticket Tracker

You've been asked to develop an issue tracking program for a small, start-up tech support company.

Ignore, for this assignment, that you would want to a way to save the information for later retrieval, action, and editing. For now, just create the interface and a way to interact with the information while the program is running.

Your program needs to allow the user to choose from a list of possible tasks:

  1. Create a new tracking ticket
  2. Assign a new ticket to a technician for handling
  3. Mark a ticket complete
  4. Print a list of new tickets
  5. Print a list of assigned tickets
  6. Print a list of completed tickets
  7. Exit the program

You should create three lists of structs: one for new tickets, one for assigned tickets, and one for completed tickets.

Each ticket is a struct that contains:

Generally, when you have a list of customer service needs, you want to handle them by completing the first one that was entered. This means that a queue ("first in, first out") is probably the most efficient strategy for managing the list.

Your program should loop until the user enters a "7" to exit the program.

Prompt the user for their choice (1 - 6) and take the appropriate action:

1) To create a new ticket, the program should prompt for all the information required for a ticket, except use "unassigned" for the technician's name. Create a new ticket node and add it to the back of the new tickets queue.

2) To assign a ticket, ask for the technician's name. Your program will need to examine the new ticket queue to see if there are any new tickets. If there are no new tickets to be assigned (the new tickets queue is empty), then report that message back to the user. Otherwise, your program will need to find a ticket to assign. If there are any urgent tickets with urgency level "1", assign the first urgent ticket to the technician by removing the ticket from the new tickets queue and adding it to the assigned tickets queue and changing the technician's name from "unassigned" to the name that was entered. If there are no urgent tickets in the queue, then take the first ticket in the new tickets queue andassign that one. You will also need to change the status of the ticket.

3) To complete a ticket, the program should ask the user which ticket number is complete. It then should examine the tickets in the assigned tickets queue to find the one with the matching number. If it does not find a match, give the user an error message. When it finds a match, change the status and remove it from the assigned tickets queue and addit to the completed tickets queue.

4) through 6) should just print the appropriate queue in order, giving all of the information associated with a ticket in an easy to read form.

7) should exit with a friendly message.

This project is specifically designed to give you practice with linked lists, dynamic memory allocation, and structs. Any program that does not incorporate these components will receive minimal points (see specific grading criteria for details).

This assignment will be worth up to 15 points.

Problem 12: File Processing - Integers

This project comes from the King textbook, Chapter 22, Programming Project #18

Write a program that reads integers from a text file whose name is given as a command-line argument. Each line of the file may contain any number of integers (including none), separated by one or more spaces.

Your program should display (to stdout) the largest number in the file, the smallest number in the file, and the median. (Remember that the median is the number closest to the middle of a series of numbers. When there is an even number of numbers in the series, then the average of the two numbers in the middle is used. For this exercise, round down, if necessary.)

Assume that the file contains no more than 10,000 integers. As the book suggests, this would be a good use of an array of integers that is sorted. You can use insertion sort or any other sorting algorithm or function except for bubble sort.

This assignment will be worth up to 12 points.

Problem 13: Sum the Command Line

This programming project comes from the King textbook, Chapter 13, #5

Write a program that adds up its command-line arguments, which are assumed to be integers that are each separated by a space.

For example, if I had created a program called sum:

sum 5 1 100 15

should print to the screen something like this:

Total: 121

See your book for a hint at how to convert the command line arguments to integers.

This assignment will be worth up to 12 points.

Problem 14: Selection Sort

This programming project comes from the King textbook, Chapter 9, #1

Write a program that asks the user to enter a series of integers, which it will sort from lowest to highest.

Your program should:

  1. Ask how many integers n will be in the series.
  2. Read the nintegers into an array.
  3. Use a function called selection_sort, called recursively, to sort the array.
  4. Print the sorted array.

The selection sort algorithm works this way, assuming an array with n elements:

  1. Search the array to find the largest element. When found, move it to the last position in the array.
  2. Call itself recursively to sort the first n - 1 elements in the array.

This assignment will be worth up to 12 points.

Problem 15: Craps Game Simulation

This programming project is taken from the King textbook, Chapter 9, #8

Write a program that simulates a game of craps. There's an extensive article at Wikipedia on the game's rules, history, and betting strategy. Don't worry, at its fundamental level, craps is fairly simple.

The game is played with two 6-sized dice, and winning or losing is based on the SUM of the rolled values of the dice.

On the first roll, the player wins if the sum of the two dice is 7 or 11. The player loses if, on the first roll, the sum is 2, 3, or 12. If the player wins or loses on the first roll, the game is over.

If any another sum occurs, the game continues. The sum of the first roll of dice is called the "point". The point becomes the objective of the subsequent rolls. If the player rolls the same sum, they win. BUT, if they roll a 7, they lose. They will keep rolling the dice until they either win (by getting the point sum) or lose (by getting 7). It can take quite a few rolls to either win or lose. Take a look at the example game on page 218 to see a typical run of craps.

Whenever the player wins or loses a game, the computer should increment a running total of wins vs. loses.

Your program should:

  1. Ask the player for their name and echo it back with a friendly greeting.
  2. Simulate rolling two 6-sized dice by using srand and rand to generate two numbers between 1 and 6. Remember to use their sum in order to determine win, loss, or point.
  3. If the player doesn't win or lose on the first round, use the point value as the target for repeated rolls that continue either until the same sum is generated or the sum equals 7.
  4. At the end of the game, increment either wins or losses
  5. At the end of the game, the computer should ask the player of they want to play again. If the player enters either a 'y' or 'Y', the computer should start a new game. Otherwise, quit and display the number of wins vs. losses.
  6. If the player has lost more than won, print a nice message, asking them to come and play again. If they have won, print a message congratulating them.

This assignment will be worth up to 12 points.