Format for the final exam

The format for the final exam will be the same as both midterm exams: an in-class, written exam. On the exam I will ask short-answer questions that will ask you to write short code snippets.

The exam will be a closed-book exam, but I will allow you to bring a two pages of notes to use as a reference in the exam.

Second chance problem

One problem I will ask will be very similar to the threads problems I asked on the two midterms. For this problem you should be familiar with some of the thread management functions:

pthread_create()
pthread_join()

You should also know how to write a thread function.

Here is the thread problem from the second exam, along with my solution:

Here is code for the Quicksort algorithm, which is a recursive sorting algorithm:

int partition(int *A,int p,int r) {
    int x = A[r];
    int i = p-1;
    for(int j = p;j < r;j++) {
        if(A[j] <= x) {
            i++;
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
    int temp = A[i+1];
    A[i+1] = A[r];
    A[r] = temp;
    return i+1;
}

void quicksort(int *A,int p,int r) {
    if(p >= r)
        return;
    
    int q = partition(A,p,r);
    quicksort(A,p,q-1);
    quicksort(A,q+1,r);
}

There are two changes we can make to this code to make the sorting process faster:

• When r - p drops below, say, 10000 we can use a nonrecursive algorithm to sort A[p..r] and bypass the recursion.
• When r - p is larger than, say, 100000 we can use threads to run the two recursive calls in parallel.

Make the following changes to this code:

1. Assuming that you have access to a function sort(A,p,r) that can sort the portion of A between indices p and r by some non-recursive algorithm, call that function any time r - p drops below 10000.
2. If r - p is greater than 100000, set up a thread to run the first recursive call. While that thread is running you go ahead and run the second recursive call. After completing the second recursive call you will have to wait for the thread to finish.

Solution

struct qs {
  int* A;
  int p;
  int r;
};

void* tf(void* arg) {
  struct qs* qsp = (struct qs*) arg;
  quicksort(qsp->A,qsp->p,qsp->r);
  return NULL;
}

void quicksort(int *A,int p,int r) {
    if(r - p <= 10000)
      sort(A,p,r);
    else {
      int q = partition(A,p,r);
      if(r - p <= 100000) {
        quicksort(A,p,q-1);
        quicksort(A,q+1,r);
      } else {
        pthread_t tid;
        struct qs s;
        s.A = A;
        s.p = p;
        s.r = q-1;
        pthread_create(&tid,NULL,tf,&s);
        quicksort(A,q+1,r);
        pthread_join(tid,NULL);
      }
    }
}

Additional things to review for the exam

The final exam will be comprehensive, so you should start by reviewing the topics I have already posted for the two midterms.

Since the second midterm exam we have covered chapter nine. Some topics from that material that you should be familiar with include

• The Linux virtual memory system
• Additional memory allocation functions, including calloc(), realloc(), and alloca().
• The sbrk() function.
• C programming techniques for manipulating individual bits.

Finally, we have spent the entire term working with pointers. One of the problems I am going to put on the final exam will ask you to do some simple manipulations with a data structure that makes use of pointers.