CS2850 2023 Past Paper Solution

Question 1: Theory Questions

(a) Static vs. Dynamic Relocation in Memory Management

• Static Relocation: In static relocation, the addresses in a program are adjusted to their absolute physical memory addresses before the program is loaded into memory. This adjustment is typically done by the linker or loader. Once loaded, the program cannot be moved to a different location in memory.
• Dynamic Relocation: In dynamic relocation, the addresses in a program are adjusted during program execution. This is usually achieved through hardware mechanisms like a base register or a Memory Management Unit (MMU). The base register holds the starting physical address of the program, and every memory access is offset by the value in this register. This allows the program to be moved in memory during its execution. An advantage of dynamic relocation is that it simplifies loading and allows for more flexible memory management, including swapping processes in and out of memory.

(b) Linked-List Allocation for Files
The linked-list allocation method stores a file as a linked list of disk blocks. Each disk block contains a pointer to the next block in the file. The directory entry for the file stores the address of the first block.

• Advantage over Contiguous Allocation: One advantage of linked-list allocation over contiguous allocation is that it does not suffer from external fragmentation. With contiguous allocation, finding a contiguous block of free space large enough for a file can be challenging over time, leading to wasted space between allocated blocks. Linked-list allocation can use any free block on the disk, regardless of its location, as long as there are enough free blocks in total.

(c) Batch System Scheduling Strategies
Given jobs A, B, C, and D with estimated running times:

• A: 4 minutes
• B: 20 minutes
• C: 3 minutes
• D: 18 minutes

We need to calculate the turnaround times and average turnaround time for FCFS (order A, B, C, D) and SJF. Turnaround time is the time from when a job arrives until it completes.

• i. First-Come First-Served (FCFS) (Order: A, B, C, D)

  • Job A: Arrives at time 0, runs for 4 minutes. Completion time: 4. Turnaround time: 4.
  • Job B: Arrives at time 0, waits for A (4 mins), runs for 20 minutes. Completion time: 4 + 20 = 24. Turnaround time: 24.
  • Job C: Arrives at time 0, waits for A and B (24 mins), runs for 3 minutes. Completion time: 24 + 3 = 27. Turnaround time: 27.
  • Job D: Arrives at time 0, waits for A, B, and C (27 mins), runs for 18 minutes. Completion time: 27 + 18 = 45. Turnaround time: 45.

  Turnaround times: A=4, B=24, C=27, D=45.
  Average Turnaround Time: (4 + 24 + 27 + 45) / 4 = 100 / 4 = 25 minutes.

• ii. Shortest Job First (SJF)
  SJF executes the job with the shortest running time first. The order would be C, A, D, B.

  • Job C: Arrives at time 0, runs for 3 minutes. Completion time: 3. Turnaround time: 3.
  • Job A: Arrives at time 0, waits for C (3 mins), runs for 4 minutes. Completion time: 3 + 4 = 7. Turnaround time: 7.
  • Job D: Arrives at time 0, waits for C and A (7 mins), runs for 18 minutes. Completion time: 7 + 18 = 25. Turnaround time: 25.
  • Job B: Arrives at time 0, waits for C, A, and D (25 mins), runs for 20 minutes. Completion time: 25 + 20 = 45. Turnaround time: 45.

  Turnaround times: C=3, A=7, D=25, B=45.
  Average Turnaround Time: (3 + 7 + 25 + 45) / 4 = 80 / 4 = 20 minutes.

(d) Concurrent Processes and Shared Variable
Consider processes P1 and P2 sharing variable x, initially x=0.

P1: x=4
P2: x=1; x=x+2; if (x==4) { x=x*5; } else { x=x-1; }

We need to find the possible values of x when the program terminates and provide an execution sequence for each.

Let’s analyze the possible interleavings of operations:

• Case 1: P1 executes fully, then P2 executes fully.

  • P1: x = 4; (x is now 4)
  • P2:
    • x = 1; (x is now 1)
    • x = x + 2; (x is now 1 + 2 = 3)
    • if (x == 4) is false (x is 3)
    • else { x = x - 1; } (x is now 3 - 1 = 2)
  • Final value of x: 2
  • Execution sequence: P1 (x=4), P2 (x=1), P2 (x=x+2), P2 (if/else)

