;; compute the nth fibonacci number, space-saving version
(define ssf  
  (lambda (n)
    (define helper
      (lambda (fi-2 fi-1 i)
        (if (= i n)
            (+ fi-2 fi-1)
            (helper fi-1 (+ fi-2 fi-1) (+ i 1)))))
    (if (< n 2)
        n
        (helper 0 1 2))))

(load "2d-table.scm")

;; Author: Jordan Barry
;; This procedure computes choose(n, k)
;; using a one-dimensional vector of size k+1
;; instead of a two-dimensional table of size (n+1)(k+1).
(define sschoose
  (lambda (n k)
    (do ((V (make-vector (+ k 1)))
         (i 0 (+ i 1)))
      ((> i n) (vector-ref V k))
      (do ((j (min i k) (- j 1)))
        ((< j 0))
        (vector-set! V j 
                     (if (or (= i j) (= j 0))
                         1
                         (+ (vector-ref V j)
                            (vector-ref V (- j 1)))))))))
    
;; Author: Martin Barnard
;; This procedure computes choose(n, k) by dynamic programing,
;; filling the table column by column.
(define dpchoose-by-columns
  (lambda (n k)
    (do ((T (make-table (+ n 1) (+ k 1)))
         (j 0 (+ j 1)))
      ((> j k) (table-ref T n k))
      (do ((i j (+ i 1)))
        ((> i n))
        (table-set! T i j
                    (cond ((zero? j) 1)
                          ((= i j) 1)
                          (else (+ (table-ref T (- i 1) j)
                                   (table-ref T (- i 1) (- j 1))))))))))