22T3 Final Exam (practice)

You have been given 22t3final_q1.c, a stub of a C program.

Your task is to add code to this function in 22t3final_q1.c:

uint32_t _22t3final_q1(uint32_t x) {
    // ADD YOUR CODE HERE
    return 42;
}

Add code to the function _22t3final_q1 so that, given a uint32_t value, it returns the middle 8 bits of the numbers.

In other words, if we number the bit positions as usual 0..31 your function should return bits 12..19 as an unsigned integer between 0 and 255 (inclusive).

For example:

make 22t3final_q1
0 == 0x00000000 0x00 == 0
./22t3final_q1 0
0
make 22t3final_q1
42 == 0x0000003A 0x00 == 0
./22t3final_q1 42
0
270336 == 0x00042000 0x42 == 66
./22t3final_q1 270336
66
305419896 == 0x12345678 0x45 == 69
./22t3final_q1 305419896
69
4294967295 == 0xFFFFFFFF 0xFF == 255
./22t3final_q1 4294967295
255

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t3final_q1

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t3final_q1 22t3final_q1.c

To verify your submissions for this activity:

1521 classrun -check 22t3final_q1

You have been given 22t3final_q2.s, a MIPS assembler program that reads a number and then prints the number.

Add code to 22t3final_q2.s, so that it is equivalent to this C program:

// // // // // // // // DO NOT CHANGE THIS FILE! // // // // // // // //
// COMP1521 22T3 ... final exam, question 2
// Modify 22t3final_q2.s so that its behaviour
// matches the following C code.

#include <stdio.h>

int main(void) {
    int a, b;

    scanf("%d", &a);
    scanf("%d", &b);

    printf("%d\n", a * a + b * b);

    return 0;
}

In other words:

It should read two numbers and print the sum of their squares.

For example:

1521 mipsy 22t3final_q2.s
3
4
25
1521 mipsy 22t3final_q2.s
6
5
61
1521 mipsy 22t3final_q2.s
5
6
61
1521 mipsy 22t3final_q2.s
42
42
3528

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t3final_q2

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t3final_q2 22t3final_q2.s

To verify your submissions for this activity:

1521 classrun -check 22t3final_q2

You have been given 22t3final_q3.s, a MIPS assembler program that reads 1 number and then prints it.

Add code to 22t3final_q3.s to make it equivalent to this C program:

//  read numbers until their sum is >= 42, print their sum

#include <stdio.h>

int main(void) {
    int sum = 0;
    while (sum < 42) {
        int x;
        scanf("%d", &x);
        sum += x;
    }
    printf("%d\n", sum);
    return 0;
}

In other words, it should read numbers until their sum is ≥ 42 and then print their sum.

For example:

1521 mipsy 22t3final_q3.s
10
20
25
55
1521 mipsy 22t3final_q3.s
20
22
42
1521 mipsy 22t3final_q3.s
100
100
1521 mipsy 22t3final_q3.s
10
10
10
10
10
50

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t3final_q3

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t3final_q3 22t3final_q3.s

To verify your submissions for this activity:

1521 classrun -check 22t3final_q3

For example, in 305419896 == 0b00010010001101000101011001111000 the longest consecutive sequence of bits set to 1 is 4 long.

You have been given 22t3final_q4.c:

// COMP1521 22T3 ... final exam, question 4

#include <stdint.h>

int _22t3final_q4(uint32_t x) {
    // TODO: complete this function
    return 42;
}

Add code to the function _22t3final_q4 so that it counts and returns the length of the longest sequence of bits set to 1 in a 32-bit unsigned integer x.

For example:

make 22t3final_q4
305419896 == 0x12345678
./22t3final_q4 305419896
4
0 == 0x00000000
./22t3final_q4 0
0
4 == 0x00000004
./22t3final_q4 4
1
15 == 0x000000f
./22t3final_q4 15
4
4294967295 == 0xFFFFFFFF
./22t3final_q4 4294967295
32
2863311530 == 0xAAAAAAAA
./22t3final_q4 2863311530
1
268566401 == 0x1001FF81
./22t3final_q4 268566401
10

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t3final_q4

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t3final_q4 22t3final_q4.c

To verify your submissions for this activity:

1521 classrun -check 22t3final_q4

You have been given 22t3final_q5.s, a MIPS assembler program that reads an integer and then prints 42.

Add code to 22t3final_q5.s so that it returns the length of the longest sequence of consecutive bits set to 1 in the supplied 32 bit integer.

In other words, it should behave the same as the previous question.

