Real-Time Computing

Problems

Problem 2.1

Using the insertion sorting method, sort the fruits in the table shown here by hand, from least to most expensive.

Fruit Price
Apple $\(1.50\)
Orange $\(1.00\)
Banana $\(0.50\)
Pineapple $\(3.00\)
Pear $\(0.75\)

To sort these fruits, we start start with the order as shown. The first step is to compare the price of the first two fruits. Since apple is more expensive than the orange, the order of these two fruits should be swapped resulting in a list:

Fruit Price
orange $\(1.00\)
apple $\(1.50\)
banana $\(0.50\)
pineapple $\(3.00\)
pear $\(0.75\)

With the first two fruits sorted we move on to the third fruit, the banana. Since the price of the banana is less than the price of the apple, the banana should come before the apple. As the banana is also less than the orange, it should also come before the orange. This results in the following list:

Fruit Price
banana $0.50
orange $1.00
apple $1.50
pineapple $3.00
pear $0.75

The next fruit is the pineapple. As the pineapple is more than the apple, no changes are necessary. The final fruit is the pear. As the pear is less than the pineapple, it should come before it. It is also more than both the apple and banana, so it should also come before them. Therefore, the final sorted list is:

Fruit Price
banana $0.50
pear $0.75
orange $1.00
apple $1.50
pineapple $3.00
Problem 2.2

The code here prints a string. What string is printed, and why? Assume that a and b are allocated to sequential blocks of memory. Note the number of characters allocated for the character array a.

char a[3] = "an ";
char b[] = "error";
printf("%s\n", a);

This code prints an error. The reason that an is not printed is that all strings in C should be terminated with a null character. As the space allocated for the character array a is 3, there is no room for a null character. Therefore, when the printf() function starts reading the character array a, it doesn't read a null character until the end of character array b since character arrays a and b are located sequentially in memory.

Problem 2.3

The code here prints a series of numbers when run. What numbers are printed? Why?

int a[] = {1, 5};
int *b = a;
printf("%d\n", *b);
printf("%d\n", ++*b);
printf("%d\n", (*b)++);
printf("%d\n", *b);
printf("%d\n", *b++);
printf("%d\n", *b);

This code does the following.

  1. The first print statement prints 1. This is because b is a pointer to the beginning of array a. As the first entry in a is 1 and the pointer is dereferenced, 1 is printed.

  2. The second print statement prints 2. This is because the pointer b which points to the beginning of the array a is dereferenced, then the prefix increment operator increments it. The operators are applied in this order because they are both at the same precedence level and their associativity is right-to-left. It is important to note that the first entry in a is now 2.

  3. The next print statement prints 2. This is because the code inside the parenthesis is executed first, dereferencing b. As b points to the start of array a the dereferenced value is 2. The postfix increment is then applied to this value. Therefore 2 is printed, and after printing the first value in the array a is 3.

  4. The following print statement prints 3. This is because the first value in the array a is now 3.

  5. The second to last print statement prints 3. This is because the postfix increment is applied because it is at the highest precedence level. However, since it is a postfix increment, nothing is changed yet. Next, the dereference operator is applied and since b points to the first entry in array a, 3 is printed. After the print statement, b is incremented so it now points to the second entry in a.

  6. The last print statement prints 5. This is because b now points to the second value in array a.

Problem 2.4

Your colleague is working on optimizing a function that populates a character array with every other character from an input array. The function takes three input arguments (an input array in, the length of the input array in_len, and the output array out), and returns the length of the output array. Your colleague asks you to determine which version of their function will run faster, func1() or func2(), without running the code. Explain your answer.

int func1(char* in,
          int in_len,
          char* out) {
  int i;
  char *out_ptr = out;
  for (i=0; i<in_len; i++) {
    if (i % 2 == 0) {
      *out_ptr++ = in[i];
    }
  }
  return out_ptr - out;
}

int func2(char* in,
          int in_len,
          char* out) {
  int i;
  char *out_ptr = out;
  for (i=0; i<in_len; i+=2) {
    *out_ptr++ = in[i];
  }
  return out_ptr - out;
}

To determine which function runs faster, we will count the number of operations that need to be performed for an output array of length \(n\). The first function, func1(), does the following. Increment the loop counter for all \(2n\) characters in the original array, check if the loop counter is divisible by 2, and if it is, add the corresponding character to the output array. This is a total of \(5n\) operations that must be performed by this function. The second function, func2(), does the following. Add \(2\) to the loop counter for each of the \(n\) characters in the output array, and add each character to the output array. This is a total of \(2n\) operations that must be performed. Therefore, the second function should be faster because it needs to perform fewer operations to create the same output array.