Last modified: 2017-01-02
This is a course page of
David Casperson
Associate Professor
Computer Science
University of Northern British Columbia

CPSC 370: Functional and Logic Programming

Old Homework Solutions:

More homework solutions

  1. How many partial binary boolean functions are there?

    There are 34=81 such functions

  2. The triangular numbers are the number of dots in a triangle that is n rows deep and n columns wide. Thus t(4) is 1+2+3+4=10. Write a standard ML function to compute t(n).
    fun triangle 0 = 0
      | triangle n = n + triangle (n-1) ;
        
    or (tail-recursively)
    fun triangle n = let
        fun t2 (0,a) = a
          | t2 (n,a) = t2(n-1,n+a)
    in t2 (n,0) end
      
  3.    .
       ..   .
       ...  ..  .
       .... ... .. .
        
    The pyramidal numbers are the number of dots in a pyramid that is n rows long and n columns wide and n columns high. Thus p(4) is 1+3+6+10=20. Write a standard ML function to compute p(n).
    fun pyramid 0 = 0
      | pyramid n = triangle n + pyramid (n-1) ;
    
  4. Generalize.
    fun nDimSimplex (_,0) = 0
      | nDimSimplex (0,_) = 1
      | nDimSimplex (k,n) = nDimSimplex (k-1,n) + nDimSimplex(k,n-1) ;
        
  5. Guesstimate the running time behaviour of the winning and losing functions discussed in class.

    See this .pdf file for a carefully worked solution.

  6. Write winning and losing functions for Doubling Nim.

    A solution can be found on galaxy.unbc.ca at /export/research/casper/cpsc370/doublingNim.sml.

    This solution found there is an exponential search rather than something clever.

  7. The function defined by
    val f = n => if n>100 then n-10 else f(f(n+11))
    has value max(n-10,91).

    We prove this by strong induction on the quantity 101-n.

    The base case is 101-n ≤ 0. Here, clearly, the claim holds as the function returns n-10 which is greater than or equal to 91.

    Now, inductively, suppose that the claim holds for all 101-n less than 101-k, that is, for all n > k.

    If 0 ≤ 101-k ≤ 11, we have that f(k) = f(f(k+11)) = f(k+11-10) = f(k+1) which by our induction hypothesis is 91.

    If on the other hand 11 < 101-k, then f(k) = f(f(k+11)) = f(91) by our induction hypothesis = 91.

Home page Semesters Site Map
go back Fall 2006 go forward
2017-09 other links

Semester Map
CPSC 141
CPSC 200
CPSC 370
Course Outline
Handing in Homework
Pending Homework Questions
Solutions
Policies
References
David’s Schedule