Homework #2

Due Date: Monday, April 18th at 9pm.

The following homework exercises are intended to help you practice some of the programming concepts introduced in weeks 2 and 3, including arrays, out parameters, heap allocation, and strings.

Getting started

You will be using a new repository for each homework in this course. Please follow the instructions in the “Getting started” section of Homework #1 for obtaining a new repository for Homework #2. Careful! Make sure to replace hw1 with hw2 as needed. Make sure that you complete all seven steps. Start by accepting the invitation link posted on Ed.

Compiling and testing your code

We will continue to use the testing infrastructure that you are now accustomed to. For a refresher, please read through the “Compiling and testing your code” section of Homework #1. To run the Homework #2 tests, you will need to replace homework1 with homework2 as needed.

Exercises

Throughout this assignment, you may assume that pointer parameters point to valid data and are not NULL. You can also assume that the value of the length of an array passed as parameter to a function is indeed the length of that array. You can call malloc as needed throughout this assignment.

  1. Complete the function flip, which takes an array of integers and its length and rearranges the elements of an array in-place so that the values of the array are “flipped” over its midpoint.

    For example, the array {-2, 10, 3} flipped has the values {3, 10, -2}. The array {1, 2, 3, 4} flipped has the values {4, 3, 2, 1}.

  2. Complete the function shift, which takes an array of integers and its length and shifts the elements of the array in-place to the right by one.

    For example, the array {-2, 10, 3} shifted has the values {3, -2, 10}. The array {1, 2, 3, 4} shifted has the values {4, 1, 2, 3}. Notice that the last element in the array becomes the first element in the shifted array.

  3. Complete the function:

    char *first_letter(char *sentence, int *num_words)

    which takes a string that contains a sentence and returns a heap-allocated array of characters. The array should contain the first letter of each word in the sentence. This function also returns the length of the character array as an out parameter.

    Consider the sentence “Hello, my name is Joe.” The first letters of each word in the sentence are ‘H’, ‘m’, ‘n’, ‘i’, and ‘J’. So, a call to first_letter with the sentence "Hello, my name is Joe." should return the array {'H', 'm', 'n', 'i', 'J'}. Furthermore, the out parameter num_words should point to the value five, since there are five words in the sentence.

    You can assume the input sentence is a well-formed sentence. That is, it does not contain any leading or trailing spaces and there is only one space between each word. You do not need to consider the distinction between words that start with a letter and words that start with a non-letter character. Both are valid.

    There are a number of ways approach this problem. We suggest you start by computing the length of the output array. Note that to solve this problem you will need to set the out parameter num_words, as well as create and return the array of first letter characters. You should not use any functions from string.h in your solution.

The next group of exercises involve a compression technique called Null encoding.

Compression is a technique to make data use less space. Nearly all images, videos, and sound files that we view and listen to are compressed to save space and transfer time. There are many sophisticated compression schemes, but one simple one is called Null encoding. This compression method is suitable for data that contains many zeros.

Null encoding proceeds as follows: Scan over the values in the data, looking for runs of zeros. For example, in the following data:

1 4 3 0 0 0 0 8 0 0 0 1

there are two runs of zeros, one of length four and one of length three.

In Null encoding, we replace each run of zeros with two values: a zero and the length of the run. For example, the Null encoding of the data above is:

1 4 3 0 4 8 0 3 1

The run 0 0 0 0 was replaced with 0 4 and the run 0 0 0 was replaced with 0 3. This takes less space, but only by a little bit. It would take a lot less space if there were hundreds or thousands of zeros in a row.

In some cases, Null encoding does not save space. For example, the following data:

4 0 5 0 0

is compressed to:

4 0 1 5 0 2

which contains one value more than the original data. Data that contains runs of length one will not benefit from being Null encoded.

The good news is that the compressed data may take less space. The bad news is that the format has been changed, so no program can use the data directly. The data must be decompressed, which performs the inverse of compression. For example, 0 4 must be converted back to 0 0 0 0 and 0 3 must be converted to 0 0 0. As another example, consider the following Null encoded data:

0 2 5 6 0 1 3 0 3

Decompressing this Null encoded data produces:

0 0 5 6 0 3 0 0 0

In the following exercises, you will encode (compress) data using Null encoding, decode (decompress) Null encoded data, and determine when Null encoding is benficial.

  1. Complete the function count_zeros_and_runs, which takes an array of integers and its length and returns the number of zeros in the array and the number of runs of zeros, both as out parameters.

    For example, the array {1, 4, 3, 0, 0, 0, 0, 8, 0, 0, 0, 1} contains seven zeros and two runs.

  2. Complete the function saves_space, which takes an array of integers and its length and returns true if Null encoding the array saves space, and false otherwise. That is, determine whether or not the Null encoded version of the array contains strictly fewer elements than the original.

    For example, a call to saves_space with the array {1, 4, 3, 0, 0, 0, 0, 8, 0, 0, 0, 1} should return true, since the encoded array has nine elements (fewer than the original twelve).

    A call to saves_space with the array {4, 0, 5, 0, 0} should return false.

    Note that you do not need to do the work of encoding the array in this problem. You only need to calculate how many elements will be in the encoded array.

  3. Complete the function:

    int *encode(int *a, int len, int *encoded_len)

    which takes an array of integers and its length, and returns a heap-allocated Null encoded version of the array. The function also returns the length of the Null encoded array as an out parameter.

    For example, a call to encode with the array {0, 0, 4, 2, 0, 0, 0, 0, 0, 3} should return the array {0, 2, 4, 2, 0, 5, 3} and encoded_len should point to the value seven.

  4. Complete the function:

    int *decode(int *a, int len, int *decoded_len)

    which takes a Null encoded array of integers and its length, and returns a heap-allocated version of the array, decoded. The function also returns the length of the decoded array as an out parameter.

    For example, a call to decode with the array {8, 0, 1, 4, 0, 3} should return the array {8, 0, 4, 0, 0, 0} and decoded_len should point to the value six.

    You may use the calloc function in Exercises #6 and #7.

Grading

For this assignment, the weights will be:

  • Completeness: 60%

  • Code Quality: 40%

The code quality score will be determined by code clarity, design, efficiency, and style.

Preparing your submission

There are three things you should do before you submit your work.

First, make sure you have added the required information to the header comment in homework2.c:

  • your name,

  • the names of anyone beyond the course staff you discussed the assignment with, and

  • links to any resources that you used other than course materials and the course textbook.

Please remove the explanation for what is required. Note: write None in the relevant field, to indicate that you did not use any sources and/or consult anyone beyond the course staff.

Second, remove directives, such as:

// YOUR CODE HERE

// Replace 0.0 with an appropriate return value

from your code. Make sure to recompile and rerun the tests after you make these changes. It is easy to introduce a syntax error at this stage.

Third, add, commit, and push your work to GitHub.

And finally, get your directory into a clean state. Run make clean to remove any executables that are laying around.

Submission

To submit your work, you will need to add, commit, and push your code to GitHub. Before you upload your code to GitHub, run git status . to make sure you did not forget to add/commit any of the required files. Then upload your submission to Gradescope under the “Homework #2” assignment. Make sure to choose the right assignment on Gradescope!

You are welcome to upload your code to Gradescope multiple times before the deadline, but it is wildly inefficient to use Gradescope as a compute server. You should test your code on the CS Linux machines and only upload it when you think you are finished or when you are getting close to the deadline and want to do a “safety” submission.

You are responsible for making sure that the code you upload compiles and runs. You will get zero credit for code that does not compile.

Finally, a reminder that we will not accept late work.