Introduction

These are the questions from previous versions of the final exam. The tests are available for download.

Questions

Racket

MARKS: 7

In mathematics, the dot product of two @@math:n@@-element vectors is defined as

Write a Racket function dot that computes the dot product of two lists of numbers. You may assume both lists are the same length, and contain only numbers.

For full marks, your solution must

• Use the language “Intermediate Student with Lambda”, or #lang htdp/isl+.
• Work for arbitrarily long input
• Avoid the use of append, assoc, assq, length, list-ref, member, memq, range, remove, remove-all, and reverse.
• Pass the following tests
• Avoid recursion.
• Have reasonable coding style, including indentation and naming.
• Have complete test coverage.

(check-expect (dot '(1 1 1) '(1 2 3)) 6)
(check-expect (dot '(2 2 2) '(1 2 3)) 12)
(check-expect (dot '(-1 -2 3) '(1 2 3)) 4)
(check-expect (dot '(1 0 1) '(0 1 0)) 0)
(check-expect (dot (range 1 101 1) (make-list 100 2)) 10100)

JavaScript

MARKS: 7

Write a Tree class with method map that applies a given function to the value in each node of a binary tree. For full marks your solution must

• have no uncovered lines
• have reasonable coding style, including indentation and naming,
• handle arbitrary binary trees, and
• pass the following tests.

const tree1 = new Tree(1,null,null);
const tree2 = new Tree(2,null,null);
const tree3 = new Tree(3, tree1, tree2);
const tree4 = new Tree(6, new Tree(2,null,null), new Tree(4,null,null))

test("one node",()=>assert.deepStrictEqual(tree1.map((x)=>(x + 1)),
                                           new Tree(2,null,null)));

test("three nodes",()=>assert.deepStrictEqual(tree3.map((x)=>(x * 2)),
                                              tree4));

test("immutable",() => {
    let tree5 = tree4.map(x=>x - 100);
    assert.deepStrictEqual(tree4, new Tree(6, new Tree(2,null,null),
                                           new Tree(4,null,null)));
});

test("list", ()=>{
    const size=17;
    let list1=null;
    let list2=null;
    for (let i=0; i<size; i++) {
        list1=new Tree(i,list1,null);
        list2=new Tree(size-i-1,list2,null);
    }
    assert.deepStrictEqual(list1.map((x)=>size-x-1),list2);
    assert.deepStrictEqual(list2.map((x)=>size-x-1),list1);
});

Python

MARKS: 7

Write a class IterDict that provides a dictionary interface to two iterables, the first for keys, and the second for values. You may want to refer to Section 4.3 of Practical Python for hints on how to provide a dictionary interface. For full marks your solution should

• have complete test coverage,
• have reasonable coding style, including indentation and naming,
• handle arbitrary (including infinite) iterables as input, and
• pass the following tests.

def test_single():
    d = IterDict(["hello"], ["world"])
    assert d['hello'] == 'world'

def test_multiple():
    d = IterDict(range(10), [f'{x}' for x in range(10)])
    assert (d[3],d[7])==('3','7')

def test_range():
    d = IterDict(range(100),range(0,200,2))
    assert (d[0],d[10],d[99]) == (0,20,198)

def test_generator():
    d =IterDict((f'{x}' for x in range(100)),
                (x for x in range(200) if x % 2 == 0))
    assert (d['0'],d['10'], d['99']) == (0,20,198)

def test_infinite():
    def naturals():
        n=0
        while True:
            yield n
            n+=1
    def alternate():
        flag=False
        while True:
            yield flag
            flag = not flag

    d = IterDict(naturals(), alternate())
    assert (d[0],d[1001],d[1234]) == (False, True, False)

Octave

MARKS: 9

As you probably know, by tradition $X$ marks the spot on a map where treasure can be found. In this question you are asked to write a function howmany that, given a $(0,1)$ matrix representing an image, counts the number of @@math:X@@s present in the image. Here we are only concerned with the smallest possibly @@math:X@@s, namely $3 \times 3$ pixels. For full marks your solution should

• handle any 2D array with $0$, $1$ elements,
• pass the following tests,
• be fully vectorized, not using loops, arrayfun, rowfun, or cellfun, and
• be well commented (i.e. with meaningful comments).

%!shared X,CB
%! X=[1,0,1;0,1,0;1,0,1];
%! CB=gallery("circul",[1,0,1,0,1,0,1,0]);
%% Single X
%!assert (howmany(X) == 1)
%% Disjoint X's
%!assert (howmany(blkdiag(X,X,X,X)) == 4)
%% 2 Overlapping X's
%!assert (howmany(gallery("circul",[1,0,1,0])) == 2)
%% Checkerboard image
%!assert (howmany(CB) == 18)
%!assert (howmany(blkdiag(CB,CB,CB,CB,CB,CB))==108)
%% Missing a pixel in the second X
%!assert (howmany([1,0,1,0;0,1,0,1;1,0,1,0;0,1,0,0]) == 1)
%% Non-square image
%!assert (howmany([1,0,1;0,1,0;1,0,1;0,1,0;1,0,1]) == 2)
%% Non square, disjoint X's
%!assert (howmany([X,X,X;X,X,X])==6)
%% filled gaps
%!assert (howmany([1,1,1,1;0,1,1,0;1,1,1,1]) == 0)