• Case 2: P2 executes fully, then P1 executes fully.

  • P2:
    • x = 1; (x is now 1)
    • x = x + 2; (x is now 1 + 2 = 3)
    • if (x == 4) is false (x is 3)
    • else { x = x - 1; } (x is now 3 - 1 = 2)
  • P1: x = 4; (x is now 4)
  • Final value of x: 4
  • Execution sequence: P2 (x=1), P2 (x=x+2), P2 (if/else), P1 (x=4)

• Case 3: Interleaving where P1 executes between P2’s operations.

  • P2: x = 1; (x is now 1)
  • P1: x = 4; (x is now 4)
  • P2:
    • x = x + 2; (x is now 4 + 2 = 6)
    • if (x == 4) is false (x is 6)
    • else { x = x - 1; } (x is now 6 - 1 = 5)
  • Final value of x: 5
  • Execution sequence: P2 (x=1), P1 (x=4), P2 (x=x+2), P2 (if/else)

• Case 4: Another interleaving.

  • P2: x = 1; (x is now 1)
  • P2: x = x + 2; (x is now 3)
  • P1: x = 4; (x is now 4)
  • P2:
    • if (x == 4) is true (x is 4)
    • { x = x * 5; } (x is now 4 * 5 = 20)
  • Final value of x: 20
  • Execution sequence: P2 (x=1), P2 (x=x+2), P1 (x=4), P2 (if/else)

• Case 5: Another interleaving.

  • P1: x = 4; (x is now 4)
  • P2: x = 1; (x is now 1)
  • P2: x = x + 2; (x is now 3)
  • P2: if (x == 4) is false (x is 3)
  • P2: else { x = x - 1; } (x is now 2)
  • Final value of x: 2. (This is the same as Case 1, but a different execution sequence).
  • Execution sequence: P1 (x=4), P2 (x=1), P2 (x=x+2), P2 (if/else)

The different possible values for the variable x when the program terminates are 2, 4, 5, and 20.

Question 2: Theory Questions

(a) Mutual Exclusion Algorithm
Consider the proposed mutual exclusion solution for two processes (P1 and P2) sharing variable v, initially 0.

P1:

while (1) {
    if (v % 2 == 0) {
        critical_region1();
        v++;
    }
    non_critical_region1();
}

P2:

while (1) {
    if (v % 2 == 1) {
        critical_region2();
        v++;
    }
    non_critical_region2();
}

• i. Operation and Strict Alternation
  The algorithm attempts to enforce mutual exclusion by using the shared variable v to control access to the critical regions. P1 can only enter its critical region if v is even, and P2 can only enter its critical region if v is odd. After entering and exiting their critical region, each process increments v.

  This algorithm enforces strict alternation. If P1 enters its critical region (because v is even), it increments v to an odd number. This prevents P1 from immediately re-entering its critical region and allows P2 (if it’s waiting) to enter its critical region. Once P2 leaves its critical region, it increments v to an even number, allowing P1 to potentially enter its critical region again. This strict dependency on the parity of v ensures that P1 and P2 take turns entering their critical regions.

• ii. Violated Condition
  This algorithm does not comply with the progress condition required for solving the mutual exclusion problem. The progress condition states that if no process is executing in its critical region and some processes wish to enter their critical regions, then only those processes that are not executing in their non-critical regions can participate in the decision of which process will enter the critical region next, and this decision cannot be postponed indefinitely.

  An example of execution order violating the progress condition:
  Suppose P1 is in its non_critical_region1 and P2 finishes its critical_region2 and increments v to an even number. Now, v is even, allowing P1 to enter its critical region. However, if P1 is stuck or spends a very long time in its non_critical_region1 and P2 wants to enter its critical region again, P2 cannot enter because v is even. P2 is blocked even though the critical region is free, and P1 is not attempting to enter its critical region. This violates the progress condition because a process (P2) is prevented from entering its critical region by the activity (or inactivity) of another process (P1) in its non-critical region.

(b) Banker’s Algorithm with Single Resource Type
The Banker’s algorithm is a deadlock avoidance algorithm that can be used in systems with multiple resources of different types. With a single resource type, it simplifies to checking if granting a resource request leads to a safe state.

The algorithm requires information about:

• The total number of resources of the single type.
• The number of resources currently allocated to each process.
• The maximum number of resources each process may request (its “claim”).

When a process requests a certain number of resources, the Operating System uses the Banker’s algorithm as follows:

