UNB/ CS/ David Bremner/ teaching/ cs2613/ tests/ T4/ Final Exam Practice

Introduction

These are the questions from the last two final exams. Solutions will be posted 48h before the exam.

Racket

Dot product

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.

Passing

For 4 marks (roughly a C), your solution must

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

Full Marks

For full marks, your solution must

Find

Implement a Racket function find that given a list of numbers, return the position (starting from 0) of all non-zero numbers in the list. This is similar to the Octave builtin of the same name.

Good solution

For 5 marks (roughly a B), your solution must

(check-expect (find '()) '())
(check-expect (find '(0)) '())
(check-expect (find '(1)) '(0))
(check-expect (find '(1 2 0 3)) '(0 1 3))
(check-expect (find (build-list 10 (lambda (x) (modulo x 3)))) '(1 2 4 5 7 8))

Full Marks

For full marks, your solution must must not use explicit recursion.

JavaScript

Iterator Fib

Write a class Fib that works as an iterator to generate successive Fibonacci numbers. For reference, here is a recursive definition of the Fibonacci numbers.

function fib(n) {
    if (n<=0) return 0;
    if (n<=2) return 1;
    return fib(n-1)+fib(n-2);
}

Passing

For 4 marks (roughly a C), your solution must

test("Fib(6)", (t)=> {
    let results = [];
    for (let f of new Fib(6)) { results.push(f); }
    assert.deepStrictEqual(results,[0,1,1,2,3,5,8]);
});

test("Fib(42)", (t)=> {
    let result = -1;
    for (let f of new Fib(42)) { result = f; }
    assert.strictEqual(result,267914296);
});

test("Fib(2) destructure", (t)=> {
    let [a,b,c] = new Fib(6);
    assert.deepStrictEqual([a,b,c],[0,1,1]);
});

test("Fib(6) spread", (t)=> {
    assert.deepStrictEqual([...new Fib(6)], [0,1,1,2,3,5,8]);
});

Full Marks

For full marks your solution must

Filtered Class

Write a JavaScript iterator class Filtered that filters a given list according to a given predicate (single argument function returning true or false).

Good solution

For 5 marks (roughly a B), your solution must have reasonable coding style, including indentation and naming, handle arbitrary lists and predicates as input, and pass the following tests.

test("empty", (t)=> {
    let results = [];
    for (let f of new Filtered([],(x)=>true)) { results.push(f); }
    assert.deepStrictEqual(results,[]);
});

test("nonempty", (t)=> {
    let results = [];
    let filter_obj = new Filtered([1,2,3,4],(x)=>(x % 2 == 0))
    for (let f of filter_obj) { results.push(f); }
    assert.deepStrictEqual(results,[2,4]);
});

test("big", (t)=> {
    let input = [], results=[];
    for (let i=0; i<100; i++){ input.push(i);}
    let filter_obj = new Filtered(input, (n) => n % 4 == 0 && n*n < 100);
    for (let f of filter_obj) { results.push(f); }
    assert.deepStrictEqual(results,[0,4,8]);
});

Full Marks

For full marks your solution must have no uncovered lines, not call the predicate (directly or indirectly) from the Filtered constructor, and support restarting the iterator.

test("restart", (t)=> {
    let results1 = [];
    let filter_obj = new Filtered([1,2,3,4],(x)=>(x % 2 == 0));
    for (let f of filter_obj) { results1.push(f); }
    assert.deepStrictEqual(results1,[2,4]);
    let results2 = [];      
    for (let f of filter_obj) { results2.push(f); }
    assert.deepStrictEqual(results2,[2,4]);
});

Python

Convert tables to dictionaries

Write a Python function table2dict that converts a table (list of lists) to a dictionary, where the keys of the dictionary are the elements of the first row, and the the values are the columns underneath those headers.

Passing

For 4 marks (roughly a C), your solution should pass the following tests, and work for arbitrarily sized tables.

def test_one_row():
    table=[["alice", "bob"],
           [27, 32]]
    assert table2dict(table)== { "bob": [32], "alice": [27] }

def test_two_rows():
    table2 = [["alice", "bob"],
              [1, 2],
              [False, True]]
    assert table2dict(table2)== { "bob": [2,True], "alice": [1,False] }

Full Marks

For full marks, your solutions should not use any loops, but only comprehensions (and other builtin functions as needed). My loop-free solution uses the following Python feature. Sometimes called the splat operator, the prefix * operator expands l into 3 arguments 1,2,3 to func.

def func(a, b, c):
    return a+b+c;
l = [1,2,3]
assert func(*l) == func(1,2,3)
assert func(*l) == 6

Merge dictionaries

Octave

Vectorized FizzBuzz

Write an octave function fizzbuzz that counts the elements of an array divisible by 3, 5, and both 3 and 5, and returns an array of those three counts.

Passing

For $5$ marks (roughly a C), your solution should handle any shape of array and pass the given tests.

%!assert(fizzbuzz(27),[1,0,0]);
%!assert(fizzbuzz(25),[0,1,0]);
%!assert(fizzbuzz(60),[1,1,1]);
%!assert(fizzbuzz([1,7,11]),[0,0,0]);
%!assert(fizzbuzz([1,3,7; 5,11,30]),[2,2,1]);
%!assert(fizzbuzz([1,2,3; 4,5,6; 7,8,9]),[3,1,0])
%!assert(fizzbuzz(ones(10,10,10)*45),[1000,1000,1000])

Full Marks

For full marks your solution must

Rooks

In chess, two rooks can attack each other if they are in the same row or column (without intervening pieces). If all the pieces are rooks, we can ignore the rule about intervening pieces.

In this question you are given an array representing a chess board, with $1$ representing black rooks, $-1$ white rooks, and $0$ blank spaces. Your task is to report the total number of rows and columns containing rooks which can attack each other; in other words to count the rows and columns containing both $1$ and $-1$.

Passing

For $6$ marks (roughly a B-), your solution should handle any 1D or 2D array and pass the following tests.

%!assert (rooks([1,0]) == 0)
%!assert (rooks([1,0,-1]) == 1)
%!assert (rooks([1,0;0,-1]) == 0)
%!assert (rooks([1,1;0,-1]) == 1)
%!assert (rooks([1,1;-1,-1]) == 2)
%!assert (rooks([1,-1;-1,1]) == 4)
%!assert (rooks([1,0; 0, -1]) == 0)
%!assert (rooks([1,1,-1]) == 1)
%!assert (rooks([1,1,-1; -1,0,1]) == 4) 

%!test
%! V=[1   1   1   1   1;
%!    0   0   0   0   1;
%!    1  -1   1  -1   1;
%!    1   1   1   1   1;
%!    1  -1   1  -1   1];
%! assert (rooks(V) == 4)

Full Marks

For full marks your solution must