ROB 502: Programming for Robotics: Homework 5
Clicker Questions
Use p4rclicker to submit your answer

How many bits are in a byte?
There are 8 bits in a byte! A byte is the smallest amount of data that the computer can easily work with. So for example, if you have 8 boolean values, the fastest way to work with them is to have 8bool
types which are each 1 byte large. It is possible to use the bits individually with bitwise operations, but that is going to be slower, because again, a byte is the smallest data type the computer can perform operations on! 
How many bits are in a single hexadecimal digit?
There are two hexadecimal digits in a byte, so the 8 bits divided in 2 give 4 bits for each hex digit! 
How many values can be represented by a single hexadecimal digit
So the very word hexadecimal has the answer in it! "hex" means 6 and "deci" means 10, so 6+10=16 different values in hexadecimal. We can also get this answer by knowing that a hex digit has 4 bits, and each bit can encode 2 different values, so 2 to the 4th power2^4 = 16
. 16 different values are possible. 
char msg[] = "taco cat"; msg[3] = '\0'; printf("%s", msg);
Here we count to index 3 in "taco cat", [0] = t, [1] = a, [2] = c, [3] is now the null terminator, so all that gets printed is "tac"; 
printf("%ld, %ld", sizeof("hello!"), strlen("hello!"));
sizeof
gives the number of bytes used for some type. The type of "hello!" ischar[7]
, because that has enough space for the 6 characters and the 1 null terminator character. The length of the string is 6 characters, so we get "7, 6".
You have a 5 by 5 image buffer of 24bit bgr pixels.

How many bytes large is this buffer?
There are a total of 25 pixels, and each pixel is 3 bytes large (24 bits / (8 bits / pixel)), so there are 25 * 3 = 75 bytes total! 
What is the index of the coordinate (4, 2)?
The formula for index in a 2dimensional buffer is, in general, y * width + x, so by that formula, 2 * 5 + 4 = 14.
The buffer is going to look like this, by the indices:
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
But of course in actual memory, that will all be linear:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

What is the bigO time complexity of a search through an unsorted array for a given value?
On average we will have to check half of all the elements, so we would have N/2 * some constant number of operations for each check. Dropping all the constants we getO(N)
. 
What is the bigO time complexity of a binary search through a sorted array for a given value?
Each iteration of the binary search lets us cut the search space in half, so for N=8 we need log2(8)=4 iterations, for N=32 we need log2(32)=6 iterations, and so on. We can drop the constant factor from the base 2, though and just getO(log N)
. 
If a calculation takes
2A + 100log(A)
operations, what is the complexity in BigO notation?
Dropping the constants, we have a linear term and a logarithmic term. For large A, the linear term grows faster so the result is justO(A)
. 
Suppose I give you a special number
uint32_t value = 7364963;
and promise that it is actually a nullterminated 3character string! How would you go about printing it out as a string usingprintf
?
In order to cast pointers, first we need to have a pointer at all! So we can get a pointer to the value by writing&value
. Next, we want to treat this as a string, so we want to cast to type pointer to charchar *
, so we will write(char *)&value
and finally, we useprintf
with the string specifier:printf("%s\n", (char *)&value);

The following code example is compiled with the maximum optimizations (
O3
). Is it guaranteed to terminate?
bool thread_finished = false;
void *producer_thread(void *user) {
thread_finished = true;
return NULL;
}
int main(int argc, char **argv) {
pthread_t thread;
pthread_create(&thread, NULL, producer_thread, NULL);
while (!thread_finished) {
printf("Still running!\n");
}
return 0;
}
So no, it isn’t guaranteed to terminate, because thread_finished
is only modified in a separate thread, and the C language and compiler do not actually know about the concept of threads: they are introduced with an external library called pthread
. So as far as the compiler is concerned, thread_finished
at the start of the while loop in main is false
and so the while loop might as well just read while (!false)
or while (true)
and the program would never exit! Whether compiler makes that optimization or not is a different question, but it is allowed to do so!
13. On the other hand, does the example above terminate on the instructor’s computer?
So in actual fact, the example above still does terminate on my computer, and it is because of the printf
statement. Remove that printf
and it will make an infinite loop. The reason (I am fairly sure) that this happens is because the printf
function was written, as best as possible, to be threadsafe. This means that if you call printf
from different threads you won’t see the lines get all garbled together, like getting "Hello frHello fromom thread1from thread2!!" instead of "Hello from thread1! Hello from thread2!". Now, I suspect that the measures that printf
uses to make itself threadsafe also ends up extending to our while loop, preventing the optimization of while (!thread_finished)
in a way that will not be valid with another thread modifying that value.
 What about this example? Is it guaranteed to terminate?
volatile bool thread_finished = false;
void *producer_thread(void *user) {
thread_finished = true;
return NULL;
}
int main(int argc, char **argv) {
pthread_t thread;
pthread_create(&thread, NULL, producer_thread, NULL);
while (!thread_finished) {
// do nothing
}
return 0;
}
Yup! Now that we have thread_finished
properly marked as volatile
, the compiler knows it is not allowed to optimize thread_finished
in any way, and must always reload the variable from memory, making sure that we always get the most uptodate value from it, and don’t loop forever.