University of Minnesota
Machine Architecture and Organization (sec 010)
index.php

CSci 2021 Lab 0x1

The main theme of this lab is basic C programming. You'll also get a chance to try out the use of GDB as a source-level debugger for C programs. We'll say a few words about GDB at the beginning of lab, and more details about GDB will come in future lectures. Some other good sources of information about it are a tutorial from a similar class at Stanford, and the full GDB manual.

You can also peek ahead in the lecture slides about C and GDB here.

  1. (Pointer Practice.)

    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. You can use printf to print integers, pointers, and characters using %d, %p, and %c like this:

      int i = 12;
      int *ip = &i;
      printf("The values of ip and i are %p and %d", ip, i);
      char c = 'A';
      printf("The value of c is %d as a number and %c as a letter", c, c);
    
    (see man printf for more details).

     
    	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) ?

  2. (Loops and powers of ten.)

    Though we haven't gotten to introducing them in lecture yet, loops in C using while, for and break work similarly as in Java.

    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.

  3. (Fix this Fibonacci.)

    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/Spring-2020/csci2021/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>.

  4. (Factoring with recursion.)

    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/Spring-2020/csci2021/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?

  5. (Drawing the Mandelbrot set.)

    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/Spring-2020/csci2021/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: