Lab overview
Lab 01
Lab 02
Lab 03
Lab 04
Lab 05
Lab 06
Lab 07
Lab 08
Lab 09
Lab 10
Lab 11
Lab 12
Lab 13
Review

[Course home page]

CSC 209 lab 05 exercises, week of 7 June 2022

[solutions are available (requires teach.cs authentication)]

Attendance

As usual, please either run /u/csc209h/summer/present on the console of a lab workstation, or get the TA to record your attendance. Please do this first so that you don't forget.

Remember that you can check that your attendance has been recorded properly at https://wwwcgi.teach.cs.toronto.edu/~ajr/cgi-bin/auth/present


1. Makefile exercise

This part of the lab introduces the make command, a tool which builds software from source code, or performs any process which involves executing shell commands to bring files up to date with respect to other files.

make reads the file "Makefile" in the current directory, which tells it what to do to make the various files in that directory. For each target file, you list commands to create that file; and you also list the "dependencies", which are the files from which this file is built. Then if you edit a file and type "make", it checks which dependencies are newer than their targets (using the last-modified time of the file, or "mtime"), and executes the commands to (re-)build that file. All this will hopefully become clear with an example.

For this lab we will use the gcd.c separate-compilation example from lecture, in which we split up gcd.c into testgcd.c and gcd.c, with gcd.h to connect them.

