Disclaimer: This question is significantly more challenging than the rest of this exam. It is strongly recommended that you complete all other questions before attempting this question.

The level first order is a method of node insertion in a binary tree wherein the nodes are inserted from left to right at each level of the tree with an aim to completely fill up all the lower levels of the tree before considering the higher levels.  

For example: 

If the numbers 1 2 3 4 5 6 are inserted into a binary tree following the level first order, the resulting tree can be graphically depicted as follows:

Utilizing the skeleton code available at this link, complete the definition of the function insert_node_level_first() that inserts a node into a binary tree following the level first order.

• rootPtr: address of the pointer to root node of the binary tree
• headPtr: address of the pointer to first node of a queue that stores the address of nodes within the binary tree. The queue is utilized to support the binary tree node insertion based on the algorithm explained in the skeleton code.
• data: the integer that should be inserted into the binary tree

1. You should write your code only within the section specified in the skeleton code provided.
2. You are not allowed to add, delete or modify any lines within the main(), push(), pop() and inOrder() functions in the skeleton code.

1. In order to verify the functionality of your code within WSL environment in VS Code:
   • Download a copy of the test script run_tests.py and place it within the same folder as your .c file. 
   • Then, run the following commands sequentially on the terminal. The first command ensures that both the .c file and the compiled object file have the same name (your unique student ID, considered for example as 12345678). The second command runs the python test script by providing your student ID as input argument.
     
2. Your code MUST be submitted as a .txt file below BEFORE the end of the test. Late submissions cannot be accepted.
3. Your .txt file should be named as q9_studentID.txt, eg q9_12345678.txt

4. You should use good programming practices

Consider a modified version of the IEEE754 single-precision floating-point format as depicted in the figure below.

The floating-point format consists of the following fields:

• S (Sign-bit): a 1-bit field that equals 1 for negative numbers and 0 for positive numbers
• Integer: a 16-bit field that represents the integer portion (digits before the decimal dot) of the floating-point number as a 4221 Binary Coded Decimal (BCD) code. The 4221 BCD code represents an integer (in base 10) by converting each decimal digit into a 4-bit binary code such that:
  • the MSB (bit 3) represents the value              : 2² = 4 
  • the next bit (bit 2) represents the value         : 2¹ = 2
  • the next bit (bit 1) also represents the value : 2¹ = 2
  • the LSB (bit 0) represents the value                : 2⁰ = 1
  • For example: 
    • the integer 7 is represented using 4-bits as 1011 = 4 (MSB) + 0 + 2 + 1 (LSB)
    • the integer 23 is represented using 8-bits as 0010 0011 where the first 4 binary digits represent the number 2 (in base 10) and the last 4 binary digits represent the number 3 (in base 10)
• Fraction: a 15-bit field that represents the fractional portion (digits after the decimal dot) of the floating point number such the MSB represents 2^-1 and the LSB represents 2^-15

Represent the number -5789.125 in 32-bits based on the floating-point standard described above. Further, explain how this format changes the range of floating-point numbers that can be represented as compared to the IEEE754 single-precision format.

Define a histogram class that creates histograms (counting how many values fall in each of a number of intervals) given the values and bounds. The class should satisfy the following:

1. The constructor should be passed a single argument that is a vector of doubles containing the bounds of the histogram bins. The elements of the vector can be assumed to be strictly increasing (each value is greater than the previous value). For example, instantiating the class with the vector: {0.0, 3.14, 20.0, 42.42, 69} would create a histogram with four bins, corresponding to the intervals: [0, 3.14), [3.14, 20), [20. 42.42), [42.42, 69).

1. The histogram class should have a method named clear, that clears the histogram statistics.

1. The histogram class should have a method named update, that is passed a single argument: a double that represents a new data point to add to the histogram. You can assume all data passed to this method will be within the range of the histogram bins.

1. The histogram class should have a method named display, that prints each bin’s range, followed by the number of values that fall into that bin.

