COMP1511 17s1 Introduction to Programming

Your tutor has asked a lab pair to present their week 5 work.

Discuss the good, the bad and the ugly aspects of their code.

Please be gentle in any criticism - we are all learning!

1. Did you blog last week? What is this week's blogging theme?
1. Encode and decode a message with a Caesar cipher.
2. The shift is the key for a Caesar Cipher - how many bits are in it?
25 possible shifts log2(25) = ~4.6 bits
3. How would you crack a Caesar Cipher?
Brute force - try all shifts
4. Encode and decode a message with a Substitution cipher.
5. The letter mapping is the key for a Substitution cipher - how many bits are in it?
factorial 26 orderings log2(26!) = ~88 bits
6. How would you crack a Substitution Cipher (assume the plain text is English)?
Use the differing frequency of English letters and differing probability of pairs of letters or words.
2. Write a program `sum_digits.c` which reads characters from its input and counts digits.

When the end of input is reached it should print a count of how many digits occured in its input and their sum.

The only functions you can use are `getchar` and `printf`.

For example:

```./sum_digits
1 2 3 o'clock
4 o'clock rock
Input contained 4 digits which summed to 10
./sum_digits
12 twelve 24 twenty four
thirty six 36
Input contained 6 digits which summed to 18
```
Sample solution for `sum_digits.c`
```#include <stdio.h>

int
main(void) {
int c;
int digitCount, digitSum, digitValue;

digitCount = 0;
digitSum = 0;

// getchar returns an int which will contain either
// the ASCII code of the character read or EOF

c = getchar();
while (c != EOF) {

// test if ch is digit, isdigit would be better
if (c >= '0' && c <= '9') {
digitCount = digitCount + 1;
digitValue = c - '0';
digitSum = digitSum + digitValue;
}

c = getchar();
}
printf("Input contained %d digits which summed to %d\n", digitCount, digitSum);
return 0;
}

```
3. Write a program `letter_triangle.c` that read an positive integer n and outputs a triangle of letters of height n as below. For example:
```./letter_triangle
Enter height: 3
A
BCB
DEFED
./letter_triangle
Enter height: 7
A
BCB
DEFED
GHIJIHG
KLMNONMLK
PQRSTUTSRQP
VWXYZABAZYXWV
./letter_triangle
Enter height: 10
A
BCB
DEFED
GHIJIHG
KLMNONMLK
PQRSTUTSRQP
VWXYZABAZYXWV
CDEFGHIJIHGFEDC
KLMNOPQRSRQPONMLK
TUVWXYZABCBAZYXWVUT
```
Sample solution for `letter_triangle.c`
```
// Description: Prompts the user for a strictly positive number N
//              and outputs an equilateral triangle of height N.
//              The top of the triangle (line 1) is labeled with the letter A.
//              For all nonzero p < N, line p + 1 of the triangle is labeled
//              with letters that go up in alphabetical order modulo 26
//              from the beginning of the line to the middle of the line,
//              starting wth the letter that comes next in alphabetical order
//              modulo 26 to the letter in the middle of line p,
//              and then down in alphabetical order modulo 26
//              from the middle of the line to the end of the line.
//
// Written by Eric Martin for COMP9021
// modified by Andrew Taylor for 1911

#include <stdio.h>

int main(void) {
int ch, i, j, k;
int height = 0;

printf("Enter height: ");
scanf("%d", &height);

ch = 'A';
i = 1;
while (i <= height) {

/* Displays spaces on the left */
j = 0;
while (j < height - i) {
printf(" ");
j = j + 1;
}

/* Displays letters before middle column */
k = 1;
while (k < i) {
putchar(ch);

/* code of next letter */
ch = (ch - 'A' + 1) % 26 + 'A';
k = k + 1;
}

/* Displays middle column */
putchar(ch);

/* Displays letters after middle column */
k = 1;
while (k < i) {

/* Code of previous letter */
ch = (ch - 'A' + 25) % 26 + 'A';
putchar(ch);
k = k + 1;
}
printf("\n");

/* Code of first letter to be input on next line */
ch = ((1 + i) * i / 2) % 26 + 'A';
i = i + 1;
}

return 0;
}

```
4. Write a program `input_statistics.c` that for the characters provided on standard input.:
• outputs the number of white-space characters (spaces, tabs and new lines)
• outputs the numbers of words word (any contiguous sequence of non-white-space characters), and
• outputs the length of the shortest word
• outputs the length of the longest word

