Lab 4: Loops

Preachy nodle Note

We’ve done quite a few of these “make a prediction before compiling and checking” and this is for good reason. The C compiler is a double edged sword.

1. It is insanely helpful in helping you spot syntax errors, and warns you about potentially bad behaviour. In the same way you would just use a calculator to multiply numbers, the C compiler is a great way to help you verify whether what you wrote is syntactic.
2. It’s still important for you to be able to internalise programming language syntax because it fundamentally structures your thinking process. The more programming languages and paradigms you know, the more flexible your thinking process. An analogy would be the spinning ballerina. With enough effort, one can see the ballerina spinning both ways. Along those same lines, with enough practice and effort, you’ll be able to shift how you see processes.

Get Started

Run cs1010, select Download CS1010 content, then choose Labs and Lab 4 to download the starter code.

After the download finishes, enter the downloaded Lab 4 directory and run ls. You should see activity-1, activity-2, activity-3, problem-solving-1, and problem-solving-2.

Work in that directory for this lab.

For the activity examples, use the filename shown with each example, then compile and run it from the Lab 4 directory with, for example:

clang -std=c23 -Wall -Wextra activity-1/part1.c -o part1
./part1

For the problem-solving exercises, edit student.c in the named directory, then use make, ./sum-all or ./int-sqrt, and make test as described below.

Activity 1: Scoping Mechanisms

We’ve seen how scoping helps us maintain cleaner code, and hence why people generally might prefer to use a for loop over a while loop. We’re going to cover one more mechanism surrounding scoping that are quite useful for cleaner code.

Shadowing

Open activity-1/part1.c:

Consider the following C code below:

#include <stdio.h>
int main(){
	int x = 5;
	{
		printf("%d\n", x);
		int x = 21;
		printf("%d\n", x);
	}
	printf("%d\n", x);
}

It might surprise you to know that not only does this code compile, the behaviour is actually defined! (Take special notice of the fact we have added braces { }, without them, this wouldn’t work).

Part 1: Compilation and Prediction

Make a prediction on what the lines of output would be, before compiling and running the program. (Hopefully what happens here isn’t too surprising.)

Part 2: Shadowing vs Redeclarations

Turns out this is called shadowing, and many programming languages have this in some way, shape, or form (it also exists in Python in a different way). Based on what you know about the snippet above, look at the snippet below.

Open activity-1/part2.c:

Identify which variables:

1. are being shadowed.
2. have re-declarations that would invoke a compiler error.

int main(){
	int x = 1, y = 2, z = 3;
	{
		int y = x;
		{
			int x = 4;
		}
		int x = 5;
		int y = z;
	}
	int z = 6;
}

As usual, compile it after to see which lines were causing compiler errors. Feel free to comment them out after to see if it compiles.

Part 3: Applying Block Scope

Block scope lets us restrict a temporary variable to the part of the program that needs it. We will try to get you to apply this.

Open activity-1/part3.c:

#include <stdio.h>
 
int foo(){
	return 5;
}
 
int main(){
	// pretend these are muy importanto
	// variables
	int x = 1, y = 2, z = 3;
 
	// swap x and y
	int temp = x;
	x = y;
	y = temp;
 
	// swap y and z
	int temp = y;
	y = z;
	z = temp;
 
 
	printf("x: %d, y: %d, z: %d\n", x, y, z);
 
	int temp = foo(); // do this to save on 1 function call
	int squared = temp * temp;
 
	printf("squared: %d\n", squared);
}

You might notice that we’re using temp a lot and in fact this code would not compile. Without adding blocks, one fix would be to simply remove the int from all statements involving temp after the very first one. But you might imagine that in a big enough program this is not feasible. And so far we can’t use functions either since they would maintain their own explicit local scope.

Fix this code to make it compile-able by only adding { } where appropriate. I.e. we want to restrict each declaration of temp within its own scope. In fact, if you did it correctly, temp should never exist beyond a certain point.

---

Activity 2: Tracing while and Revising Loop Exits

Open activity-2/part1.c:

#include <stdio.h>
 
int main(void) {
    int i = 0;
    while (i < 3) {
        printf("before: %d\n", i);
        i += 5;
        printf("after: %d\n", i);
        i -= 4;
    }
    printf("finished: %d\n", i);
}

There is one aspect we likely didn’t have too much time to touch upon in the lecture. The idea that a loop condition does not have to be fulfilled in the middle of an iteration, and only has to be fulfilled when evaluated. This code should be a be able to illustrate that example.

Part 1: Trace the Loop

Predict the lines of output that will happen. It is important to be able to track line by line the evolution of the value of variable i.

Part 2: Compile and Run

As usual, compile and run it. Hopefully the program behaviour matched your expectation. If not, you might need to see where your tracing differed from what the program should have done.

Part 3: Try a for Loop

Notice that at the end of the loop, we wish to print the final value (and only the final value) of the variable i. Could we have done this with a for loop?

Part 4: continue, break, and return

Open activity-2/part4.c:

#include <stdio.h>
#include <stddef.h> // for size_t
 
