Before the lab

Before every lab in this course, you will be given tasks to complete. These will generally be easy tasks like watching videos, but you need to complete them in order to keep up with the class.

Command Line Familiarity Check

1. In an FCS linux lab (remote or locally) log in, and open a terminal.

2. Make a directory *

3. Create a file in that directory using one of the available text editors

4. Now clean up, removing the file and the directory.

If any of this was new to you, then please take the time to go through parts 1 to 5 of the Learning the Shell Tutorial.

Read the course syllabus.

The Course Syllabus is available on line. Please read it, and bring any questions you have about it to the first lab.

Background Reading

For every lab there will be some related reading. I'll point these out as we go through the lab, but I'll also collect them at the start of the lab in case you want to get a head start (or refer back to them later).

• The Frog manual
• Git Basics from Pro Git
• Basic Shell Background

About the course

1. What's similar to other CS courses you've taken?

2. What's different?

3. Key point, how are labs evaluated?

Software Setup

1. Open a terminal.

2. Install frog and the other tools we need via the following command (throughout the course, $ at the beginning of a line will indicate a shell prompt, you don't need to type it.):

     $ raco pkg install --auto unb-cs2613
   

3. Install the python library pygments, used by frog for syntax highlighting

    $ python -m ensurepip --upgrade
    $ python -m pip install pygments
   

There are an unfortunate number of warnings here, but we can ignore them for now.

Getting Started with Frog

We'll be using frog frog to keep a journal of what we learn in this course.

1. Open a terminal.

2. Make a directory called cs2613 that will keep all of your work (note that case and spaces matter in Linux and this is not the same as CS2613 or CS 2613. For the rest of this course we will assume it is directly under your home directory. The shortcut ~/cs2613 will refer to this directory in the lab texts and in the shell.

3. Make a directory journal inside ~/cs2613. Inside ~/cs2613/journal, run

    $ raco frog --init
   

4. Try viewing the newly created blog with

    $ raco frog -bp
   

5. Start a new blog page for today's lab, and delete the fake entry created by the frog setup command. Note that you may have to refresh the browser after running raco frog -bp.

Setting up a git repo

1. Change to ~/cs2613. This directory should have one subdirectory called journal, which has the results of your experiments above with frog.

2. Create the git repository

    $ git init -b main
   

   Git will reply with something like

    Initialized empty Git repository in /home1/ugrads/$username/cs2613/.git/
   

   You’ve now initialized the working directory — you may notice a new directory created, named ".git". You should mentally replace "$username" with whatever the login name is that you use to log into the FCS linux machines.

3. Read the git-quickref page, and follow the initial configuration steps there.

   • note that the "--wait" option for gedit is important here.

4. Next, tell Git to take a snapshot of the contents of all files under the journal, with git add:

   $ git add journal
   

This snapshot is now stored in a temporary staging area which Git calls the "index". You can permanently store the contents of the index in the repository with git commit:

   $ git commit

This will open and editor and prompt you for a commit message. Enter one and exit the editor. You’ve now stored the first version of your project in Git. See §5.2 of Pro Git for some hints about writing good commit messages. As mentioned in the class git policy, you will be marked on your commit messages, so you may as well get started with good habits.

Pushing to a central repo

Since we are using the FCS git repositories there is an existing repository for all students who registered early enough. If it turns out there is no repository for you, you may need to do the last step later.

• First add the remote. This something like a nickname for the URL where the repo will be stored.

    $ git remote add origin https://$username@vcs.cs.unb.ca/git/cs2613-$username
  

  origin is the default name for a remote, but we could have used a different name here. Replace $username with your FCS Linux account name.

• Now upload your local copy of the repo.

    $ git push --all origin
  

  you should see something like

            Counting objects: 388, done.
            Delta compression using up to 8 threads.
            Compressing objects: 100% (350/350), done.
            Writing objects: 100% (388/388), 71.63 KiB | 0 bytes/s, done.
            Total 388 (delta 223), reused 59 (delta 33)
            To https://$username@vcs.cs.unb.ca/git/cs2613-$username
               e7e5311..f1ae959  main -> main
  

• If you have extra time, start L02

Before next lab

Before the lab

Background

• This lab completes our discussion git, and starts our first programming language, namely Racket.

• For learning racket, we will mainly follow Functional Introduction to computer science

• You may also find the BSL reference helpful.

Git Tutorial Continued

Making Changes in git

Having at look at our test post from Lab 1, we can observe the post template adds a bunch of stuff related to social media. Let's suppose that for our cs2613 journal we want a more minimal look.

Start by finding the right files to edit with

$ git grep disqus

git grep is a very useful (and fast!) tool to find occurrences of strings in your git repository. Notice in the output there are some files created by frog; we will clean those up later. Find the template file (under _src) and edit it to remove the undesired social media links. Check the results with

$ raco frog -bp

You might notice one more link to twitter in a different template file. Feel free to remove that one as well.

Use git add to stage your changes:

$ git add file1 file2 file3

You are now ready to commit. You can see what is about to be committed using git diff with the --cached option:

$ git diff --cached

(Without --cached, git diff will show you any changes that you’ve made but not yet added to the index.) You can also get a brief summary of the situation with git status:

$ git status
# On branch master
# Changes to be committed:
#   (use "git reset HEAD <file>..." to unstage)
#
#       modified:   file1
#       modified:   file2
#       modified:   file3
#

If you need to make any further adjustments, do so now, and then add any newly modified content to the index. Finally, commit your changes with:

$ git commit

This will again prompt you for a message describing the change, and then record a new version of the project.

Alternatively, instead of running git add beforehand, you can use

$ git commit -a

which will automatically notice any modified (but not new) files, add them to the index, and commit, all in one step. Keep in mind that you will be marked on the logical structure of your git commits, so you are better off using git add to explicitely choose what changes to commit.

Cleaning up generated files

A common phenomenon in software development is the existence of generated files. These files are created by some tool, typically based on some source files. In general it is a bad idea to track generated files in version control because they introduce spurious changes into history. We'll look at this more later, but for now let's try to clean up. We can find out what files are generated .e.g. by consulting the frog docs. Let's first try a shortcut. Run

$ cd ~/cs2613/journal
$ raco frog --clean

To find out what changed, run

$ git diff --stat

All going well, you will see a bunch of deletions. We can tell git to make those deletions permanent in several ways. It turns out that there is a handy option to git add that tells git to stage all of the changes in the working tree. Try to figure out which option it is.

• to see the effect of a git add command, run git diff --cached --stat
• to undo the effect of a git add command, run git reset.

When you are satisfied with the changes, run git commit.

It will turn out that this is not all of the generated files; we can use git rm to clean up further as we find more.

Make sure you run

$ raco frog -bp

To make sure the the blog still works after your deletions.

Viewing project history

1. At any point you can view the history of your changes using

    $ git log
   

   Use this command to verify that all the changes you expected to be pushed to the server really were.

   If you also want to see complete diffs at each step, use

    $ git log -p
   

   Often the overview of the changes is useful to get a feel for each step

    $ git log --stat --summary
   

2. In most projects, you have to share commit messages to (at least) the same people who view your source code. Share your "best commit" message with one or more of your neighbours.

3. Find something positive to say about the other commit messages you are reading.

4. Find a constructive improvement with one of the other messages. Don't be mean, people have varying levels of experience with this.

Getting started with racket

Hello Racket World

• Open a terminal

• Make a directory ~/cs2613/labs/L02 (if it does not already exist) and change there with cd

• Save the following code to ~/cs2613/labs/L02/hello.rkt

#lang htdp/bsl
"hello world"
(* 6 7)

Command Line

• run the program with

    $ racket hello.rkt
  

• What is the difference between the first and second line of output?

DrRacket: A Racket Specific IDE

• Start DrRacket from the activities menu

• Referring to the DrRacket documentation as needed, open and run the hello.rkt program from the previous part.

• What is the meaning of the first line of the file?

Racket Expressions.

• Form groups of 2 or 3.

• Work through Exercise 0: for each of the following lines of code, someone from the group should guess what is wrong before trying it in the Interactions window of DrRacket.

    (* (5) 3)
    (+ (* 2 4)
    (5 * 14)
    (* + 3 5 2)
    (/ 25 0)
  

• Work through Exercise 1. In general where the text asks you to predict the value of an expression, you can also enter into the definitions window something like

    (check-expect (* 6 9) 42)
  

  When you run (e.g. F5), then you will find out if your prediction is correct.

• Work through Exercise 2. You can test your answers by applying the following functions to appropriate arguments. Notice that the value of y does not matter.

#lang htdp/bsl
(define y 18)
(define (t1 x)
  (or (= x 0) (< 0 (/ y x))))
(define (t2 x)
  (or (< 0 (/ y x)) (= x 0)))
(define (t3 x)
  (and (= x 0) (< 0 (/ y x))))
(define (t4 x)
  (or (< 0 (/ y x)) (not (= x 0))))

Racket functions

• Do this part on your own.

• Do Exercise 4

  Here are some tests to help you check your function

(check-expect (middle-of-three 1 2 3) 2)
(check-expect (middle-of-three 2 1 3) 2)
(check-expect (middle-of-three 1 3 2) 2)

• Do these tests suffice? Why or why not?

Before Next Lab

Before the lab

Git Questions

Some questions from before:

• What is a remote?
• What is merging?
• What is a conflict?

Setup

• make a directory labs/L03 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

The DrRacket stepper

• copy arith.rkt, save it as ~/cs2613/labs/L03/arith.rkt and commit it.

• run your arith.rkt in DrRacket; observe that the test fails

• run your arith.rkt in the DrRacket Stepper. Notice that after about 7 steps, we have reduced the test case to multiplication by zero which looks wrong. That means that the problem is with the recursive (reduction) step.

• Fix the a > 0 case of my-* to match the following formula a * b = (a - 1) * b + b, while still using my-+

• DrRacket should report "The test passed!" when you have it working. Commit this version of your code. Remember that git commit message quality counts in this course, so work on making commit messages.

Semantics

As you read in FICS unit 3, we can understand evaluation ("running") of Racket programs as a sequence of "reductions" or "substitutions". These rules are similar to the reduction steps in the DrRacket stepper.

The stepper uses the following rules for and and or (notice that these rules enforce short circuit evaluation)

(and true exp2 ...) => (and exp2 ...)
(and false exp2 ...) => false
(or true exp2 ...) => true
(or false exp2 ...) => (or exp2 ...)
(and) => true
(or) => false

Following Exercise 7, write a new set of rules that requires at least two arguments for and and or. The rules are for human consumption; you can write them as comments in DrRacket. You can write "exp1 exp2 ..." to mean at least 2 expressions.

Discuss your answers with a your group, and try a couple evaluation small examples by hand using your rules.

Test Coverage

Unit testing is an important part of programming, and has inspired something called test driven development.

• This activity continues arith.rkt from the first half of the lab.

• Under

  Language -> Choose Language -> Show Details -> Dynamic Properties
  

  enable

  ⊙ Syntactic test suite coverage
  

• comment out the given test

• run your code in DrRacket again

• most likely you will have some code highlighted with orange text and black foreground. This means that code is not covered by your test suite. Uncomment the given test, and if needed add tests to cover each piece of uncovered code.

• When you have complete test coverage, commit your code.

  In this course, for all racket assignments you will lose marks if you don't have complete test coverage.

• Push your repo to coursegit.

If you have extra time

• Run the tests on the command line with raco test arith.rkt
• Read the first assignment A1
• Update your journal.

Before Next Lab

Before the lab

Questions from last time

• The programming languages we will study this term are all dynamically typed. This means that not only the value but also the type of variables can change at runtime. Why does this make testing even more important?

• What kind of software problems is testing not well suited to find?

• Why might mutable state (e.g. instance variables in Java) make writing unit tests harder?

Setup

• make a directory labs/L04 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

Simulating Natural Numbers I

Write the times function from Exercise 11 in FICS. You can (and should) use the following code from the linked discussion

#lang htdp/bsl
(define-struct Z ())
(define-struct S (pred))
(define (pred nat)
  (cond
    [(Z? nat) (error "can't apply pred to Z")]
    [(S? nat) (S-pred nat)]))

(define (plus nat1 nat2)
  (cond
    [(Z? nat1) nat2]
    [(S? nat1) (make-S (plus (S-pred nat1) nat2))]))

Here is the template for structural recursion on (simulated) natural numbers. See the linked text (or the plus function just above) for how to add a second "carried-along" parameter.

(define (my-nat-fn nat)
  (cond
    [(Z? nat) ...]
    [(S? nat) ... (my-nat-fn (S-pred nat)) ...]))

Here are some tests to get you started. As always, try to have complete test coverage.

;; 0 * 0 = 0
(check-expect (times (make-Z) (make-Z)) (make-Z))
;; 0 * 1 = 0
(check-expect (times (make-Z) (make-S (make-Z))) (make-Z))
;; 2 * 1 = 2
(check-expect (times (make-S (make-S (make-Z)))
                       (make-S (make-Z)))
              (make-S (make-S (make-Z))))

You may find it helpful to refer back to your solution from L03.

Simulating Natural Numbers II

Write the compare function from Exercise 11 in FICS. Your function compare should use the struct definitions Z and S, and pass the following tests

;; 0 = 0
(check-expect (compare (make-Z) (make-Z)) 'equal)
;; 0 < 1
(check-expect (compare (make-Z) (make-S (make-Z))) 'less)
;; 1 > 0
(check-expect (compare (make-S (make-Z)) (make-Z)) 'greater)
;; 2 > 1
(check-expect (compare (make-S (make-S (make-Z)))
                       (make-S (make-Z))) 'greater)

Structural recursion, on numbers

Use structural (note that structural here is only indirectly related to Racket structs) recursion on natural numbers (not the simulated ones from above, but regular Racket numbers like 1, 42, and 1337) to define a function (sum-factors n max-factor) that sums all factors of n (including 1) no larger than max-factor

Recall the template for structural recursion on natural numbers:

(define (my-nat-fn n)
  (cond
    [(zero? n) ...]
    [(positive? n) ... (my-nat-fn (sub1 n)) ...]))

Try to use only one recursive call to sum-factors like in the template. Keep in mind that the n in the template might be a different parameter of your function. You can use the builtin function remainder to test for divisibility.

The following tests should pass

;; 1+2+3 = 6
(check-expect (sum-factors 6 5) 6)
;; 1+2+4+7+14 = 28
(check-expect (sum-factors 28 27) 28)

Before Next Lab

Lab 5 was cancelled due to Campus closure. Content was moved to Lab 6.

Before the lab

• Read FICS Section 5.1, 5.2

Setup

• make a directory labs/L05 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

Substitute in a list

Complete FICS Exercise 13.

Note the template for structural recursion.

(define (my-list-fn lst)
  (cond
    [(empty? lst) ...]
    [(cons? lst) ... (first lst) ...
                 ... (my-list-fn (rest lst)) ...]))

Here is a test case based on the linked test

(check-expect
 (substitute 3 "three" (list "four" 3 4 "three" 3))
 (list "four" "three" 4 "three" "three"))

Uniquifying lists

Complete FICS Exercise 15. Although probably not intended by the original question, use the built-in BSL function member? to simplify your solution. Otherwise use only the constructs specified in Exercise 14, and structural recursion. My solution contains an auxilary function (also using structural recursion) to remove all copies of a particular value from a list. Here is one test case derived from the linked text.

(check-expect
 (unique-right
  (list 1 4 2 1 5 4))
 (list 2 1 5 4))

Add an element to all lists

Recall the template for structural recursion on lists

(define (my-list-fn lst)
  (cond
    [(empty? lst) ...]
    [(cons? lst) ... (first lst) ...
                 ... (my-list-fn (rest lst)) ...])

Use this template to write a function cons-all that adds a given element to the front of each given sublist. This is related to FICS Exercises 23-25 (but you only need to write cons-all, not do those exercises).

The following test case illustrates the use of cons-all. You will need to use the language #lang htdp/bsl+ or "Beginning Student with List Abbreviations" or replace the use of ' in the following.

(check-expect (cons-all 3 '((2 4) () (5)))
              '((3 2 4) (3) (3 5)))

Before next lab

Before the lab

Questions

• Questions about Assignment 1?
• Questions about Assignment 2?

Setup

• make a directory labs/L07 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

Structural recursion on two parameters

• Form a group of 2 or 3.

• Work together to design the template in FICS Exercise 17

• Individually implement the function keep-first which follows this template.

• Compare your functions. Are there any interesting differences?

• Here is a test case

    (check-expect (keep-first (list 1 2 3 4) 3) (list 1 2 3))
  

• If that isn't enough for complete coverage for your solutions, add additional test cases.

Intersection of two ordered lists

Recall the template for structural recursion on two lists

(define (my-list-fn lst1 lst2)
  (cond
    [(empty? lst1) ... lst2 ...]
    [(empty? lst2) ... lst1 ...]
    [(cons? lst1)
        ... (first lst1) ... (first lst2) ...
        ... (my-list-fn (rest lst1) lst2) ...
        ... (my-list-fn lst1 (rest lst2)) ...
        ... (my-list-fn (rest lst1) (rest lst2)) ...]))

Use this template to complete FICS Exercise 20 You may find it helpful to refer to the function o-union defined in Section 5.4. Note that the fact that the lists are sorted is key an efficient solution here; you do not have to check that property.

Here are some test cases for the function intersection

(check-expect (intersection (list 1 2 3 4 5) (list 2 4 6 7))
              (list 2 4))

(check-expect (intersection (list 2 4 11) (list 1 2 3 4 5))
              (list 2 4))

Generating all subsets of fixed size

Start with the template from the first exercise and complete FICS Exercise 24. If your template needs updating, compare with cases in the two list template.

Use the built-in function append and the function cons-all you wrote in Lab 5.

Here are some test cases to illustrate the use of the function comb

(check-expect (comb '(a) 1) '((a)))
(check-expect (comb '(1 2) 1) '((1) (2)))
(check-expect (comb '(1 2 3) 2) '((1 2) (1 3) (2 3)))

Before next lab

Before the lab

Questions

• Questions about Assignment 2?

Setup

• make a directory labs/L08 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

Introducing foldr

• Form a group of 2 or 3.

• Work together to solve FICS Exercise 27

• Contracts were introduced in The Design Recipe

• Optionally write your contract in the form of a signature

• Here is an implementation of foldr, with the name changed so as not to conflict with the builtin. It is often easier to infer a type from a (simple) implementation.

(define (Foldr combine base lst)
  (cond
    [(empty? lst) base]
    [else (combine
            (first lst)
            (Foldr combine base (rest lst)))]))

Guess the function

This part of the lab is based on FICS Exercise 29

Fill in the two instances of ... in the following template with a builtin function so that the tests pass. Try some other values for mylist, mylist1, mylist2 to help you guess.

#lang htdp/isl+
(define mylist '(1 2 buckle my shoe))
(check-expect (foldr cons empty mylist) (... mylist))
(define mylist1 '(3 4 5))
(define mylist2 '(1 2))
(check-expect (foldr cons mylist1 mylist2) (... mylist2 mylist1))

• Do these uses of foldr fit your contract above? If not, how can you fix your contract.

Filter in terms of foldr

On your own, complete FICS Exercise 28

• You will have to rename the function to Filter to avoid colliding with the builtin filter.

• You will need to use the language htdp/isl+ or "Intermediate Student with Lambda"

• Your solution should pass the following test cases. odd? is a builtin function.

• The previous part (Ex. 29) may give you some ideas about how to do this part.

(check-expect (Filter (lambda (x) #f) '(1 2 3)) '())

(check-expect (Filter odd? '(0 1 2 3 4 5 6 7 8 9))
              (list 1 3 5 7 9))

Before next lab

Before the Lab

Background

• Node.js REPL
• JavaScript functions
• NodeJS test runner

Getting started

• make a directory labs/L09 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

Questions

• Questions about Quiz 1?
• Questions about Assignment 2?

Running JavaScript

In a file

• Create a new file ~/cs2613/labs/L09/hello-world.js
• Add some JavaScript code, save

    console.log("Hello world");

Running a script

• open a terminal, find the right directory

  $ node hello-world.js

• commit your file

In a Browser

• Start Firefox

• Open the "Web Console" with Ctrl-Shift-K (or navigate via the "hamburger menu" to "Web Developer -> Web Console" ).

• Select the tab "Console"

• Copy-paste the code in.

In the REPL

• Start up a node repl

  $ node

• Load your code into the repl

    > .load hello-world.js
  

• Evaluate some expressions

    > 1 + 1
    > "Hello " + "world!"
  

JavaScript equality and type coercion

From Eloquent JavaScript Chapter 1, and the WAT talk by Gary Bernhardt, we know that type coercion is an important part of evaluating JS expressions. This is sometimes useful

> 42 + 'is a big number'

But just as often a source of errors and confusion.

> "" + 1
> x=""
> x++

One operator where type coercion can be particularly surprising is the standard equality test ==. Not only does type coercion apply:

> "" == 0
> false == 0
> "" == 0

but special rules apply to "undefined" and "null"

> false == undefined
> undefined == null
> undefined == undefined

even though they would normally be considered falsy (considered false in boolean contexts).

   > if (undefined) { console.log("truthy") } else { console.log("falsey") }

NaN is another falsy value not == to the other falsy values, not even itself:

   > NaN == undefined
   > NaN == NaN

To avoid this twisty maze of "helpful" type coercion, you can use the "strict equality" checker ===

   > "" === 0
   > false === 0
   > "" === 0
   > false === undefined
   > undefined === null
   > undefined === undefined

Javascript functions

Reference for this section is JavaScript functions Like Racket, JavaScript has two different ways of defining functions. The first way is by assigning an anonymous function to a variable.

    (define square (lambda (x) (* x x)))

    let square = x => x*x;
    let square2 = function (x) {return x*x};

• Answer the following questions in your journal:

  • How is assignment (=) in javascript different from binding (let, define) in Racket?

  • return is mandatory. What does it mean?

  • what is the difference between the two kinds of anonymous functions in JavaScript? Hint: the first example is an arrow function.

The more compact way of defining functions in both Racket and JavaScript combines the binding and creation of a function/lambda

    (define (square x) (* x x))

    function square(x) { return x*x }

• Start a new file ~/cs2613/labs/L09/loop-arith.js, and fill in the following definition for mult using plus and for.

const plus = (a,b) => {
    for (let i=0; i < a; i++){
        b++;
    }
    return b;
}

const mult = function (a,b) {
    sum=0;



    return sum;
}

• Test your file manually, using e.g. the node REPL.

Node test runner

In order to provide similar functionality to check-expect in racket, we will use the nodejs test framework.

In order to use the test runner, we need to add two lines to the beginning of our javascript files.

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

We'll talk more about both const and require later.

A test is considered to pass if it does not throw an exception. assert provides several functions useful for this kind of test. We will concentrate on assert.strictEqual for now, which corresponds to the === test discussed above.

Here is a complete example with one passing test and one failing one

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

function add1(n) {
    return n+1;
}

test('one plus one is two', (t)=>assert.strictEqual(add1(1),2));
test('one plus one is three', (t)=>assert.strictEqual(add1(1),3));

Test coverage

We will use an experimental feature of node v20 in order to make sure we have test coverage (analogous to how we set up DrRacket for visual test coverage).

Getting a coverage report

• Run our sample program from above with arguments to node to see a test coverage report.

   $ node --test --experimental-test-coverage sample.js
  

• All going well, your output should contain something like

ℹ start of coverage report
ℹ ---------------------------------------------------------
ℹ file      | line % | branch % | funcs % | uncovered lin…
ℹ ---------------------------------------------------------
ℹ sample.js | 100.00 |   100.00 |  100.00 |
ℹ ---------------------------------------------------------
ℹ all files | 100.00 |   100.00 |  100.00 |
ℹ ---------------------------------------------------------
ℹ end of coverage report

Writing tests

• Add tests to your loop-arith.js solution until you have complete coverage.

• Check your work for test coverage.

• Make sure your tests pass as well as having coverage.

Before the next lab

Before the lab

Questions

• Questions about Quiz 1?
• Questions about Assignment 2?
• About JavaScript functions?
• About the node test framework?

Deep Comparison

Follow the Deep Comparison Exercise to write a function deepEqual that passes the following tests. assert uses something very similar for the deepStrictEqual test used below. Your function should pass the following tests.

let obj = {here: {is: "an"}, object: 2};
test("self", (t)=> assert.strictEqual(deepEqual(obj,obj),true));
test("null", (t)=> assert.strictEqual(deepEqual(null,null),true));
test("!null", (t)=> assert.strictEqual(deepEqual(null,obj),false));
test("different", (t)=>
    assert.strictEqual(deepEqual(obj, {here: 1, object: 2}),false));
test("equivalent", (t)=>
    assert.strictEqual(deepEqual(obj, {here: {is: "an"}, object: 2}),true));

Remember from L09 that you need the following lines to use the test framework

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

JavaScript Arrays

JavaScript supports arrays. They are actually implemented as objects, which leads to some slightly surprising behaviour:

> x=[]
> x[10]=1
> x
> x["bob"] = 2
> x

Generating arrays

Follow the (first part of the) Sum of a Range Exercise to write a range function that passes the following tests.

test("empty", (t)=>assert.deepStrictEqual(range(2,1),[]));
test("single", (t)=> assert.deepStrictEqual(range(2,2),[2]));
test("multiple", (t)=>
    assert.deepStrictEqual(range(42,50),[42,43,44,45,46,47,48,49,50]));

Arrays Continued

Follow the (second part of the) Sum of a Range Exercise to write a sum function that passes the following tests.

test("empty", (t)=> assert.strictEqual(sum([]),0));
test("single", (t)=> assert.strictEqual(sum([2]),2));
test("multiple", (t)=> assert.strictEqual(sum(range(1,10)),55));

Adding step argument to range.

Add an optional step argument to the range function so that the following tests pass. The original tests should keep passsing, that's a big part of the point of having unit tests.

test("step 2", (t)=> assert.deepStrictEqual(range(1,10,2),[1,3,5,7,9]));
test("step -1", (t)=> assert.deepStrictEqual(range(5,2,-1),[5,4,3,2]));

Before next lab

Instructions

1. The real quiz is individual, so do this one on your own.

2. Save your answers to a directory labs/L11/ in your cs2613 git repository. Commit and push to https://vcs.cs.unb.ca before 10:20AM. Try to complete the practice quiz in under 1h, to get practice working under time pressure.

3. This practice quiz is open book. You can use

   1. The local mirror of A Functional Introduction Computer Science (FICS), linked from multiple labs or directly from

      https://www.cs.unb.ca/~bremner/teaching/cs2613/books/FICS/

   2. The local Racket documentation (run raco docs, or the drracket help menu).

   3. Other parts of the course web site

   4. Your own notes and work from previous labs and assignments.

Questions

Write a function steamroller that returns a list of the numbers, symbols and strings in a given list in order. In particular your function should pass the following tests.

(check-expect (steamroller empty) empty)
(check-expect (steamroller '(() ())) empty)
(check-expect (steamroller '((a) (b))) '(a b))
(check-expect (steamroller '(((a 1) (b 1)) ((c 2) (d 2) )))
              '(a 1 b 1 c 2 d 2))

Notice the behaviour in the last test is to completely flatten the list. Start with the following template for structural recursion on lists

(define (steamroller lst)
  (cond
    [(empty? lst) ...]
    [(cons? lst) ... (first lst) ...
                 ... (steamroller (rest lst)) ...]))

Good solution

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

• Pass the tests above.
• Be reasonably indented and use reasonable variable names.
• Have full test coverage.
• Use language “htdp/isl+” (Intermediate Student with lambda)
• Only use builtins from the following list
  • define, cond, if
  • list?, empty?, cons?
  • first, rest, empty, cons, list
  • foldr
  • append (but only for this part, not the next).

Full marks

For full marks

• Satisfy the conditions above, and
• Do not use the builtin function append (you may write your own function that does the same thing if you want).
• Add at least two good tests and explain what you are testing.

There is no lab on February 17, 2025.

Before the lab

A Vector class

Do the Vector Type exercise.

test("addition", (t) =>
    assert.deepStrictEqual(new Vec(1, 2).plus(new Vec(2, 3)),
                           new Vec(3,5)));
test("subtraction", (t)=>
    assert.deepStrictEqual(new Vec(1, 2).minus(new Vec(2, 3)),
                           new Vec(-1,-1)));
test("length", (t) =>
    assert.strictEqual(new Vec(3, 4).length,5));

A Set ("Group") class

Do the Group exercise. Instead of the suggested array, use an object to store the elements of the "Group". The simplest way to implement from is to loop over the iterable argument and repeatedly call add.

const test=require("node:test");
const assert=require("assert");
class Group {
    constructor() {
        this.elements={}
    }
    add(element) {
        this.elements[element]=true;
    }
    has(element) {
    }
    delete(element) {
    }
    static from(iterable) {
    }
}
// move this inside tests to avoid race conditions
let group = Group.from([10, 20]);
test("has yes",(t)=>assert.strictEqual(group.has(10),true));
test("has no",(t)=>assert.strictEqual(group.has(30),false));
test("add existing is not error", (t)=>group.add(10));
test("delete existing", (t) => {
    group.delete(10);
    assert.strictEqual(group.has(10),false);
});

Symbols

You might remember symbols from Racket. It turns out JavaScript has something similar (but more confusing). Just like strings, Symbols can be used as keys (e.g. method names for objects). Here we rely on a predefined value to be able to call a method. In the last part of the lab, you will use the global Symbol.iterator as a method name.

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

let sym=Symbol("my cool symbol name");

test("uniqueness",
     (t)=>assert.notEqual(sym, Symbol("my cool symbol name")));

class Thing {
    constructor() {
        this.count=0;
    }
    // note the syntax to define indirect method names
    [sym]() {
        return this.count++;
    }
}

test("call",
     (t)=> {
         let x = new Thing();
         assert.strictEqual(x[sym](),0);
         assert.strictEqual(x[sym](),1);
     });

Iterable class

Do the Iterable Group exercise.

Start by adding the following two methods to your Group class.

    // Utility function for iterator class
    keys() {
        return Object.keys(this.elements);
    }
    // Mark this class as iterable.
    [Symbol.iterator]() {
        return new GroupIterator(this);
    }

Next create a GroupIterator class.

class GroupIterator {
    constructor(group) {
        this.index=0;
        this.group=group;
    }
    next() {
    }
}

Refer to the MatrixIterator class for inspiration, but note that you should always return an object with a value property. When you are done, the following test should pass.

test("iterate", (t) => {
    let vals=[];
    for (let value of Group.from(["a", "b", "c"])) {
        vals.push(value+value);
    }
    assert.deepStrictEqual(vals,["aa","bb","cc"]);
});

Before next lab

Before the lab

Background

• node.js filesystem API
• Promises API
• Async Functions

Callback Chaining

The recommended way to get maximimum performance from the node.js filesystem API is to use callbacks, i.e. functions to call when the I/O operation completes.

Replace the ALL-CAPITALS words in the following code sample with defined identifiers to make this callback chaining example work.

const fs=require("node:fs");

function log(string, next) {
    let date = new Date();
    function finish(err) {
        if (err) throw err;
        console.timeEnd("write");
        CALLBACK();
    }
    function write(err, fd) {
        if (err) throw err;
        fs.write(VALUE, date.toISOString() + ": " + string, CALLBACK);
    }
    console.time("write");
    fs.open("log.txt", "a", CALLBACK)
}

console.time("log");
log("first\n",
    () => {
        log("second\n",
            () => console.log("done"));
    });
console.timeEnd("log");

When you get the code working, the file log.txt should contain lines like the following (the exact date and time may differ):

2024-10-25T17:31:56.626Z: first
2024-10-25T17:31:56.629Z: second

Questions for your journal:

• Why are the functions write and finish defined inside log?
• What can you tell about the execution order from the printed output?
• Based on the printed timings, does it make sense to use asynchronous I/O to write a single string to a file?

Promises

In the Promises API file system methods return a Promise object that automates the chaining of callbacks. These Promise objects can be chained together using then. Fill in the appropriate API calls (they should be very similar to the first part, without the explicit callbacks).

const fs=require("node:fs/promises");

function log(string) {
    let date = new Date();
    return new Promise(next=> {
        console.time("write");
        API_CALL
            .then(fd=>API_CALL)
            .then(()=>console.timeEnd("write"))
            .then(CALLBACK)
            .catch((err) => console.log(err));
    });
}

console.time("log");
log("first\n")
    .then(()=>log("second\n"))
    .catch((err) => console.log(err));
console.timeEnd("log");

Questions for your journal:

• According to the NodeJS Documentation, what is one disadvantage of the Promises API?

• What does the Promise.catch method do?

Async Functions

Async Functions provide some nice features for programming with Promises, essentially eliminating some of the boilerplate from our previous example. They also introduce one very important keyword.

Replace the ALL-CAPITALS parts of the following program to duplicate the functionality of the previous versions.

const fs=require("node:fs/promises");

async function log(string) {
    console.time("write")
    const fd = MAGIC_KEYWORD API_CALL()
    let date = new Date();

    const promise=API_CALL();
    console.timeEnd("write");
    return promise;
}

console.time("log");
log("first\n")
    .then(()=>log("second\n"))
    .catch((err) => console.log(err));
console.timeEnd("log");

• What is the keyword used as MAGIC_KEYWORD above, and what does it do?

Before Next Lab

Before the Lab

Questions

• Questions about Quiz 2?

Getting Started

• Make a directory ~/cs2613/labs/L14

• Download Work.zip and unzip in your newly created directory.

Mortgage Calculator

Do exercises 1.7 and 1.8 from Python Numbers

Introduction to Python strings

Do exercises 1.13, 1.14, 1.15 from Python Strings

Pytest

• In a terminal run

    pipx install --include-deps unb-cs2613
    rehash
  

• Save the following sample code (based on Exercise 1.19) to a file listex.py in the directory you created above.

symbols = 'HPQ,AAPL,IBM,MSFT,YHOO,DOA,GOOG'
symlist = symbols.split(',')

def test_lookup0():
    assert symlist[0] == 'HPQ'

def test_lookup1():
    assert symlist[1] == 'AAPL'

• In ~/cs2613/labs/L14, run

    pytest listex.py
  

• You should see

[student@id414m22 L14]$ pytest listex.py
=================== test session starts ===================
platform linux -- Python 3.9.18, pytest-7.4.3, pluggy-1.3.0
rootdir: /home1/ugrad/student/cs2613/labs/L14
plugins: pylama-8.4.1, cov-4.1.0
collected 2 items

listex.py ..                                        [100%]

==================== 2 passed in 0.02s ====================

• Modify one of the tests so it fails. Run pytest again.

• Question for your journal: what are three ways failing tests are indicated?

Lists and Pytest

• For each of the remaining interactive evaluations in Exercise 1.19, add a corresponding test to listex.py.

• make sure each test_* function (def) has a unique name.

• if you want, you can have multiple asserts in a single test.

• Questions for your journal:

  • what are some differences between == in JavaScript and Python?
  • based on what you have seen so far, what are similarities and differences between the node test framework and pytest

Functions and coverage

We have already been using python functions for pytest, without really thinking about how they work. In Part 1.7 of Practical Python, functions are explained.

• Consider the sumcount function

def sumcount(n):
    '''
    Returns the sum of the first n integers
    '''
    total = 0
    while n > 0:
        total += n
        n -= 1
    return total

• Make a recursive version of this function.

• Add sufficient pytest tests for both versions of the function.

• Check your test(s) for coverage with

    pytest --cov=sum --cov-report=term-missing sum.py
  

  (assuming your file is called sum.py)

Before next lab

There is no labs the week of March 3, 2025.

Before the Lab

Getting Started

• Make a directory ~/cs2613/labs/L16
• Download Work.zip and unzip in your newly created directory.

Files

• Do Exercise 1.26.

• Convert the interactive demos to pytest tests. You can replace print with appending to a list.

Data types

• Exercise 2.1

• Exercise 2.2. Instead of using the REPL for this one, write functions parse_row, compute_cost, and update_dict so that the following tests pass.

def test_cost():
    d = parse_row(row)
    cost = compute_cost (d)
    assert cost == pytest.approx(3220.000,abs=0.00000001)

def test_d():
    d = parse_row(row)
    update_dict(d)
    assert d == {'name': 'AA', 'shares': 75, 'price':32.2, 'date': (6, 11, 2007),
                 'account': 12345}

Containers: read_portfolio

• Exercise 2.4. Embed the following tests in report.py, and make sure they pass.

def test_read():
    portfolio = read_portfolio('Data/portfolio.csv')
    assert portfolio == \
        [('AA', 100, 32.2), ('IBM', 50, 91.1),
         ('CAT', 150, 83.44), ('MSFT', 200, 51.23),
         ('GE', 95, 40.37), ('MSFT', 50, 65.1), ('IBM', 100, 70.44)]

def test_total():
    portfolio = read_portfolio('Data/portfolio.csv')
    total = 0.0
    for name, shares, price in portfolio:
        total += shares*price
    assert total == pytest.approx(44671.15,abs=0.001)

• Exercise 2.5. Call this version report2.py Embed the following tests in report2.py, and make sure they pass.

def test_read():
    portfolio = read_portfolio('Data/portfolio.csv')
    assert portfolio == \
        [{'name': 'AA', 'shares': 100, 'price': 32.2}, {'name': 'IBM', 'shares': 50, 'price': 91.1},
         {'name': 'CAT', 'shares': 150, 'price': 83.44}, {'name': 'MSFT', 'shares': 200, 'price': 51.23},
         {'name': 'GE', 'shares': 95, 'price': 40.37}, {'name': 'MSFT', 'shares': 50, 'price': 65.1},
         {'name': 'IBM', 'shares': 100, 'price': 70.44}]

def test_total():
    portfolio = read_portfolio('Data/portfolio.csv')

    total = 0.0
    for s in portfolio:
        total += s['shares']*s['price']
    assert total == pytest.approx(44671.15,abs=0.001)

Sequences

• Exercise 2.13,2.14

• Exercise 2.17. For this one build a script embedding the following tests.

• Use list() to fix the following test

def test_items():
    assert prices.items() == \
        [('GOOG', 490.1), ('AA', 23.45), ('IBM', 91.1), ('MSFT', 34.23)]

• Question for your journal: what is list() being used for in this section?
• Embed the following tests and make sure they pass

def test_zip():
    assert pricelist == \
        [(490.1, 'GOOG'), (23.45, 'AA'), (91.1, 'IBM'), (34.23, 'MSFT')]

def test_min_max():
    assert min(pricelist) == (23.45, 'AA')
    assert max(pricelist) == (490.1, 'GOOG')

• Question for your journal: What is this kind of ordering of tuples usually called?
• Add a test for last part of 2.17 about different input length lists

List Comprehensions

• Exercise 2.19

• Exercise 2.20. Start with the following skeleton, and convert the given examples into pytest tests.

import pytest
from report2 import read_portfolio
prices = {
        'GOOG' : 490.1,
        'AA' : 23.45,
        'CAT': 35.46,
        'IBM' : 91.1,
        'MSFT' : 34.23,
        'GE': 13.48,
    }

Note that the value test will need to be adjusted for a value of approximately 31167.10, since our price list is different from the one used in the book.

Before next lab

Before the Lab

Getting Started

• Make a directory ~/cs2613/labs/L17
• Download Work.zip and unzip in your newly created directory.

Higher order functions

• Complete Exercise 3.5. Note that you are given an initial version of fileparse.py containing a function parse_csv in Exercise 3.4 just above. Make sure that your modified function passes the following test.

def test_portfolio():
    portfolio = parse_csv('Data/portfolio.csv', types=[str, int, float])
    assert portfolio == [{'price': 32.2, 'name': 'AA', 'shares': 100},
                         {'price': 91.1, 'name': 'IBM', 'shares': 50},
                         {'price': 83.44, 'name': 'CAT', 'shares': 150},
                         {'price': 51.23, 'name': 'MSFT', 'shares': 200},
                         {'price': 40.37, 'name': 'GE', 'shares': 95},
                         {'price': 65.1, 'name': 'MSFT', 'shares': 50},
                         {'price': 70.44, 'name': 'IBM', 'shares': 100}]

def test_shares():
    shares_held = parse_csv('Data/portfolio.csv', select=['name', 'shares'], types=[str, int])
    assert shares_held == [{'name': 'AA', 'shares': 100}, {'name': 'IBM', 'shares': 50},
                           {'name': 'CAT', 'shares': 150}, {'name': 'MSFT', 'shares': 200},
                           {'name': 'GE', 'shares': 95}, {'name': 'MSFT', 'shares': 50},
                           {'name': 'IBM', 'shares': 100}]

• Question for your journal: what is the type of the argument types?

Refactoring a function

• Complete Exercise 3.6. You only need to write a few lines of code, but you will need to make several blocks of code conditional on has_headers. Be careful when re-indenting code, remember Python is picky about indentation.

• Make sure the following test (and your previous tests) pass

def test_tuple():
    prices = parse_csv('Data/prices.csv', types=[str,float], has_headers=False)
    assert prices == [('AA', 9.22), ('AXP', 24.85), ('BA', 44.85), ('BAC', 11.27),
                      ('C', 3.72), ('CAT', 35.46), ('CVX', 66.67), ('DD', 28.47),
                      ('DIS', 24.22), ('GE', 13.48), ('GM', 0.75), ('HD', 23.16),
                      ('HPQ', 34.35), ('IBM', 106.28), ('INTC', 15.72), ('JNJ', 55.16),
                      ('JPM', 36.9), ('KFT', 26.11), ('KO', 49.16), ('MCD', 58.99),
                      ('MMM', 57.1), ('MRK', 27.58), ('MSFT', 20.89), ('PFE', 15.19),
                      ('PG', 51.94), ('T', 24.79), ('UTX', 52.61), ('VZ', 29.26),
                      ('WMT', 49.74), ('XOM', 69.35)]

JavaScript Quiz

The second half of the lab will be a quiz on JavaScript

Before next lab

Before the Lab

Getting started

• Make a directory ~/cs2613/labs/L18
• Download Work.zip and unzip in your newly created directory.
• Download Part of the textbook solution to Exercise 3.18

Methods

• Start from the following skeleton class

  class Stock:
    def init(self, name, shares, price):
        self.name=name
        self.shares=shares
        self.price=price

• Complete Exercise 4.2; in particular add methods cost and sell to your Stock class so that the following tests pass.

def test_cost2():
    s = Stock('GOOG', 100, 490.10)
    assert s.cost() == pytest.approx(49010.0,0.001)

def test_sell():
    s = Stock('GOOG', 100, 490.10)
    s.sell(25)
    assert s.shares == 75
    assert s.cost() == pytest.approx(36757.5, 0.001)

Special Methods

• Complete Exercise 4.9. In particular add the appropropriate method to the Stock class so that the following test passes.

def test_repr():
    goog = Stock('GOOG', 100, 490.1)
    assert repr(goog) == "Stock('GOOG', 100, 490.1)"

Static methods

• Using the code of Exercise 4.3 as a hint, add the static method read_portfolio to the Stock class.

    @staticmethod
    def read_portfolio(filename):
        # code from 4.3 goes here

Your completed static method should pass

def test_read_portfolio():
    portfolio = Stock.read_portfolio('Data/portfolio.csv')
    assert repr(portfolio[0:3]) == \
        "[Stock('AA', 100, 32.2), Stock('IBM', 50, 91.1), Stock('CAT', 150, 83.44)]"

• Question for your journal: what feature of the repr function does this test demonstrate?

Inheritance

Start with following class hierarchy based on Exercises 4.5 and 4.6

class TableFormatter:
    def headings(self, headers):
        '''
        Emit the table headings.
        '''
        raise NotImplementedError()

    def row(self, rowdata):
        '''
        Emit a single row of table data.
        '''
        raise NotImplementedError()

class TextTableFormatter(TableFormatter):
    '''
    Emit a table in plain-text format
    '''
    def headings(self, headers):
        
        output = ''
        for h in headers:
            output += f'{h:>10s} '
        output+='\n'
        output+=(('-'*10 + ' ')*len(headers))
        output += '\n'
        return output
    
    def row(self, rowdata):
        output = ''
        for d in rowdata:
            output+=f'{d:>10s} '
        output += '\n'
        return output

def test_text_2():
    portfolio=stock.Stock.read_portfolio('Data/portfolio.csv')
    formatter= TextTableFormatter()
    output= formatter.headings(['Name','Shares','Price', 'Cost'])
    for obj in portfolio[0:3]:
        output +=formatter.row([obj.name,f'{obj.shares}',
                                f'{obj.price:0.2f}',f'{obj.cost():0.2f}'])

    assert '\n' + output == '''
      Name     Shares      Price       Cost 
---------- ---------- ---------- ---------- 
        AA        100      32.20    3220.00 
       IBM         50      91.10    4555.00 
       CAT        150      83.44   12516.00 
'''

• Define an appropriate method so that the str function for Stock instances returns the same output as in one (non-heading) row of the given test.

• Define a new class StockTableFormatter that uses the str builtin function for Stock objects and passes the following test

 
def test_string_1():
    portfolio=stock.Stock.read_portfolio('Data/portfolio.csv')
    formatter= StockTableFormatter()
    output= formatter.headings(['Name','Shares','Price', 'Cost'])
    for obj in portfolio[0:3]:
        output +=formatter.row(obj)

    assert '\n' + output == '''
      Name     Shares      Price       Cost 
---------- ---------- ---------- ---------- 
        AA        100      32.20    3220.00 
       IBM         50      91.10    4555.00 
       CAT        150      83.44   12516.00 
'''

• Note that both the test test_text_2 and test_string_1 are sensitve to whitespace, so be careful when copying the strings.

Before next lab

Before the lab

Getting started

• Make a directory ~/cs2613/labs/L18
• Download Work.zip and unzip in your newly created directory.

Generators and iterator classes

Consider the countdown generator from Section 6.2

def countdown(n):
    print('Counting down from', n)
    while n > 0:
        yield n
        n -= 1

Referring to Section 6.1 an equivalent iterator class. Here we will implement the entire protocol with one class, but multiple classes like we did for JavaScript is also reasonable. Modify only the __next__ method of the following skeleton class so that given tests pass.

def countdown(n):
    yield 'starting'
    while n > 0:
        yield n
        n -= 1

def test_generator():
    counter = countdown(3)
    assert [ t for t in counter ] == \
        ['starting', 3,  2,  1]

class Counter:
    "Iterator class simulating countdown"
    def __init__(self,n):
        self.n = n
        self.first = True

    def __iter__(self):
        return self
    
    def __next__(self):
        # insert code here
        self.n -= 1
        return self.n+1

def test_class():
    counter = Counter(3)
    assert [ t for t in counter ] == \
        ['starting', 3,  2,  1]

What is __iter__ for?

Update the __iter__ method of your previous solution so that the following additional test passes

def test_twice():
    counter = Counter(3)
    assert [ t for t in counter ] == \
        ['starting', 3,  2,  1]
    assert [ t for t in counter ] == \
        ['starting', 3,  2,  1]

• Question for your journal: what is an important functionality difference between generators and more general iterators?

Using Generators I

Do Exercises 6.5 and 6.6.

Note that 6.5 just asks you to run some code, but you do have to be in the correct directory when running it.

For 6.6, you essentially need to split the given code so that the first part is the new generator follow.

Using Generators II

Start with the following stock related classes:

portfolio.py
Tue 18 Mar 2025 04:03:40 PM

fileparse.py
Tue 18 Mar 2025 04:03:40 PM

tableformat.py
Tue 18 Mar 2025 04:03:40 PM

stock.py
Tue 18 Mar 2025 04:03:40 PM

report.py
Tue 18 Mar 2025 04:03:40 PM

Complete Exercise 6.7. I suggest you make a new file follow2.py so that you preserve solutions for 6.6 and 6.7.

Before the lab

Background

We will mainly rely on the Octave Interpreter Reference. A more tutorial style guide is the Gnu Octave Beginner's Guide, which is available in ebook form from the UNB library.

We'll refer to the online text by Robert Beezer for linear algebra background. We can happily ignore the stuff about complex numbers.

Running Octave

• There is a GUI accessible from Applications -> FCS -> GNU Octave, or by running from the command line

    % octave --gui
  

• There is also a REPL accessible from the command line by running

    %  octave
  

• To sanity check your octave setup, run the following plots

    >> surf(peaks)
    >> contourf(peaks)
  

Recursive Fibonacci

Here is a JavaScript recursive function for Fibonacci:

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

Let's translate this line by line into an Octave function.

Save the following in ~/cs2613/labs/L20/recfib.m; the name of the file must match the name of the function.

function ret = recfib(n)
  if (n <= 0)
    ret = 0;
  elseif (n <= 2)
    ret = 1;
  else
    ret = recfib(n-1) + recfib(n-2);
  endif
endfunction

Like the other programming languages we covered this term, there is a built in unit-test facility that we will use. Add the following to your function

%!assert (recfib(0) == 0);
%!assert (recfib(1) == 1);
%!assert (recfib(2) == 1);
%!assert (recfib(3) == 2);
%!assert (recfib(4) == 3);
%!assert (recfib(5) == 5);

• Note the %! assert. These are unit tests that can be run with

    >> test fib
  

• The syntax for %!assert is a bit fussy, in particular the parentheses are needed around the logical test.

Questions for your journal

• How are values returned from functions in octave?

Table based Fibonacci

A powerful technique for making recursive A more problem specific approach (sometimes called dynamic programming) is to fill in values in a table.

Save the following in ~/cs2613/labs/L20/tabfib.m. Complete the missing line by comparing with the recursive version, and thinking about the array indexing.

function ret = tabfib(n)
  table = [0,1];
  for i = 3:(n+1)
    table(i)=
  endfor
  ret = table(n+1);
endfunction

%!assert (tabfib(0) == 0);
%!assert (tabfib(1) == 1);
%!assert (tabfib(2) == 1);
%!assert (tabfib(3) == 2);
%!assert (tabfib(4) == 3);
%!assert (tabfib(5) == 5);

Questions for your journal

• What are two important differences about array access in Octave compared to Python and JavaScript?

Performance comparison

Let's measure how much of a speedup we get by using a table.

Of course, the first rule of performance tuning is to carefully test any proposed improvement. The following code gives an extensible way to run simple timing tests, in a manner analogous to the Python timeit method, whose name it borrows.

# Based on an example from the Julia microbenchmark suite.

function timeit(func, argument, reps)
    times = zeros(reps, 1);

    for i=1:reps
      tic(); func(argument); times(i) = toc();
    end

    times = sort(times);
    fprintf ('%s\tmedian=%.3fms mean=%.3fms total=%.3fms\n',func2str(func), median(times)*1000,
             mean(times)*1000, sum(times)*1000);
endfunction

We can either use timeit from the octave command line, or build a little utility function like

function bench
  timeit(@recfib, 25, 10)
  timeit(@tabfib, 25, 10)
endfunction

Questions for your journal

• What are the new features of Octave used in this sample code?

• Roughly how much speedup is there for using tables to compute the 25th fibonacci number?

Using a constant amount of storage.

As a general principle we may want to reduce the amount of storage used so that it doesn't depend on the input. This way we are not vulnerable to e.g. a bad input crashing our interpreter by running out of memory. We can improve tabfib by observing that we never look more than 2 back in the table. Fill in each blank in the following with one variable (remember, ret is a variable too).

function ret = abfib(n)
  a = 0;
  b = 1;
  for i=0:n
    ret = _ ;
    a = _ ;
    b = _  + b ;
  endfor
endfunction

%!assert (abfib(0) == 0);
%!assert (abfib(1) == 1);
%!assert (abfib(2) == 1);
%!assert (abfib(3) == 2);
%!assert (abfib(4) == 3);
%!assert (abfib(5) == 5);

• This algorithm is quite tricky. To understand how to fill in the blanks
  • what happens for n==0 (first blank)
  • what happens for n==1 (second blank)
  • in loop repetition i, b is assigned to (i+2)nd Fibonacci number.
• Check the change in performance with the following. Although not as spectacular as repacing recursion (in Octave), there should be a noticable speedup.

function bench2
  timeit(@tabfib, 42, 10000)
  timeit(@abfib, 42, 10000)
endfunction

Fibonaccci as matrix multiplication

The following is a well known identity about the Fibonacci numbers F(i).

[ 1, 1;
  1, 0 ]^n = [ F(n+1), F(n);
               F(n),   F(n-1) ]

This can be proven by induction; the key step is to consider the matrix product

 [ F(n+1), F(n);   F(n),   F(n-1) ] * [ 1, 1; 1, 0 ]

Since matrix exponentiation is built-in to octave, this is particularly easy to implement the formula above in octave

Save the following as ~/cs2613/labs/L20/matfib.m, fill in the two matrix operations needed to complete the algorithm

function ret = matfib(n)
  A = [1,1; 1,0];


endfunction

%!assert (matfib(0) == 0);
%!assert (matfib(1) == 1);
%!assert (matfib(2) == 1);
%!assert (matfib(3) == 2);
%!assert (matfib(4) == 3);
%!assert (matfib(5) == 5);
%!assert (matfib(6) == 8);
%!assert (matfib(25) == 75025);

We can expect the second Fibonacci implementation to be faster for two distinct reasons

• It's possible to compute matrix powers rather quickly (O(log n) compared O(n)), and since the fast algorithm is also simple, we can hope that octave implements it. Since the source to octave is available, we could actually check this.

• Octave is interpreted, so loops are generally slower than matrix operations (which can be done in a single call to an optimized library). This general strategy is called vectorization, and applies in a variety of languages, usually for numerical computations. In particular most PC hardware supports some kind of hardware vector facility.

• For the following, you will need either your solutions from last time, or to download timeit.m and tabfib.m. Note that the code here assumes the repetitions come first for timeit, as expected by the version for this lab.

function bench3
  timeit(@tabfib, 42, 10000)
  timeit(@matfib, 42, 10000)
endfunction

Before next lab

Before the lab

Broadcasting

In Octave we can multiply every element of a matrix by a scalar using the .* operator

A=[1,2,3;
   4,5,6];
B=A.*2

In general .* supports any two arguments of the same size.

C=A .* [2,2,2; 2,2,2]

It turns out these are actually the same operation, since Octave converts the first into the second via broadcasting

Quoting from the Octave docs, for element-wise binary operators and functions

The rule is that corresponding array dimensions must either be equal, or one of them must be 1.

In the case where one if the dimensions is 1, the smaller matrix is tiled to match the dimensions of the larger matrix.

Here's another example you can try.

x = [1 2 3;
     4 5 6;
     7 8 9];

y = [10 20 30];

x + y

Reshaping arrays

One potentially surprising aspect of Octave arrays is that the number of dimensions is independent from the number of elements. We can add as many dimensions as we like, as long as the only possible index in those dimensions is 1. This can be particularly useful when trying to broadcast with higher dimensional arrays.

     ones(3,3,3) .* reshape([1,2,3],[1,1,3])
     ones(3,3,3) .* reshape([1,2,3],[1,3,1])

Scaling layers of arrays

Complete the following function. You may want to copy the definitions of A and B into the REPL to understand the use of cat.

## usage: scale_layers(array, weights)
##
## multiply each layer of a 3D array by the corresponding weight
function out = scale_layers(array, weights)
  out =
endfunction

%!test
%! onez = ones(3,3);
%! A=cat(3,onez, 2*onez, 3*onez);
%! B=cat(3,onez, 6*onez, 15*onez);
%! assert(scale_layers(A,[1;3;5]),B)

Scaling a colour channel

Save the image above left as ~/cs2613/labs/L21/paris.jpg (make sure you get the full resolution image, and not the thumbnail).

Run the following demo code; you can change the weight vector for different colourization.

paris=imread("paris.jpg");
sepia=scale_layers(paris,[0.9,0.62,0.34]);
imshow(sepia);

You should get something like the following

The second half of the lab will be a quiz on Python.

Before next lab

Before the lab

Converting to monochrome

Either for creative reasons, or as part of a more complex image processing task, it is common to convert images to monochrome.

Save the following image as ~/cs2613/labs/L21/owl.jpg (make sure you get the full resolution image, and not the thumbnail).

Complete the following function using scale layers

function out = monochrome(in, weights=[0.21,0.72,0.07])
  out =
endfunction

Run the monochrome function on owl.jpg, you should get something like the following.

Try a few different values of weight vectors, see if you can generalize some rules from your experiments.

Gradient

One useful operation on images is to detect how they are changing locally. Roughly speaking the gradient can be thought about as specifying both how much the intensity is changing, and what direction that change is happening in. Octave returns that information as an (x,y) vector in the usual parallel array way.

A = [0,0,0,0,0,1;
     0,1,1,1,0,0;
     0,1,1,1,0,1;
     0,1,1,1,1,0;
     0,1,1,1,1,0;
     0,0,0,0,0,0];

[Dx, Dy] = gradient(A);

imshow(A);
figure;
imshow(Dx);
figure;
imshow(Dy);

Complete the follow function, by combining the Dx and Dy arrays into a single array such that normimg(i,j) = norm([Dx(i,j),Dy(i,j)]). Don't use a loop. The demo should produce an image somewhat like the one below.

function normimg = normgrad(img)
  [Dx, Dy] = gradient(img);
  normimg = 
endfunction

%!demo
%! owl=imread("owl.jpg");
%! monowl=monochrome(owl);
%! ng = normgrad(monowl);
%! imshow(ng*2, [0,20]);

Thresholding: overexposure detection

One common feature of photo editing software (or camera firmware) is to highlight overexposed or underexposed pixels. In this exercise we will use our solutions for scale layers (from L21) and monochrome in order to mark the pixels above a certain level.

Download the following image (make sure you download the actual full resolution image) and save it as ~/cs2613/labs/L22/leaf.jpg.

Use the builtin function find to complete the threshold function to find all pixel positions with value higher than a given threshold. Note that this use of find depends on broadcasting. In all of the calls to plot in this lab, you may want to adjust markersize to better see the selected pixels (it depends a bit on screen resolution and image size).

function [rows, cols] = threshold(in, lower=100)
  [rows,cols] =
endfunction

%!test
%! A=[1,2,3; 4,5,6];
%!  [rows,cols]=threshold(A,4);
%!  assert(rows==[2;2]);
%!  assert(cols==[2;3]);

%!demo
%! leaf=imread("leaf.jpg");
%! monoleaf=monochrome(leaf);
%! [rows, cols] = threshold(monoleaf,200);
%! clf
%! hold on;
%! imshow(leaf);
%! plot(cols,rows,".","markersize",1);

The output of demo threshold should be something like the following.

Thresholding gradient

In order to extract a description of a scene from an image, an early step is to detect the boundaries between various objects in the scene via edge detection. There are many different methods, but one approach is to find pixels where the gradient is particularly high. Use =monochrome= and =normgrad= functions from above to complete the following script.

leaf=imread("leaf.jpg");
monoleaf=
ng =
[rows, cols] = threshold(ng, __ );

clf
hold on;
imshow(leaf);
plot(cols,rows,".","markersize",1);

Try different values for the threshold. The output of this script should be something like the following; it's interesting as far as detecting texture, but not very helpful for dividing the scene into objects. There's also a fair amount of isolated "edge" pixels in the background. Both of these problems can be addressed via smoothing in the next lab.

Before next lab

Before the lab

Convolution and smoothing I

In order to smooth out some of the noise (or just isolated bright pixels), we can replace the value of each pixel with a weighted average of it's neighbourhood. The simplest approach is the so called box blur, where each pixel in the neighbourhood is added up, and the result divided by the number of pixels. The Octave function conv2(A,B) provides an easy way to apply a convolution or kernel to a matrix. This just means that B specifies the weights in averaging the neighbourhood.

Fill in the appropriate matrix (formula) B to make the following smoothing demo work.

A = [0,0,0,0,0,1;
     0,1,1,1,0,0;
     0,1,1,1,0,1;
     0,1,1,1,1,0;
     0,1,1,1,1,0;
     0,0,0,0,0,0];


for j=2:12
  B=
  AB = conv2(A,B);
  imshow(AB,[]);
  pause(1);
endfor

As the variable j increases, the images should look smoother but also less detailed.

Convolution and Smoothing II

Generalize the demo above to make a smoothing function. For variety we're going to use the Paris image image from a previous lab for the demo.

function S=smooth(in, side=3)
    S =
endfunction

%!test
%! A = [0,0,0,1;
%!      1,1,0,0;
%!      1,1,0,1;
%!      1,1,1,0];
%! B= [0.50, 0.25, 0.25, 0.25;
%!     1.00, 0.50, 0.25, 0.25;
%!     1.00, 0.75, 0.50, 0.25;
%!     0.50, 0.50, 0.25, 0.00];
%! assert(smooth(A,2),B,eps);

%!demo
%! paris=imread("paris.jpg");
%! monoparis=monochrome(paris,[1/3,1/3,1/3]);
%! imshow(monoparis,[])
%! pause(1);
%! imshow(smooth(monoparis),[])
%! pause(1);
%! imshow(smooth(monoparis,10),[])
%! pause(1);
%! imshow(smooth(monoparis,20),[])

Use your new function to complete the following script. Adjust the smoothing and threshold parameters to approximate the image below. You will need to download the leaf image from last lab.

leaf=imread("leaf.jpg");
monoleaf=monochrome(leaf);
smoothed=
ng = normgrad(smoothed)
[rows, cols] =

clf
hold on;
imshow(leaf,[]);
plot(cols,rows,".","markersize",1);

Smoothing and gradient via convolution

As you probably saw, the second argument to conv2 can be much more general than just uniform weights. In particular some of the weights can be negative, e.g. to approximate a gradient calculation.

One example is the Soebel Operator which combines gradiant and smoothing operations.

Refering to the Wikipedia page, complete the function to calculuate the Soebel operator. You will also need to define function norm2, which can be copied from the definition of normgrad (without the gradient part).

function [Gx,Gy]=soebel(in)


  Gx =
  Gy =
endfunction

%!demo
%! leaf=imread("leaf.jpg");
%! monoleaf=monochrome(leaf);
%! [Dx, Dy] = soebel(monoleaf);
%! ns = norm2(Dx,Dy);
%! [rows,cols] = threshold(ns,150);
%! clf
%! hold on
%! imshow(leaf);
%! plot(cols,rows,".","markersize",10);

In the resulting figure the size of the detected pixels is exaggerated to make them easier to spot.

Before next lab

Before the lab

K nearest neighbour

The k-Nearest neighbour algorithm (KNN) is a famous machine learning or pattern classification algorithm. In this algorithm you are given a training set of numerical measurement vectors (e.g. lab attendance and height) each labelled with a class (e.g. final grade). Given a new, unlabelled measurement, the algorithm predicts the corresponding class by looking at the k-closest training vectors, and voting.

In this lab we will work with a famous set of measurements of iris flowers, where the "class" is the species of flower.

You need to know the following definition from linear algebra

distance(X,Y) = norm(X-Y)

Complete the following function which returns the row indices of the k closest rows of data to v. In our data sets, we will assume the first column is always the class label, and should ignored in distance calculations.

function out = nearest(v, k, data)
  for i=1:rows(data)
    dist(i)=
  endfor
  [sorted, indices]=sort(dist);
  out = sort(indices(1:k));
endfunction

%!test
%! v = [0,1,1]
%! data = [0,0,0; 0,0,1; 0,1,0; 1,1,1]
%! assert(nearest(v,1,data) == 4)
%! assert(nearest(v,3,data) == [2,3,4])

You can time your nearest neighbour query with the following:

• Download training.mat, testing.mat
• Create a file ~/cs2613/labs/L20/bench.m with the following content
• you will need an updated version of timeit.m to handle variable numbers of arguments.

load training
load testing
timeit(1000,@nearest,testing(1,:), 3, training);

K nearest neighbours continued

In practice the function nearest would probably be combined with something like the following; they are split out here to help with debugging and testing. Use the parameter fun here rather than calling nearest directly, so we can swap in a different query function later.

function out=findclass(v, k, data, fun=@nearest)
    selection=
    out = mode(data(selection,1));
endfunction

%!test
%! v = [0,1,1];
%! data = [0,0,0; 0,0,1; 0,1,0; 1,1,1];
%! assert(findclass(v,1,data) == 1)
%! assert(findclass(v,3,data) == 0)

Here is a for-loop based version of a kNN classifier. The return value is the success rate of the classifier (i.e. the fraction of the time it gets the right answer on the test set).

function ratio=knn(k,training, testing, output=0)

  correct = 0;
  for i=1:rows(testing)
    row=testing(i,:);
    if findclass(row,k,training) == row(1);
      correct += 1;
    endif
  endfor

  ratio = correct/rows(testing);
endfunction

You can try out the classifier with

load testing
load training
knn(3,testing,training)

Vectorizing nearest

We need a couple of ideas from basic linear algebra to make this vectorization work. We can make many copies of the input vector v by multiplying it by a ones column vector on the left (no loop required). Try this in octave

ones(10,1)*[1,2,3,4]

As a convenience, we can also sort by the square of the norm, which is simply the dot product of a vector with itself.

function out = nearest2(v, k, data)

  diff = data(       ) - ones(          ,1)*v(2:end);
  normsq = dot(            )
  [sorted, indices]=sort(normsq);
  out = sort(transpose(indices(1:k)));
endfunction

%!test
%! v = [0,1,1];
%! data = [0,0,0; 0,0,1; 0,1,0; 1,1,1];
%! assert(nearest2(v,1,data) == 4)
%! assert(nearest2(v,3,data) == [2,3,4])

Finally, check the speedup with this second knn frunction

function ratio=knn2(k,training, testing, output=0)

  correct = 0;
  for i=1:rows(testing)
    row=testing(i,:);
    if findclass(row,k,training,@nearest2) == row(1);
      correct += 1;
    endif
  endfor

  ratio = correct/rows(testing);
endfunction

You can use the follow lines in bench.m

timeit(10,@knn,3,training,testing);
timeit(10,@knn2,3,training,testing);