For example:

```./input_statistics
"Beauty is truth, truth beauty," -- that is all
Ye know on earth, and all ye need to know.
Input contains 27 blanks, tabs and new lines
Number of words: 19
Length of shortest word: 2
Length of longest word: 8
./input_statistics
And here is another example with only one line of input!!!!!!!!!
Input contains 11 blanks, tabs and new lines
Number of words: 11
Length of shortest word: 2
Length of longest word: 14
```
Sample solution for `input_statistics.c`
```/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Description: Outputs                                                        *
*              - the number of blank characters (spaces, tabs and new lines)  *
*              - the length of the shortest word                              *
*                (any sequence of nonblank characters), and                   *
*              - the length of the longest word                               *
*                (any sequence of nonblank characters)                        *
*              read from standard input.                                      *
*                                                                             *
* Written by Eric Martin for COMP9021                                         *
* Modified by Andrew Taylor for COMP9021                                         *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#include <stdio.h>

int main(void) {
int whiteSpaceCount;
int wordMinLength, wordMaxLength, wordCurrentLength;
int wordCount;
int ch;

wordCount = 0;
whiteSpaceCount = 0;
wordCurrentLength = 0;

ch = getchar();
while (ch != EOF) {

// iswhite would be better here
if (ch == ' ' || ch == '\t' || ch == '\n') {

whiteSpaceCount = whiteSpaceCount + 1;

// A complete word has just been read iff wordCurrentLength > 0,
// which is then the length of that word.

if (wordCurrentLength > 0) {
if (wordCount == 0) {
wordMinLength = wordCurrentLength;
} else if (wordCurrentLength < wordMinLength) {
wordMinLength = wordCurrentLength;
} else if (wordCurrentLength > wordMaxLength) {
wordMaxLength = wordCurrentLength;
}

wordCurrentLength = 0;
wordCount = wordCount + 1;
}
} else {
wordCurrentLength = wordCurrentLength + 1;
}
ch = getchar();
}

printf("Input contains %d blanks, tabs and new lines\n", whiteSpaceCount);

if (wordCount == 0) {
printf("No word has been input\n");
} else {
printf("Number of words: %d\n", wordCount);
printf("Length of shortest word: %d\n", wordMinLength);
printf("Length of longest word: %d\n", wordMaxLength);
}

return 0;
}

```
5. ```#include <stdio.h>

int main(void) {
char str;
str = 'H';
str = 'i';
printf("%s", str);
return 0;
}
```
1. What will happen when the above program is compiled?
The above program will compile without errors . `printf`, like many C library functions expects strings to be null-terminated.

In other words `printf`, expects the array `str` to contain an element with value 0 (also writen '\0') which marks the end of the sequence of characters to be printed.

`printf` will print `str` ('H'), `str` then examine `str`.

Code produced by `dcc --valgrind` will then stop with an error because `str` is uninitialized.

The code with gcc will keep executing and printing element from `str` until it encounters one containing '\0'. Often `str` will by chance contain '\0' and the program will work correctly.

Another common behaviour will be that the program prints some extra "random" characters.

It is also possible the program will index outside the array which would result in it stopping with an error if it was compiled with `dcc`.

If the program was compiled with gcc and uses indices well outside the array it may be terminated by the the operating system because of an illegal memory access.

2. How do you correct the program?
```#include <stdio.h>

int main(void) {
char str;
str = 'H';
str = 'i';
str = '\0';
printf("%s", str);
return 0;
}
```

### Revision questions

The remaining tutorial questions are primarily intended for revision - either this week or later in session.

Your tutor may still choose to cover some of the questions time permitting.

6. How many ints can the array `matrix` below hold?
```#include <stdio.h>

#define N_ROWS 12
#define N_COLUMNS 15

int main(void) {
int matrix[N_ROWS][N_COLUMNS];
```
Write nested for loops that sets every element of `matrix`. Each element should be set to the product of its two indices.

Write nested for loops that print the elements of `matrix` plus sums of each row and sums of each column.

The output of your code should look like this:

