Lab #3: Loops and Arrays¶

Due Date Wednesday, April 13th at 9pm.

The purpose of this lab is to give you practice working with:

loops,
arrays as parameters,
out parameters, and
dynamically allocating arrays.

You must complete this lab on a CS Linux machine. You can use the machines in CSIL or can use VSCode + ssh on` your own machine to get to one of the Linux servers.

Getting Started¶

You will be using the same repository for all the labs in this course. To pick up the files you need for this lab (aka, the distribution), you should navigate to your cmsc15200/labs-GITHUB_USERID directory (where GITHUB_USERID) is replaced with your GitHUb account name and then run:

$ git pull upstream main

(We will use $ to indicate the Linux command-line prompt. It is not part of the command that you will run.)

If this command succeeded, you will have a subdirectory named lab3. You will do all of your work for this lab in this directory. See the file README.md for a description of the files in the distribution.

Compiling and testing your code¶

As in Lab #2, we have provided a Makefile that has targets for compiling your code with tests that you write, for compiling your code with our automated tests, and for cleaning up generated files. To use this file to compile your code, run one of the following commands from the Linux command-line:

$ make student_test_lab3

$ make test_lab3

$ make

The first command will compile your code in lab3.c along with any tests you have added to student_test_lab3.c and will, if possible, generate an executable (student_test_lab3). To run the resulting executable, you can run:

$ ./student_test_lab3

We have provided some simple tests as examples in student_test_lab3.c. You should add tests of your own as your work on your code.

The second command will compile your code with our automated tests and will, if possible, generate an executable (test_lab3). To run all of the tests using the resulting executable, run this command from the command line:

$ ./test_lab3 -f --verbose

The -f flag tells the test code to stop after the first failure. The --verbose flag generates information which specific tests passed and failed.

The tests are broken into suites. To run a specific suite or test, you can add a filter. For example, to run all of the tests in count_occurrences suite, you would run:

$ ./test_lab3 -f --verbose --filter="count_occurrences/*"

To run a specific test, replace the * with the name of the test. For example, the first test in the count_occurrences suite, you would run:

$ ./test_lab3 -f --verbose --filter="count_occurrences/test0"

Deliverables¶

Task 1¶

Complete the function count_occurrences, which counts the number of occurrences of a target value in an array. The function takes the following parameters:

nums: an array of integers,
N: the number of elements in the array, and
val: the target value

and returns the number of occurrences of val in nums. Here are two sample uses of this function:

int target1 = 5;
int sample_nums1[] = {5, 4, 5, 2, 3, 1, 10, 0};
int len1 = 8;

int count1 = count_occurrences(sample_nums1, len1, target1);
int count2 = count_occurrences(sample_nums1, len1, 20);

The value of count1 after the first call will be 2, because 5 occurs twice in sample_num1. The value count2 after the second call will be 0 because 20 does not occur in sample_nums1.

Task 2¶

Complete the function, div_and_mod, which computes the result of integer division and remainder. The function takes the following parameters:

x: the numerator,
y: the denominator,
remainder: an out parameter to be set to the integer remainder of x and y.

The function should return the result of performing integer division on x and y and set the out parameter remainder to the integer remainder of x divided by y.

Here is a sample use of this function:

int rem;
int div = div_and_mod(5, 2, &rem);

After the call, the value of div will be 2 and the value of rem will be 1.

Task 3¶

Complete the function find_first_last_occurrence, which finds the indices of the first and last occurrence of a given value in an array. The function takes the following parameters:

nums: an array of integers
N: the length of the array (will be at least 1)
val: the target value
first: an out parameter for index of the first occurrence of the target value in the list.
last: an out parameter for index of the last occurrence of the target value in the list.

The purpose of this function is to set the two out parameters. Use an “index” of -1 to signal that the value does not occur in the array.

Here is a sample use of this function:

int sample_nums[] = {4, 5, 4, 3, 1, 10, 5, 4, 1};
int len = 9;
int first;
int last;

find_first_and_last_occurrence(sample_nums, len, 5, &first, &last)

After the call, the value of first will be 1 and the value of last will be 6. The value 5 occurs for the first time at index 1 and for last time at index 6.

Here’s another sample call:

find_first_and_last_occurrence(sample_nums, len, 20, &first, &last)

After the call, the value of both first and last will be -1, because 20 does not occur in the array.

Allocating Arrays¶

The next task requires you to return an array. Local arrays (that is, arrays created as local variables inside a function) are allocated on the stack and cannot be returned from functions. Instead, arrays that will returned from functions need to be allocated on the heap. You can use one of two functions from the stdlib library for this purpose: malloc or calloc. malloc takes a number of bytes as an argument and returns either a pointer (of type void *) to the requested bytes in memory or NULL, depending on whether it was able to allocate the requested space.

Here’s a sample use of malloc to allocate an array named nums of N integers:

int *nums = (int *) malloc(sizeof(int) * N);
if (nums == NULL) {
    fprintf(stderr, "Ran out of space in some function \n");
    exit(1);
}

Notice that we cast the type of the value that comes back from malloc, which is initially of type void * to have the desired type of the variable (in this case, int *). Also, notice that we check the return value from malloc and fail when it returns NULL.

The general form for allocating arrays is:

typ *some_name = (typ *) malloc(sizeof(typ) * N);
if (some_name == NULL) {
    fprintf(stderr, "Ran out of space in some function\n");
    exit(1);
}

where typ is the type of the elements of the array, some_name is the name of the resulting array, and N is the number of elements in the array. Note: you should always check the return value from malloc.

The space returned from malloc is not initialized to any particular value. You can use calloc if you wish to allocate space and have it initialized to zero. Unlike malloc, calloc takes two arguments: the number of elements to allocate and their size. Here’s a sample use of calloc:

int *nums = (int *) calloc(sizeof(int), N);
if (nums == NULL) {
    fprintf(stderr, "Ran out of space in some function \n");
    exit(1);
}

Notice that we are casting the value that comes back from calloc to have the right type and we are checking the return value to make sure the call succeeded.

Once an array is allocated, you can use the standard array notation for accessing the elements. For example, if we allocated nums using malloc, we might want to initialize the elements to zero:

for (int i=0; i < N; i++) {
    nums[i] = 0;
}

Space allocated on the heap is known as dynamically-allocated space. When you are finished with dynamically allocated space, you need to return it to the runtime system using free, which takes a (dynamically-allocated) pointer as an argument. For example, to free the space allocated above, we would write:

free(nums)

Space is frequently allocated in one function and freed in another.

Task 4¶

Complete the function compute_frequencies, which computes the number of times each value between a specified lower bound (lb) and a specified upper bound (ub) occurs in an array. The function takes the following values:

lb: lower bound of the range (where lb >= 0),
ub: lower bound of the range (where ub >= lb),
nums: an array of integers between lb and ub (inclusive),
N: number of values in the array, and
result_len: an out parameter that will be set to the length of the result

and returns array with frequency of each value between lb and ub in the array. The ith index in the result should contain the number of times that value i+lb occurred. If the range ran 20 to 30, then the result would contain 11 values. Index 0 would contain the number of times the value 20 occurred, index 1 would contain the number of times 21 occurred, etc.

While you may assume that the values in nums will all be in the range from lb to ub (inclusive), it would not hurt to add an assertion in the loop that processes the array to verify that the values fall with in the specified range.

Here is a sample use of this function:

int sample_nums[] = {4, 5, 4, 3, 1, 10, 5, 4, 1};
int count_len;
int *counts = compute_frequencies(1, 10, sample_nums, 9, &count_len);

The value of counts will be {2, 0, 1, 3, 2, 0, 0, 0, 0, 1}, because 1 (the lowest value in the range) occurs twice, 2 does not occur, etc. The value of count_len after the call will be 10, since there are ten values in the range from 1 to 10.

Here’s another call that uses the same data, but with a different range:

int count_len_other;
int *counts_other = compute_frequencies(0, 12, sample_nums, 9, &count_len_other);

In this case, the value of counts_other will be {0, 2, 0, 1, 3, 2, 0, 0, 0, 0, 1, 0, 0}. The value of counts_other[0] will be 0 because 0 (the smallest value in the range) does not occur in the array. The value of count_len_other will be 13 since there are thirteen values in the range from 0 to 12.

Restriction This work can be done in linear time, that is, in time proportional to the length of the array. Your implementation is allowed to make exactly one pass over the array nums. In particular, you may not use a nested loop in this function. You will not receive full credit for this task, if your implementation uses a nested loop or any other algorithm that takes quadratic time (that is, time proportional to the square of the length of the array) or worse.

Task 5¶

Complete the function freq_max, which computes the value that occurs most frequently in the array. This function takes the following parameters:

lb: lower bound of the range of the values in nums,
ub: upper bound of the range of the values in nums,
nums: an array of values between lb and ub. (not every value in the range is required to occur),
N: length of the array nums, and
most: out parameter for the value that occurs the most frequently in the array.

Ties should be broken by choosing the smaller value. For example, given the array: {2, 2, 3, 3, 5, 5, 5, 4, 4, 4}, four is deemed to be the most frequently occurring value because four and five occur the most times and four is less than five.

Here’s a sample call:

int sample_nums[] = {2, 5, 5, 7, 5, 2, 2, 5, 5, 7};
int len = 10;
int most_freq;

freq_max(0, 10, sample_nums, len, &most_freq);

After the call, the value of most_freq will be 5.

Requirement: Your implementation of this task must use your compute_frequencies function and you must free the space returned from compute_frequencies when you are finished with it.

Some useful stuff¶

Most labs in this course will contains some material that is intended to help you become more fluent in Linux. Today’s topics—file permissions and ownership–are an essential part of using Linux.

There are no deliverables for this section. That does not mean you should skip it!

File Permissions¶

Sometimes we want to restrict who can access certain resources on the file system.

Most file systems assign ‘File Permissions’ (or just permissions) to specific users and groups of users. Unix is no different. File permissions dictate who can read (view), write (create/edit), and execute (run) files on a file system.

All directories and files are owned by a user. Each user can be a member of one or more groups. To see your groups, enter the command groups into the command line.

File permissions in Unix systems are managed in three distinct scopes. Each scope has a distinct set of permissions.

User - The owner of a file or directory makes up the user scope.

Group - Each file and directory has a group assigned to it. The members of this group make up the group scope.

Others - Every user who does not fall into the previous two scopes make up the others scope.

If a user falls into more than one of these scopes, their effective permissions are determined based on the first scope the user falls within in the order of user, group, and others.

Each scope has three specific permissions for each file or directory:

read - The read permission allows a user to view a file’s contents. When set for a directory, this permission allows a user to view the names of files in the directory, but no further information about the files in the directory. r is shorthand for read permissions.

write - The write permission allows a user to modify the contents of a file. When set for a directory, this permission allows a user to create, delete, or rename files. w is shorthand for write permissions.

execute - The execute permission allows a user to execute a file (or program) using the operating system. When set for a directory, this permission allows a user to access file contents and other information about files within the directory (given that the user has the proper permissions to access the file). The execute permission does not allow the user to list the files inside the directory unless the read permission is also set. x is shorthand for execute permissions.

To list information about a file, including its permissions, type:

ls -l <filepath>

You’ll get output of the form:

<permissions> 1 owner group <size in bytes> <date modified> <filepath>

For example, if we want information on /usr/bin/python3.5:

$ ls -l /usr/bin/python3.5
-rwxr-xr-x 1 root root 4460272 Aug 20 /usr/bin/python3.5

First thing we can notice is that the owner of the file is a user named root. (FYI, root is a name for an account that has access to all commands and files on a Linux system. Other accounts may also have “root” privileges.) The file’s group is also root.

The permissions are -rwxr-xr-x. The initial dash (-) indicates that /usr/bin/python3.5 is a file, not a directory. Directories have a d instead of a dash. Then the permissions are listed in user, group, and others order. In this example, the owner, root, can read (r), write (w), and execute (x) the file. Users in the root group and all other users can read and execute the files.

Exercises¶

By default, any files or directories that you create will have your username as both the user and the group. (If you run groups, you’ll notice that there is a group with the same name as your username. You are the only member of this group.) On our Linux machines, by default, new files are give read and write permissions to user and group and no permissions to other. New directories will be set to have read, write and execute permissions for user and group.

Create a directory named backups in your lab3 subdirectory using the mkdir command. Verify the claims about permissions for new directories by running ls -ld backups. The -d flag tells ls to list the directory, instead of its contents. Notice that that the first letter in the permissions string for backups is a d
Create a file:
```
echo "Hello world" > backups/hello.txt
```
Verify the claim about permissions for new files by running ls -l backups/hello.txt. Notice that the first letter in the result is -, which indicates that hello.txt is a file.

Once you have verified these claims, go ahead and remove the backups directory using the command: rm -r backups.

Changing Permissions, Owner, & Group¶

`chmod` <permissions> <path-name>	set the permissions for a file/directory
`chmod` <changes> <path-name>	update the permissions for a file/directory
`chown` <username> <path-name>	change the owner of a file to username
`chgrp` <group> <path-name>	change the group of a file
`cat` <path-name>	print the contents of a file to the terminal

To change permissions, we use the chmod command. There are two ways to specify the permissions. We’ll describe the more accessible one first: to set the permissions you specify the scope using a combination of u, g, and o, the permission using r, w, and x, and either + or - to indicate that you want to add or remove a permission. For example uo+rw indicates that you want to add read and write permissions for the user and others groups.

We can demonstrate this using the cat command to print file contents to the terminal:

$ echo "Hello!" > testfile
$ ls -l testfile
-rw-rw---- 1 username username 7 Aug 23 11:22 testfile
$ cat testfile
Hello!
$ chmod ug-r testfile #remove read and permissions from user and group
$ ls -l testfile
--w--w---- 1 username username 7 Aug 23 11:22 testfile
$ cat testfile
cat: testfile: Permission denied
$ chmod u+r testfile #give user scope read permissions

In this last example, we have added user read permissions to testfile.

In addition to the symbolic method for setting permissions, you can also use a numeric method: each permission has a unique value: read = 4, write = 2, execute = 1. As a result, you can describe the permissions of each scope using the sum of its permissions’ values. For example, if a file has read and write permissions for the user scope, its permissions can be described as 6 (4 + 2 = 6).

You can describe the permissions of a file overall using these values for each scope. For example, 761 describes the permissions for a file with read, write, and execute permissions for the user scope, read and write permissions for the group scope, and only execute permissions for the others scope.

The symbolic approach is relative: it allows you to add and remove permissions relative the the current file permissions. The numeric method is absolute: it sets the permissions to a specific configuration. We recommend starting the symbolic approach. It is easier to get right. As you get more comfortable with setting permissions, it is useful to learn how to use the numeric method.

To change the owner of a file or directory (if you are the owner or root), use the command:

chown <new owner> <path to file>

To change a file’s group (if you are the owner or root), use the command:

chgrp <new group> <path to file>

It is unlikely that you will need to use these two commands for this course.

Exercises¶

Run echo "Hello!" > testfile to construct testfile. Look at the permissions using ls -l.
Change the permissions on testfile to allow and read access for others. Run ls -l testfile to check the new permissions.
Remove group write access from testfile. Check the corrected permissions.
Remove testfile using rm.

Grading¶

For this assignment, the weights will be:

Completeness: 80%
Code Quality: 20%

The completeness score will be determined by the automated tests. The code quality score will largely be determined by whether your implementation uses a linear-time algorithm for Task 4 and makes effective use compute_frequencies in Task 5.

Cleaning up¶

Before your submit your work, we strongly encourage you to get your directory into a clean state. Run make clean to remove any executables that are laying around and then run git status . to make sure you did not forget to add/commit any of the required files.

Also, 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 clean up. It is easy to introduce a syntax error at this stage.

Submission¶

Before you upload your submission, make sure you have added the required information to the header comment in lab3.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.

To submit your work, you will need to add, commit, and push your code to GitHub. From within your lab3 directory run:

git add lab3.c
git commit -m"Ready to submit Lab #3"
git push

Once you have completed this step, upload your repository to Gradescope under the lab3 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.