CS16: Programming Assignment 07

Introduction

The assignment for this week will utilize multidimensional arrays and the debugger.

This assignment is due on August 5th 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 07 Directory

Start by changing into your CS 16 directory:

$ cd cs16

And then create and move into a PA 07 directory:

$ mkdir pa07
$ cd pa07

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 a two files called climb.cpp and matrix.cpp:

$ touch climb.cpp matrix.cpp

You will also need to download the segfault.cpp file into the directory. You can find the file here. To download it directly into the current directory, you can use the following command:

$ wget http://cs.ucsb.edu/~cspensky/labs/segfault.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 three problems, each of which is described below. The first problem is worth 20 points, and the last two are each worth 40 points. Each should be solved in its own file and both must be submitted for full assignment credit.

gdb and Fixing Memory Errors

For this problem, you do not have to write a program. Instead, you will fix memory errors present in a provided program. To do this, you will make use of the gdb debugger program. First download the program to your PA07 directory with this command:

$ wget http://koclab.cs.ucsb.edu/teaching/cs16/pa/segfault.cpp

Next, compile and run the program. When the program runs, you will see output that looks like the following:

Segmentation fault (core dumped)

This means that the program has accessed memory in an invalid way, causing the program to “fault” or crash. To find out what is going on, we want to get more information about the problem. To do this, we will run the program in the debugger.

First, re-compile the program “with the debug flag on” by using the following command (note the bold part):

$ g++ -g -std=c++11 -o segfault segfault.cpp

Then, start the debugger with our segfault program as the target:

$ gdb ./segfault

The debugger will show a good amount of informational output, ending with something like the following:

Reading symbols from ./segfault...done.
(gdb)

The first line means that the debug flag applied successfully, and the second line is the debugger's command prompt. It is waiting for you to start typing commands. First, tell it to run the program by typing run at the prompt.

The segfault program will now run. Eventually, the debugger will show something like the following output:

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400a44 in main () at segfault.cpp:16
16		cout << *y << endl;

This tells us exactly which line caused the fault to happen. In this case it is because we accessed the value pointed to by the y variable, when the y variable was an invalid pointer.

Now, you can exit the debugger. Type quit at the prompt. Now, to fix this error, change line 14 in the segfault.cpp file to look like this:

14	*y = 0;

(Note the asterisk in front of the y variable)

Re-compile (with the debug flag) and run the program in gdb again. You should now see that the program prints the number 0, but still crashes at a line further down in the program.

Your task for this problem is to solve the second segmentation fault by changing only one more line in the file. Use the debugger to diagnose the error. A list of useful debugger commands is provided below:

Some examples of the print command:

Hint: C++ vectors cause issues when the [] operator is used when the vector has zero capacity.

Hint: The number in the vector constructor (line 19 in this program) specifies the initial capacity.

For full credit, you need to use the debugger and only two lines should be changed from the original program when you submit.

Chapter 7: Mountain Climb

This should be solved in the climb.cpp file.

Write a program which determines how steep the climb is to the top of a mountain. The program will take user input which looks like the following:

1 2 3
2 2 2

Which represents a two-dimensional rectangle of integers. We are looking at a mountain (or mountains) from above, and the area has a rectangular base. Each value is the height of the terrain at that specific point in the rectangle (in increments of 1 on both axes). Each horizontal row will be on a new line, and the end of the entire input will be noted with an empty line with no integers.

In this case, the top left corner is the lowest point at height/elevation 1 and the top right corner is the peak of the mountain at height 3.

The horizontal distance between each point is the standard 2-dimensional distance. In this example, the distance between the top left and top right corners is 2, and the distance between the top left and bottom right corners is sqrt(5).

Your program should find lowest and highest heights in the input. It should then compute the angle between a line between the terrain at those two points and the horizontal plane (i.e. the angle you would be climbing if you went in a straight line from the lowest to highest point). The angle should then be printed in radians.

With the heights given above, the horizontal distance between the lowest and highest points is 2 and the change in height is also 2 (lowest at 1 to highest at 3). Therefore the angle of the line between them (from the horizontal) is 45 degrees or 0.785 radians.

Hint: remember that the distance between two points is sqrt((x1 - x2)2 + (y1 - y2)2).

Hint: the <cmath> library contains the arctangent function, with the name atan.

Note: Assume that the lowest and the highest points are unique. This may not be true for other points.

The input should be stored in a multidimensional integer array. The rectangle of heights will have a size less or equal to 10 by 10.

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 one of the following examples (including whitespace and formatting), with a possibly numbers and letters in the output:

Enter heights:
5 5 6 5
5 6 7 6
5 5 6 6
3 4 4 5
2 3 3 3
2 2 2 2
1 2 2 2

The angle of the climb is 0.839 radians.

Enter heights:
1 2 3

The angle of the climb is 0.785 radians.

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

The angle should be printed to three places after the decimal.

Chapter 7: Matrix Multiplication

This should be solved in the matrix.cpp file.

Write a program which multiplies two matrices. The matrices may be any size, contain integers, and will come as input from the user. Each matrix will be input with the columns separated by spaces and the rows each on a new line. The end of each matrix will be specified by an empty line with no integers. Your program should print the resulting matrix with each column separated by a space, and each row on a new line.

Remember that the matrix product is defined as:

(AB)ij = sum of (Aik * Bkj) for k = 1 to m (where m is the number of columns in A)

Your program should output an error if the dimensions of the input matrices are incompatible (the number of columns in the first is not equal to the number of rows in the second).

Each input matrix should be stored in a multidimensional integer array. You may also want to use a multidimensional array to store the result matrix. All three matrices have sizes less or equal 10 by 10.

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

Enter first matrix:
1 2 3
4 5 6

Enter second matrix:
7 8
9 0
1 2

The product is:
28 14
79 44

Enter first matrix:
1 2 3

Enter second matrix:
4 5 6

The two matrices have incompatible dimensions.

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

Top

Step 6: Compile the Code

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

$ g++ -g -std=c++11 -o segfault segfault.cpp
$ g++ -std=c++11 -o climb climb.cpp
$ g++ -std=c++11 -o matrix matrix.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:

$ gdb ./segfault
$ ./climb
$ ./matrix

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

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 7”. Then click “Make Submission”, and make your submission the same way as last week. Remember to submit all three .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 three source files to this assignment by running the command:

$ ~submit/submit -p 505 segfault.cpp matrix.cpp climb.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