Introduction
AB
（
Assignment 2 (Due: March 2 – 2:00pm on coursys and in the CSIL dropbox)
This assignment is designed to get us more familiar with different implementations of the sorting and
searching algorithms learned in class. You must do this assignment on your own. Any academic
dishonesty cases will result in an immediate 0 on the assignment (and worst in some cases). If you’re
not sure if your assignment falls under academic dishonesty, please ask your instructor).
For Problems 2 and 3, your code must compile with the given parameters and the correct names.
Failure to do so will result in a 0 for that question.
Problem 1
a. [3 marks]
Description: The idea of the insertion sort algorithm is that we must repeated “search” a sorted area (of
the array) for the insertion point. Since the area that we are searching for is already sorted, we can
instead use a binary search in an attempt to speed up the algorithm.
Task: Consider a slightly altered version of the insertion sort algorithm; we can to use a binary search to
search for the insertion point. The idea is the following: We are searching a sorted area (see Ex.2-5 in
notes) for the insertion point. Instead of using a linear search, we could instead use a binary search to
find the insertion point. What is the running time of the new algorithm? You should include an (English)
argument with your conclusion.
b. [5 marks]
Task: You have a row R of 2N coins consisting of N pennies (1¢) and N dimes (10¢). They alternate as
follows: (1¢) (10¢) (1¢) (10¢) … and so on. Design a sorting (pseudocode) algorithm to sort these coins
from smallest to largest value. The only moves you are allowed to make are those that interchange the
positions of two neighboring coins. You may use array notation in your pseudocode (i.e. R[0] refers to
the first position, R[1] is the second position, etc.). As an example, the sorted version for N=3 will look
like the following:
(1¢) (10¢) (1¢) (10¢) (1¢) (10¢) è (1¢) (1¢) (1¢) (10¢) (10¢) (10¢)
Analyze your function in O-notation (function class only). Once again, a portion of your mark will be
based on the efficiency of your algorithm.
Assignment 2 (Due: March 2 – 2:00pm on coursys and in the CSIL dropbox)
Problem 2 [8 marks]
For this question, you must submit proper (well commented) C code to coursys:
Complete the C code below so that it performs the Selection Sort algorithm, but recursively. Don’t forget
to fill in the post-condition — it is there to help you. (Hint: you should not be using any loops for this
problem). You may find it helpful to write other functions other than the SelectionSort function.
However, any additional functions that you write must also be recursive.
// Post: …
void SelectionSort(int arr[], int len) {
…
}
In your submission please only include your function. We will call your function from a main() program
so please make sure your function is named correctly. We will call the function: SelectionSort(arr,
len) . Please submit your code to coursys and also include a printout of the code on your hardcopy
submission.
Assignment 2 (Due: March 2 – 2:00pm on coursys and in the CSIL dropbox)
Problem 3 [14 marks]
Part (a) deals with the recursive version of binary search:
// Post: Returns 1 iff target is in arr[0..len-1], 0 otherwise.
int RecBinarySearch(int arr[], int len, int target) {
if (len <= 0) { return 0; }
int mid = len/2;
if (target == arr[mid]) return 1;
if (target < arr[mid])
return BinarySearch(arr, mid, target);
else return BinarySearch(arr+mid+1, len-mid-1, target); }
a. Adjust the recursive binary search code so that it returns the index of the target, or -1 (fail)
Parts (b) to (d) deal with the iterative binary search:
int ItBinarySearch(int arr[], int len, int target) {
int first = 0;
int last = len-1;
while (first <= last) {
// Assert: . . .
int mid = (first+last) / 2;
if (target == arr[mid]) return 1;
if (target < arr[mid]) last = mid-1;
else first = mid+1;
}
return 0;
}
b. Adjust the iterative binary search code so that it uses only two comparisons instead of three (in
the main while loop). *Note: The three comparisons are in the while loop, and two if statements
within the loop.
c. Fill in the assertion for the Algorithm (at the beginning of the while loop) for the original version
of the iterative BinarySearch (not your answer for part b).
d. Prove the correctness of the algorithm by using the initialization-maintenance-termination
technique discussed in class.
For this problem, please submit one program with the two functions written in parts (a) and (b) to
coursys. We will run a main function to call these function (and to check validity) so please make sure
that functions are named correctly: RecBinarySearch(arr, len, target) and ItBinarySearch(arr,
len, target) . You must upload your code to coursys.
For parts (a) and (b), please also submit your solution as part of your hardcopy to the CSIL dropbox.
Assignment 2 (Due: March 2 – 2:00pm on coursys and in the CSIL dropbox)
Problem 4 [6 marks]
Description: The term “search” is pretty general. So far, we have only dealt with searching for elements
in an array. This behavior. is very much like search and update in a database of information, and we will
likely spend more time improving this search later in the course. But this is not the only type of search.
The general approach can be extended to: solving numerical systems, planning, AI strategy, and path
finding, to name just a few.
The input will be a 2-dimensional array A[n][n] of numbers, representing the topographic map of a
geographic surface — each of the entries representing the elevation [above sea level]. Also among the
input will be a starting location (r,c), referring to entry A[r][c] .
If you were planning hiking trails, you would be bound by the differences in elevation between
neighboring entries. For the purposes of this question, a person could traverse between two adjacent
locations, if their elevations differ by no more than 2. Adjacency follows just the 4 standard compass
directions, i.e., no diagonals. Thus, a point on the map is considered reachable if it is traversable from
A[r][c] through any sequence of adjacent entries.
Your task is to write an algorithm that computes all of the reachable locations in the grid. The output will
be another 2-D array R[n][n] with true/false values — true means reachable, false means unreachable.
Sample: Suppose A[10][10] looks like this, for starting location A[0][0] :
50 51 54 58 60 60 60 63 68 71
48 52 51 59 60 60 63 63 69 70
44 48 52 55 58 61 64 64 66 69
44 46 53 52 57 60 60 61 65 68
42 45 50 54 59 61 63 63 66 70
38 42 46 56 56 63 64 61 64 62
36 40 44 50 58 60 66 65 62 61
36 39 42 49 56 62 67 66 65 60
30 36 40 47 50 64 64 63 62 60
50 50 50 50 50 50 50 50 50 50
Both south and east are traversable from the start. However, going south leads to a dead end because
44 and 52 are too far away. Here’s the map again, but with reachable entries highlighted:
50 51 54 58 60 60 60 63 68 71
48 52 51 59 60 60 63 63 69 70
44 48 52 55 58 61 64 64 66 69
44 46 53 52 57 60 60 61 65 68
42 45 50 54 59 61 63 63 66 70
38 42 46 56 56 63 64 61 64 62
36 40 44 50 58 60 66 65 62 61
36 39 42 49 56 62 67 66 65 60
30 36 40 47 50 64 64 63 62 60
32 34 38 45 51 53 58 58 57 57
Assignment 2 (Due: March 2 – 2:00pm on coursys and in the CSIL dropbox)
Thus, the resulting array should be:
1 1 0 0 0 0 0 1 0 0
1 1 1 0 0 0 1 1 0 0
0 0 1 0 0 0 1 1 1 0
0 0 1 1 0 0 0 0 1 0
0 0 0 1 0 0 0 0 1 0
0 0 0 1 1 0 0 0 1 1
0 0 0 0 1 1 0 0 1 1
0 0 0 0 1 1 0 0 0 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
Write your algorithm using pseudocode and document it with comments. Submit it as part of the
hardcopy to the CSIL dropbox.
Determine the running time of your algorithm using O-notation, as a function of n. And like last time:
the faster your algorithm, the better your grade.