Lab 3: Arrays and Recursion

Getting Ready for the PE Environment

For this lab session, we will use the lab desktop PC and the real pelogin system so you can get a feel for working in the Practical Exam (PE) environment. Read the PE0 page for the exam procedure. This lab is still ungraded, and you can ask your TA for help.

Find Your Practice Credentials

Your practice username and password will be provided in a comment on the Canvas assignment CS1010 PE Practice Credentials once it is published. These are the credentials to use for this lab session. The PE0 page explains how you will receive your credentials for the actual exam.

Open the CS1010 course on Canvas, open CS1010 PE Practice Credentials, and read the comment containing your username and password. Keep these details available for the two login steps below. If you cannot find the assignment or your comment when the lab begins, ask your TA for help.

Log In to the Lab PC

1. Use your lab desktop PC for this session
2. If it is running Windows, save any open work and restart it. Select Ubuntu from the operating-system menu. Ask your TA if you cannot find this option. If Ubuntu is already logged in to another account, log out first
3. At the Ubuntu login screen, enter the practice username and password from the Canvas comment. If another username is shown, choose the option to enter a different username
4. After the desktop appears, open a terminal with Ctrl+Alt+T, as described on the PE0 page. You can also open Terminal from the applications menu

Connect to pelogin

Logging in to Ubuntu gives you a desktop on the lab PC. You must now connect your terminal to the remote PE system using SSH, as practised in Tutorial 3. This session uses the real pelogin service, rather than Tutorial 3’s simulation.

1. In the terminal, type the following and press Enter:

   ssh pelogin

   SSH uses the username you used to log in to Ubuntu

2. If this is your first connection and you see the host-authenticity prompt, type yes and press Enter

3. If asked for a password, type the password from the Canvas comment and press Enter. Nothing appears as you type, not even asterisks; this is normal

4. Wait for the remote shell prompt, then run whoami. It should print your practice username. The machine name in the prompt may differ from pelogin

Keep this terminal connected for the rest of the lab. If you get a login error, ask your TA for help before continuing.

Copy the Lab Code to Your Home Directory

The starter code is in the shared, read-only directory /opt/course/cs1010/lab3. Make your own copy before editing anything. Here, ~ means your home directory on the remote PE system.

Run these commands in the terminal connected to pelogin:

cp -R --update=none /opt/course/cs1010/lab3 ~/
cd ~/lab3
ls

cp -R copies the whole directory, including its subdirectories. The --update=none option keeps any existing files in your copy, so repeating the command does not overwrite work you have already started. You should see activity-1, problem-solving-1, and problem-solving-2.

Work in ~/lab3 on pelogin for the activities below. Use your terminal editor, make, and make test, as practised in Tutorial 3. Save your files regularly. Your saved files remain in your remote home directory when you disconnect; there is no separate submission step for this ungraded lab.

Preface

In Lab 3, we’re going to work on a few mechanics about arrays (not too many). And then mostly work on recursive problem solving. Some of these questions are also in your volume, we’re dedicating lab time to help guide you through the problem solving process. Up until before this lab, we’ve only given very small snippets. Today we will have you writing slightly bigger snippets.

As with the previous labs, do not immediately compile each program. First predict what it will do. Then run it, observe what happened, and explain why.

Activity 1: Arrays and Functions

The starter code for this activity is in activity-1/.

From the Lab 3 directory, run cd activity-1 before compiling these examples. Return to the Lab 3 directory with cd .. when you finish Activity 1.

Part 1: One-Dimensional Arrays

Consider arrays-and-functions.c:

#include <stddef.h>
#include <stdio.h>
 
void change_number(int value) {
  value = 99;
  printf("inside change_number: %d\n", value);
}
 
void change_element(int values[], size_t index) {
  values[index] = 99;
  // Alternative 1
  // values[index] += 1;
 
  // Alternative 2
  // int x = values[index];
  // x += 1;
}
 
int main(void) {
  int number = 10;
  int values[3] = {10, 20, 30};
 
  change_number(number);
  change_element(values, 1);
 
  printf("number: %d\n", number);
  printf("values: %d %d %d\n",
      values[0], values[1], values[2]);
}

What do you think will happen?

Before compiling:

1. Predict the value printed inside change_number
2. Predict the value of number printed in main
3. Predict all three values in values
4. Decide whether either function changes something in main

Compile and run the program:

clang -std=c23 arrays-and-functions.c -o arrays-and-functions
 
./arrays-and-functions

What happened?

Then, try changing the change_element function with the alternatives listed. Does the behavior change? Why?

Next, consider the separate program arrays-and-functions-2.c:

#include <stddef.h>
#include <stdio.h>
 
void print_element(int values[], size_t index) {
  printf("%d\n", values[index]);
}
 
int main(void) {
  int values[3] = {10, 20, 30};
 
  print_element(values, 3);
}

What do you think will happen?

Compile and run the separate program:

clang -std=c23 arrays-and-functions-2.c \
  -o arrays-and-functions-2
./arrays-and-functions-2

What happened this time? Why?

Part 2: Two-Dimensional Arrays

Consider two-dimensional.c:

#include <stddef.h>
#include <stdio.h>
 
void change_cell(int grid[][3], size_t row, size_t column) {
  grid[row][column] = 99;
}
 
int main(void) {
  int grid[2][3] = {
      {10, 20, 30},
      {40, 50, 60},
  };
 
  printf("%d\n", grid[0][2]);
  printf("%d\n", grid[1][0]);
 
  change_cell(grid, 1, 2);
 
  printf("%d %d %d\n", grid[0][0], grid[0][1], grid[0][2]);
  printf("%d %d %d\n", grid[1][0], grid[1][1], grid[1][2]);
}

