Homework 7 - Starting with C

From now on, we’ll assume that you work on homework by connecting to the CS portal and that you are familiar with the command line environment. If you have not been practicing with the terminal, we strongly encourage reviewing Lab 1.

We will also assume that you ran the setup script from that lab and have all modules (including clang and git) by default.

For this homework, you’ll be editing a file named homework7.c and implementing at least five of the following six functions. You should copy our initial version of that file into your cso1-code directory by using the cd command to enter cso1-code and then copying the file in with the following command:

cp /p/cso1/homework/homework7.c .

No function you write in this file should invoke a function you did not write.

When you submit do not remove our comments in the file. You are strongly encouraged to update the main method for testing purposes, but we will replace it when running your code. Note: there are limited submissions available for Gradescope.

Writing your code

For this and future assignments, we are expecting that you will write your code using the portal. If you need to refresh, please review Lab 1. Feel free to use whatever editor you like (nano, vim, VSCode, etc.). If you are not yet comfortable with the terminal, you may find it helpful to use a command line editor.

Why a CLI editor?

It is common to interact with servers that do not have their own monitors. In these cases, you typically attach to the server via ssh and have access only to a terminal, not a full windowing environment. The more comfortable you are with doing common programming tasks in the terminal, the better these experiences will be.

Functions

Implement five of the following six functions:

Titlecase

void titlecase(char *s);

Write a function with the above signature that converts any lower-case letters preceded by a space in s into upper-case letters.

You did something like this in Lab 2.

Example: The following usage code

char *s = strdup(" the book \"the C programming language.\"");
printf("before: %s\n", s);
titlecase(s);
printf("after:  %s\n", s);
free(s);

will display

before:  the book "the C programming language."
after:   The Book "the C Programming Language."

Tip: test this with empty strings, strings with digits and punctuation in them, etc.

Fibonacci Array

void fibarray(unsigned short *dest, unsigned num);

Write a function with the above signature that places the first num fibonacci numbers (modulo 65536, since the array stores only 2-byte values) into dest.

You implemented something very like this in Lab 5. Unlike Lab 5, however, your code must work for any location and number of values requested.

Example: The following usage code

unsigned short a[64];
fibarray(a, 64);
for (int row=0; row<8; row+=1) {
    for (int col=0; col<8; col+=1) {
        printf(" %04hx", a[row*8 + col]);
    }
    printf("\n");
}

will display

0001 0001 0002 0003 0005 0008 000d 0015
0022 0037 0059 0090 00e9 0179 0262 03db
063d 0a18 1055 1a6d 2ac2 452f 6ff1 b520
2511 da31 ff42 d973 d8b5 b228 8add 3d05
c7e2 04e7 ccc9 d1b0 9e79 7029 0ea2 7ecb
8d6d 0c38 99a5 a5dd 3f82 e55f 24e1 0a40
2f21 3961 6882 a1e3 0a65 ac48 b6ad 62f5
19a2 7c97 9639 12d0 a909 bbd9 64e2 20bb

Tip: test this with 0- and 1-entry arrays as well as larger ones, and make sure you don’t set more values of the array than the requested num.

Recursive Power

long recpow(long x, unsigned char e);

Write a function with the above signature that computes and returns x^e. You must implement this recursively, not iteratively (do not use for, while, do, or goto).

Your code must work for any x (including negative and zero) and any e (including zero).

Example: The following usage code

long x = -21;
unsigned char e = 13;
long ans = recpow(x, e);
printf("%ld\n", ans);
printf("%ld\n", recpow(11, 0));

will display

-154472377739119461
1

Tip: test with both negative and positive x and both even and odd e.

Next Prime

unsigned long nextprime(unsigned long x);

Write a function with the above signature that returns the smallest prime number larger than x.

Example: The following usage code

long x = 100;
for (int i=0; i<10; i+=1) {
    x = nextprime(x);
    printf("%ld\n", x);
}
printf("%ld\n", nextprime(1000000000000));

will display

101
103
107
109
113
127
131
137
139
149
1000000000039

Note: if your code is not very efficient, the last number might not appear for so long you lose patience waiting for it. That’s OK; we’ll only test with inputs that end in a reasonable time.

Tip: A number x is prime if and only if it is 2, or it is odd and is not a multiple of any odd number between 3 and √x.

Tip: Make sure you test with the arguments 0, 1, and 2.

You implemented something similar to this in Homework 5. Unlike Homework 5, however, your code is looking for the next prime number.

Pull Zeros

void pull0(int *arr, unsigned length);

Rearrange the first length values of arr in place, such that all of its zero values appear first, followed by its non-zero values in their original order.

Example: The following usage code

int x[] = {1, 7, 3, 2, 0, 5, 0, 8, 0, 7, 5, 6, 8, 8, 7, 7, 2, 9};
for (int i=0; i<18; i+=1) printf("%d ", x[i]); printf("\n");
pull0(x, 15);
for (int i=0; i<18; i+=1) printf("%d ", x[i]); printf("\n");

will display

1 7 3 2 0 5 0 8 0 7 5 6 8 8 7 7 2 9
0 0 0 1 7 3 2 5 8 7 5 6 8 8 7 7 2 9

Tip: Test this with both arrays that do and do not include zeros.

Find Non-duplicated Element

int nondup(int *arr, unsigned length);

Assume that arr’s first length elements contains exactly two copies of each value it contains, except one value it has only once. Return that one non-duplicated element.

If the array does not have a unique non-duplicated element, the behavior of nondup is undefined.

Example: The following usage code

int x[] = {28, 12, 8, 0, 0, 28, 8};
printf("%d\n", nondup(x, 7));
printf("%d\n", nondup(x + 2, 5));

will display

12
28

Tip: There are (at least) two very different solution approaches: one with nested loops and another using xor.

Grading

For this assignment, the grade will consist of an autograded component (for correctness). The breakdown is as follows:

100% code correctness (passing Gradescope tests)

Submission

Submit your code on Gradescope. You may only submit a maximum of 15 times to the autograder, so you should test your code extensively by calling your functions in main(). After the 15th attempt, Gradescope will accept submissions, but the autograder will not run; Gradescope will only report the score of the 15th attempt.

Note: The submission site will be available beginning on Wednesday.