See /u/csc209h/summer/pub/lab/05/make. Please create and cd to a new working directory of your own and do:

	cp /u/csc209h/summer/pub/lab/05/make/* .
	mv Makefile.partial Makefile

Makefile.partial (which you've now renamed to "Makefile") says:

	testgcd: testgcd.o gcd.o
		gcc -o testgcd testgcd.o gcd.o

The first line means that this recipe gives commands to create or re-create "testgcd". But it also says that before you can execute these commands, you need both testgcd.o and gcd.o. It further means that to bring testgcd up to date these commands will need to be re-run any time either testgcd.o or gcd.o change; and again, that you need to make sure that "testgcd.o" and "gcd.o" are up to date first before you run these commands to create or recreate testgcd. Later the files "testgcd.o" and "gcd.o" can each have their own recipes, and dependencies, all of which would need to be satisfied/executed first; there's a non-trivial "topological sort" algorithm in the 'make' program.

All that is just the first line. Next we have the commands (any number of them). How does make tell which line is the recipe header (with the dependencies) and which lines are the commands? The rule is: lines which are commands have to start with a tab. Not with an equivalent number of spaces; it has to be a tab. This is a bad file format design, but it's not quite horrible enough that we want to break compatibility by changing it at this date. So, tab it is.

Let's now tell it how to make testgcd.o, by appending further lines to that file. Normally we separate the recipes with a blank line. Then write:

        testgcd.o: testgcd.c gcd.h

This is because if either testgcd.c or gcd.h changes, testgcd.o should be re-made.

And then, indented by a tab (unlike the above line, which is not indented):

                gcc -Wall -c testgcd.c

The '−c' option means just compile to a .o file, not all the way to an a.out file. So the fact that testgcd.c calls gcd(), which is not defined in any of the files included in the above command-line, is fine for now. But the final "gcc −o testgcd testgcd.o gcd.o", which doesn't have a −c option, will put them all together; all needed functions must be included at that point.

Try typing "make" now. If there are syntax errors etc, fix them, then we'll say a bit more...

Actually 'make' knows by default that .o files depend on .c files by the same name, and how to rebuild them, so it managed to build gcd.o too, and get it all linked together. But we can do better in two ways: First of all, note that the gcc command it used doesn't have "−Wall" in it! Secondly, if we modify gcd.h, it won't know that this alone means that gcd.c needs to be recompiled; it will only recompile gcd.c if gcd.c itself is modified.

So let's improve this by writing a recipe for gcd.o the same as the testgcd.o one.

[do it and test it; sample solution in /u/csc209h/summer/pub/lab/05/makesoln/Makefile]

If you type "make", it builds the first thing mentioned in the file. Alternatively, you can type something like "make gcd.o" and it will do what it needs to do for just that.

Now, look at /u/csc209h/summer/pub/lab/05/makesoln/Makefile. Note the additional recipe at the end labelled "clean". There is no file named "clean". So, if you type "make clean", even though it doesn't list any dependencies, 'make' will see that it doesn't exist and will try to build it (by executing the commands listed). So this removes the automatically-generated files.

Copy that Makefile to your directory and try it (either renaming or overwriting your own). The '−f' option to rm means that rm won't complain if the files don't exist; try it by typing "make clean" a second time. Furthermore, 'make' checks the exit status of each command and stops if it hits an error, so if we don't want it to abort and print scary messages, we need the −f -- it's not only about avoiding an error message from rm, it's also about avoiding an error exit status from rm and hence a fatal error from make as well. Experiment with this by removing the "−f" and trying more "make"s and "make clean"s in various sequences.

There is a video about 'make' which discusses the above and goes on to explain other features of 'make' which you are likely to use soon.


2. printf formats

Printf has a fairly rich language for displaying the data it's formatting.

Right now we will look at the field width, and one particular "flag" you can use. For a fuller description of printf, see https://www.teach.cs.toronto.edu/~ajr/209/notes/printf.html

After the '%', we can put various possible flags, and we can put an optional width. Some of the flags go before the width and some after; the one we will look at right now, which is the digit '0', goes before (otherwise it would seem to change the width!).

Please see /u/csc209h/summer/pub/lab/05/part2.c
We have a value known as "dollars", and a value known as "cents", and we're trying to print them, together, in the usual way. Since dollars is 2 (here) and cents is 3, we want the output "$2.03".

Copy the program into your own directory, and compile and run it. It does not produce the desired output. (Why not?)

Add a field width of 2 for the cents. This is an improvement (try it).

Add the flag '0', while also listing the field width. This is the solution (try it). The '0' flag means to pad the field with zeroes instead of spaces.


3. Arrays and pointers

1. Write a function which does a linear search for an int in an array of ints. The arguments to the function should be the base pointer of the array, the size of the array, and the search object.
The return value is of type pointer-to-int. It is NULL if the item is not found.

An example use of this function (which you can compile with, or edit) can be found in /u/csc209h/summer/pub/lab/05/usepart3q1.c , which is modified from my lab 04 stats.c solution and calls its fillarray() to read a bunch of numbers, then calls your search function to find the number 42.

2. Modify the previous answer (really, my usepart3q1.c) to use pointer arithmetic to output which array index the number 42 was found at, rather than the number itself.

3. A similar main program can be found in /u/csc209h/summer/pub/lab/05/usepart3q3.c which just reads the array and then outputs it.
To this file, add a function which sorts the array, and add a call to your function inbetween fillarray() and printarray(). Since sorting algorithms aren't the point right now, use some very simple sort algorithm, such as perhaps bubblesort.

4. Lab 04's stats.c was intended to teach you how you can easily specify a sub-array in C:

So, starting with one of these programs or with /u/csc209h/summer/pub/lab/05/usepart3q4.c , write a function to sum an array recursively, using binary subdivision. This is not a good algorithm, but it's a good experiment with pointers.


4. Simple strings

1. Take the following code (available in /u/csc209h/summer/pub/lab/05/part4starter.c, or copy from this web page):
#include <stdio.h>

int main()
{
    char s[27];
    LOOP GOES HERE
    printf("%s\n", s);
    return(0);
}
and add a loop where indicated such that the program outputs "ABCDEFGHIJKLMNOPQRSTUVWXYZ" (without the quotes), without using any of the str* functions (e.g. strcpy). Just create the string 's' by setting the items in the array to the successive letters of the alphabet using a simple for loop by doing arithmetic on character values, and then setting s[26] to zero.

2. Given an int value between 10 and 99 inclusive (e.g. start your code with "int x = 38;" for a test), write code to convert this number to its string representation in a three-character array. The zeroth character of your string is the number div 10 + '0'; the next character of your string is the number mod 10 + '0'; and the array element two is the terminating zero. Note the difference between 0 and '0' (the latter is 48 in ASCII).


5. To submit: string processing

A "palindrome" is a coherent phrase which consists of the same letters and digits forwards and backwards, although the spacing and capitalization may be different (in fact, all non-alphanumeric characters are irrelevant). Some examples:
	Sator Arepo tenet opera rotas.
	Madam, I'm Adam.
	Won 12 tons?  Not 21 now.
	Doc, note: I dissent!  A fast never prevents a fatness.  I diet on cod.

Write a C program named "ispalindrome.c" which insists on having one argument (i.e. argc == 2). It checks its argument string to see whether it's a palindrome, and exits with exit status 0 if it is a palindrome, or 1 if it is not. Similar to the test program, there is no output, unless there is a usage error.

Remember that the alternate definition of main() begins like this:

        int main(int argc, char **argv)
	{

argv is an array of strings which include the command itself (argv[0]), then the command-line arguments (argv[1] and following). But how many string values are there? That's what the "argc" parameter is for. So in this case, you should insist that argc==2 (the command plus one argument), else print a usage message and exit (by returning 1 from main()).

So argv[1] will be the argument on the command-line which you're supposed to check whether or not it's a palindrome. Subsequent arguments aren't permitted; e.g. you have to type "./a.out 'won now'" and NOT "./a.out won now".

An example of using ispalindrome is in the "findpal" program in /u/csc209h/summer/pub/lab/05/findpal , the execution of which looks like this:

$ /u/csc209h/summer/pub/lab/05/findpal even odd or never
never odd or even
$ 
(but only after you complete your "ispalindrome"! You may have to copy and modify the 'findpal' shell script to get it to run your ispalindrome in the right location.)

Implementation technique for ispalindrome.c: Start a pointer-to-char at the beginning of the string and another pointer-to-char at the end of the string. (Find the end of the string with a simple linear search to find the zero byte. DO NOT COPY the string! Just use it in place in argv[1].) The pointer which started at the beginning of the string gets incremented and the pointer which started at the end of the string gets decremented, until they meet or pass.
So your loop will look something like "while (p < q)".

Note: Since this exercise is about strings and pointers, you must use this pointer strategy to get the point for the lab. That is to say, your access to a character in the string has to look more like "*p" than like "s[i]". (And "*(s+i)" doesn't count as the pointer strategy, that's the same as s[i] (by definition). You have to use a pointer variable which you are stepping through the string without indexing.)

Note relevant functions available after "#include <ctype.h>": isalnum(c) returns whether the character c is alphanumeric (you should skip all non-alphanumeric characters in making your comparison), and tolower(c) returns a lower-case version of the character c if it's an upper-case letter (e.g. tolower('E') returns 'e'), and returns the character itself otherwise (e.g. tolower('e') returns 'e', and tolower('2') returns '2').

Submit your program with

        submit -c csc209h -a lab05 ispalindrome.c
, by the end of Friday June 10. And no matter when you submit it, don't forget to run /u/csc209h/summer/present during the tutorial time, on the console of a tutorial lab workstation, or get the TA to record your attendance.

(Other 'submit' commands are described at the end of the notes for lab one.)

Your program must compile on the teach.cs machines with "gcc −Wall ispalindrome.c" with no errors or warning messages.


Q: Do we need to check argc and output a usage message?

A: Yes! Always! Insist that argc==2. And the usage message must be in the standard format, and to stderr, and you must exit with a non-zero exit status in case of error.