For example, if the histogram was initialised with the vector : {0.0, 3.14, 20.0, 42.42, 69} and the update method was called with the following numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, then calling the display method would print the following:

[0, 3.14): 3

[3.14, 20): 7

[20, 42.42): 3

[42.42, 69): 2

1. All data attributes of the class should be private.

1. Your code MUST be submitted as a .txt file below BEFORE the end of the test. Late submissions cannot be accepted.
2. Your .txt file should be named as q6_studentID.txt, eg q6_12345678.txt

3. You should use good programming practices

Consider the following C++ program that performs the following activities:

1. Opens a .csv file (path supplied through command line argument) that contains details of the ECE2071 final project demonstration conducted by student teams. In order to ensure that Project Team IDs are redacted in the file, the team that refers to a particular line in the file is identified through the combination of STM 32 Nucleo kits used during the demonstration. Thus, each line of the file stores the unique IDs of STM32 boards utilised and audio processing parameters achieved by a particular team during the demonstration in the following format:
   sampling_STM_serial_number, processing_STM_serial_number, sampling_rate (sps), bits_per_sample, duration (in seconds)

   The first few lines of the .csv file are shown below.

   025,057,22050,16,25

   016,087,10000,8,25

   001,004,44100,16,60

   015,022,05000,16,45

2. Stores the details in the input file into a map container to ensure that duplicate entries for a particular team are avoided during the grading process.
3. Writes the details in the map to an output file (path again supplied through command line argument) that will be utilized by the unit coordination team during the grading.

Answer the following questions:

1. What is the significance of this-> pointer utilized in the program? (2 marks)
2. What is the significance of the address operator (&) on Line 44 in the program? (2 marks)
3. How does the map container deal with a duplicate entry in the input file? (2 marks)
4. Describe the activities performed in Lines 31-34 of the program. (2 marks)
5. Describe the format of information in the output file. Is the order of teams in the input and output files similar? If yes, why? If no, explain why the order is different. (2 marks)
6. Explain how the map container utilizes the information stored in the elements of the vector container in the program. (2 marks) 

Consider the C program below and then answer the following questions.

1. Describe what the function compute_array() does? (2.5 marks)
2. What does the printed output of the program indicate? (2.5 marks)
3. Is the program memory safe? If yes, why? If no, how could it be made memory safe? (2.5 marks)

Part 1 (15 marks)

int string_hash (char* string_1, int starting_value)

Write a C function string_hash that takes in the following input arguments:

1.  A pointer to character (string_1) representing a C string 
2.  An integer (starting_value) greater than 0

• Step 1: Find the smallest composite number (integer greater than 1 and has more then 2 factors) that is greater than starting_value and stores this as the current composite value (current_composite)

• Step 2: Starting from the first character, for each character in the string (except the terminating NULL character), calculate the sum of the ASCII value of the current character and current_composite. 

• Step 3: Add the result of the calculation in Step 2 to the accumulator value (accumulator), which is initialized as zero at the start of the function.

• Step 4: Find the next smallest composite number that is greater than the current_composite and assign this as the new value of current_composite. 

• Step 5: Repeat steps 2-4 until all non-NULL characters in the string have been considered.

• Step 6: Return the value of accumulator upon exit.

Part 2 (5 marks)

Write a C code inside the main function that performs the following activities:

• Scan a string (string_1) with a maximum of 20 non-NULL characters (inclusive of whitespaces) and an integer (starting_value) in one line as input from the user through the terminal. The two pieces of information should be separated using a comma delimiter.

• Call the hash_string function written in Part 1, using string_1 and starting_value as the inputs

• Prints string_1, starting_value and accumulator in the following format on the terminal:

<string_1><whitespace><starting_value><whitespace>-<whitespace><accumulator>'\n'

Note:

1. Your code MUST be submitted as a .txt file below BEFORE the end of the test. Late submissions cannot be accepted.
2. Your .txt file should be named as q1_studentID.txt, eg q13_12345678.txt

3. You should use good programming practices