The University of New South Wales
Term 3, 2023
COMP1521: Computer Systems Fundamentals

22T3 Final Exam (practice)

— Friday 1 December 2023 —
10 questions — 100 marks
10 minutes reading; 3 hours working

Examination Information

Examination Instructions and Conditions

  • You can start reading the text of this examination when instructed to do so by your invigilator.

  • You can start working on examination questions when instructed to do so by your invigilator.

  • You must stop working on examination questions immediately when instructed to do so by your invigilator.

  • Only submissions made before this time will be marked.

    For students with approved examination extensions from UNSW Equitable Learning Services,
    You should continue working until your extended working time expires.

    Your invigilator will tell you when this time expires.

  • You must not communicate with any person during the examination
    except for COMP1521 Course Staff and Exam Invigilators.

  • You are not permitted to talk, email, telephone, message , etc. all
    except to COMP1521 Course Staff and Exam Invigilators.

  • You must not get help from anyone during this exam,
    except from COMP1521 Course Staff and Exam Invigilators.

  • You must not communicate (email, message, post, ...) your exam answers to anyone, even after the exam has finished.

    There are two sessions, so other students may still be taking the exam after you have finished.

    Additionally Some students have extended time to complete the exam.

    And some students may be taking the exam on a different day.

  • Communicating your answers to other students, even after the exam, may be academic misconduct.

  • You must ensure that, during and after the examination, no other person can access your work.

  • You must not use code-synthesis tools, such as GitHub Copilot, during this exam.

  • Your zPass should not be disclosed to any other person. If you have disclosed your zPass, you should change it immediately.

  • This is a closed-book examination.

  • You are not permitted to access papers, books, or any other written materials.

  • You are not permitted to access files on your computer or other computers, except the files provided by the exam.

  • You are not permitted to access web pages or other Internet resources, except the web pages provided by the exam, and the online language documentation linked below.

Deliberate violation of exam conditions is academic misconduct,
and will be referred to the UNSW Student Conduct and Integrity Unit.

Examination Structure

  • This examination has 10 questions,
    worth a total of 100 marks.
    Questions are worth equal marks.

  • All 10 questions are practical questions.

  • Not all questions may provide files. You should create any files needed for submission if they are not provided.

  • You must answer each question in a separate file. Each question specifies the name of the file to use. Make sure you use exactly this file name.

  • When you finish working on a question, you should submit your files using the give command specified in the question. You should not wait until the submission deadline to submit your answers. Running autotests does not automatically submit your code.

  • You do not receive additional time for submitting your answers.

    You must submit all questions before the end of the 3 hour exam period.

    Failing to logout immediately at the end of the exam period is academic misconduct.

  • You may submit as many times as you like; only the last submission will be marked.

  • You can verify what submissions you have made with 1521 classrun -check

Available Resources: Language Documentation

You may access this language documentation while attempting this test:

Troubleshooting

If you are having issues working on the exam:

  • Immediately inform your invigilator.

Fit-to-Sit

This exam is covered by UNSW's Fit-to-Sit policy. That means that, by sitting this exam, you are declaring yourself well enough to do so. You will be unable to apply for special consideration after the exam for circumstances affecting you before it began.

Getting Started

All provided files for this exam are located in your home directory.

simply open a terminal or text editor in your home directory and you will be able to access all the files.

If you make a mistake and need a new copy of a particular file, you can do the following:

rm broken-file
1521 fetch exam_22t3final

Only files that don't exist will be recreated. All other files will remain untouched.

Question 1 (10 marks)

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

Question 2 (10 marks)

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

Question 3 (10 marks)

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

Question 4 (10 marks)

Your task in this question is to find the length of the longest consecutive sequence of bits set to 1 in an integer.

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

Question 5 (10 marks)

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

Question 6 (10 marks)

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

Question 7 (10 marks)

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 😭?
Further example inputs are provided in the 22t3final_q7_examples/ directory.

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

make 22t3final_q7

A reminder of how UTF-8 is encoded:

#bytes #bits Byte 1 Byte 2 Byte 3 Byte 4
1 7 0xxxxxxx - - -
2 11 110xxxxx 10xxxxxx - -
3 16 1110xxxx 10xxxxxx 10xxxxxx -
4 21 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

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

Question 8 (10 marks)

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

Question 9 (10 marks)

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

Question 10 (10 marks)

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

Submission

When you are finished working on a question, submit your work by running give.

You can run give multiple times. Only your last submission will be marked.

Don't submit any questions you haven't attempted.

Do not leave it to the deadline to submit your answers.

Submit each question when you finish working on it.

Running autotests does not automatically submit your code.

— End of examination. —