CS16: Programming Assignment 10

Introduction

The assignment for this week will utilize pointers and dynamic arrays.

This assignment is due on August 12th at 23:59.

Top

Step 1: Open a Terminal

The first step in every assignment will be to open a terminal window, which will be the environment you use to write, compile, and run your programs.

For a reminder on how to do this step, take a look at Step 2 of PA 01.

Top

Step 2: Programming Assignment 10 Directory

Start by changing into your CS 16 directory:

$ cd cs16

And then create and move into a PA 10 directory:

$ mkdir pa10
$ cd pa10

Remember that at any time, you can check what directory you are current in with the command pwd.

Top

Step 3: Create Your C++ Files

This week, you will need to create two files called palindrome.cpp and choose.cpp:

$ touch palindrome.cpp choose.cpp
Top

Step 4: Edit Your C++ Files

You will now need to complete each source file. Each corresponds to one of the problems listed below, which make up this lab.

For a reminder on how to open the text editor and how edit files, take a look at Step 5 of PA 01.

Top

Step 5: Write the Code

This assignment consists of two problems, each of which is described below. The problems are worth 50 points each. Each should be solved in its own file and both must be submitted for full assignment credit.

Chapter 14: Practice Program 5

This should be solved in the palindrome.cpp file.

Write a recursive function that returns true if an input string is a palindrome and false if it is not. You can do this by checking if the first character equals the last character, and if so, make a recursive call with the input string minus the first and last characters. You will have to define a suitable stopping condition.

Then write a program that takes in a string as user input, then calls the above function and outputs the result. Input string may have characters and numbers. Ignore case when comparing two chracters.

The program should print a string of text to the terminal before getting the inputs from the user. A session should look like one of the following examples (including whitespace and formatting):

Enter string:
redivide
"redivide" is not a palindrome.

Enter string:
detartrated
"detartrated" is a palindrome.

The strings printed by the program should include a newline at the end, but no other trailing whitespace (whitespace at the end of the line).

Chapter 14: Programming Project 1

This should be solved in the choose.cpp file.

The formula for computing the number of ways of choosing r different things from a set of n things is the following:

C(n, r) = n! / (r! · (n – r)!)

The factorial function n! is defined by

n! = n · (n – 1) · (n – 2) · ... · 1

Discover a recursive version of this formula and write a recursive function that computes the value of the formula. Using this recursive function, write a function which computes the formula for number of ways to choose r different things from a set of n things.

Then write a program that takes r and n as user input, then calls the above functions and outputs the result.

Hint: some of the intermediate values (such as 16!) are too large to fit in a variable of int type. Consider using a type which can store larger numbers such as long (or even unsigned long, since our numbers are all positive in this problem).

The program should print a string of text to the terminal before getting each line of input from the user. A session should look like the following example (including whitespace and formatting), with possibly different numbers in the output:

Enter r (number of things to choose):
3
Enter n (the number of things to choose from):
6
There are 20 ways to choose 3 things from a set of 6 things.

The strings printed by the program should include a newline at the end, but no other trailing whitespace (whitespace at the end of the line). Also take care of singular and plural words in the sentence (1 way, 2 things etc.)

Top

Step 6: Compile the Code

To compile our code, we will use the same g++ command as last week. The following two commands will compile the two source files (in the same order as listed above):

$ g++ -std=c++11 -o palindrome palindrome.cpp
$ g++ -std=c++11 -o choose choose.cpp

If the compilation is successful, you won't see any output from the compiler. You can then use the following commands to run your programs:

$ ./palindrome
$ ./choose

Remember to re-compile the relevant files after you make any changes to the C++ code.

If you encounter memory errors (like segmentation faults or bus errors), you will need to make use of gdb to diagnose and solve the errors. Refer to the first problem of PA07 for a reminder on how to use gdb.

Top

Step 7: Submit

Once you are satisfied that your program is correct, it is time to submit it. Login at https://submit.cs.ucsb.edu/session, then navigate to “CS16_m16” and click on “Programming Assignment 10”. Then click “Make Submission”, and make your submission the same way as last week. Remember to submit both .cpp files.

Please remember that you must submit the program to obtain any credit for the assignment; just completing the program is not enough.

Once you submit, you should see a page detailing your submission. The system will automatically grade your program and will show you the results on this page after a 1 minute delay.

You can alternatively submit your code from the command line (terminal) on any CS machine, including the Phelps lab machines or the CSIL server. You can use this method when logged in remotely. To submit the the two source files to this assignment by running the command:

$ ~submit/submit -p 508 palindrome.cpp choose.cpp

You can copy the URL shown in the output of the above and paste into a web browser to reach the submission result page.

Top

Step 8: Check Submission Results

After the 1 minute delay, the submit system will show your score and give you feedback on your submission. Refresh the webpage after a minute to see this information.

You may submit multiple times. The highest score among submissions uploaded before the deadline will be used as your assignment grade.

Top

Step 9: Done!

Once your submission receives a score of 100/100, you are done with this assignment.

If you are in the Phelps lab or in CSIL, make sure to log out of the machine before you leave. Also, make sure to close all open programs before you log out. Some programs will not work next time if they are not closed. Remember to save all your open files before you close your text editor.

If you are logged in remotely, you can log out using the exit command:

$ exit