5/5 - (1 vote)

5/5 – (1 vote)

Topics Covered: Operations on inductive definitions, building an interpreter, big step operational semantics and using map, foldLeft and filter functions to replace loops.

Name: WRITE YOUR NAME HERE

// TEST HELPER: PLEASE run this cell first
def passed(points: Int) {
    require(points >=0)
    if (points == 1) print(s"Tests Passed (1 point)")
    else print(s"Tests Passed ($points points)") 
}

Problem 1: Manipulating ASTs, Inference Rules (30 points)

1A: Derivatives of Expressions (20 points)

We have defined a grammar for arithmetic expressions in our class notes. For this problem, you will be writing an automatic differentiation method that, given an expression e which involves just a single identifier x (no need to check this fact), will return an expression for de/dx, the derivative of e with respect to x.

Eg., e = Sine(Mult(Identifier("x"), Const(2.0))) should return Mult(Const(2.0), Cosine( Mult(Identifier("x"), Const(2.0))). In plain math, $\frac{d \sin (2 x)}{d x} = 2 \cos (2 x)$

We will write down the inference rules for derivative, as follows.

A rule for constants ( $\frac{d c}{d x} = 0, c \in R$ )

$\begin{matrix} derivative (Const(f), x) = Const(0.0) \end{matrix} (C o n s t a n t)$

A rule for identifiers $\frac{d x}{d x} = 1, \frac{d y}{d x} = 0$ for $y \neq x$ .

$\begin{matrix} derivative (Ident(s), x) = {\begin{cases} Const(1.0) & x == s \\ Const(0.0) & otherwise \end{cases} \end{matrix} (I d e n t i f i e r);;;$

A rule for plus $\frac{d}{d x} (e_{1} + e_{2}) = \frac{d e_{1}}{d x} + \frac{d e_{2}}{d x}$ .

$\begin{matrix} derivative (e1, x) = f1, derivative (e2, x) = f2 \\ derivative (Plus(e1, e2), x) = Plus(f1, f2) \end{matrix} (P l u s)$

A rule for multiplication: $\frac{d}{d x} (e_{1} e_{2}) = e_{2} \frac{d e_{1}}{d x} + e_{1} \frac{d e_{2}}{d x}$ .

$\begin{matrix} derivative (e1, x) = f1, derivative (e2, x) = f2 \\ derivative (Mult(e1, e2), x) = Plus(Mult(f1, e2), Mult(f2, e1)) \end{matrix} (M u l t)$

A rule for division $\frac{d}{d x} (\frac{e_{1}}{e_{2}}) = \frac{\frac{d e_{1}}{d x}}{e_{2}} - \frac{e_{1} \frac{d e_{2}}{d x}}{e_{2}^{2}}$

$\begin{matrix} derivative (e1, x) = f1, derivative (e2, x) = f2 \\ derivative (Div(e1, e2), x) = Minus(Div(f1, e2), Div(Mult(e1, f2), Mult(e2, e2))) \end{matrix} (D i v)$

A rule for exponentiation $\frac{d}{d x} (e^{e_{1}}) = e^{e_{1}} \frac{d e_{1}}{d x}$

$\begin{matrix} derivative (e1, x) = f1 \\ derivative (Exp(e1), x) = Mult(Exp(e1), f1) \end{matrix} (E x p)$

The rules for $M i n u s$ , $S i n e$ , and $C o s i n e$ are left for you to write. You do not need to write your solution for these rules in this notebook, but, you do need to give them in code below. (Don’t forget about the chain rule!)

sealed trait Expr
case class Const(f: Double) extends Expr
case class Ident(s: String) extends Expr
case class Plus(e1: Expr, e2: Expr) extends Expr
case class Minus(e1: Expr, e2: Expr) extends Expr
case class Mult(e1: Expr, e2: Expr) extends Expr
case class Div(e1: Expr, e2: Expr) extends Expr
case class Sine(e: Expr) extends Expr
case class Cosine(e: Expr) extends Expr
case class Exp(e: Expr) extends Expr
// We will skip over Log(e: Expr)

Write a function derivativeExpr that calculates the derivative of an expression e w.r.t a given identifier as a string x.

def derivativeExpr(e: Expr, x: String): Expr =
    ??? // YOUR CODE HERE

// TEST HELPERS
def evalExpr (e: Expr, env: Map[String, Double]): Double = e match {
    case Const (f) => f
    case Ident (str) => { if (env.contains(str)){
                                env(str)
                            } else {
        throw new IllegalArgumentException(s"Environment does not contain mapping for $str")
    }
                        }
    case Plus(e1, e2) => {
        (evalExpr(e1, env)) + (evalExpr(e2, env))
    }
    
    case Minus(e1, e2) => {
        (evalExpr(e1, env)) - (evalExpr(e2, env))
    }
    
    case Mult(e1, e2) => {
        (evalExpr(e1, env)) * (evalExpr(e2, env))
    }
    
    case Div(e1, e2) => {
        val v2 = evalExpr(e2, env)
        if (math.abs(v2) > 1E-09){
            (evalExpr(e1, env)) / (v2)
        } else {
            throw new IllegalArgumentException("Division by Zero Error -bailing out")
        }
    }
    
    case Exp(e) => math.exp( evalExpr(e, env))
    
    case Sine(e) => math.sin( evalExpr(e, env))
    
    case Cosine(e) => math.cos(evalExpr(e, env))
}

def testExpressions(exp: Expr, deriv_expected: Expr, testVals: List[Double]): Boolean = {
    val tol: Double = 1E-06
    val deriv_act = derivativeExpr(exp, "x")
    testVals forall { 
            x => {
              val res = math.abs( evalExpr(deriv_act, Map("x"-> x)) - evalExpr(deriv_expected, Map("x" -> x)) ) <= tol
              if (!res) { println(s"Failed at $x")}
              res
            }
    }
}

val allVals = List(-5.0, -4.5, -4.0, -3.5, -3.0, -2.5, -1.9, -1.4, -1.0, -0.5, 0.1, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5, 5.0)

// BEGIN TEST
val e1 = Plus(Ident("x"), Const(2.0))
assert(testExpressions(e1, Const(1.0), allVals ), s"Test 1 Failed -- Input: $e1 ")

passed(5)
// END TEST

// BEGIN TEST
val e2 = Plus(Cosine(Ident("x")), Sine(Ident("x")))
val ed2 = Minus(Cosine(Ident("x")), Sine(Ident("x")))
assert(testExpressions(e2, ed2, allVals), s"Test 2 Failed: Input is $e2")

passed(5)
// END TEST

// BEGIN TEST
val x = Ident("x")
val e3 = Exp(Mult(x, x))
val ed3 = Mult(Mult(Const(2.0), x), e3)
assert(testExpressions(e3, ed3, allVals), s"Test 3 Failed: Input is $e3")

passed(5)
// END TEST

// BEGIN TEST
val e4 = Div(x, Plus(x, Const(2.0)))
val ed4 = Div(Const(2.0), Mult(Plus(x, Const(2.0)), Plus(x, Const(2.0))) )
assert(testExpressions(e4, ed4, allVals), s"Test 4 Failed: Input is $e4")


val e5 = Sine(Mult(Exp(Minus( Cosine(Div(x,x)), Cosine(Const(1.0)) )), x))
val ed5 = Cosine(x)
assert(testExpressions(e5, ed5, allVals), s"Test 5 Failed: Input is $e5")

passed(5)
// END TEST

1B: Newton’s Algorithm Reloaded (10 points)

Let’s revisit problem 5 from assignment 1. Back in assignment 1, we hard coded the expression and its derivative. Here, we will use our Expr abstract syntax to define expressions and use the function you wrote in 2A to compute derivatives. You may also use the evalExpr function provided below.

Newton invented the Newton-Raphson method for solving an equation. We are going to ask you to write some code to solve equations.

solveEquation(e: Expr, x0: Double, maxIters: Int = 1000)

Assume that the input expression has involves just one variable “x”.

To solve an equation of the form

x 2 - 3 x + 2 == 0

with initial guess at the solution: say

x 0 = 4.5

We will input val e = Plus(Minus(Mult(Ident("x"), Ident("x")), Mult(Const(3.0), Ident("x"))), Const(2.0)) into the function

solveEquation( e, 1.5, 1000)

Each time we have the $i^{t h}$ guess $x_{i}$ , we update it as

x i + 1 = x i - f ( x i ) f ' ( x i )

For our equation, $f (x) = x^{2} - 3 x + 2$ and $f^{'} (x) = 2 x - 3$ ( $f^{'}$ is the derivative of $f$ ).

Thus, our update equation is $x_{i + 1} = x_{i} - \frac{x_{i}^{2} - 3 x_{i} + 2}{2 x_{i} - 3}$ .

We stop whenever $| f (x_{i}) | \leq 10^{- 8}$ : i.e, we are very close to a root of the function or $i \geq maxIters$ .

Gory details are here: http://www.math.ubc.ca/~anstee/math104/newtonmethod.pdf

def evalExpr (e: Expr, env: Map[String, Double]): Double = e match {
    case Const (f) => f
    case Ident (str) => { if (env.contains(str)){
                                env(str)
                            } else {
        throw new IllegalArgumentException(s"Environment does not contain mapping for $str")
    }
                        }
    case Plus(e1, e2) => {
        (evalExpr(e1, env)) + (evalExpr(e2, env))
    }
    
    case Minus(e1, e2) => {
        (evalExpr(e1, env)) - (evalExpr(e2, env))
    }
    
    case Mult(e1, e2) => {
        (evalExpr(e1, env)) * (evalExpr(e2, env))
    }
    
    case Div(e1, e2) => {
        val v2 = evalExpr(e2, env)
        if (math.abs(v2) > 1E-09){
            (evalExpr(e1, env)) / (v2)
        } else {
            throw new IllegalArgumentException("Division by Zero Error -bailing out")
        }
    }
    
    case Exp(e) => math.exp( evalExpr(e, env))
    
    case Sine(e) => math.sin( evalExpr(e, env))
    
    case Cosine(e) => math.cos(evalExpr(e, env))
}

def solveEquation(e: Expr, x0: Double, maxIters:Int = 1000): Double  =
    ??? // YOUR CODE HERE

// BEGIN TEST
def checkSolution(e: Expr, v: Double): Boolean = {
    val y = evalExpr(e, Map{"x" -> v}) 
    math.abs(y) <= 1e-08
}

val e1 = Plus(Minus(Mult(Ident("x"), Ident("x")), Mult(Const(3.0), Ident("x"))), Const(2.0))
val v1 = solveEquation(e1, 10.0, 1000)

assert(checkSolution(e1, v1), s"Test 1 failed: $e1 == 0, your code returned $v1 with f(x) = ${evalExpr(e1, Map{"x" -> v1}) }")

// Sine(x)  - Cos(x) - x == 0
val x = Ident("x")
val e2 = Minus(Sine(x), Plus(Cosine(x), x))
val v2 = solveEquation(e2, 1.4)
assert(checkSolution(e2, v2), s"Test 2 failed: $e2 == 0, your code returned $v2 with f(x) = ${evalExpr(e2, Map{"x" -> v2}) }")

// e^x - 5.0 = 0
val e3 = Minus(Exp(x), Const(5.0))
val v3 = solveEquation(e3, 2.0)
assert(checkSolution(e3, v3), s"Test 3 failed: $e3 == 0, your code returned $v3 with f(x) = ${evalExpr(e3, Map{"x" -> v3}) }")

// e^cos(x) + e^sin(x) - 2.0 = 0

val e4 = Minus(Plus(Exp(Sine(x)), Exp(Cosine(x))), Const(2.0))
val v4 = solveEquation(e4, 1.8)
assert(checkSolution(e4, v4), s"Test 3 failed: $e4 == 0, your code returned $v4 with f(x) = ${evalExpr(e4, Map{"x" -> v4}) }")


// x sin(x) -  cos(x) - 5.0
val e5 = Minus(Mult(x, Sine(x)), Plus(Cosine(x), Const(5.0)))
val v5 = solveEquation(e5, 1.8)
assert(checkSolution(e5, v5), s"Test 3 failed: $e5 == 0, your code returned $v5 with f(x) = ${evalExpr(e5, Map{"x" -> v5}) }")

passed(10)
// END TEST

Problem 2: map, filter, reduce on containers (25 points)

Solve the problems using a combination of map, filter and foldLeft/foldRight opertions over lists. The use of mutables, recursion, For/While loops is forbidden for this problem.

2A: Compute the dot-product of two lists of numbers.

Write a function computeDotProduct that takes two lists lstA and lstB of double precision numbers. The lists are given to be the same size. You need to compute the dot product.

$(a_{0}, \dots, a_{n}) \cdot (b_{0}, \dots, b_{n}) = \sum_{j = 0}^{n} a_{j} b_{j}$ .

List API functions that you are allowed to use: zip, map, filter, foldLeft, and sum. You can look the list API documentation for scala to find out more about these functions. Post/Search on piazza if you are unsure. You are not allowed to use var, any kind of loops or recursion.

def dotProduct(lstA: List[Double], lstB: List[Double]): Double =
    
    {
        require(lstA.length == lstB.length)
    ??? // YOUR CODE HERE
    }

// BEGIN TEST

val t1 = dotProduct(List(1.1,2.0), List(3.0, 4.2))
assert(math.abs(t1 - 11.7)<= 1E-08, "Test 1 failed")

val t2 = dotProduct(List(1.1), List(2.0))
assert(math.abs(t2 - 2.2)<= 1E-08, "Test 2 failed")

val t3 = dotProduct(List(), List())
assert(math.abs(t3)<= 1E-08, "Test 3 failed")

val t4 = dotProduct(List(1.5, 0.0, 2.3, -1.1, 0.0), List(0.0, 4.5, 1.1, 2.3, 5.0))
assert(math.abs(t4) <= 1E-08, "Test 4 failed")

passed(5)
// END TEST

2B: LCM of all Denominators.

You are given a list of pairs of integers that are supposed to represent fractions. You can assume that all fractions are positive and already in their lowest terms. This problem asks you to compute the LCM of the denominators.

Eg., Input: List((1,2), (3,4), (8,9), (15,24)) The denominators are 2, 4, 9, 24 and their LCM is 72, which is the answer your function should return.

For the empty list as input, your code must return the answer 1.

You should assume that all the denominators are positive.

You are allowed to use the provided lcm function that computes LCM of two numbers, map, filter, foldLeft, and foldRight. You cannot use var, loops or recursive calls other than the call made for LCM.

import scala.annotation._

@tailrec
private def gcd(a: Int, b: Int):Int=if (b==0) a.abs else gcd(b, a%b)

def lcm(a: Int, b: Int)=(a*b).abs/gcd(a,b)

def lcmOfDenominators(lst: List[(Int, Int)]): Int = {
    ??? // YOUR CODE HERE
}

// BEGIN TEST
val i1 = lcmOfDenominators(List((1,2), (3,4), (5,6),(8,9), (11,12)))
assert(i1 == 36, s"Test 1 failed -- expected answer is 36, you got $i1")
val i2 = lcmOfDenominators(List())
assert(i2 == 1, s"Test 2 failed -- empty list must trivially have lcm of 1")
val i3 = lcmOfDenominators(List((4,5),(5,9),(18,15)))
assert(i3 == 45, s"Test 2 failed -- your answer is $i3")
passed(5)
// END TEST

2C (7 points): Convert a list into an indexed list.

Write a function to convert a list of strings into an indexed list of strings. Indices start at 0. As an example:

Input List(“hello”, “world”, “my”, “cat”, “is”, “grumpy”, “today”)

Output List( (0, “hello”), (1, “world”), (2, “my”), (3,”cat”), (4, “is”), (5, “grumpy”), (6,”today”) )

You are allowed to use just the basic list operations such as cons of an element to a list (::) and concatenation of two lists (++, or ::: operators). List API functions reverse, map, filter, foldLeft and foldRight but not other list API functions. Do not use var, loops or recursion.

def makeIndexedList(lst:List[String]): List[(Int, String)] = {
    ??? // YOUR CODE HERE
}

// BEGIN TEST
val t1 = makeIndexedList(List("hello"))
assert(t1 == List((0,"hello")), s"Test 1 failed - your code returned $t1")

val t2 = makeIndexedList(List("hello", "world"))
assert(t2 == List((0,"hello"), (1, "world")), s"Test 2 failed - your code returned $t2")

val t3 = makeIndexedList(Nil)
assert(t3 == Nil, s"Test 3 failed - your code returned $t3")

val t4 = makeIndexedList(List("a","b","c","d","e"))
assert(t4 == List((0,"a"), (1,"b"), (2,"c"), (3,"d"), (4,"e")), s"Test 4 failed - your code returned $t4")

passed(8)
// END TEST

2D: Value larger than index.

Given a list of numbers, return a new list which includes those elements of the original list whose values are greater than or equal to their indices in the list.

Example:

Input: List(0, 1, 4, -5, -3, 5)

In this list, at index 0, we have 0; index 1 is a 1, index 2 is a 4. At these indices note that the values are greater than the indices. However at index 3, we have a -5 in the list whose value is less than its index. The returned value should be

Output: List(0, 1, 4, 5)

You are allowed to use just the basic list operatios such as cons of an element to a list (::) and concatenation of two lists (++, or ::: operators). List API functions reverse, map, filter, foldLeft and foldRight but not other list API functions. Do not use var, loops or recursion.

def valueLargerThanIndex(lst: List[Int]): List[Int] = {
    ??? // YOUR CODE HERE
}

// BEGIN TEST
val i1 = valueLargerThanIndex(List(0, -2, 1, 4, 7,-5))
assert(i1 == List(0,4,7), s"Test 1 failed -- your code returned $i1")

val i2 = valueLargerThanIndex(List(-1, 1, 1, 1, 5,-5))
assert(i2 == List(1,5), s"Test 1 failed -- your code returned $i2")

val i3 = valueLargerThanIndex(Nil)
assert(i3 == Nil, s"Test 3 failed -- your code returned $i3")

passed(7)
// END TEST

Reviews

There are no reviews yet.

Only logged in customers who have purchased this product may leave a review.

Whatsapp Us

[SOLVED] Cspb 3155: assignment 4

Problem 1: Manipulating ASTs, Inference Rules (30 points)

1A: Derivatives of Expressions (20 points)

1B: Newton’s Algorithm Reloaded (10 points)

Problem 2: map, filter, reduce on containers (25 points)

2A: Compute the dot-product of two lists of numbers.

2B: LCM of all Denominators.

2C (7 points): Convert a list into an indexed list.

2D: Value larger than index.

Reviews

Whatsapp Us

[SOLVED] Cspb 3155: assignment 4

Problem 1: Manipulating ASTs, Inference Rules (30 points)

1A: Derivatives of Expressions (20 points)

1B: Newton’s Algorithm Reloaded (10 points)

Problem 2: map, filter, reduce on containers (25 points)

2A: Compute the dot-product of two lists of numbers.

2B: LCM of all Denominators.

2C (7 points): Convert a list into an indexed list.

2D: Value larger than index.

Reviews

Related products

[SOLVED] Implementing Hashtable-based Symbol Tables

[SOLVED] LINEAR DATA STRUCTURES AND ALGORITHMS ASSIGNMENT 2

[SOLVED] MongoDB CRUD Faculty

[SOLVED] Assignment 1 – a maze game

[SOLVED] PRC Assignment JavaFX

[SOLVED] :web222 assignment 6 html forms via html, css, and javascript.