Lab #2 — Scheme Exercises CS 152 Section 5 — Fall 2020 Michael McThrow San José State University

Prelude – Installing and Using DrRacket We will be using the DrRacket IDE in this course for running Scheme programs. DrRacket is available for Windows, macOS, and Linux. You can download it by going to https://racket-lang.org, clicking on the “Download” button on the top right of the page, and choosing the appropriate platform for your computer.

Once you have Racket installed, open DrRacket. Here is what DrRacket looks like on Linux; it should look similar on Windows and macOS:

Note that the window has two sections. The first section where you see “#lang racket” is the source code file. The second section is the interpreter, which some programmers call the REPL, which stands for the “Read Eval Print Loop,” which describes how the user interface for interactive Lisp interpreters is implemented. (This REPL terminology has been now widely applied for other interactive interpreters, such as those for Python and JavaScript.) When you write your programs, you’re going to use the upper portion. However, if you just want to evaluate an expression on the fly, you can use the REPL on the lower portion.

Now, notice the “#lang racket” in the source code file section of DrRacket. That indicates that the program written below that line will be in the Racket programming language, which is a variant of

Scheme. For this assignment, however, we will be sticking to functions that are included in the R6RS version of Scheme. This enables us to use the REPL (sadly R6RS Scheme doesn’t have REPL support implemented in DrScheme) and to make use of DrScheme’s excellent debugging facilities.

Let’s try out the REPL by evaluating (+ 2 (* 3 5)). Type “(+ 2 (* 3 5))” at the prompt (with no quotes) and press Enter.

When you write your code, you are going to use the upper portion of the window, and you are going to use the Run button to run your code, either the entirety of the source code or a selection of it.

For a more detailed tutorial of the DrRacket IDE, please visit the DrRacket IDE manual at https://docs.racket-lang.org/drracket/.

Warmup Exercises (40 points) 1. (10 points) Write a function named fizz-buzz that accepts no arguments. The fizz-buzz

function outputs numbers 1 to 100 (inclusive) and prints them line-by-line as standard output. If a number is divisible by 3, we print “fizz” instead of the number. If a number is divisible by

5, we print “buzz” instead of the number. If a number is divisible by both 3 and 5 (e.g., 15), we print “fizzbuzz” instead of the number.

Hint: Scheme provides a remainder function (e.g., (remainder 3 2) evaluates to 1.) The display function accepts both numbers and strings. Note, though, that unlike Java’s System.out.println() function, display does not automatically append a new line.

2. (15 points) Write a function named gcd that accepts two arguments m and n. This computes the greatest common denominator of m and n; you may assume these are integers. For example, if m is 16 and n is 36, the greatest common denominator is 4. You may assume that m and n are integers.