1. Check if the request is valid: The requested amount must not exceed the process’s remaining claim or the total available resources.
2. Tentatively grant the request: Assume the resources are granted. Update the number of allocated resources for the process and the number of available resources.
3. Check for a safe state: Determine if the system is in a safe state with this new allocation. A state is safe if there exists a sequence of process executions such that all processes can complete without causing a deadlock. With a single resource type, this check involves seeing if there’s any process whose maximum need can be met by the currently available resources plus the resources held by processes that have already finished (or can finish). If such a process exists, assume it finishes and releases its resources, adding them to the available pool. Repeat this process until all processes can be shown to finish.
4. Grant or deny the request: If the state is safe, the request is granted. If the state is unsafe, the request is denied, and the process must wait.

(c) Two-Level Page Table
A virtual memory system has 32-bit virtual addresses and a page size of 4K (4096 bytes). It uses a two-level page table, with the leftmost 12 bits of the virtual address used to index the top-level table.

• i. Number of second-level page tables
  The top-level page table is indexed by the leftmost 12 bits of the virtual address. This means there are $2^{12}$ entries in the top-level page table. Each entry in the top-level page table points to a second-level page table. Therefore, there can be a maximum of $2^{12} = 4096$ second-level page tables in total.

• ii. Number of entries in each second-level page table
  The virtual address is 32 bits. The leftmost 12 bits are used for the top-level page table. The remaining bits are used to index the second-level page table and the offset within the page.
  Number of bits for page offset = $\log_2(\text{page size})$
  Page size = 4K = 4096 bytes
  Number of bits for page offset = $\log_2(4096) = 12$ bits.

  The total bits for the virtual address is 32.
  Bits for top-level page table index = 12 bits.
  Bits for page offset = 12 bits.
  Bits remaining for the second-level page table index = 32 - 12 - 12 = 8 bits.

  Each second-level page table is indexed by these 8 bits. Therefore, each second-level page table has $2^8 = 256$ entries.

Question 3: Pointers

Let’s analyze the C code and its possible output line by line.

#include <stdio.h>

struct point {
    int x;
    int y;
    char label;
};

int main() {
    int i = 1.234;
    printf("1. (float)i = %f\n", (float)i); // Line 1
    printf("2. (void *) &i = %p\n", (void *)&i); // Line 2

    int j = 12.345;
    printf("3. j = %d\n", j); // Line 3

    int *ip = &i;
    int *jp = &j;

    printf("4. (void *) (&i - jp) = %p\n", (void *)(&i - jp)); // Line 4
    printf("5. *(&i + 100) = %d\n", *(&i + 100)); // Line 5

    ip = &j;
    *ip = i;

    printf("6. i - j = %d\n", i - j); // Line 6

    printf("7. sizeof(struct point) = %lu\n", sizeof(struct point)); // Line 7
    struct point z;
    printf("8. sizeof(z) = %lu\n", sizeof(z)); // Line 8

    (&z)->x = i;
    z.y = j;
    (&z)->label = '1';

    printf("9. (&z)->label = %d\n", (&z)->label); // Line 9
    printf("10. z.label = %c\n", z.label); // Line 10

    return 0;
}

Possible output:

1. (float)i = 1.000000
2. (void *) &i = 0x7ffe7c124520
3. j = 14
4. (void *) (&i - jp) = 0xfffffffffffffffc
5. *(&i + 100) = 2081580231
6. i - j = 0
7. sizeof(struct point) = 12
8. sizeof(z) = 12
9. (&z)->label = 49
10. z.label = 1

Let’s explain each line of the output based on the C code and typical behavior:

1. 1. (float)i = 1.000000

   • Explanation: The variable i is declared as an int and initialized with the floating-point literal 1.234. When a floating-point value is assigned to an integer variable in C, the fractional part is truncated. So, i is initialized to the integer value 1. The printf statement casts i to a float and prints it using the %f format specifier, which is for floating-point numbers. The value 1.0 is printed with the default precision of 6 decimal places.

2. 2. (void *) &i = 0x7ffe7c124520

   • Explanation: This line prints the memory address of the integer variable i. The &i operator gives the address of i. This address is then cast to a void * (a generic pointer) which is the standard way to print pointer values using the %p format specifier. The specific hexadecimal address 0x7ffe7c124520 will vary depending on the system and execution, as it represents a memory location assigned at runtime.

