These exercises are provided to give you practice with material we have covered recently in class, before the second exam. You do not need to submit them, and they will not be graded. Instead, we will provide sample solutions before the exam.

These problems are not intended to provide comprehensive coverage of all the material we have learned throughout the quarter; rather, just new material that you will want to gain experience with before the test. Please see Piazza for a study guide with a list of all material.

Although we will not be collecting your work, you should follow similar procedures when working on these problems: first, be sure still to require the cs151-core library. Second, checking in your work to subversion for safekeeping is still prudent.

Practice Problems

Stay in the habit of writing principled code: continue to look for opportunities to write helper functions, to document your code, and to write tests. These are beneficial for all coding, graded or not.

Efficiency Analysis

For these problems, you will not actually need to write a single line of code. Rather, like we did in class, determine the cost of the code we have provided below. For each question, you will need to decide what the unit of work you are measuring should be (e.g., the number of times the > operator is being applied), and what the input to your cost function should be (e.g., the length of the function's list parameter). Write a recurrence relation, and then solve it for a closed-form solution.

Sierpinski triangle

Refer to this post, giving a version of the Sierpinski triangle code we saw in lecture. Recall that this code motivated the efficiency benefits of using a local definition to calculate a sub-triangle a single time rather than three identical times at each level of refinement. Perform an efficiency analysis for both the bad version and the good version of this code.

Checkers

We have been implementing the game of chess in our project. A simpler game that uses a similar board is the game of checkers; it consists of black and white pieces on an 8x8 board. For the purposes of this problem, however, consider that the board may be of any desired size.

Here are two possible representations (there are others as well) of the locations of the pieces:

The latter representation is called a sparse representation: it has the potential to save memory or time if there are few pieces relative to the overall board size, in other words, if the pieces are only sparsely placed on the board.

Here are the data type definitions for these representations: 

(define-type (Optional T) (U 'None (Some T)))
(define-struct (Some T)
  ([val : T]))

(define-type Piece (U 'Black 'Red))

(define-type Square (Optional Piece))

(define-type Board (Listof Square))

(define-struct Loc
  ([row : Integer]
   [col : Integer]))

(define-struct PiecePos
  ([pos   : Loc]
   [piece : Piece]))

(define-type SparseBoard (Listof PiecePos))
The first representation, the one similar to the chess project, is called a Board, and the second, sparse, representation, a SparseBoard.

Here is code to count the number of pieces on the board of a given color, in these two different representations: 

(: count1 : Board Piece -> Integer)
(define (count1 b p)
  (match b
    ['() 0]
    [(cons 'None tl) (count1 tl p)]
    [(cons (Some bp) tl)
      (+ (if (symbol=? bp p) 1 0) (count1 tl p))]))

(: count2 : SparseBoard Piece -> Integer)
(define (count2 b p)
  (match b
    ['() 0]
    [(cons (PiecePos _ bp) tl)
      (+ (if (symbol=? bp p) 1 0) (count2 tl p))]))
Determine the cost functions for these two implementations.

Here is code to get the piece at a given location, for the two representations: 

(: board-ref1 : Board Integer Loc -> Square)
(define (board-ref1 b ncols l)
  (local
    {(: index : Integer)
     (define index (+ (* (Loc-row l) ncols) (Loc-col l)))
     (: lr : Board Integer -> Square)
     (define (lr b i)
       (match* (b i)
         [((cons hd _) 0) hd]
         [((cons _ tl) _) (lr tl (sub1 i))]
         [('() _) (error "out of bounds")]))}
    (lr b index)))

(: board-ref2 : SparseBoard Loc -> Square)
(define (board-ref2 b l)
  (match* (b l)
    [('() _) 'None]
    [((cons (PiecePos (Loc br bc) bp) tl) (Loc lr lc))
      (if (and (= br lr) (= bc lc)) (Some bp)
        (board-ref2 tl l))]))
Again, determine the efficiency of these two functions.

Matrix multiplication

We can represent a matrix as a list of lists. Specifically, a row or column of a matrix is a list of numbers. And the entire matrix is a list of rows, or a list of columns.

We can multiply two matrices (according to the standard matrix multiplication procedure) in this representation using the below data types and code. Because the first matrix is accessed along rows during the process of matrix multiplication, we will store it as a list of rows. Because the second matrix is accessed along columns during matrix multiplication, we will store it as a list of columns rather than rows, or, alternatively, you can think of it as being stored in the same manner as the first matrix, but having been transposed. 

(define-type Matrix (Listof (Listof Integer)))

(: dot-product : (Listof Integer) (Listof Integer) -> Integer)
(define (dot-product x y)
  (match* (x y)
    [('() '()) 0]
    [((cons xh xt) (cons yh yt))
      (+ (* xh yh) (dot-product xt yt))]
    [(_ _) (error "dimension mismatch")]))

(: do-row : (Listof Integer) Matrix -> (Listof Integer))
(define (do-row row m2)
  (match m2
    ['() '()]
    [(cons col tl)
      (cons (dot-product row col) (do-row row tl))]))

(: matrix* : Matrix Matrix -> Matrix)
(define (matrix* m1 m2)
  (match m1
    ['() '()]
    [(cons row rst)
      (cons (do-row row m2)
        (matrix* rst m2))]))

Determine the cost of the matrix* function.

Accumulators

The following problems give practice with the concept of accumulators. As we have seen in class, an accumulator can help you build a partial result as you traverse a data structure. A problem that benefits from an accumulator often does not have a parameter already provided that is suitable to use as an accumulator, so we often need to make a helper function that introduces an additional parameter. Following this advice, write the given functions, using helper functions with an extra parameter which is an accumulator. 

(: running-total : (Listof Integer) -> (Listof Integer))
which creates a list whose values are based on the input list as follows: each value in the new list is the sum of the corresponding value in the input list, and all the elements before it 
(check-expect (running-total (list 1 2 3 4)) (list 1 3 6 10))


(define-type (Optional T) (U 'None (Some T)))
(define-struct (Some T)
  ([val : T]))

(define-type Tree (U 'E Nd))
(define-struct Nd
  ([val    : Exact-Rational]
   [level : (Optional Integer)]
   [lsub   : Tree]
   [rsub   : Tree]))

(: label-level : Tree -> Tree)
Given a tree, this function should work its way down the tree, starting at the root, and generate a tree with identical structure and contents. However, the level field should reflect a given node's distance from the root: the root itself should have level (Some 0), its children should have level (Some 1), its grandchildren, (Some 2), and so on. Label all the nodes of the tree. 

(: list-mean : (Listof Exact-Rational) -> Exact-Rational)
Calculate the mean of the given list, making only a single pass over the list. It is a useful exercise to accomplish this task by using recursion and an accumulator, and separately by using fold (for practice on both topics). 

(: bst-valid? : Tree -> Boolean)
Analyze a tree, which is possibly a BST, to determine if all the elements are arranged in a way that meets the BST ordering property. Hint: you might want to use more than a single accumulator.

BST Removal

For this exercise, we work with the data definitions from lab 6. 

(define-type (Compare A)
  (A A -> Boolean))

(define-type (BSTree A)
  (U 'E (Nd A)))

(define-struct (Nd A)
  ([root    : A]
   [count   : Integer]
   [lesser  : (BSTree A)]
   [greater : (BSTree A)]))

(define-struct (BST A)
  ([less-than : (Compare A)]
   [tree-data : (BSTree A)]))

Implement remove-item: All (A) A (BST A) -> (BST A).

If the item doesn't appear in the tree, return the tree as is.

If the item appears more than once in the tree, subtract one from its counter.

If the item appears once in the tree, the items in the tree must be rearranged correspondingly to accommodate the removal of the singleton node. The algorithm is as follows:

Solutions Forthcoming

Sample solutions to these exercises will be available on piazza shortly. Please note these are in some cases substantially more difficult than what we will ask you to do on the test. For example, we would not present BST removal as an exam question; it's too complex.