```a.out
0    0    0    0    0    0    0    0    0    0    0    0    0    0    0 |    0
0    1    2    3    4    5    6    7    8    9   10   11   12   13   14 |  105
0    2    4    6    8   10   12   14   16   18   20   22   24   26   28 |  210
0    3    6    9   12   15   18   21   24   27   30   33   36   39   42 |  315
0    4    8   12   16   20   24   28   32   36   40   44   48   52   56 |  420
0    5   10   15   20   25   30   35   40   45   50   55   60   65   70 |  525
0    6   12   18   24   30   36   42   48   54   60   66   72   78   84 |  630
0    7   14   21   28   35   42   49   56   63   70   77   84   91   98 |  735
0    8   16   24   32   40   48   56   64   72   80   88   96  104  112 |  840
0    9   18   27   36   45   54   63   72   81   90   99  108  117  126 |  945
0   10   20   30   40   50   60   70   80   90  100  110  120  130  140 | 1050
0   11   22   33   44   55   66   77   88   99  110  121  132  143  154 | 1155
---------------------------------------------------------------------------
0   66  132  198  264  330  396  462  528  594  660  726  792  858  924
```
Sample solution
```#include <stdio.h>

#define N_ROWS 12
#define N_COLUMNS 15

int main(void) {
int matrix[N_ROWS][N_COLUMNS];
int row, column, rowSum, columnSum;
row = 0;
while (row < N_ROWS) {
column = 0;
while (column < N_COLUMNS) {
matrix[row][column] = row * column;
row = row + 1;
}
column = column + 1;
}

row = 0;
while (row < N_ROWS) {
rowSum = 0;
column = 0;
while (column < N_COLUMNS) {
printf(" %4d", matrix[row][column]);
rowSum = rowSum + matrix[row][column];
column = column + 1;
}
row = row + 1;
printf(" | %4d\n", rowSum);
}

for (column = 0; column < N_COLUMNS; column = column + 1) {
printf("-----");
}
printf("\n");
column = 0;
while (column < N_COLUMNS) {
columnSum = 0;
row = 0;
while (row < N_ROWS) {
columnSum = columnSum + matrix[row][column];
row = row + 1;
}
printf(" %4d", columnSum);
column = column + 1;
}
printf("\n");

return 0;
}

```
7. A student has written this program to read ints until the end-of-input. It counts how many numbers it reads categorized by their last digit:
```#include <stdio.h>

#define N 10

int main(void) {
int digitCount[N];
int x, lastDigit;

while (scanf("%d", &x) == 1) {
lastDigit = x % N;
digitCount[lastDigit] = digitCount[lastDigit] + 1;
}
lastDigit = 0;
while (lastDigit < N) {
printf("%d numbers with last digit %d read\n", digitCount[lastDigit], lastDigit);
lastDigit = lastDigit + 1;
}

return 0;
}

```
It works on the students laptop:
```gcc -Wall -O last_digit.c
a.out
42 121 100 11
<cntrl-d>
1 numbers with last digit 0 read
2 numbers with last digit 1 read
1 numbers with last digit 2 read
0 numbers with last digit 3 read
0 numbers with last digit 4 read
0 numbers with last digit 5 read
0 numbers with last digit 6 read
0 numbers with last digit 7 read
0 numbers with last digit 8 read
1 numbers with last digit 9 read

```
print counts of how many numbers read.

But when run at uni fails

```dcc last_digit.c
a.out
42 121 100 11
<cntrl-d>
778121076 numbers with last digit 0 read
7632239 numbers with last digit 1 read
-2032569224 numbers with last digit 2 read
32727 numbers with last digit 3 read
0 numbers with last digit 4 read
0 numbers with last digit 5 read
-2032409578 numbers with last digit 6 read
32727 numbers with last digit 7 read
-21600000 numbers with last digit 8 read
32767 numbers with last digit 9 read

```
Why doesn't the code work at uni .

Why doesn't `dcc` detect an error?

The student had not initialized array `digitCount`.

Their program used values elements of `digitCount` which had not previously had values stored in them.

This is illegal C and can hence produce *any* output.

On the student's laptop by chance the bytes used for the array already had zeros in them. This is not uncommon and leads to illegal C seeming to be correct. But changing compiler flags, machine, or even time of day can affect this.