3. 3. j = 14

   • Explanation: The variable j is declared as an int and initialized with the floating-point literal 12.345. Similar to i, the fractional part is truncated, so j is initialized to the integer value 12. The printf statement prints the value of j using the %d format specifier for integers. The output shows 14, which indicates that some operation or memory layout has potentially affected the value of j after its initialization but before this print statement, or there might be platform-specific behavior regarding how floating-point literals are handled when assigned to integers, although truncation to 12 is the standard behavior. Assuming standard C behavior, the output should be 12. The provided output of 14 suggests an unexpected side effect or behavior not immediately obvious from the provided code snippet up to this print statement. However, based solely on the initialization int j = 12.345; and the printf("3. j = %d\n", j);, the expected output should be 12. The discrepancy might be due to compiler optimizations or memory layout affecting nearby variables, which is less predictable. Assuming the provided output is correct for the context of the exam, there must be an interaction or memory corruption happening that is not immediately evident before this print statement.

4. 4. (void *) (&i - jp) = 0xfffffffffffffffc

   • Explanation: This line calculates the difference between the memory address of i and the pointer jp (which points to the address of j). Pointer subtraction in C calculates the number of elements of the pointer’s base type between the two addresses. In this case, &i and jp are both int *, so the result is the number of int elements between the address of i and the address of j. The specific value 0xfffffffffffffffc is a large negative number. This indicates that the address of i is a certain number of int sizes lower in memory than the address of j. The exact difference in addresses will depend on how the compiler allocates space for i and j on the stack or in memory. The output 0xfffffffffffffffc (which is -4 in two’s complement for a 64-bit system) suggests that i is located 4 int sizes before j in memory. The result is then cast to void * and printed as a pointer address.

5. 5. *(&i + 100) = 2081580231

   • Explanation: This line performs pointer arithmetic. &i + 100 calculates the memory address that is 100 int sizes away from the address of i. Dereferencing this address using *(&i + 100) attempts to access the integer value stored at that memory location. Accessing memory this far away from the intended variable i is likely accessing uninitialized memory or memory belonging to another variable or part of the program. The value 2081580231 is whatever integer value happened to be stored at that specific memory location at the time of execution. This demonstrates the potential for reading garbage values or causing segmentation faults by accessing invalid memory addresses through pointer arithmetic.

6. 6. i - j = 0

   • Explanation: At this point in the code, i still holds the value 1 (from its initialization). Before this print statement, the code ip = &j; *ip = i; was executed. This means the pointer ip was made to point to the address of j, and then the value of i (which is 1) was assigned to the memory location pointed to by ip, which is the memory location of j. So, the value of j is updated to 1. The printf statement then calculates and prints i - j, which is $1 - 1 = 0$.

7. 7. sizeof(struct point) = 12

   • Explanation: This line prints the size of the struct point structure in bytes. The structure contains an int x, an int y, and a char label. Assuming int is 4 bytes and char is 1 byte, the total size would be $4 + 4 + 1 = 9$ bytes. However, due to memory alignment, compilers often pad structures to ensure that members are aligned on addresses that are multiples of their size or the system’s word size. If the compiler aligns int on 4-byte boundaries and the structure on a 4-byte boundary, the structure might be padded to a multiple of 4 bytes. A size of 12 bytes suggests that there might be padding after the char label to bring the total size up to a multiple of 4 (the size of int) or potentially 8 (depending on system architecture and padding rules). A common padding scheme would be 4 bytes for x, 4 bytes for y, 1 byte for label, and 3 bytes of padding to reach a total of 12, making the next element start at a 4-byte boundary.

8. 8. sizeof(z) = 12

   • Explanation: This line prints the size of the variable z, which is an instance of the struct point. The sizeof operator applied to a variable of a structure type returns the size of the structure, including any padding. As explained in the previous point, the size of struct point is determined by its members and memory alignment, resulting in 12 bytes.

9. 9. (&z)->label = 49

   • Explanation: This line accesses the label member of the struct point variable z using a pointer to z. &z gives the address of z, (&z) casts it to a pointer, and ->label accesses the label member through the pointer. The label member was assigned the character literal '1'. In C, character literals have corresponding ASCII values. The ASCII value of the character ‘1’ is 49. The %d format specifier tells printf to print the value of (&z)->label as an integer. Therefore, the ASCII value 49 is printed.

10. 10. z.label = 1

    • Explanation: This line accesses the label member of the struct point variable z using the direct member access operator .. The label member holds the character value ‘1’. The %c format specifier tells printf to print the value of z.label as a character. Therefore, the character ‘1’ is printed.

Question 4: Swapping Functions

