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

Before the lab

Flattening

Time
25 minutes
Activity
Exercise from book.

Solve the Flatten Exercise using reduce and concat methods. Your solution should pass the following test suite.

test("base case", ()=> assert.deepStrictEqual(flatten([]),[]))
test("single element",
     function () {
     assert.deepStrictEqual(flatten([1]),[1]);
     assert.deepStrictEqual(flatten(["foo"]),["foo"]);
     assert.deepStrictEqual(flatten([{foo: 1}]),[{foo: 1}]);
     });
test("longer list", ()=>
    assert.deepStrictEqual(flatten([[1],2,[3],4,[5,6]]),[1,2,3,4,5,6]));

Does the following test pass with your implementation? If not, why not?

test("deeper nesting", (t)=>
    assert.deepStrictEqual(flatten([[[1],2,[3]],4,[5,6]]),[1,2,3,4,5,6]));

Referring back to L07, answer the following in your journal.

Every

Time
25 minutes
Activity
Exercise from book.

Solve the Every Exercise

Call the version using a loop every_loop

test("all true", (t)=>
    assert.strictEqual(every_loop([1, 3, 5], n => n < 10), true));
test("last false", (t)=>
    assert.strictEqual(every_loop([2, 4, 16], n => n < 10), false));
test("last middle false", (t)=>
    assert.strictEqual(every_loop([2, 16, 3], n => n < 10), false));
test("empty list", (t)=>
    assert.strictEqual(every_loop([], n => n < 10),true));

Call the version using the some method every_some. The tricky part here is to construct a function that is the negation of the given function.

test("all true", (t)=>
    assert.strictEqual(every_some([1, 3, 5], n => n < 10), true));
test("last false", (t)=>
    assert.strictEqual(every_some([2, 4, 16], n => n < 10), false));
test("last middle false", (t)=>
    assert.strictEqual(every_some([2, 16, 3], n => n < 10), false));
test("empty list", (t)=>
    assert.strictEqual(every_some([], n => n < 10),true));

Timing functions

Time
40 minutes
Activity
Individual work.

We are presented with two different implementations of the Fibonacci function, and we want to see which one is faster 1.

const test=require("node:test");
const assert=require("assert");

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

let cache = {};
function memfib(n) {
    if (cache[n] !== undefined)
        return cache[n];

    if (n<=2)
        cache[n] = 1;
    else
        cache[n] = memfib(n-1)+memfib(n-2);

    return cache[n];
}

test("fib(35)=9227465",(t)=>assert.strictEqual(fib(35),9227465));
test("memfib(35)=9227465",(t)=>assert.strictEqual(memfib(35),9227465));

Using the function noisy as a template, write the higher order function timed that uses the builtins console.time and console.timeEnd to output timing information. The wrapped function produced by timed should produce the same values as the original function, as shown by the following tests.

test("timed(fib)(35)=9227465", (t)=>assert.strictEqual(timed(fib)(35),9227465));
test("timed(memfib)(35)=9227465",(t)=>assert.strictEqual(timed(memfib)(35),9227465));
let out=timed(fib)(42);
let out2=timed(memfib)(42);
test("fib(42)≈memfib(42)",assert.ok(Math.abs(out-out2)<0.000001))

It turns out that memfib is much faster. On my computer, the output from the last two timed calls is

fib(42): 970.887ms
memfib(42): 0.034ms

Notice how I have included the name of the function and the parameter in the output. Try to do the same.

Answer the following in your journal:

Before Next Lab


  1. There are several better versions of Fibonacci that we will see later in the course.