Name: [SOLVED] Cspb 3155: assignment 2
Brand: Assignment Chef
SKU: 45703
Price: 25 USD
Availability: InStock
Rating: 5 (1 reviews)

5/5 - (1 vote)

5/5 – (1 vote)

Topics covered: recursion and inductive definitions.

YOUR NAME HERE

Note: Please first run the TEST HELPER cell that defines the passed function below. Failing to run this cell will make it hard for you to check your work.

// TEST HELPER
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 (10 points total)

A (5 points) Recursive `logTen`

Given a positive integer $n$ , we wish to compute $floor (\log_{10} (n))$ . Recall floor of a real number is the smallest integer that is less than or equal to it. Write a recursive function logTen(n: Int): Int that does the same. Ensure that your precondition restricts the inputs to $n > 0$ .

def logTen(n: Int): Int = {
    require( n >= 1) // If this is violated, you will get a "requirement failed message"
    ??? // YOUR CODE HERE
}

//BEGIN TEST
assert(logTen(1) == 0, "logTen(1) must be 0")
assert(logTen(10) == 1, "logTen(10) must be 1")
assert(logTen(11) == 1, "logTen(11) must be 1")
assert(logTen(4100) == 3, "logTen(4100) must be 3")
assert(logTen(30108100) == 7, "logTen(30108100) must be 7")
passed(5)
//END TEST

B (5 points) Tail Recursive `logTen`

Now, write a tail recursive version of the logTen function, called logTenTail. You should implement the helper function as a tail recursive function.

import scala.annotation.tailrec

@tailrec
def logTenHelper(n: Int, acc: Int): Int = {
    require(n >= 1)
    ??? // YOUR CODE HERE
}

def logTenTail(n: Int): Int = { 
    ??? // YOUR CODE HERE
}

// BEGIN TEST
assert(logTenTail(1) == 0, "logTen(1) must be 0")
assert(logTenTail(218) == 2, "logTen(218) must be 2")
assert(logTenTail(3) == 0, "logTen(3) must be 0")
assert(logTenTail(159) == 2, "logTen(159) must be 2")
assert(logTenTail(121349) == 5, "logTen(121349) must be 5")
passed(5)
//END TEST

Problem 2 (15 points)

We define a function shuffleString(s: String): String that, given an input string s, does the following:

If the string s is empty or length 1, the result is the same as input string s.
Let n be the length of s.
Recursively call shuffleString on the substring s(n/2)... s(n-1). Let s1 be the result
Concatenate s1 to the first half s(0)..s(n/2-1) to the result of the call.

Here is an implementation of this function and some examples, for your reference.

def shuffleString(s: String): String = {
    val n = s.length()
    if (n <= 1) { s }
    else {
        val secondHalf = s.substring(n/2, n)
        val shuffledHalf = shuffleString(secondHalf)
        val firstHalf = s.substring(0, n/2)
        return  shuffledHalf +  firstHalf 
    }
}

val f0 = shuffleString("1234")
val f1 = shuffleString("12345")
val f2 = shuffleString("123456")
val f3 = shuffleString("1234567")
val f4 = shuffleString("12345678")
val f5 = shuffleString("123456789")

Implement a tail recursive version of shuffleString using an accumulator variable. It will help to carefully examine how different parts of the string get rearranged to design this function or even first try to write a simple while loop that mimics shuffleString.

def tailRecursiveShuffleString(s: String, acc: String = ""): String = {
    ??? // YOUR CODE HERE
}

//BEGIN TEST
assert(shuffleString("1") == tailRecursiveShuffleString("1"), "Failed test 1")
assert(shuffleString("12") == tailRecursiveShuffleString("12"), "Failed test 12")
passed(5)
//END TEST

//BEGIN TEST
assert(shuffleString("123") == tailRecursiveShuffleString("123"), "Failed test 123")
assert(shuffleString("1234") == tailRecursiveShuffleString("1234"), "Failed test 1234")
passed(5)
//END TEST