We need to write the definitions for swapx and changeLabel functions based on the provided C code and expected output.

Listing 1 (partial):

#include <stdio.h>

struct point {
    int x;
    int y;
    char label;
};

void swapx (int *p1, int *p2); // Function declaration
void changeLabel (struct point *pz); // Function declaration
void printPoints (struct point *p, struct point *q); // Function declaration

int main() {
    struct point z1, z2;

    (&z1)->x = 1; (&z1)->y = 2; (&z1)->label = '1';
    (&z2)->x = 3; (&z2)->y = 4; (&z2)->label = '2'; // Assuming label for z2 is '2' based on output structure

    printPoints(&z1, &z2); // Prints initial points

    swapx(&(z1.x), &(z2.x)); // Swaps x coordinates
    printPoints(&z1, &z2); // Prints points after swapping x

    changeLabel(&z1); // Changes label of z1
    printPoints(&z1, &z2); // Prints points after changing label

    return 0;
}

void printPoints (struct point *p, struct point *q) {
    printf("point %c: (x=%d, y=%d)\n", p->label, p->x, p->y);
    printf("point %c: (x=%d, y=%d)\n", q->label, q->x, q->y);
}

Expected Output:

point 1: (x=1, y=2)
point 2: (x=3, y=4)
swapping x coordinates
point 1: (x=3, y=2)
point 2: (x=1, y=4)
enter a new label for point 1:
q
the new label for point 1 is q
point q: (x=3, y=2)
point 2: (x=1, y=4)

(a) swapx function
The swapx function takes two pointers to integers (int *p1, int *p2) and should swap the values they point to. In main, it’s called with the addresses of the x members of z1 and z2 (&(z1.x) and &(z2.x)).

void swapx (int *p1, int *p2) {
    int temp;
    temp = *p1; // Store the value pointed to by p1
    *p1 = *p2; // Assign the value pointed to by p2 to the location pointed to by p1
    *p2 = temp; // Assign the stored value (original *p1) to the location pointed to by p2
}

(b) changeLabel function
The changeLabel function takes a pointer to a struct point (struct point *pz) and should change its label member based on user input. The hint suggests using getchar() to read a character from the terminal.

void changeLabel (struct point *pz) {
    printf("enter a new label for point %c:\n", pz->label); // Prompt user
    char c = getchar(); // Read a character from input
    // Consume the newline character left in the input buffer by getchar()
    // This is important if there are subsequent reads from standard input.
    int next_char;
    while ((next_char = getchar()) != '\n' && next_char != EOF);

    pz->label = c; // Assign the read character to the label
    printf("the new label for point 1 is %c\n", pz->label); // Confirm the new label
}

Note: The printPoints function in the expected output prints “the new label for point 1 is q” specifically referring to point 1, which aligns with changeLabel being called on &z1. The confirmation message in the changeLabel function should ideally reflect the point being changed dynamically, but based on the expected output, a hardcoded “point 1” in the confirmation message is used. However, a more general implementation would use pz->label in the confirmation message as well. I’ve included the logic to consume the newline character after getchar(), which is a common issue when mixing getchar() with other input functions.

Question 5: String Merger

This question analyzes a C program that uses dynamic memory allocation to handle strings. We need to understand the main function and the provided stringLen and merge functions.

Listing 2: stringLen and merge functions

int stringLen (char *string) {
    if (!string) return 0;
    int i = 0;
    while (*(string + i) != '\0') i++;
    return i;
}

char *merge (char *string, char *s) {
    int n = stringLen(string);
    int m = stringLen(s);
    char *new = malloc(n + m + 1); // +1 for the null terminator

    int i = 0;
    while (i < n) {
        *(new + i) = *(string + i); // Copy string to new
        i++;
    }

    while (i < (n + m)) {
        *(new + i) = *(s + i - n); // Copy s to new, offset by n
        i++;
    }

    *(new + i) = '\0'; // Null-terminate the new string

    if (string) free(string); // Free the old string if it exists

    return new;
}

Let’s analyze the questions about the main function and the provided functions:

(a) In main:

• i. What does the program do and why dynamic allocation?
  The program reads lines of input from the standard input until EOF (End Of File). Each line read (up to MAX-1 characters) is appended to a dynamically growing string called string. The merge function is used to combine the existing string with the newly read line s. After each merge, the updated merged string is printed, and the memory occupied by the previous version of string is freed.

  Dynamic memory allocation is needed because the total length of the resulting string string is not known in advance. It grows with each line of input read. Dynamic allocation allows the program to allocate memory as needed during runtime to accommodate the growing string, rather than being limited by a fixed-size buffer declared at compile time.