void foo(int arr[], size_t len){
	for(size_t idx = 0; idx < len; ++idx){
		printf("Point A\n");
		if(arr[idx] % 2 == 0){
			continue;
		}
		printf("Point B\n");
		if(arr[idx] >= 100){
			break;
		}
		printf("Point C\n");
		if(arr[idx] % 3 == 0){
			return;
		}
		printf("Point D\n");
	}
	printf("loop ended, returning from foo!\n");
}
 
int main(void){
	int arr[] = {}; /* your array here */
	foo(arr, 0); // replace 0 with the number of elements in your array
}

Consider the code above.

Part 4.1:

Can you think of an array that will cause the program to output exactly the following lines?

Point A
Point B
Point C
Point D
Point A
Point B
Point C
Point D
loop ended, returning from foo!

Write that array directly in main() and fill in its length in the call to foo. Compile and run to make sure it’s correct.

Part 4.2:

Can you think of an array that will cause the program to output exactly the following lines?

Point A
Point B
Point C
Point D
Point A
loop ended, returning from foo!

Write that array directly in main() and fill in its length in the call to foo. Compile and run to make sure it’s correct.

Part 4.3:

Can you think of an array that will cause the program to output exactly the following lines?

Point A
Point A
Point B
Point C

Write that array directly in main() and fill in its length in the call to foo. Compile and run to make sure it’s correct.

---

Activity 3: Bug Squashing

Open activity-3/part1.c:

#include <stddef.h>
#include <stdio.h>
 
int main(void) {
    int readings[4] = {12, -1, 18, 0};
    size_t length = 4;
    size_t i = 0;
 
    while (i < length) {
        if (readings[i] == -1) {
            continue;
        }
        printf("%d\n", readings[i]);
        i += 1;
    }
}

Consider this program. Your colleague has written this with the goal of printing elements that are not -1.

Part 1: Observe the Problem

Compile and run it. What behaviour do you see? Does the program look stuck? (Hit ctrl+C if need be to terminate the program forcefully.)

Part 2: Investigate the Problem

Investigate the issue, add printf statements where you need to in order to try to see why the value i does not seem to ever reach length nor exceed it. Compile and run again. (Hit ctrl+C if need be to terminate the program forcefully.)

Part 3: Fix the Loop

How should you fix the program so that it does what your colleague had originally intended? Make as few edits as possible. (Try not to re-write the entire program.)

---

Writing Your Own Loops

We’re going to end on two exercises where you should figure out how to write your own loops. We’ll work on an example where the iteration condition is more clear cut, and one slightly less so.

Problem Solving Practice 1: Fixed Iterations

Often times, iterations are quite straightforward because you really only have to iterate a fixed number of times. An example of this would be to sum up all elements in an array.

The starter code for this exercise is in problem-solving-1/. Open student.c and implement:

#include "student.h"
 
int sum_all(int arr[], size_t len) {
	// Your code here
}

What if we had to implement a function that would sum up all values within an array and return it? What should you initialise? What should the condition be? What do you need to maintain after the loop body?

Input: The first line contains count, an integer from 0 to 100. If count is positive, the second line contains exactly count integers. Each value is between INT_MIN / 100 and INT_MAX / 100, inclusive.

Output: Print the sum followed by a newline. For count = 0, the empty sum is 0. The supplied main reads the input and prints the value returned by sum_all; your sum_all function should return the sum and should not print anything.

To help you figure it out, think about how you might want to start from the 0th index of the array all the way to the last index. Notice that this is a “fixed” kind of iteration because really you just need index 0, index 1, index 2, …, index len - 1.

From the Lab 4 directory, run:

cd problem-solving-1
make
./sum-all
make test

To try an input manually, enter the count and then the values on the next line. Press Enter after the values; you do not need to send EOF:

3
4 -2 7

The program should print 9.

Problem Solving Practice 2: Other Termination Conditions

Let’s explore another example that is a little less straightforward. What if we wanted to find the integer square root of a number $x$? Mathematically, we would write that as $\lfloor \sqrt{x}\rfloor$.

The starter code for this exercise is in problem-solving-2/. Open student.c and implement:

Aside

No, you can’t just always return floor(sqrt(x)), turns out sometimes precision issues arise and this isn’t always reliable.

So here’s an idea, can we keep testing numbers until we find the largest number $r$ whose square does not exceed $x$? So basically try numbers from $0$ and so on until we’re sure we’ve found $r$. (Yes this is purposely worded slightly vague. You’ll need to figure out the blanks.)

#include "student.h"
 
int int_sqrt(unsigned int x) {
	// Your code here
}

Figure out what kind of loop you need, what kind of termination condition you might want, the body of the loop, what to return.

Input: The program reads one unsigned integer x from standard input, between 0 and 4294967295 (UINT_MAX), inclusive.

Output: Print floor(sqrt(x)) as an integer followed by a newline. The returned type is int, so the largest possible answer is 65535. The supplied main reads the input and prints the value returned by int_sqrt; your int_sqrt function should return the answer and should not print anything. Be careful when testing r * r: an overflowing multiplication is not a valid way to compare with x. The starter driver accepts the full unsigned range, including values near UINT_MAX.

From the Lab 4 directory, run:

cd problem-solving-2
make
./int-sqrt
make test

To try an input manually, enter a value such as:

10

The program should print 3. Test 0, 1, 16, 17, and a value near 4294967295 as well.