UNB/ CS/ David Bremner/ teaching/ cs2613/ labs/ Lab 24

Before the lab

Racket questions

Hash tables, recursion

Write a racket function list->hash that, given a list, returns a hash table which maps the number i to the list element in ith position (starting from position 1). For full marks, your function should

(module+ test
  (require rackunit)
  (define hash-table (list->hash (list "a" "b" "c") (hash) 1))
  (check-equal? (hash-ref hash-table 1) "a")
  (check-equal? (hash-ref hash-table 2) "b")
  (check-equal? (hash-ref hash-table 3) "c"))

Tail recursion + lists I

Complete the Racket function sum-pos-helper to tail-recursively sum the positive elements of a list of integers.

#lang racket
(define (sum-pos . nums)
  (define (sum-pos-helper nums acc)
    (cond
      [(empty? nums)   ]
      [(positive? (first nums)) ]
      [else  ]))
  (sum-pos-helper nums 0))

(module+ test
  (require rackunit)
  (check-equal? (sum-pos) 0)
  (check-equal? (sum-pos 1) 1)
  (check-equal? (sum-pos 1 0 -1) 1)
  (check-equal? (apply sum-pos (range -9 10)) 45))

Tail recursion + lists II

Write a tail-recursive function sixes-and-sevens that keeps all multiples of 6 or 7. It should in particular pass the following test.