3. (5 points) Write a function named linear-search that accepts two arguments: items and key. This function performs a linear search on the list items, determining whether key (an integer) is among those items. The function evaluates to true (#t) if the key is found, and false (#f) is the key is not found. For this function, when it comes to operating on the list, you are only allowed to use the Scheme functions first and rest; you may not use Scheme’s built-in search functions, nor are you allowed to take advantage of maps and filters.

4. (10 points) Write a function named my-remove that accepts two arguments: items (a list) and key. This function returns a new list that does not have any elements that match the key. Once again, you may only use first and rest for traversing the existing list, and for creating the new list, you are limited to the cons, list, and append functions.

Binary Search Tree (60 points) We will be writing a binary search tree in Scheme. Recall from CS 146 that a binary search tree is a data structure that allows for the storage of elements in a manner that is amenable to performing searches in O(log n) in the average case. For example, suppose we are adding the elements 3, 4, 2, 5, 8, 1, and 4.5 (in that order) to construct a binary search tree. We will end up with the resulting tree:

In Scheme, we could represent the above binary search tree as a collection of embedded lists:

(3 (2 (1)) (4 () (5 (4.5) (8))))

Each node is a list with up to three elements. The first element of the list refers to the node’s value. If a node is terminal (i.e., has no children), then it is represented as a one-element list. If a list has only two elements, that means the node only has a left child. If a node has only a right child, then it has three elements, but because there is no left child, the second element is the empty list (). A node with both a left and right child has three elements: the value, the left child, and the right child.

Let’s do each insertion step by step:

3 => (3) 4 => (3 () (4)) 2 => (3 (2) (4)) 5 => (3 (2) (4 () (5))) 8 => (3 (2) (4 () (5 () (8)))) 1 => (3 (2 (1)) (4 () (5 () (8)))) 4.5 => (3 (2 (1)) (4 () (5 (4.5) (8))))

Note that no duplicate elements are allowed in the binary search tree.

Write the following functions as follows (note: you may assume that all elements in the binary search tree are numbers): 1. (22.5 points) add-to-binary-search-tree with two arguments bst (the binary search tree)

and item, which is the item to be inserted into the binary search tree. This function returns a new binary search tree in its correct order. Note that if item is already in the binary search tree, then this function simply returns the existing binary search tree.

2. (7.5 points) create-binary-search-tree with argument items, a list of items to be inserted into the binary search tree. This function returns a new binary search tree with all of the items inside, excluding duplicates.

3. (15 points) search-binary-search-tree with two arguments bst (the binary search tree) and key, which is the item to search for in the binary search tree. This function returns #t if found and #f otherwise.

4. (15 points) binary-search-tree-to-list with two arguments bst (the binary search tree) and traversal, a symbol that indicates the traversal method. If the symbol is preorder, then place the elements in a list using preorder traversal. If the symbol is inorder, then use inorder traversal. If the symbol is postorder, then use postorder traversal.

Rules • No side effects are allowed with the exception of the display function and other functions that

print to the screen. • No mutation is allowed; this includes the use of set! • No do loops; either use recursion or map/filter/fold style functions (for-all is acceptable). • Make sure all of your code cleanly runs when turning it in; if I cannot evaluate your function,

that function gets a grade of zero.

• No external libraries or Racket-only libraries; use only the R6RS Scheme standard library.

Recommendations and Hints • I highly recommend writing some test cases for your code. One of the nice things about coding

without side effects is that you can just use simple equality functions to test what your functions evaluate to.

• Functional programming can sometimes feel like a mind-bending exercise for beginners. I highly recommend working out your programs on paper and thinking about how you would express with recursion, map, filter, and/or fold what you would normally express with loops in your Java programs. In some ways it’s like learning how to code again. But don’t feel discouraged; remember the first time you learned how to program, or the first time you learned how to write in assembly language. With practice, though, then functional programming will be second nature for you.

• Helper functions are vital in an immutable world. Remember that you can have as many arguments as you can in your helper functions.

• You are allowed to define your own top-level functions besides the ones that have been specified as common helper functions, but these functions are subject to the same restrictions as the others (for example, these functions can’t take advantage of any features that the functions specified cannot take advantage of).

Instructions for Turning In the Assignment Please place all of your functions in a file called lab2.rkt. This is the file that you will be turning in to me via Canvas.

Updated on September 30, 2021

Hints for Homework 5

1. (Improved triangular substitutions; adapted from FNC 2.3.5)

(a) The function backsub handles the case in which A is upper triangular; call it U:

U

 x1 x2 · · · xp

 

︸ ︷︷ ︸ =X

=

 b1 b2 · · · bp

 

︸ ︷︷ ︸ =B

.

For any j ∈ N[1,p], the solution of Uxj = bj is obtained by applying the backward substitution formula given in lecture:

 xn,j =

bn,j un,n

and

xi,j = 1 ui,i

 bi,j − n∑

k=i+1 ui,kxk,j

  for i = n− 1,n− 2, . . . , 1.

Encode these formulas using nested for-loops in your program: • outer loop: iterate over columns (j = 1, 2, . . . ,p) • inner loop: implement the backward substitution formula (i = n,n− 1, . . . , 1).

You may use the following template to begin your program backsub.m1 by function X = backsub(U,B) % BACKSUB X = backsub(U,B) % Solve multiple upper triangular linear systems. % Input: % U upper triangular square matrix (n-by-n) % B right-hand side vectors concatenated into an (n-by-p) matrix % Output: % X solution of UX = B (n-by-p)

[n,p] = size(B); % grab dimensions X = zeros(n,p); % preallocate output %% Implement back. subs. formula (nested for-loop)

end

1You do not need to write external function m-files. Simply write them at the end of the document as instructed in the problem.

1

The function forelim can be written in a very analogous manner. Note. If you want to include a check for triangularity of the coefficient matrix, use

istriu (upper triangular) or istril (lower triangular), e.g., if ~istriu(U)

error(’The matrix U must be upper triangular.’); end

The inclusion of such a check will not be part of the grading rubrics. (b) One way to test your code using the given examples is to compute the norm of the

difference of the analytical inverse and the numerically calculated inverse. For example, L1 = …..; L1inv = …..; % analytical inverse given L1invNum = ltinverse(L1); % numerically calculated inverse norm(L1inv – L1invNum) % norm of the difference

We want to see a small norm, if not zero.

2. (Triangular substitution and stability; FNC 2.3.6)

(a) In this part, you show that x = (1, 1, 1, 1, 1)T solves the system for any values of α and β; this is an analytical result.

(b) In this second part, however, you check whether the computer indeed produces the same answer for changing values of β while α is fixed. When the problem says “Using MATLAB, solve the system . . .”, it simply means that you use the backslash \ to solve the system Ax = b.

3. (Vectorizing mylu.m; FNC 2.4.7)

(a) For this part, follow the direction given in the problem: • delete the keyword for in the inner loop; (just for, not the rest) • delete the matching end of the inner loop; • put a semicolon at the end of i = j+1:n.

This defines i to be a vector of indices (j + 1,j + 2, . . . ,n). Passing i into L or A in the next two lines, the code effectively accesses the (j + 1)st through nth rows of the respective matrices; see the slides titled “Using Vectors as Indices” in Lecture 7 on arrays.

(b) Let x ∈ Rn and A ∈ Rn×n, not necessarily the ones appearing in the problem. The ordinary elementwise vector/matrix notation refers to the convention of denoting the elements of a vector or a matrix using subscripts such as

• xi: the ith element of vector bx; • Ai,j: the element of A on the ith row and jth column.

In MATLAB, they are expressed as x(i) and A(i,j), respectively. Now, let’s concen- trate on the matrix case:

A(< rowindex >,< columnindex >)

When one of the two indices is a vector, as in the case of the problem, it represents the slice of the matrix on a specified row or column. For example,

2

• A row vector consisting of 5th through 8th elements on the 3rd row of A:

A(3, 5 : 8) −→ [ A3,5 A3,6 A3,7 A3,8

] • A column vector consisting of 5th through 8th elements on the 3rd column of A:

A(5 : 8, 3) −→

  A5,3 A6,3 A7,3 A8,3

 

When both indices are vectors, it represents the submatrix on the specified rows and columns. For example,

• The submatrix of A between 2nd and 4th rows and between 1st and 5th columns:

A(2 : 4, 1 : 5) −→

 A2,1 A2,2 A2,3 A2,4 A2,5A3,1 A3,2 A3,3 A3,4 A3,5 A4,1 A4,2 A4,3 A4,4 A4,5

 

You are to translate the MATLAB statements in your vectorized mylu into mathematical notations as shown above.

4. (Application of LU factorization: FNC 2.4.6)

(a) Recall the following properties of the determinant from linear algebra: • det(AB) = det(A) det(B). • det(T) = t11t22 · · ·tnn =

∏n i=1 tii, where T ∈ Rn×n is a triangular matrix.

(b) Try to vectorize your code. The function can be written in only couple lines (excluding the function header and the end statement) without using any loop. It would be also useful to recall that if you only want to generate the second output of a certain function, you put ~ in place of the first output argument as a placeholder. For instance, if you only need U from mylu(A), instead of calling it with [L,U] = mylu(A), use

[~, U] = mylu(A);

Note. Use the vectorized version of mylu which you already wrote for Question 3.

5. (Proper usage of lu; FNC 2.6.1) The expression U \ L \ b is equivalent to (U \ L) \ b.

6. (FLOP Counting)

(a) Consider the following example question. Question. How would you code x = ABb most efficiently in MATLAB, and how many flops are needed? Answer. There are only two ways2 to code it: x=A*(B*b) or x=(A*B)*b. If the former is used, MATLAB i. carries out B*b: matrix-by-vector multiplication (∼ 2n2 flops)

2This is the same as x = A*B*b.

3

ii. left-multiplies the previous result by A: another matrix-by-vector multiplication (∼ 2n2 flops)

In total, it takes ∼ 4n2 flops. On the other hand, the latter version requires the matrix- by-matrix multiplication A*B, which already takes ∼ 2n3 flops. So the former is the efficient one.

Lesson. Avoid matrix-by-matrix multiplication as much as possible! Also remember to use the backslash operator if matrix inversion is required, instead of inv. When \ is invoked, MATLAB in general does a pivoted Gaussian elimination, which takes ∼ (2/3)n3 flops.

7. (Matrix norms; Sp20 midterm) Hints are found in the lecture for 10/01/21 (F).