What do you think will happen?

Before compiling:

1. Draw grid as two rows and three columns
2. Label each element with its row and column indices
3. Predict the first two values printed
4. Identify the element changed by change_cell
5. Predict the final two lines of output

Compile and run the program:

clang -std=c23 two-dimensional.c \
  -o two-dimensional
./two-dimensional

Now, try to remove the number 3 from [3] in change_cell. Compile the code again? What happened? Try to read and understand the output.

Now consider the separate program two-dimensional-2.c:

#include <stdio.h>
 
int main(void) {
  int grid[2][3] = {
      {10, 20, 30},
      {40, 50, 60},
  };
 
  printf("%d\n", grid[0][3]);
}

What do you think will happen?

Compile and run the separate program:

clang -std=c23 two-dimensional-2.c \
  -o two-dimensional-2
./two-dimensional-2

What happened? Is this program ok?

Discuss:

1. Which index selects the row?
2. Which index selects the column within that row?
3. What are the valid row and column indices of grid?
4. How is the two-dimensional array parameter written in change_cell?
5. Which dimension is omitted and which dimension is specified in int grid[][3]?

---

Problem Solving Primer

As our tasks get bigger, here’s the problem solving pipeline we wish to teach you today:

1. Before writing your code, you are going to have to plan out your strategy. (Sometimes we call this whiteboarding)
2. You might have to identify whether any existing library function or given function already serves your needs. If not, what kind of functions do you need? Do you need to break the problem up into smaller logical steps?
3. Only then, start writing the code.

Whiteboarding

This is just a quick reminder of how to solve recursive problems from the lecture (since now you’ll get hands-on experience doing this in the lab itself).

1. Identify the simple/base case and how to solve it then return.
2. For all the other cases, figure out how to work towards the simple case, and make use of its solution to solve the main problem that we were given.

Draw shapes and scribble if you have to. It helps. Discuss with your lab and lab TA.

Problem Solving Practice 1: Warmup

Input: You’re given an array values of length length. There are between 1 and 100 elements in the array. You are guaranteed that incrementing any element by 1 will not overflow an int.

Task: Your task is to increment every value in the array by 1. You should do so recursively.

The starter code for this activity is in problem-solving-1/.

Step 1.1: Identify the Simple Case

What’s the “smallest version” of the problem you can think of? In that case what should you do?

Step 1.2: Use the Solution to the Smaller Case to Solve the Current Problem

Given that in general our array might have $n>1$ elements, how should we head from $n$ towards the simple case?

Let’s say that solving the smaller case is already handled. What else is there for you to do?

Step 2: Break the Problem up into Logical Steps (if Need Be)

As usual, following the recursive “template”, we’ve already broken the problem up into the simple case vs the remaining case. Plan out what you should write in your if-else.

Step 3: Start Writing the Code

Open up student.c in problem-solving-1/ and implement the function provided.

void increment_all(int values[], size_t length);

You need not worry about reading from input, that code has been written for you. We will also print the result of your work.

From the Lab 3 directory, compile and run your program:

cd problem-solving-1
make
./increment-array

Run make test to check your program against the supplied test cases.

Providing Input

To provide input, run the program and type the number of elements, and then on the next line, the elements themselves separated by spaces. Like so:

5
1 3 1 -1 7

Press Enter after the values line; you do not need to send EOF.

If you did your code right, the program in this example should then print:

2 4 2 0 8

Problem Solving Practice 2: Mirror

Input: You’re given an array values of length length. You’re promised that length is even and between 0 and 100.

Task: Your task is to mirror the first half of the array into the second half.

The starter code for this activity is in problem-solving-2/.

Example: Given array $\{0,1,1,5,3,3,0,0\}$, the expected output is $\{0,1,1,5,5,1,1,0\}$.

Step 1.1: Identify the Simple Case

Identify the simple case for Mirror.

This is probably slightly trickier than the previous one. The same approach there won’t fit but perhaps we can take inspiration from one of the problems solved in lecture.

Hint

Remember reverse? Perhaps that, or helper functions based on it, might be useful here.

Step 1.2: Use the Solution to the Smaller Case to Solve the Current Problem

In general, when our array has $n>2$ elements, how should we make it head towards the simpler case?

Hint

Again, think about reverse. Copy-pasting it will not help, but it, or helper functions based on it, might be useful here.

Step 2: Break the Problem up into Logical Steps

Lay out your general strategy first. What do you do in the simple case? What do you do in the general case? Do you need any additional functions?

Hint

You just need to be able to copy elements from one index into another. Thinking in terms of reverse, or helper functions based on it, might be useful here.

Step 3: Start Writing the Code

Open up student.c in problem-solving-2/ and implement the function provided.

void mirror(int values[], size_t length);

You need not worry about reading from input, that code has been written for you. We will also print the result of your work.

From the Lab 3 directory, compile and run your program:

cd problem-solving-2
make
./mirror

Run make test to check your program against the supplied test cases.

Providing Input

To provide input, run the program and type the number of elements, and then on the next line, the elements themselves separated by spaces. Like so:

6
1 2 5 7 9 0

Press Enter after the values line; you do not need to send EOF.

If you did your code right, the program in this example should then print:

1 2 5 5 2 1

For an empty Mirror array, enter 0 and press Enter. No values line is needed.

Problem Solving 3: Grey Codes (Volume)

This exercise discusses the actual Volume question on Grey Codes to help you think of the solution.

Continue to Grey Codes in Volume 3.