mipsy input is signed, so it won't accept some of the input we used in the last question. For example, mipsy won't accept as 4294967295 as input. We can get the same bit pattern (0xFFFFFFFF) by using -1 as input. This doesn't affect the code you need to write.

For example:

305419896 == 0x12345678
1521 mipsy 22t3final_q5.s
305419896
4
0 == 0x00000000
1521 mipsy 22t3final_q5.s
0
0
4 == 0x00000004
1521 mipsy 22t3final_q5.s
4
1
15 == 0x0000000F
1521 mipsy 22t3final_q5.s
15
4
-1 == 0xFFFFFFFF
1521 mipsy 22t3final_q5.s
-1
32
-1431655766 == 0xAAAAAAAA
1521 mipsy 22t3final_q5.s
-1431655766
1
268566401 == 0x1001FF81
1521 mipsy 22t3final_q5.s
268566401
10

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t3final_q5

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t3final_q5 22t3final_q5.s

To verify your submissions for this activity:

1521 classrun -check 22t3final_q5

Write a C program, 22t3final_q6.c, which takes two arguments, a filename and an integer n.

Your program should delete the n-th line from the file.

Lines are numbered starting at 1.

If the file has less than n lines, your program should do nothing.

Your program should print nothing on stdout. It should only modify the file.

For example:

printf 'Hello\nhow\nare\nyou\n' > hello.txt
cat hello.txt
Hello
how
are
you
./22t3final_q6 hello.txt 3
cat hello.txt
Hello
how
you

printf 'I\nam\nreally great thank you\n' > answer.txt
cat answer.txt
I
am
really great thank you
./22t3final_q6 answer.txt 5
cat answer.txt
I
am
really great thank you
./22t3final_q6 answer.txt 1
cat answer.txt
am
really great thank you

seq 7 15 > numbers.txt
cat numbers.txt
7
8
9
10
11
12
13
14
15
./22t3final_q6 numbers.txt 5
cat numbers.txt
7
8
9
10
12
13
14
15

You can use make(1) to build your code:

make 22t3final_q6

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t3final_q6

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t3final_q6 22t3final_q6.c

To verify your submissions for this activity:

1521 classrun -check 22t3final_q6

You have been given 22t3final_q7.c, which contains a C function _22t3final_q7, that takes a string, and returns it unmodified.

Add code to the function _22t3final_q7 so that, given a UTF-8 encoded string, it returns a new string that has any invalid UTF-8 sequences replaced with the character '?'.

For example:

xxd 22t3final_q7_examples/hello_world.txt
00000000: 6865 6c6c 6f20 776f 726c 64              hello world
./22t3final_q7 < 22t3final_q7_examples/hello_world.txt
hello world
xxd 22t3final_q7_examples/bad_hello_world.txt
00000000: 6865 6c6c 6fa1 776f 726c 64              hello.world
./22t3final_q7 < 22t3final_q7_examples/bad_hello_world.txt
hello?world
xxd 22t3final_q7_examples/valid_with_emoji.txt
00000000: 796f 7520 6172 6520 646f 696e 6720 6772  you are doing gr
00000010: 6561 7420 f09f 918d f09f 918d f09f 918d  eat ............
./22t3final_q7 < 22t3final_q7_examples/valid_with_emoji.txt
you are doing great 👍👍👍
xxd 22t3final_q7_examples/invalid_with_emoji.txt
00000000: 7468 6973 f0a1 3923 7374 7269 6e67 a269  this..9#string.i
00000010: 73e7 8936 6e6f 74a0 646f 696e 67c2 c273  s..6not.doing..s
00000020: 6fa0 6772 6561 74f1 3242 a068 6f77 6576  o.great.2B.howev
00000030: 6572 20f0 9f98 ad91                      er .....
./22t3final_q7 < 22t3final_q7_examples/invalid_with_emoji.txt
this?string?is?not?doing?so?great?however 😭?

You can use make(1) to build your code:

make 22t3final_q7

A reminder of how UTF-8 is encoded:

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t3final_q7

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t3final_q7 22t3final_q7.c

To verify your submissions for this activity:

1521 classrun -check 22t3final_q7

You have been given 22t3final_q8.s, a MIPS assembler program that reads a line of input and then prints 'T' on a new line.

Add code to 22t3final_q8.s to make it equivalent to this C program:

// // // // // // // // DO NOT CHANGE THIS FILE! // // // // // // // //
// COMP1521 22T3 ... final exam, question 8
// Modify 22t3final_q8.s so that its behaviour
// matches the following C code.


#include <stdio.h>

char *s;

int expression(void);
int term(void);
int value(void);

