Main navigation | Main content
The two main themes for this lab are basic C programming, and the use of GDB as a source-level debugger for C programs. We introduced a few features of GDB in lecture, but if you'd like more information, this tutorial from a similar class at Stanford covers the highlights and has some advice on understanding common error messages. Full details are in the GDB manual.
Create a C program containing a loop that enumerates all the powers of 10 that can be represented by a C int value. Your program should have a variable that starts with the value 1, and a loop in which that variable is repeatedly multiplied by 10. The multiplication operation will always appear to succeed, but at some point the results will stop making sense because the numbers are too big to be represented in an int. (This phenomenon is called overflow, and we'll talk about it in more detail in the next part of the course.) To check whether the multiplication is working correctly, you can take the value you got by multiplying by 10 and divide it by 10, and see whether you got the value you started with. Your program shouldn't print the value 10*x such that (10*x)/10 != x, since it won't actually be a power of ten. But you should print all the values up to that point, stopipng at x.
You may find that this is an unintuitive kind of loop to write, because the most natural way to evaluate the termination condition is after part of the loop body. You will definitely have to have more than one variable, and in addition you have some choices including duplicating some computations, or writing a loop with a break statement in the middle.
You should verify that the last number printed by your program is one billion, 1000000000.
The Fibonacci sequence is a famous series of integers with a very simple construction. The first two numbers are 0 and 1, and every number thereafter is the sum of the previous two numbers, e.g. the third and forth numbers are (0 + 1) = 1 and (1 + 1) = 2. Your friend is writing a Fibonacci generator as their very first C program, but they've made an absolute mess of it! Help them fix their obvious compilation errors and the runtime errors that lurk beneath.
Get a copy of their program with:
cp /web/classes/Fall-2018/csci2021-010/labs/0x1/lab1-fibonacci.c .
TIP #1: If you hit a Segmentation Fault, try running the
program through GDB and use the backtrace command.
TIP #2: Never-ending programs often have bugs in while and
for loops. Pay careful attention to their ending conditions of
any while or for loops. Hit the keys CTRL+C to terminate a stuck
program, or (in another terminal) find the PID (process ID) of the stuck process with
ps and use kill <PID>.
Mastering pointers and their operations is critical to understanding
C programs. Pointer reference and dereference mistakes are some of the most
common errors for beginner C programmers (and even experienced people make
mistakes). Answer the questions following each code snippet. Try answering
without writing any code, then check your work with the printf
function (see man printf if you don't know how to print
integers, pointers, or characters).
int i = 20;
What is i ?
What is &i ?
What would happen if you wrote *i ?
char *str = "Hello World";
What are str, &str, and *str ?
What are str[2] and str[12] ?
What is str+3 ? How does it releate to str ?
What is (*str)+3 ? How does it relate to *str ?
What about *(str+3) ?
... or &*str+3 ? Would you ever write this?
What are the order of operations for *, &, +, -, *, () ?
char *str_array[2] = {"Dear", "John"};
What are all the ways to declare an array of strings?
What are *str_array, and **str_array ?
What is str_array[0][0] ?
What is *str_array[1] ?
What is str_array+1 ?
How about *(str_array+1) ?
What is str_array+6 ?
How about *(*str_array+6) ?
Besides regular loops, you can also implement repeating computations in C using recursion, where you have a function that does some work by calling itself with different arguments. Recursion is a good structure for your program when you can think of breaking down the solution of a large instance of a problem assuming that you can solve one or more smaller problems of the same kinds.
For this problem, use recursion to factor an integer into its prime factors. You can think of this problem using recursion if imagine first searching for a divisor of your number. Then, if you find a divisor, and divide by it, you are left with a smaller number that you can factor in the same way.
We've given you the skeleton of code for this question in a file that you can get with:
cp /web/classes/Fall-2018/csci2021-010/labs/0x1/lab1-factor.c .
You may want to fill in one or more additional base cases: that is, code that factors some easy numbers without making recursive calls. Then you'll also need to fill in the recursive case, the one that searches for a divisor and then calls factor again with a smaller argument. Searching for small divisors before large ones will ensure you find a divisor that is itself prime.
By the way, the lab machines already have a program named factor that does something similar to what we're asking for here, though it uses some somewhat more sophisticated algorithms.
Some other questions to ponder: what does it make sense to print for 1, or for negative numbers? For 32-bit integers, this code won't be too slow because a modern CPU can do on the order of a billion operations per second, and 232 is only about 4 billion. However this approach would be too slow for 64-bit long integers. 263-25 is prime; about how long would it take this algorithm to verify that?
You might have already heard of the Mandelbrot set, a well known fractal that has a simple definition in terms of an iterative operation on complex numbers. For the purposes of this problem it's just a pretty picture, but in order to draw that picture you need to complete a program by implementing the operation of multiplication over complex numbers. We'll represent a complex number as an array of two doubles, the first (index 0) for the real part and the second (index 1) for the imaginary part. Copy the framework code with:
cp /web/classes/Fall-2018/csci2021-010/labs/0x1/lab1-mandelbrot.c .
And then complete the program filling in the implementation of the function complex_multiply. Your function should read from the arrays a and b, and write the result of the multiplication to c. If you're not familiar with complex multiplication you can find the definition in the usual kinds of online places.
You can test your program by running commands like:
./lab1-mandelbrot 900 600 >mandelbrot.pgm
eog mandelbrot.pgm
Where eog is an image-viewing program. Your result should look like a more detailed version of this:
In most assignments, yous will work with small programs where you can read all the code, and if you can read the whole program, you can understand everything that's going on. In the real world, though, programmers often have to work with large amounts of code where it isn't practical to read all of it. Often these are the situations where tool like debuggers and IDEs can be most useful.
For this question, you'll debug some slightly artificial bugs in a large program: much too large for you to even skim over the whole program. The program is the Linux version of the Unix ls command, which prints a list of all the files in the current directory; part of why it is complex is that it has a lot of options. You can get a copy of the program with:
cp /web/classes/Fall-2018/csci2021-010/labs/0x1/lab1-ls-buggy.c .
And you can compile it in the normal way. For most purposes you should see that it behaves just like the regular Ubuntu ls command. (This one large file is based on the real source code, though we've done some work to combine it all into one file to make it a bit easier to work with; the original program is spread across several files and libraries.)
The first problem for you to debug is based on a report from a user that the program sometimes crashes when run on a directory that contains a lot of files. The problem seems a little inconsistent in that it doesn't always occur, even when running on the same directory, but the user says the crash still happened pretty frequently in their testing. You should be able to see the problem too if you run the program a few times. But to understand what the problem is, try getting the crash to happen while you run the program under GDB. If you can observe the problem crashing under GDB, you should be able to use the backtrace command and other GDB features to find where the crash is coming from in the source code.
If you want to try a more challenging debugging task, there is also a more subtle problem in the program, which you should be able to see if you compare the output of this version of the program to the output of the system ls command when you give both the -l option. However this one is a bit harder to track down because it doesn't cause the program to crash, it just causes it to produce an unexpected result. But if you think about what the code must be doing when it goes wrong and look for keywords in the code, you may be able to narrow down where the problem might be happening, and by stepping through the code in GDB you can see where the correct answer becomes incorrect. To understand the problem you may also want to look into the documentation for the standard library functions that the code calls.