//BEGIN TEST
assert(shuffleString("12345") == tailRecursiveShuffleString("12345"), "Failed test 12345")
assert(shuffleString("123456") == tailRecursiveShuffleString("123456"), "Failed test 123456")
assert(shuffleString("1234567") == tailRecursiveShuffleString("1234567"), "Failed test 1234567")
assert(shuffleString("12345678") == tailRecursiveShuffleString("12345678"), "Failed test 12345678")
assert(shuffleString("123456789") == tailRecursiveShuffleString("123456789"), "Failed test 123456789")
assert(shuffleString("1234567890") == tailRecursiveShuffleString("1234567890"), "Failed test 1234567890")
passed(5)
//END TEST

Problem 3 (20 points)

Convert the following inductive definition for regular expressions into a grammar first and then into a set of scala classes.

A regular expression is defined inductively as follows:

Any string s is an “atomic” regular expression.
If r1, r2 are regular expressions then so are
- The concatenation $r_{1}; r_{2}$ ,
- The disjunction $r_{1} | r_{2}$ , and
- The conjunction $r_{1} & r_{2}$ .
If $r$ is a regular expression, then its Kleene star $r^{*}$ is also a regular expression.

Use the constructor symbols:

$Atom (s)$ to denote an atomic regular expression,
$Concat (r_{1}, r_{2})$ for the “;” operator,
$Or (r_{1}, r_{2})$ for the “|” operator,
$And (r_{1}, r_{2})$ for the “&” operator and
$Star (r)$ for the Kleene-star operator.

You may use the nonterminal $string$ without definition to denote a string of characters.

A (7 point)

Write the grammar using constructor symbols for the inductive definition above. Tip: you can examine the notebooks with inductive definitions to see how we typeset the grammar. There are no tests for this because it will be manualy graded.

YOUR ANSWER HERE

B (7 points)

Define the structure as a set of case class in scala.

sealed trait Regex
// Use constructors: Atom, Concat, Or, And and Star
??? // YOUR CODE HERE

//BEGIN TEST
val v1 = Atom("Hello")
val v2 = Concat(v1, v1)
val v3 = Or(v1, v2)
val v4 = Star(v3)
val v5 = Or(v1, v4)
passed(7)
//END TEST

C (6 points)

Write down the representation of the regular expression in Scala. Your cell must define a term that should be called finalAnswerC.

(“hello”) *; ((“scala”; “best”) *)

val finalAnswerC = {
    ??? // YOUR CODE HERE
}

//BEGIN TEST
def munge(r: Regex): String = r match {
    case Atom(st) => "$A$"+st
    case Concat(r1, r2) => munge(r1)+"$C$"+munge(r2)
    case Star(r) => "$K$"+munge(r)+"$S$"
    case Or(r1, r2) => munge(r1)+"_O_"+munge(r2)
    case And(r1,r2) => munge(r1)+"/\"+ munge(r2)
}

assert(munge(finalAnswerC) == "$K$$A$hello$S$$C$$K$$A$scala$C$$A$best$S$", "Test failed: you should seek help from the course staff to help you debug this problem, please")
passed(6)
//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 2

Problem 1 (10 points total)

A (5 points) Recursive logTen

B (5 points) Tail Recursive logTen

Problem 2 (15 points)

Problem 3 (20 points)

A (7 point)

B (7 points)

C (6 points)

Reviews

Related products

[SOLVED] Info 4604/5604 assignment #1: perceptron #1 1 (version 1.0)

[SOLVED] Implementing Hashtable-based Symbol Tables

[SOLVED] Individual Programming Assignment

[SOLVED] PRC Assignment JavaFX

[SOLVED] The Nutshell Term Project

[SOLVED] COP3503 Image Processing Project C++

A (5 points) Recursive `logTen`

B (5 points) Tail Recursive `logTen`