Foundations of Algorithms (COMP10002_2020_SM1)

Quiz Instructions

Link to technical support for the exam (https://students.unimelb.edu.au/your-course/manage-your-course/exams-assessments-and-results/exams/technical-support)

Number of questions: 5

Authorised Materials:

You are allowed to refer to any study materials. However, you may NOT:

● accept or request help from any other person.

● act in any manner that could be regarded as providing assistance to another student who is undertaking this assessment, or will in the future be undertaking this assessment.

What gets typed into your answer must be your own individual work.

Instructions to Students:

● Once submitted, you will NOT be able to reopen the quiz to change your answers. This means that you will be able to click the "Submit" button ONLY once.

● Answer all questions.

● You are not required to write comments except when you are explicitly asked to. If a question says "write a function", you may write further relevant functions if you believe that a decomposition of the problem is appropriate.

● You may make use of library functions except when their use is explicitly prohibited. If you do make use of library functions, you must add suitable #include lines at the start of each corresponding answer.

● Constants should be #define'd prior to use, when appropriate.

Academic Integrity Declaration

By commencing and/or submitting this assessment I agree that I have read and understood the University’s policy on academic integrity. (https://academicintegrity.unimelb.edu.au/)

I also agree that:

1. Unless paragraph 2 applies, the work I submit will be original and solely my own work (cheating);

2. I will not seek or receive any assistance from any other person (collusion) except where the work is for a designated collaborative task, in which case the individual contributions will be indicated; and,

3. I will not use any sources without proper acknowledgment or referencing (plagiarism).

4. Where the work I submit is a computer program or code, I will ensure that:

a. any code I have copied is clearly noted by identifying the source of that code at the start of the program or in a header file or, that comments inline identify the start and end of the copied code; and

b. any modifications to code sourced from elsewhere will be commented upon to show the nature of the modification.

This exam begins at 9.00 AM Australian Eastern Standard Time (AEST) on Tuesday 30/06/2020 in Canvas (lms.unimelb.edu.au). The exam must be completed by 10.00 AM AEST on Tuesday 30/06/2020. This exam has 60 minutes of writing time.

Question 1

A credit card transaction record is represented by a struct type named trans_t defined as follows:

#define TANS_ID_LEN 12

#define CARD_ID_LEN 8

typedef struct {

int year, month, day; /* the year, month, and day of a transaction */

} date_t;

typedef struct {

char id[TANS_ID_LEN+1]; /* transaction ID: 12 alphanumeric characters;

no uppercase letters */

char card_id[CARD_ID_LEN+1]; /* card ID: 8 alphanumeric characters; no

uppercase letters */

date_t date; /* transaction date */

int amount; /* the amount spent in a transaction: a positive integer */

} trans_t;

Write a function

int trans_comp(void *trans1, void *trans2);

that compares two transaction records pointed to by trans1 and trans2 using their transaction IDs in alphabetical order:Quiz:

● If the id of the transaction record pointed to by trans1 is smaller than the id of the transaction record pointed to by trans2, the function should return -1;

● If the id of the transaction record pointed to by trans1 is larger than the id of the transaction record pointed to by trans2, the function should return 1;

● If either trans1 or trans2 is NULL, the function should return 0;

● You may assume that the ids of the two transaction records will not be the same.

● You may NOT use any library function in your answer to this question.

For example:

● If trans1 points to {"mlgtqk8oo74e", "ceww0p66", {2020, 5, 15}, 90} and trans2 points to {"u7s604f0u6bz", "xnwxw8tl", {2020, 6, 22}, 50}, the function should return -1;

● If trans1 points to {"mlgtqk8oo74e", "ceww0p66", {2020, 5, 15}, 90} and trans2 points to {"6hjqaydtmrq5", "vb3dtxp0", {2020, 5, 15}, 20}, the function should return 1.

Instructions on how to enter code in the answer box (also applies to the other coding questions):

The following instructions intend to make entering code easier. You may ignore these and simply enter code in the answer box. Code formatting and indentation will not be marked.

Click the "Paragraph" button below and choose the "Preformatted" option. Then, continue with any of the following options:

● Option A: Type your answer in the answer box directly, and use whitespaces for indentation.

● Option B: Write code in Grok/jEdit/any other code editor. Paste your answer back to the answer box when you are done.

○ The indentation may get lost. No need to worry about it. If you want to fix the indentation, select all code that you just pasted in the answer box, click the "Paragraph" button and choose "Preformatted" again. If this does not fix it, ignore the indentation and move on to the other questions.

● Option C [This option is highly discouraged if you have not tried it out with our sample quiz. Uploading a photo may cause delays. This will not serve as grounds for special considerations]: Write code on paper, take a photo of your answer, and upload the photo by:

○ Click the "More options" button below (the rightmost button, with three vertical dots).

○ In the expanded menu, click the Images icon.

○ Choose the "Upload Image" option to upload your answer photo. If the upload is successful, you should be able to see the uploaded photo in the answer box.

Question 2

Consider the same trans_t type definition as in Question 1.

Write a function

int compute_card_total_amount(trans_t trans[], int n, char *card_id)

that takes an array of n (n > 0) trans_t records and a credit card id card_id as the input. The function returns the total amount spent over the credit card with id card_id.

Note:

● If card_id is NULL or cannot be found in trans, the function should return 0.

● You may NOT use any library function in your answer to this question.

For example, if trans has the following 10 records and card_id = "xnwxw8tl", the function should return 10 + 60 + 50 = 120.

See Question 1 for instructions on how to enter code in the answer box.

Question 3

Consider the same trans_t type definition as in Question 1.

Write a function

int find_month_with_max_total_amount(trans_t trans[], int n, int *max_total)

that takes as input an array of n (n > 0) trans_t records in which all records have the same year. The function returns the month that has the transactions with the maximum total amount and records this maximum total amount in the variable pointed to by max_total.

If there are multiple months with the same maximum total amount, the function should return the earliest month among those months.

Note:

● You may assume that max_total is not NULL, and trans is sorted in ascending order of transaction date.

● If you use any additional array (beyond the trans array which is already given) in your answer to this question, the full mark of this question will be reduced to 8.

For example, if trans stores the 10 transaction records shown in Question 2, the function should return 3 because the total amount of the transactions in March (190 + 10 = 200) and the the total amount of the transactions in June (50 + 50 + 60 + 40 = 200) are both the maximum, while March is an earlier month. The variable pointed to by max_total should be updated to 200.

See Question 1 for instructions on how to enter code in the answer box.

Question 4

Consider the same trans_t type definition as in Question 1.

In addition, you are given the following binary search tree type definitions:

typedef struct node node_t;

struct node {

void *data; /* pointer to a trans_t struct */

node_t *left; /* left subtree of node */

node_t *right; /* right subtree of node */

};

typedef struct {

node_t *root; /* root node of the tree */

int (*cmp)(void*,void*); /* function pointer to comparison function */

} tree_t;

Assume that trans_tree points to a binary search tree where the cmp function is the trans_comp function as defined in Question 1, and the data field in each tree node points to a transaction record of trans_t type.

Write a function

int compute_card_total_amount_tree(tree_t *trans_tree, char *card_id) 

that takes trans_tree and and a credit card id card_id as the input. The function returns the total amount spent over the credit card with id card_id. 

For example, if the 10 transaction records shown in Question 2 have been inserted into the binary search tree pointed to by trans_tree (the order of insertion is irrelevant to the question), and card_id = "xnwxw8tl", the function should return 10 + 60 + 50 = 120.

Note:

● You can answer this question even if you have not answered Question 1. 

● If trans_tree is NULL, or card_id is NULL, or card_id cannot be found in the tree, the function should return 0.

● You are NOT allowed to create any new arrays in your answer to this question.

● If you make use of any library functions, you must add suitable #include lines.

See Question 1 for instructions on how to enter code in the answer box.

Question 5

Assume a 16-bit floating point number system as described in the textbook, where the most significant bit (the left-most bit) represents the sign; the following three bits represent an integer exponent (of 2) with two's complement representation; and the rest of the bits represent the mantissa. Note that the first bit of the mantissa is hidden, that is, the first bit of the mantissa is not stored.

For example, decimal number 0.375 is represented by 0 111 1000 0000 0000 in this system.

Then, what bit pattern represents the decimal number -0.625 in this system?