CMPT 125 Assignment 3
a) Using C code complete the mergesort function shown below,
your function must be implemented iteratively (i.e. using loops instead of
recursion). You can assume the existence of a merge function with the following
header (i.e. you don't have to write the merge
function, and can call it in your mergesort
function). [4 marks]
void merge(int
arr[], int start, int mid, int end);
void mergesort(int arr[], int len){
// …
}
b) Using C code write a merge function that merges two
sorted arrays, not sub-arrays of the
same array, into a single sorted array and that returns a pointer to the resulting
merged array. Your function should have parameters for the two input arrays and
their lengths. [4 marks]
The call stack is part of main memory that is reserved
for function calling. Like all computer memory it is finite, so can be
exhausted resulting in a stack overflow.
Recursive functions allocate space on the stack for each recursive call; if
there are many such recursive calls a stack overflow can result. The questions
that follow ask you to investigate recursive functions and stack overflows.
Note that when running programs in the Linux terminal
a stack overflow results in a segmentation fault.
a) Using C code write a recursive function that is
equivalent to the iterative function shown below that prints the numbers from 1
to the largest possible integer value. Note that the constant INT_MAX is
contained in the limits.h
header file. [2 marks]
void overflow(){
for(int i = 1; i
<= INT_MAX; i++){
printf("%d\n", i);
}
}
Your recursive function should have a single integer
parameter, and you should initially call the function by passing 1 to its
parameter.
b) Write a main function and run your solution to part
(a) given above. The function will cause a stack overflow. When this has
occurred take a screenshot of the terminal and include that in your submission.
Your screenshot should show the segmentation fault and (at least) the last
value that was printed. [2 marks]
c) Run each of the two functions shown below in turn, initially
passing each function the value 1 to its parameter. Again, take screenshots of
the terminal showing the segmentation fault and the last value that was
printed. [2 marks]
void foo(int n)
{
int* arr = malloc(100 * sizeof(int));
assert(arr);
for(int i=0; i < 100; i++){
arr[i] =
i + n;
}
printf("%d\n", arr[99]);
foo(n+1);
}
void bar(int n)
{
int arr[100];
for(int i=0; i < 100; i++){
arr[i] =
i + n;
}
printf("%d\n", arr[99]);
bar(n+1);
}
d) Explain why, or why not, the segmentation fault
occurred at different times for the two functions that you ran in part (c). [2
marks]
e) Assume that a computer system has a heap of 2GB and that
the size of the call stack for an application is 1MB. Quicksort is used to sort
an array that is stored on the heap (i.e. it is stored in the computer's
internal memory not on a file). Assume that each recursive call to quicksort
requires 256 bytes to be allocated to the call stack. Explain why the call to
quicksort will not result in a stack overflow regardless of the size of the
array being sorted. You should assume that the call to quicksort results in the
average case O Notation running time for the algorithm. [2 marks]
The law firm that employs Bob has a (menial) task for
him. He is to sort 1,000 documents by their case number. Each document is 8.5 by
11 inches and the case number is an eight digit number in the top right hand
corner of each document. Bob is to sort the documents in a small (10 by 12
feet) room which contains a single 60 by 30 inch table.
Bob knows that you have been studying sorting
algorithms so asks you to help him figure out how to sort the documents in a
reasonable amount of time.
a) Describe to Bob a process for sorting the documents. The
process should be based on one of the four sorting algorithms we have studied
in class (selection sort, insertion sort, merge sort and quick sort). Marks are
allocated to how quickly Bob can sort the documents using your process. Your
description should either be in (clear) English or pseudo-code. Remember that
you are describing how to sort documents, not the contents of an array. Also
note that Bob has not studied Computing Science and has not studied Maths since
grade 11 (and he wasn't very good at it) and your description must be easy for
Bob to follow. [6 marks]
b) Estimate the amount of time that Bob will take to
sort the documents. State your assumptions. [4 marks]
Assessment
The assignment is out of 28.
Submission
You should submit your assignment online to the CoursSys submission server. Your solution should consist of a single .pdf
file, please read the documentation on site for further information. The
assignment is due by 11:59pm on Monday the 3rd of July.
John Edgar (johnwill@sfu.ca)