(module+ test
  (require rackunit)
  (check-equal? (sixes-and-sevens '(1 6 7 12)) '(6 7 12)))

You may use reverse in your solution, but for full marks do not use append.

Testing

Copy your solution to the previous question and add at least 3 tests tests for your sixes-and-sevens function. For full marks you should test 3 logically different things, and document what you are testing.

Higher order functions

Write the Racket function binmap to apply the passed binary operator (function) to the two given lists. Your function should use no other list functions other than first, rest, cons, and empty? (in particular don’t use the builtin function map). Your function should pass the following tests.

(module+ test
  (require rackunit)

  (check-equal? (binmap + '(1 2 3) '(4 5 6)) '(5 7 9))
  (check-equal? (binmap * '(1 2 3) '(4 5 6)) '(4 10 18))

  (check-equal? (binmap string-append '("hello" "world ")
                                      '(" mom" "travel"))
        '("hello mom" "world travel"))

  (check-equal? (binmap + '(1 2 3) '(4 5 6 7)) '(5 7 9))
  (check-equal? (binmap + '(1 2 3 4) '(4 5 6)) '(5 7 9)))

More Tail recursion

Complete the Racket function helper to re-impliment the function binmap from the previous question tail-recursively. Provide appropriate tests for binmap2. Your function helper should use no other list functions other than first, rest, cons, and empty?.

(define (binmap2 op list1 list2)
  (define (helper lst1 lst2 acc) #|function body goes here|#)
  (reverse (helper list1 list2 '())))

JavaScript Questions

Recursion, classes

In this question, the Expr JavaScript class represents simple expressions using multiplication and addition, e.g. (6*9)+(3*4). Write the eval method for Expr. Your method should compute the value of the expression (a number), and should pass the following jasmine tests

let Expr=require("../expr.js").Expr;

describe("expr",
         function() {
             let six_plus_nine = new Expr('+', 6, 9);
             let six_times_nine = new Expr('*', 6, 9);
             it("addition",
                function() {
                    expect(six_plus_nine.eval()).toBe(15);
                });
             it("multiplication",
                function() {
                    expect(six_times_nine.eval()).toBe(54);
                });
             it("compound",
                function() {
                    expect(new Expr('+', six_times_nine,
                                    six_plus_nine).eval()).toBe(69);
                });});

Strings, Higher order functions

Complete the following JavaScript function to concatenate strings. For full marks, use the reduce method.

function join(lst) {

}
exports.join = join;

Your function should pass the following tests.

join=require("./join.js").join;
describe("join", function () {
    it("empty", function () { expect(join([]), ""); });
    it("single", function () {
      expect(join(["holidays"]), "holidays");
    });
    it("several", function () {
      expect(join(["happy", " ", "holidays"]), "happy holidays");
    });
});

More strings and higher order functions

Use a higher-order array method (i.e. no loops or recursion) to impliment a JavaScript function revapp that appends its string arguments in reverse order. Your code should pass the following test.

revapp=require("../revapp.js").revapp;
describe("revapp", function () {
    it("letters", function () {
        expect(revapp("a","b","c","d")).toEqual("dcba");
    })});

JSON, classes

Write a JavaScript class called Student that supports writing and reading objects from disk. Your class should pass the following Jasmine test. The first argument to the constructor is the name, and the second the id number of the student.

let Student = require("../student.js").Student;

describe("json", function () {
    let bob = new Student("bob",42);

    it("roundtrip", function() {
        let filename = "test-roundtrip.json";
        bob.write(filename);
        expect(Student.read(filename)).toEqual(bob);
    })});

You may use the following module (extended from Lab 11)

let fs = require("fs");

function read_json_file(filename) {
    return JSON.parse(fs.readFileSync(filename));
}

function write_json_file(obj,filename) {
    fs.writeFileSync(filename,JSON.stringify(obj));
}

exports.read_json_file=read_json_file;
exports.write_json_file=write_json_file;

More classes

Write a class Person that passes the following jasmine tests. You need to write a constructor and a method birthday.

let person=require("../person.js");
let Person=person.Person;
let People=person.People;

describe("person",
         function () {
             let bob=new Person("bob", 42);
             
             it("constructor",
                function () {
                    expect(bob.name).toEqual("bob");
                    expect(bob.age).toEqual(42);
                });
             it("birthday does not mutate",
                function (){
                    let newbob = bob.birthday();
                    expect(bob.age).toEqual(42);
                    expect(newbob.age).toEqual(43);
                });
             
         });

Write a second class People that passes following jasmine tests. You need to write a constructor and a length attribute.

describe("people",
         function() {
             let people=new People("ancestry.json");
             it("read all records",
                function () {
                    expect(people.length).toEqual(10);
                });
             it("hash table",
                function() {
                    console.log(people);
                    expect(people["Clara Aernoudts"]).toEqual(new Person("Clara Aernoudts",95));
                });
         });

You will need the file ancestry.json with the following content

[
    {"name": "Carolus Haverbeke", "sex": "m", "born": 1832, "died": 1905, "father": "Carel Haverbeke", "mother": "Maria van Brussel"},
    {"name": "Emma de Milliano", "sex": "f", "born": 1876, "died": 1956, "father": "Petrus de Milliano", "mother": "Sophia van Damme"},
    {"name": "Maria de Rycke", "sex": "f", "born": 1683, "died": 1724, "father": "Frederik de Rycke", "mother": "Laurentia van Vlaenderen"},
    {"name": "Jan van Brussel", "sex": "m", "born": 1714, "died": 1748, "father": "Jacobus van Brussel", "mother": "Joanna van Rooten"},
    {"name": "Philibert Haverbeke", "sex": "m", "born": 1907, "died": 1997, "father": "Emile Haverbeke", "mother": "Emma de Milliano"},
    {"name": "Jan Frans van Brussel", "sex": "m", "born": 1761, "died": 1833, "father": "Jacobus Bernardus van Brussel", "mother":null},
    {"name": "Pauwels van Haverbeke", "sex": "m", "born": 1535, "died": 1582, "father": "N. van Haverbeke", "mother":null},
    {"name": "Clara Aernoudts", "sex": "f", "born": 1918, "died": 2012, "father": "Henry Aernoudts", "mother": "Sidonie Coene"},
    {"name": "Emile Haverbeke", "sex": "m", "born": 1877, "died": 1968, "father": "Carolus Haverbeke", "mother": "Maria Sturm"},
    {"name": "Lieven de Causmaecker", "sex": "m", "born": 1696, "died": 1724, "father": "Carel de Causmaecker", "mother": "Joanna Claes"}
]

Python questions

Generator

Write a python generator powergen(n) that returns a sequence
1, n, n2, n3, n4, …
when passed to next.

def powergen(n):




def test_powergen():
    gen = powergen(2)
    first = next(gen)
    second = next(gen)
    third = next(gen)
    assert (first == 1)
    assert (second == 2)
    assert (third == 4)

List comprehension

Use a list comprehension to complete the following test for powergen.

def test_powergen_list():
    gen = powergen(3)
    threes = 
    assert(threes == [1, 3, 9, 27, 81, 243, 729, 2187, 6561])

FizzBuzz Iterator

Complete the next method to return 'FizzBuzz', 'Fizz', 'Buzz' for iterations divisible by 3 and 5, 3 only, and 5 only, respectively. next should return the iteration number otherwise.

 
class FizzBuzz:
    def __init__(self, max=100):
        self.n=1; self.max=max

    def __next__(self):



def test_fizzbuzz_next():
    fb=FizzBuzz(15)
    assert (list(fb) == [1,2,'Fizz',4,'Buzz','Fizz',7,8,'Fizz',
                        'Buzz', 11, 'Fizz', 13, 14,'FizzBuzz'])

FizzBuzz Iterator part II

Complete the iter method for the FizzBuzz class.

def __iter__(self):

def test_fizzbuzz_iter():
    fb=FizzBuzz(100)
    first = list(fb); second = list(fb)
    assert (first == second)

ArithSeq iterator

Write a python iterator class ArithSeq where ArithSeq(first, step, max) creates a sequence of integers starting at first, going up by step, and stopping at the last value in the sequence no larger than max. Your class should pass the following tests.

from arithseq import ArithSeq

def test_evens():
    assert [ x for x in ArithSeq(0,2,10) ] == [0,2,4,6,8,10]

def test_odds():
    assert [ x for x in ArithSeq(1,2,10) ] == [1,3,5,7,9]<

Testing

Write two more tests for ArithSeq. Explain what you are testing, and why that case is not covered by the given tests.

ArithSeq function

Write a python function arith_seq using a list comprehension that passes the following tests (i.e. produces the same sequences as the class ArithSeq).

from arithseq2 import arith_seq

def test_evens():
    assert arith_seq(0,2,10) == [0,2,4,6,8,10]

def test_odds():
    assert arith_seq(1,2,10) == [1,3,5,7,9]</code></pre></li>

Octave Questions

Image processing

Complete the Octave function nbrcount that counts for each element of a zero/one matrix, how many of the neighbours are one. For full marks your solution should be vectorized.

function out = nbrcount(img)

endfunction

%!test
%! A=       [1,0,0;
%!           0,0,0;
%!           0,0,1;
%!           1,0,0];
%! counts = [0,1,0; 1,2,1; 1,2,0; 0,2,1]
%! assert(nbrcount(A) == counts)

Isolated

Use the nbrcount function from the previous question to define a function isolated that finds all the isolated ones (those ones whose neighbours are all zero). For full marks your solution should be vectorized.

function out = isolated(img)

endfunction

%!test
%! A= [1,0,0; 0,0,0; 0,0,1; 1,0,0];
%! assert(isolated(A) == A)

%!test
%! A=[1,0,0;
%!    0,0,0;
%!    0,1,1;
%!    1,0,1];
%! assert(isolated(A) == [1,0,0; 0,0,0; 0,0,0;0,0,0])

Normalize

Complete the vectorized Octave function normalize according to the given comment and tests. You do not need to copy the usage comment.

##usage: matrix = percent(raw, maxes)
##
## raw - raw scores, one row per student.
## maxes - maximum possible for that column
##
## Output is a matrix one row per student, with ratios
function out=normalize(raw, maxes)

endfunction
%!test
%! #    journal,assgn,  midterm,final
%! mxs=[260,    60,     20,     60];
%! nrm = [0.9, 0.9, 0.9, 0.9; 0.75, 0.75, 0.75, 0.75; 1, 0, 1, 0];
%! raw=[234, 54, 18, 54; 195, 45, 15, 45; 260, 0, 20, 0];

%! assert(normalize(raw, mxs), nrm, eps);

percent

Use the function normalize from the previous question to complete the following vectorized Octave function to calculate final percentages for students in a class. You do not need to copy the usage comment.

##usage: scores = percent(raw, maxes, weights)
##
## raw - raw scores, one row per student.
## maxes - maximum possible for that column
## weights - weight for that column in percent
##
## Output is a column vector of a percent for each student.
function out=percent(raw, maxes, weights)

end

%!test
%! #    journal,assgn,  midterm,final
%! mxs=[260,    60,     20,     60];
%! wgt=[20,     30,     20,     30];
%! raw=[234,    54,     18,     54;
%!      195,    45,     15,     45;
%!      260,    0,      20,     0;
%!      0,      60,     0,      60;
%!      200,    40,     17,     33];
%! assert(percent(raw, mxs, wgt), [90;75;40;60;68.88], .01);

Check diet

Write an octave function checkdiet that checks if a proposed diet meets the minimum daily requirements. Your function should pass the given tests. For full marks your function should be fully vectorized (i.e. no loops).

## usage: passes = checkdiet(TABLE, MINS, DIET)
##
## Check if DIET passes the min daily requirements
##   TABLE(i,j) is the amount of nutrient i in food j
##   MINS(i) = minimum amount of nutrient i required
##   DIET(j) = amount of food j in proposed diet
function yesno = checkdiet(table, mins, diet)
end
%!test
%! assert(checkdiet(eye(3),ones(3,1),ones(3,1)) == 1)
%!test
%! assert(checkdiet(eye(3),zeros(3,1),[1;0;0]) == 1)
%!test
%! assert(checkdiet(eye(3),[1;0;0],zeros(3,1)) == 0)
%!test
%! assert(checkdiet(eye(3),[1;0;0],0.5*ones(3,1)) == 0)
%!test
%! assert(checkdiet(ones(3,3),[1;0;0],0.5*ones(3,1)) == 1)

testing

Identify two weaknesses of the given test suite for checkdiet and add two new tests.

mincol

Write the octave function mincol that finds the position of the smallest element in each row of a matrix. You function should pass the given test. For full marks your function should be fully vectorized (i.e. no loops).

## usage: given a matrix of integers, for each row
## return the column containing the minimum value
function out = mincol(data)

endfunction
%!test
%! A = [1,2,3;
%!     3,2,4;
%!     1,2,0;
%!     5,3,4;
%!     3,2,1;
%!     -10,0,0];
%! assert (mincol(A) == [1;2;3;2;3;1]);