`dcc` checks (among other things) that array indices are valid but doesn't check that array elements have been initialized.

`dcc --valgrind` checks that array elements have been initialized (but not that indices are valid)

The student's program can be fixed by adding a for loop to initialize the elements of the array digitCount to 0.

A less obvious problem is that entering a negative number will produce an (illegal) negative array index (also fixed below).

Fix the code (make sure you understand how it works - its an common & useful programming pattern).

Sample solution
```#include <stdio.h>

#define N 10

int main(void) {
int digitCount[N];
int x, lastDigit;

lastDigit = 0;
while (lastDigit < N) {
digitCount[lastDigit] = 0;
lastDigit = lastDigit + 1;
}

while (scanf("%d", &x) == 1) {
lastDigit = x % N;
if (lastDigit < 0) {
lastDigit = - lastDigit;
}
digitCount[lastDigit] = digitCount[lastDigit] + 1;
}

lastDigit = 0;
while (lastDigit < N) {
printf("%d numbers with last digit %d read\n", digitCount[lastDigit], lastDigit);
lastDigit = lastDigit + 1;
}

return 0;
}

```
1. What is the effect of each of the following statements? What are the initial values in the arrays?
```int nums1;
```
Creates an array of 10 integers without any initialisation. Each element will contain undefined values.
```int nums2[] = {0,1,2,3,4,5,6,7,8,9};
```
Ccreates an array of 10 integers, and initialises the array with the given numbers.
```int nums3 = {0,2,4,6,8,-2};
```
Creates an array of 10 integers, and initialises the first six elements with the given numbers and the rest with 0's.
```int nums4 = {0};
```
Creates an array of 10 integers, and initialises the array with ten 0's
```int nums5 = {{0,1,2,3,4,5,6,7,8,9},
{10,20,30,40,50,60,70,80,90,100}};
```
Creates a 2 dimensional array of size 2x10. You can think of it as having 2 rows and 10 columns. The array at `nums5` contains 0,1,2,3,4,5,6,7,8,9. The array at `nums5` contains 10,20,30,40,50,60,70,80,90,100
8. What would the output of the following fragment of code be - given the array definitions above?
```int i;
printf("%d\n",nums2);  prints 3
printf("%d\n",nums3);  prints -2
printf("%d\n",nums5);  prints 1
printf("%d\n",nums5);  prints 10
nums1 = nums2 + 10 ;
printf("%d\n",nums1);     prints 11
i = 0;
printf("%d\n",nums1[i]);     prints 11
```
9. What is wrong with the following piece of code - given the above array definitions?
```printf("%d\n",nums2);    This is an error.
The indexes in nums2 go from 0..9.
By using an index of 10 we are trying to go past the end of the array

printf("%d\n",nums5); This is an error.
The first index in nums5 goes from 0..1.
By using an index of 2 we are trying to go past the end of the array

printf("%d\n",nums5); This is an error.
The second index in nums5 goes from 0..9.
By using index of 10 we are trying to go past the end of the array

```
10. Strlen is a function that returns the length of a string. Write your own C function to do the same.
```        int myStrlen(char *string);
```
The key part to the question is knowing that a string has a nul terminator character "\0" to note the end of the string. You simply loop until you come across that character.
11. Write a C function that is given two strings and returns 1 if they are both equal and 0 otherwise. This is a simplified version of strcmp, provided in the C library. Try writing one yourself.
```        int myStrCmp(char *string1, char *string2);
```
Remember that strings are just arrays of characters. The end of the string has the special nul terminator. The tricky part with this question is dealing with strings of uneven lengths.
12. Write a C function that is given two strings and returns 1 if the first begins with the second (and 0 otherwise). For example, "APPLE" begins with "APP".
```        int beginsWith(char *string1, char *string2);
```
This is similar to doing the string compare, but you need to be careful of the uneven lengths as well. Eg: What happens if the first string is longer than the second?
13. Write a C function that is given two strings and returns 1 if the first is a substring of the second (and 0 otherwise). For example, "APP", "E", "PL" are all substrings of "APPLE".
```        int isSubstring(char *substring, char *string);
```
This is a bit harder, because unlike beginsWith, you don't know where the substring can start. The simplest method would be to go through the string, and attempt to do soemthing like beginsWith from each character. Be very careful about going beyound the bounds of the array.