• ii. Why would char c; instead of char c = '\0'; produce an execution error?
  In the main function, the while (c != EOF) loop condition is checked at the beginning of the loop. If c is declared as char c; without an initial value, its initial value is undefined. If this undefined value happens to be equal to EOF, the loop condition c != EOF would be false from the start, and the while loop would not execute even once. This would lead to the program finishing without processing any input. While not strictly an “execution error” in the sense of a crash, it would prevent the program from functioning as intended by reading and processing input. Initializing c = '\0'; ensures that c has a defined value that is unlikely to be EOF initially, allowing the loop to start.

• iii. Why do you need i < (MAX-1) instead of i < MAX?
  The while (((c = getchar()) != '\n') && (c != EOF)) && i < (MAX-1)) loop in main reads characters into the s array. The s array is declared with a size of MAX (char s[MAX];). C-style strings need a null terminator (\0) at the end to mark the end of the string. If the loop condition was i < MAX, it would be possible to read MAX characters into the s array, filling it completely. The line *(s + i) = '\0'; after the loop is responsible for adding the null terminator. If i reached MAX, then *(s + MAX) would be an out-of-bounds access, leading to a buffer overflow and potential security vulnerabilities or crashes. By using i < (MAX-1), the loop ensures that at most MAX-1 characters are read into s, leaving at least one position free for the null terminator at index MAX-1.

• iv. What happens if the user enters more than MAX-1 characters?
  If the user enters more than MAX-1 characters on a single line before pressing Enter (\n) or reaching EOF, the while (((c = getchar()) != '\n') && (c != EOF)) && i < (MAX-1)) loop will stop reading characters once i reaches MAX-1. The remaining characters on that line will be left in the input buffer. The program will then proceed to null-terminate s at index MAX-1 and merge the truncated string s with the existing string. The unread characters in the input buffer will affect subsequent calls to getchar().

• v. Why do you need to null-terminate s before passing it to merge?
  The merge function uses the stringLen function to determine the lengths of the input strings string and s. The stringLen function determines the length by iterating through the characters until it finds a null terminator (\0). If s is not null-terminated, stringLen(s) would continue reading past the intended end of the characters read from input, potentially accessing invalid memory and returning an incorrect length. This would lead to incorrect merging in the merge function. Null-terminating s guarantees that stringLen calculates the correct length of the input read from the line.

• vi. Why do you need free(string) at the end?
  Inside the while loop in main, the merge function allocates new memory for the combined string using malloc. It then frees the memory that was previously allocated for string (if string was not NULL). After the while loop finishes (when EOF is reached), the last dynamically allocated memory for string is still held. If this memory is not explicitly deallocated using free, it will remain allocated until the program terminates. While the operating system will reclaim all memory upon program termination, explicitly freeing dynamically allocated memory using free is crucial to prevent memory leaks in long-running programs or within loops where memory is repeatedly allocated. The free(string); after the loop ensures that the memory allocated for the final version of string is released.

(b) In merge:

• i. Purpose of the first and second while loops?

  • First while loop (while (i < n)): This loop copies the characters from the existing string (pointed to by the string parameter) into the newly allocated memory block pointed to by new. It iterates n times, where n is the length of the existing string.
  • Second while loop (while (i < (n + m))): This loop copies the characters from the input string s into the newly allocated memory block pointed to by new, starting immediately after the copied characters from the original string. It iterates m times, where m is the length of the input string s. The index i continues from where the first loop left off, and i - n is used to access the characters in s from its beginning (index 0).

• ii. Why check if string is a valid pointer before freeing it?
  In the merge function, if (string) free(string); is used to free the memory of the old string. The check if (string) (or if (string != NULL)) is necessary because the free() function should only be called on a valid pointer that was returned by a memory allocation function like malloc, calloc, or realloc. When the program starts, the string pointer in main is initialized to NULL. The first time merge is called, the string parameter will be NULL. Calling free(NULL) is explicitly allowed by the C standard and does nothing. However, calling free() on a pointer that was not returned by an allocation function or has already been freed results in undefined behavior, which can lead to crashes or corrupted memory. The check ensures that free is only called when string points to a valid, previously allocated memory block.

I hope this detailed explanation helps with your revision! Good luck with your exam.