int main(void) {
    char buffer[10000];
    fgets(buffer, 10000, stdin);
    s = buffer;

    if (expression()) {
        printf("T\n");
    } else {
        printf("F\n");
    }

    return 0;
}

int expression(void) {
    int lhs = term();
    if (*s != '|') {
        return lhs;
    }
    s++;
    int rhs = expression();
    return lhs || rhs;
}

int term(void) {
    int lhs = value();
    if (*s != '&') {
        return lhs;
    }
    s++;
    int rhs = term();
    return lhs && rhs;
}

int value(void) {
    int retval = *s == 'T';
    s++;
    return retval;
}

The above C program reads a line of input containing a boolean expression, and evaluates it.

The boolean expression only contains the characters 'T', 'F', representing true and false respectively, and the operators '&' and '|', representing the logical AND and OR operators.

For example:

1521 mipsy 22t3final_q8.s
T&F
F
1521 mipsy 22t3final_q8.s
T|F
T
1521 mipsy 22t3final_q8.s
F|T&F
F

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t3final_q8

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t3final_q8 22t3final_q8.s

To verify your submissions for this activity:

1521 classrun -check 22t3final_q8

In Sydney, all train carriages have a unique numeric identifier.

A popular game amongst Sydney train commuters is to find some arrangement of the numbers, and four mathematical operators (+, -, *, /) inserted between them, such that the expression evaluates to the number 10.

For the purposes of this question, we will assume that there are five digits, and that each operator is used exactly once. From this, we then have 2880 possible expressions to evaluate. For simplicity, we will also evaluate the expression left to right, without order of operations.

You have been given 22t3final_q9.c, a C program that is supplied with a file containing all 2880 possible expressions (one per line) for a given five-digit value as a command line argument. At the moment, the program prints out the number of different expressions that evaluate to 10, but only uses a single thread.

Your task is to modify 22t3final_q9.c so that it creates five new threads to evenly split the work and evaluate the expressions in parallel. Your modifications must not use any global variables, and must not use any locks or mutexes. You should instead pass data to the thread, and return data as needed.

Your program must also not load the entire file into memory. Instead, it should read the file line by line.

Each byte of the file should not be read more than once. You may find it useful to have a file descriptor open for each thread, and to use the fseek library call.

We have provided you with the files 22t3final_q9.h, to provide you with some information about functions you may find useful, and 22t3final_q9_main.c, which contains a main function to help you test your code, as well as evaluate expressions. You should not modify these files.

Once complete, the output of your program should look something like this:

make
dcc -pthreads    22t3final_q9.c 22t3final_q9_main.c   -o 22t3final_q9
./22t3final_q9 22t3final_q9_examples/15211.txt
Hello from compute thread 0!
Hello from compute thread 1!
Hello from compute thread 2!
Hello from compute thread 3!
Hello from compute thread 4!
288 results found!
Your program created enough threads!
./22t3final_q9 22t3final_q9_examples/54321.txt
Hello from compute thread 0!
Hello from compute thread 1!
Hello from compute thread 2!
Hello from compute thread 3!
Hello from compute thread 4!
32 results found!
Your program created enough threads!
./22t3final_q9 22t3final_q9_examples/69913.txt
Hello from compute thread 0!
Hello from compute thread 1!
Hello from compute thread 2!
Hello from compute thread 3!
Hello from compute thread 4!
62 results found!
Your program created enough threads!

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t3final_q9

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t3final_q9 22t3final_q9.c

To verify your submissions for this activity:

1521 classrun -check 22t3final_q9

You have been given 22t3final_q10.s, a MIPS assembler program that reads a line of input and then prints 42.

Add code to 22t3final_q10.s to evaluate the line as an arithmetic expression. and print its value.

The arithmetic expression will contain only positive integers addition ('+') operator and multiply ('*') operators.

The integers may be arbitrarily large; except they must fit on a line of less than 10,000 characters.

Partial marks will be given for solutions which handle only only positive integers and addition but not multiplication.

There are no marks for approaches which handle only smaller integers; for example, those small enough to be represented in only 32 or 64 bits and stored in a register.

There are no marks for approaches which use floating point arithmetic or other methods to produce approximate results.

For example:

1521 mipsy 22t3final_q10.s
982451653*961748941*472882027*452390477
202133905243937086663174722891174767
1521 mipsy 22t3final_q10.s
2*100000000000000000000000000000000000000000000000000000000000000000000000000+3*4
200000000000000000000000000000000000000000000000000000000000000000000000012

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t3final_q10

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t3final_q10 22t3final_q10.s

To verify your submissions for this activity:

1521 classrun -check 22t3final_q10