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.
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:
Make the following changes to this code:
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.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); } } }
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
calloc()
, realloc()
, and alloca()
.sbrk()
function.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.