Three Homework Problems
March 22, 2016
All of these are simple, and we’ve seen them before. We’ll use arrays, even though it is more natural to use lists in Scheme, and use mutation as is done in the imperative language that most beginning programmers learn. Here’s the program that sums an array by adding each element, from left to right, to an accumulator:
(define (sum vec)
(let ((len (vector-length vec))
(sum 0))
(do ((i 0 (+ i 1))) ((= i len) sum)
(set! sum (+ sum (vector-ref vec i))))))
> (sum '#(4 9 1 8 3 2 6)) 33
To reverse an array, we set pointers at both ends of the array, swap the values there, move both pointer toward the middle, and repeat, stopping when the pointers meet:
(define (reverse! vec)
(let ((len (vector-length vec)))
(do ((lo 0 (+ lo 1))
(hi (- len 1) (- hi 1)))
((<= hi lo) vec)
(let ((temp (vector-ref vec lo)))
(vector-set! vec lo (vector-ref vec hi))
(vector-set! vec hi temp)))))
> (reverse! '#(4 9 1 8 3 2 6)) #(6 2 3 8 1 9 4)
Insertion sort works the same way card players sort their hands: pick an item from the unsorted portion of the array, insert it in its proper location in the sorted portion of the array, and repeat until the entire array is sorted:
(define (sort! vec)
(let ((len (vector-length vec)))
(do ((i 0 (+ i 1))) ((= i len) vec)
(do ((j i (- j 1)))
((or (zero? j)
(<= (vector-ref vec (- j 1))
(vector-ref vec j))))
(let ((temp (vector-ref vec j)))
(vector-set! vec j (vector-ref vec (- j 1)))
(vector-set! vec (- j 1) temp))))))
> (sort! '#(4 9 1 8 3 2 6)) #(1 2 3 4 6 8 9)
Common errors of beginning programmers are integer overflow in the first task, mis-understanding pointers in the second task, and getting the stopping criterion wrong in the third task. You can run the program at http://ideone.com/D1DZYX.
Programming Praxis 
In C.
int sum(int *arr, int n) { int i, thesum = 0; for (i=0; i< n; i++) thesum += arr[i]; return thesum; } static void swap(int *a, int *b) { int tmp; if (a != b) { tmp = *a; *a = *b; *b = tmp; } } void rev(int *arr, int n) { int *a, *b; a = arr; b = arr + n - 1; while (a < b) swap(a++, b--); } void isort(int *arr, int n) { int i, *a, *b; for (i=0; i < n - 1; i++) { a = arr + i; b = a + 1; while (a >= arr && *b < *a) swap(a--, b--); } }We can represent an array as a function from integers to values, together with a size, eg. in Javascript { f: f, length: n } can represent an array [f[0],f[1],..,f[n-1]]. We can then define the required operations as:
function fromarray(a) { return { f: function(i) { return a[i] }, length: a.length } } function toarray(s) { var a = []; for (var i = 0; i < s.length; i++) { a.push(s.f(i)); } return a; } function sum(s) { function aux(i,j) { if (i+1 == j) return s.f(i) var k = i + Math.floor((j-i)/2); return aux(i,k) + aux(k,j); } return aux(0,s.length); } function reverse(s) { return { f: function(i) { return s.f(s.length-i-1); }, length: s.length } } function insert(s,n) { var a = s.f(n); return { f: function(i) { if (i < n) { return s.f(i); } else if (i > n && s.f(i) >= a) { return s.f(i); } else if (i == s.length-1 || s.f(i+1) >= a) { return a; } else { return s.f(i+1); } }, length: s.length } } function sort(s,n) { if (n == undefined) n = s.length; if (n == 0) return s; return sort(insert(s,n-1),n-1); } var a = fromarray([3,10,2,5,6,8,9,4,1,7]); console.log(toarray(a)) console.log(sum(a)) console.log(toarray(reverse(a))) console.log(toarray(sort(a)))