UNB/ CS/ David Bremner/ teaching/ cs2613/ tests/ sample2

Sample Quiz 1

For this (sample) quiz you will write a JavaScript function strings. This function is to traverse the argument and report all array elements or object fields that are JavaScript string values. Several examples are given below, as tests.

Good Solution

To get 7 marks (roughly a “B”), your solution should

  1. Work for arbitrary JavaScript Array inputs, including nested arrays.
  2. Return the strings in a depth first order. See the tests for some examples of what this means.
  3. Have full test coverage.
  4. Have reasonable indentation and variable names.

In particular your function should pass the following tests.

test("empty array", (t)=> assert.deepEqual(strings([]),[]));
test("single element array", (t)=> assert.deepEqual(strings(["bob"]),
                                                    ["bob"]));
test("mixed strings and numbers", (t)=>
    assert.deepEqual(strings([1,"bob",2,"alice"]), ["bob","alice"]));
test("nested arrays", (t)=>
    assert.deepEqual(strings([1,"bob",[2,"alice"]]), ["bob","alice"]));
test("deeper nesting", (t)=>{
    const expr = [ '*', [ '*', 6, 9 ], [ '+', [ '*', 6, 9 ],
                                         [ '+', 6, 9 ] ] ];
    assert.deepEqual(strings(expr), ['*','*','+','*','+']);
});

Full marks

For full marks, your solution should

  1. Work on arbitrary JavaScript Objects.

  2. Include a (documented) test for an important class of input not tested with the given tests.

Your solution should pass at least the following additional tests.

test("empty object", (t)=> assert.deepEqual(strings({}),[]));
test("single field object",
     (t)=> assert.deepEqual(strings({ name: "bob"}),["bob"]));
test("mixed string and number fields",
     (t)=>assert.deepEqual(strings({age: 1, parent1: "bob",
                                    height: 2, parent2: "alice"}),
                           ["bob","alice"]));
test("nested objects",
     (t)=>assert.deepEqual(strings({ key: {receiver: "bob",
                                           other: {age: 2,
                                                   sender: "alice"} }}),
                           ["bob","alice"]));
test("deeper nesting",
     (t)=>{
         const expr = { op: '*', l: { op: '*', l: 6, r: 9 },
                        r: { op: '+', l: { op: '*', l: 6, r: 9 },
                             r: { op:'+', l: 6, r: 9 } } };
         assert.deepEqual(strings(expr), ['*','*','+','*','+']);
     });

Sample Quiz 2

For this (sample) quiz you will write a JavaScript class Reducer. This class mimics the builtin Array method reduceRight to combine all of the elements of an array with a given two argument function, starting from the end of the array. Several examples are given below, as tests.

Good Solution

To get 7 marks (roughly a “B”), your solution should

  1. Work for arbitrary JavaScript Array inputs and combining functions.
  2. Not use the reduce or reduceRight method.
  3. Implement the run method using recursion.
  4. Have reasonable indentation and variable names.
  5. Have full test coverage and pass the following tests
test("basic operation",  (t)=>{ let r=new Reducer((a,x)=>a*x,1,[1,2,3,5]);
                                assert.strictEqual(r.run(),30); });

test("compare to reduceRight",
     (t)=>{ let array = [ 1, 2, 3 ]; let sub=(a,x)=> x-a;
            let r=new Reducer(sub,0,array);
            assert.strictEqual(r.run(), array.reduceRight(sub,0)); });

test("string operation",
     (t)=>{ let r=new Reducer((a,x)=>a+x,'', ['a','b','c' ]);
            assert.strictEqual(r.run(),"cba"); })

test("non-destructive",
     (t)=>{ let r=new Reducer((a,x)=>a*x,1,[ 1, 2, 3, 5 ]);
            assert.strictEqual(r.run(),r.run()); });

test("big array",
     (t)=>{ let array = Array.from({length: 1000}, (_, i) => i );
            let r=new Reducer((a,x)=>a+x,0,array);
            assert.strictEqual(r.run(),500*999); });

test("big array 2",
     (t)=>{ const array = Array.from({length: 1000}, (_, i) => i );
            let r=new Reducer((a,x)=>a.concat(x),[],array);
            assert.deepStrictEqual(r.run(),array.reverse()); });

Full marks

For full marks, your solution should

  1. Be an iterable class, returning the reduction for the rightmost $k$ elements for the @@math:k@@-th call to next.
  2. Call the combining function no more than the number of calls to next

Your solution should pass at least the following additional tests.

test("basic iterator",
     (t)=>{
         let array = [ 1, 2, 3, 5 ];
         let sub=(a,x)=> x-a;
         let r=new Reducer(sub,0,array);
         let out=[];
         for (let rval of r) { out.push(rval); }
         assert.deepStrictEqual(out,[5,-2,4,-3]);
     });

test("big iterator",
     (t)=>{
         const m=1000;
         const array = Array.from({length: m}, (_, i) => i+1 );
         const expected = Array.from({length: m},
                                     (_, j) => (j+1)*(2*m-j)/2 );
         let r=new Reducer((a,x)=>a+x, 0, array);
         let out=[];
         for (let val of r) { out.push(val); }
         assert.deepStrictEqual(out,expected);
     });

This page intentionally left blank

Sample Quiz 3

To get 7 marks (roughly a “B”), complete either Q1 or Q2. To get full marks complete both questions. In either case your answers should

  1. Not modify the data structure after it is created.
  2. Have full test coverage.
  3. Have reasonable indentation and variable names.
  4. Only use a constant amount of extra storage (e.g. no copying the whole data structure).

For this quiz (Sample) you will a write JavaScript class List. This class has the following constructor.

constructor(value, rest) {
    this.first = value;
    this.rest = rest;
}

The empty list is represented by the object null, and a simple use of List is as follows

test("object", (t) => {
    let list = new List(42, null);
    assert.strictEqual(list.first,42);
    assert.strictEqual(list.rest,null);
});

Q1: length method

Write an length method that calculates the length (number of values) of a List object. In particular your code should pass the following tests. One solution is to use recursion in a very similar way to Assignment 3.

test("one node",
     (t)=>{
         let list1 = new List("hello",null)
         assert.strictEqual(list1.length(),1);
     });

test("two nodes",
     (t)=>{
         let list2 = new List ("hello", new List("world", null));
         assert.strictEqual(list2.length(),2);
     });

test("big list",
     (t)=>{
         let list3 = null;
         for (let i=0; i<100; i++){
             list3= new List (i,list3);
         }
         assert.strictEqual(list3.length(),100);
     });

Q2: Iterator

Add appropriate methods and classes so that your List is iterable. In particular the following tests should pass.

test("iterator 1",
     (t)=>{
         let list2 = new List ("hello", new List("world", null));
         result="";
         for (let val of list2) {
             result+=val;
         }
         assert.strictEqual(result,"helloworld");
     });

  test("iterator 2",
     (t)=>{
         let list3 = null;
         for (let i=0; i<100; i++){
             list3= new List (i,list3);
         }
         let result = 0;
         for (let val of list3) {
             result+=val;
         }
         assert.strictEqual(result, 4950);
     });