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.

Pages: 1 2

2 Responses to “Three Homework Problems”

  1. Paul said

    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--);
        }
    }
    
    
  2. matthew said

    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)))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: