diff options
author | Jack Sangdahl <[email protected]> | 2024-12-12 21:01:58 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-12 21:01:58 -0700 |
commit | 532be33588fd033fc7f814e725372923cf79a6c4 (patch) | |
tree | aadebd96897ed3c2979a4986b30bbd7df4ddc657 /data-types-exercise.ipynb | |
download | csci3155-532be33588fd033fc7f814e725372923cf79a6c4.tar.gz csci3155-532be33588fd033fc7f814e725372923cf79a6c4.zip |
Unit 1
Signed-off-by: Jack Sangdahl <[email protected]>
Diffstat (limited to 'data-types-exercise.ipynb')
-rw-r--r-- | data-types-exercise.ipynb | 1633 |
1 files changed, 1633 insertions, 0 deletions
diff --git a/data-types-exercise.ipynb b/data-types-exercise.ipynb new file mode 100644 index 0000000..9ef72b4 --- /dev/null +++ b/data-types-exercise.ipynb @@ -0,0 +1,1633 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "id": "3d02434f", + "metadata": {}, + "source": [ + "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel $\\rightarrow$ Restart) and then **run all cells** (in the menubar, select Cell $\\rightarrow$ Run All).\n", + "\n", + "Make sure you fill in any place that says `???`, `YOUR CODE HERE`, \"???\", \"YOUR ANSWER HERE\", as well as your name and collaborators below:" + ] + }, + { + "cell_type": "code", + "execution_count": 47, + "id": "8a89a7aa", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36mNAME\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"Jack Sangdahl\"\u001b[39m\n", + "\u001b[36mCOLLABORATORS\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"N/A\"\u001b[39m" + ] + }, + "execution_count": 47, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val NAME = \"Jack Sangdahl\"\n", + "val COLLABORATORS = \"N/A\"" + ] + }, + { + "cell_type": "markdown", + "id": "d009c835", + "metadata": {}, + "source": [ + "---" + ] + }, + { + "cell_type": "markdown", + "id": "9d34c7c8-c787-4f41-bd3a-5628797aa728", + "metadata": {}, + "source": [ + "# Exercise: Expressions and Data Types\n", + "\n", + "<!-- 3 Expressions -->\n", + "\n", + "<!-- 4 Binding and Scope -->\n", + "\n", + "The purpose of this assignment is to warm-up with Scala.\n", + "\n", + "### Learning Goals\n", + "\n", + "The primary learning goals of this assignment are to build intuition for\n", + "the following:\n", + "\n", + "- thinking in terms of types, values, and expressions; and\n", + "- imperative iteration.\n", + "\n", + "### Instructions\n", + "\n", + "This assignment asks you to write Scala code. There are restrictions\n", + "associated with how you can solve these problems. Please pay careful\n", + "heed to those. If you are unsure, ask the course staff.\n", + "\n", + "Note that `???` indicates that there is a missing function or code\n", + "fragment that needs to be filled in. In Scala, it is also an expression\n", + "that throws a `NotImplementedError` exception. Make sure that you remove\n", + "the `???` and replace it with the answer.\n", + "\n", + "Use the test cases provided to test your implementations. You are also\n", + "encouraged to write your own test cases to help debug your work.\n", + "However, please delete any extra cells you may have created lest they\n", + "break an autograder.\n", + "\n", + "## Type Checking\n", + "\n", + "In the following, I have left off the return type of function `g`. The\n", + "body of `g` is well-typed if we can come up with a valid return type. In\n", + "this question, we will reason for ourselves that `g` is indeed\n", + "well-typed." + ] + }, + { + "cell_type": "code", + "execution_count": 48, + "id": "0db88593", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mg\u001b[39m" + ] + }, + "execution_count": 48, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def g(x: Int) = /*e1*/({\n", + " // env1\n", + " val (a, b) = /*e2*/(\n", + " // env2\n", + " (1, (x, 3))\n", + " )\n", + " /*e3*/(\n", + " // env3\n", + " if (x == 0) (b, 1) else (b, a + 2)\n", + " )\n", + "})" + ] + }, + { + "cell_type": "markdown", + "id": "27d6ff35-074c-4171-a7f5-a035015e7b83", + "metadata": {}, + "source": [ + "We have added parentheses around 3 key sub-expressions of the body of\n", + "`g` (e.g., `/*e1*/(`$\\ldots$`)`) and noted that there are corresponding\n", + "environments (e.g., `// env1` for each sub-expression).\n", + "\n", + "### Q1.1: What is the type environment `env1`? Briefly explain.\n", + "\n", + "Use either format shown in the notes (e.g.,\n", + "$[ x_1 : \\tau_1, \\ldots, x_n : \\tau_n ]$)." + ] + }, + { + "cell_type": "markdown", + "id": "672c616d-04fb-41cf-aad5-6f025548b7b7", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "e41ca86f62e024565d1f2956f3950f48", + "grade": true, + "grade_id": "q1_1", + "locked": false, + "points": 2, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "The type environment of `env1` alone is $[\\:\\mathtt{env1} \\mapsto\\mathtt{Int}\\:]$. At this point, the only variable in scope is the parameter `x: Int`, so `env1` also maps to `Int`." + ] + }, + { + "cell_type": "markdown", + "id": "d577d0ca-7375-4e10-a89f-6a9f067a8f9f", + "metadata": {}, + "source": [ + "### Q1.2: What is the type environment `env2`? Briefly explain." + ] + }, + { + "cell_type": "markdown", + "id": "62ae6788-7ed6-4acd-9d5c-40192d303dc9", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "4660b9558a8195d26712214909a62db2", + "grade": true, + "grade_id": "q1_2", + "locked": false, + "points": 2, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "The type environment of `env2` is $[\\:\\mathtt{env2} \\mapsto\\mathtt{Int}\\:]$. `env2` references the known type of `x: Int`, which also maps `env2` to `Int`." + ] + }, + { + "cell_type": "markdown", + "id": "93547002-40ae-42f1-a910-38131a7d26f6", + "metadata": {}, + "source": [ + "### Q1.3: Derive the type of expression `e2`.\n", + "\n", + "Showing the type for each sub-expression of `e2`; stop when you reach\n", + "literals or variable uses." + ] + }, + { + "cell_type": "markdown", + "id": "4114c6c1-7098-466c-bf92-69aa4a321664", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "315ba92969984b267763af81ebd0f5d0", + "grade": true, + "grade_id": "q1_3", + "locked": false, + "points": 10, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "```scala\n", + "(1, (x, 3)): (Int, (Int, Int))\n", + "- if 1: Int\n", + "- if (x, 3): (Int, Int)\n", + " - if x: Int\n", + " - if 3: Int\n", + "```" + ] + }, + { + "cell_type": "markdown", + "id": "934b39f4-9eb5-4186-8e8d-f05f24d0f578", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "Use the format shown in the notes. Here’s such a derivation for the type\n", + "of the expression `(1 + 2) + (3 + 4)`.\n", + "\n", + "``` scala\n", + "(1 + 2) + (3 + 4): Int\n", + "- if 1 + 2: Int\n", + " - if 1: Int\n", + " - if 2: Int\n", + "- if 3 + 4: Int\n", + " - if 3: Int\n", + " - if 4: Int\n", + "```\n", + "\n", + "### Q1.4: What is the type environment `env3`? Briefly explain." + ] + }, + { + "cell_type": "markdown", + "id": "2e94876a-32b9-477c-9aa1-91253dde0d30", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "e5b9bc3f55c403acbbb1e709d2b68f12", + "grade": true, + "grade_id": "q1_4", + "locked": false, + "points": 2, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "The type environment of `env3` alone is $[\\:\\mathtt{env3} \\mapsto\\mathtt{x: Int, a: Int, b: (Int, Int)}\\:]$. At this point, `env3` includes the variables `x`, `a`, and `b`. We know `x: Int` from the function argument, `a: Int` from the tuple deconstruction, and `b: (Int, Int)` also from the tuple deconstruction." + ] + }, + { + "cell_type": "markdown", + "id": "7faf5604-c103-44b1-a711-334dfdab5d6c", + "metadata": {}, + "source": [ + "### Q1.5: Derive the type of expression `e3`." + ] + }, + { + "cell_type": "markdown", + "id": "ceae2d55-bef9-4cc5-a3dc-cfd11db90e43", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "52869852b70e53b19066a880678a23b7", + "grade": true, + "grade_id": "q1_5", + "locked": false, + "points": 2, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "```scala\n", + "if (x == 0) (b, 1) else (b, a + 2): ((Int, Int), Int)\n", + "- if x == 0: Boolean\n", + " - if (b, 1): Int\n", + " - if b: Int\n", + " - if 1: Int\n", + " - if (b, a + 2): Int\n", + " - if b: Int\n", + " - if a + 2: Int\n", + " - if a: Int\n", + " - if 2: Int\n", + "```" + ] + }, + { + "cell_type": "markdown", + "id": "bab903c4-188f-46ed-86dd-9495e781ff51", + "metadata": {}, + "source": [ + "### Q1.6: Confirm your derivations by adding type assertions to each sub-expression of `g` and adding the return type of `g`.\n", + "\n", + "That is, replace sub-expressions $e$ of `g` with expressions $e$ `:`\n", + "$\\tau$. You may need to add some parentheses—`(` $e$ `:` $\\tau$ `)`—to\n", + "preserve the syntactic structure. Skip adding typing assertions for\n", + "literals and variable uses.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "id": "b472b0a7", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "c4abe7222641b8ec119ec31036e39b95", + "grade": true, + "grade_id": "q1_6", + "locked": false, + "points": 9, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mg\u001b[39m" + ] + }, + "execution_count": 6, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def g(x: Int) = /*e1*/({\n", + " // env1\n", + " val (a: Int, b: (Int, Int)) = /*e2*/(\n", + " // env2\n", + " (1, (x, 3)): (Int, (Int, Int))\n", + " )\n", + " /*e3*/(\n", + " // env3\n", + " if (x == 0: Boolean) (b, 1): ((Int, Int), Int) else (b, a + 2): ((Int, Int), Int)\n", + " ): ((Int, Int), Int)\n", + "}): ((Int, Int), Int) " + ] + }, + { + "cell_type": "markdown", + "id": "d5e75af2-a72c-4fed-a247-aa90d3f8f0ad", + "metadata": {}, + "source": [ + "*Hint*: There are 8 sub-expressions that are not literals nor variable\n", + "uses that need typing assertions (i.e., $e$ `:` $\\tau$), plus 1 more\n", + "annotation for the return type of `g`.\n", + "\n", + "## Unit Testing\n", + "\n", + "When starting to program in the large, it is useful to use a testing\n", + "framework to manage tests and integrate with IDEs. One that is commonly\n", + "used in Scala is [ScalaTest](https://www.scalatest.org/).\n", + "\n", + "While it is somewhat overkill for testing small exercises like the ones\n", + "to come, we practice here writing tests using ScalaTest.\n", + "\n", + "To load the ScalaTest library, run the following cell:" + ] + }, + { + "cell_type": "code", + "execution_count": 50, + "id": "8fea5968", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "bdf4aa1ba5caa128e0dbcd6cc1ad5766", + "grade": false, + "grade_id": "testing", + "locked": true, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[32mimport \u001b[39m\u001b[36mRUN this cell FIRST before testing\n", + "import $ivy.$ , org.scalatest._, events._, flatspec._\n", + "\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36mreport\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36massertPassed\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36mtest\u001b[39m" + ] + }, + "execution_count": 50, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "// RUN this cell FIRST before testing\n", + "import $ivy.`org.scalatest::scalatest:3.2.19`, org.scalatest._, events._, flatspec._\n", + "def report(suite: Suite) = suite.execute(stats = true)\n", + "def assertPassed(suite: Suite) =\n", + " suite.run(None, Args(new Reporter {\n", + " def apply(e: Event) = e match {\n", + " case e @ (_: TestFailed) => assert(false, s\"${e.message} (${e.testName})\")\n", + " case _ => ()\n", + " }\n", + " }))\n", + "def test(suite: Suite) = {\n", + " report(suite)\n", + " assertPassed(suite)\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "67ac4efd-c505-4a4f-a6f5-91610f977849", + "metadata": {}, + "source": [ + "### Q2.1: Unit Test `plus`\n", + "\n", + "For this question, **edit the next two code cells** to fix the\n", + "implementation of `plus` and add the appropriate assertion for the third\n", + "test case `\"add (3,4) == 7\"`.\n", + "\n", + "Our goal is unit test the following complicated function (that we’ve\n", + "gotten wrong!):" + ] + }, + { + "cell_type": "code", + "execution_count": 51, + "id": "6bc42853", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mplus\u001b[39m" + ] + }, + "execution_count": 51, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def plus(n: Int, m: Int): Int = n + m" + ] + }, + { + "cell_type": "markdown", + "id": "2fd19eae-bb49-4616-94f4-e2383aad90c9", + "metadata": {}, + "source": [ + "To use ScalaTest, we create “Spec” objects using ScalaTest methods like\n", + "`should` that define an embedded domain-specific language (DSL) for\n", + "defining tests:" + ] + }, + { + "cell_type": "code", + "execution_count": 52, + "id": "1255cbba", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n", + "\u001b[32mcmd52$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mplus\u001b[0m\n", + "\u001b[32m- should add 1 + 1 == 2\u001b[0m\n", + "\u001b[32m- should add 2 + 2 == 4\u001b[0m\n", + "\u001b[32m- should add 3 + 4 == 7\u001b[0m\n", + "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 3\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n" + ] + }, + { + "data": { + "text/plain": [ + "\u001b[36mplusSuite\u001b[39m: \u001b[32mAnyFlatSpec\u001b[39m = cmd52$Helper$$anon$1" + ] + }, + "execution_count": 52, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val plusSuite = new AnyFlatSpec {\n", + " // Define a *subject* to test (e.g., \"plus\").\n", + " // After `should`, name a test (e.g, \"add (1, 1) == 2\").\n", + " // After `in`, specify assertions (e.g., `assert(plus(1,1) == 2))\n", + " \"plus\" should \"add 1 + 1 == 2\" in {\n", + " // Specify assertions here.\n", + " assert(plus(1,1) == 2)\n", + " }\n", + "\n", + " it should \"add 2 + 2 == 4\" in {\n", + " // It is convenient to distinguish the expected result from the code that\n", + " // you're testing, which affects the error messages when the test fails.\n", + " assertResult(2 + 2) {\n", + " plus(2,2)\n", + " }\n", + " }\n", + " it should \"add 3 + 4 == 7\" in {\n", + " assertResult(3 + 4) {\n", + " plus(3, 4)\n", + " }\n", + " }\n", + "}\n", + "report(plusSuite)" + ] + }, + { + "cell_type": "code", + "execution_count": 53, + "id": "27368277", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "8ac2636aa17b31fca777bf3064b8d491", + "grade": true, + "grade_id": "q2_1", + "locked": true, + "points": 3, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36mres53\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@48f724de" + ] + }, + "execution_count": 53, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "assertPassed(plusSuite)" + ] + }, + { + "cell_type": "markdown", + "id": "be1d876b-25dc-451a-86db-ed1cf1fed54e", + "metadata": {}, + "source": [ + "## Run-Time Library\n", + "\n", + "Most languages come with a standard library with support for things like\n", + "data structures, mathematical operators, string processing, etc.\n", + "Standard library functions may be implemented in the object language\n", + "(perhaps for portability) or the meta language (perhaps for\n", + "implementation efficiency).\n", + "\n", + "For this question, we will implement some library functions in Scala,\n", + "our meta language, that we can imagine will be part of the run-time for\n", + "our object language interpreter. In actuality, the main purpose of this\n", + "exercise is to warm-up with Scala programming.\n", + "\n", + "### Q3.1: Write and test a function `abs`\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 54, + "id": "3f001698", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "d1bacc19634bfb1bf864bd58b41906c4", + "grade": false, + "grade_id": "q3_1_code", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mabs\u001b[39m" + ] + }, + "execution_count": 54, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def abs(n: Double): Double = ({\n", + " if (n < 0) {\n", + " -n\n", + " } else {\n", + " n\n", + " }\n", + "})" + ] + }, + { + "cell_type": "markdown", + "id": "71c5328d-b26d-497d-adaf-6ef22d22688f", + "metadata": {}, + "source": [ + "that returns the absolute value of `n`. This a function that takes a\n", + "value of type `Double` and returns a value of type `Double`. This\n", + "function corresponds to the JavaScript library function `Math.abs`.\n", + "\n", + "#### Notes\n", + "\n", + "- Do not use any Scala library functions.\n", + "\n", + "#### Tests\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 55, + "id": "d913e614", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 4\u001b[0m\n", + "\u001b[32mcmd55$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mabs\u001b[0m\n", + "\u001b[32m- should abs(2) == 2\u001b[0m\n", + "\u001b[32m- should abs(-2) == 2\u001b[0m\n", + "\u001b[32m- should abs(0) == 0\u001b[0m\n", + "\u001b[32m- should abs(1) == 1\u001b[0m\n", + "\u001b[36mRun completed in 3 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 4\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 4, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n" + ] + }, + { + "data": { + "text/plain": [ + "\u001b[36mabsSuite\u001b[39m: \u001b[32mAnyFlatSpec\u001b[39m = cmd55$Helper$$anon$1" + ] + }, + "execution_count": 55, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val absSuite = new AnyFlatSpec {\n", + " \"abs\" should \"abs(2) == 2\" in {\n", + " assert(abs(2) == 2)\n", + " }\n", + " it should \"abs(-2) == 2\" in {\n", + " assert(abs(-2) == 2)\n", + " }\n", + " it should \"abs(0) == 0\" in {\n", + " assert(abs(0) === 0)\n", + " }\n", + " it should \"abs(1) == 1\" in {\n", + " assert(abs(1) === 1)\n", + " }\n", + "}\n", + "report(absSuite)" + ] + }, + { + "cell_type": "code", + "execution_count": 56, + "id": "1956942b", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "8ae14654f39c831149cca3cd7bc9901f", + "grade": true, + "grade_id": "q3_1", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36mres56\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@4fd24e85" + ] + }, + "execution_count": 56, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "assertPassed(absSuite)" + ] + }, + { + "cell_type": "markdown", + "id": "21898c2c-2b50-42c1-85f9-df4be93e8284", + "metadata": {}, + "source": [ + "### Q3.2: Write and test a function `xor`\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 57, + "id": "3c119212", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "ac179e4aa90d501026fc34ffbf524ab7", + "grade": false, + "grade_id": "q3_2_code", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mxor\u001b[39m" + ] + }, + "execution_count": 57, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def xor(a: Boolean, b: Boolean): Boolean = a ^ b" + ] + }, + { + "cell_type": "markdown", + "id": "5b47755a-a0e7-44ee-acc5-10a06d925697", + "metadata": {}, + "source": [ + "that returns the exclusive-or of `a` and `b`. The exclusive-or returns\n", + "`true` if and only if exactly one of `a` or `b` is `true`.\n", + "\n", + "#### Notes\n", + "\n", + "- For practice, do not use the Boolean operators. Instead, only use\n", + " the `if`- expression and the Boolean literals (i.e., `true` or\n", + " `false`).\n", + "\n", + "#### Tests\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 58, + "id": "f723c395", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 4\u001b[0m\n", + "\u001b[32mcmd58$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mxor\u001b[0m\n", + "\u001b[32m- should !xor(true, true)\u001b[0m\n", + "\u001b[32m- should xor(true, false)\u001b[0m\n", + "\u001b[32m- should xor(false, true)\u001b[0m\n", + "\u001b[32m- should !xor(false, false)\u001b[0m\n", + "\u001b[36mRun completed in 11 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 4\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 4, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n" + ] + }, + { + "data": { + "text/plain": [ + "\u001b[36mxorSuite\u001b[39m: \u001b[32mAnyFlatSpec\u001b[39m = cmd58$Helper$$anon$1" + ] + }, + "execution_count": 58, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val xorSuite = new AnyFlatSpec {\n", + " \"xor\" should \"!xor(true, true)\" in {\n", + " assert(!xor(true, true))\n", + " }\n", + " it should \"xor(true, false)\" in {\n", + " assert(xor(true, false))\n", + " }\n", + " it should \"xor(false, true)\" in {\n", + " assert(xor(false, true))\n", + " }\n", + " it should \"!xor(false, false)\" in {\n", + " assert(!xor(false, false))\n", + " }\n", + "}\n", + "report(xorSuite)" + ] + }, + { + "cell_type": "code", + "execution_count": 59, + "id": "5fc09530", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "475a7a4bd08579befea92b998fc9a712", + "grade": true, + "grade_id": "q3_2", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36mres59\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@2780f927" + ] + }, + "execution_count": 59, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "assertPassed(xorSuite)" + ] + }, + { + "cell_type": "markdown", + "id": "4b0a894d-67f5-480a-bbcb-2abe33b45784", + "metadata": {}, + "source": [ + "## Imperative Iteration and Complexity\n", + "\n", + "### Q4.1: Write a function `filterPairsByBound`\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 60, + "id": "a9436132", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "ed640d35faac5ce44926effc28995737", + "grade": false, + "grade_id": "q4_1_code", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mfilterPairsByBound\u001b[39m" + ] + }, + "execution_count": 60, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def filterPairsByBound(list: List[(Int, Int)], k: Int): List[(Int, Int)] =\n", + " list.filter { // iterate through the tuples in list\n", + " case (n1, n2) => // for each pair (n1, n2)...\n", + " // return appropriate value when leq k \n", + " // using our abs() function from Q3.1\n", + " abs(n1 - n2) <= k\n", + " }" + ] + }, + { + "cell_type": "markdown", + "id": "d95cdad4-4de8-440e-8a25-b1f9d901091a", + "metadata": {}, + "source": [ + "that given a list of pairs of integers, for example," + ] + }, + { + "cell_type": "code", + "execution_count": 61, + "id": "15116cf9", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36minput1_l\u001b[39m: \u001b[32mList\u001b[39m[(\u001b[32mInt\u001b[39m, \u001b[32mInt\u001b[39m)] = \u001b[33mList\u001b[39m(\n", + " (\u001b[32m1\u001b[39m, \u001b[32m5\u001b[39m),\n", + " (\u001b[32m2\u001b[39m, \u001b[32m7\u001b[39m),\n", + " (\u001b[32m15\u001b[39m, \u001b[32m14\u001b[39m),\n", + " (\u001b[32m18\u001b[39m, \u001b[32m19\u001b[39m),\n", + " (\u001b[32m14\u001b[39m, \u001b[32m28\u001b[39m),\n", + " (\u001b[32m0\u001b[39m, \u001b[32m0\u001b[39m),\n", + " (\u001b[32m35\u001b[39m, \u001b[32m24\u001b[39m)\n", + ")" + ] + }, + "execution_count": 61, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val input1_l = List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )" + ] + }, + { + "cell_type": "markdown", + "id": "46a2bbe6-ac0c-4fd1-a4e2-15f66b895bf8", + "metadata": {}, + "source": [ + "output a list consisting of just those pairs $(n_1, n_2)$ in the\n", + "original list wherein $|n_1 - n_2| \\leq k$ where $k$ is an integer given\n", + "as input. Ensure that the order of the elements in the output list is\n", + "the same as that in the input list.\n", + "\n", + "For the list `input1`, the expected output, with `k == 1`, the expected\n", + "output is as follows:" + ] + }, + { + "cell_type": "code", + "execution_count": 62, + "id": "c378241a", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36minput1_k\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m1\u001b[39m\n", + "\u001b[36moutput1\u001b[39m: \u001b[32mList\u001b[39m[(\u001b[32mInt\u001b[39m, \u001b[32mInt\u001b[39m)] = \u001b[33mList\u001b[39m((\u001b[32m15\u001b[39m, \u001b[32m14\u001b[39m), (\u001b[32m18\u001b[39m, \u001b[32m19\u001b[39m), (\u001b[32m0\u001b[39m, \u001b[32m0\u001b[39m))" + ] + }, + "execution_count": 62, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val input1_k = 1\n", + "val output1 = List( (15,14), (18,19), (0,0) )\n", + "assert(filterPairsByBound(input1_l, input1_k) == output1)" + ] + }, + { + "cell_type": "markdown", + "id": "b55b49e4-2a4b-4dc6-80de-c600151fcf5a", + "metadata": {}, + "source": [ + "With `k == 4`, the expected output is as follows:" + ] + }, + { + "cell_type": "code", + "execution_count": 63, + "id": "d05fe5b9", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36minput2_k\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m4\u001b[39m\n", + "\u001b[36moutput2\u001b[39m: \u001b[32mList\u001b[39m[(\u001b[32mInt\u001b[39m, \u001b[32mInt\u001b[39m)] = \u001b[33mList\u001b[39m((\u001b[32m1\u001b[39m, \u001b[32m5\u001b[39m), (\u001b[32m15\u001b[39m, \u001b[32m14\u001b[39m), (\u001b[32m18\u001b[39m, \u001b[32m19\u001b[39m), (\u001b[32m0\u001b[39m, \u001b[32m0\u001b[39m))" + ] + }, + "execution_count": 63, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val input2_k = 4\n", + "val output2 = List( (1, 5), (15, 14), (18, 19), (0,0) )\n", + "assert(filterPairsByBound(input1_l, input2_k) == output2)" + ] + }, + { + "cell_type": "markdown", + "id": "984c452b-5302-48a6-8fe1-e1a1ff22cbaa", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- Your function must be called `filterPairsByBound` with two\n", + " arguments: (1) a list of pairs of integers, and (2) the $k$ value.\n", + " It must return a list of pairs of integers.\n", + "- You can use `for`-loops (or `foreach`) and the following operators\n", + " for concatenating elements to a list:\n", + " - `:+` appends an element to the back of a list.\n", + " - `:::` concatenates two lists together.\n", + " - `::` prepends an element to the front of a list.\n", + "- You can use the `List` API method `reverse`. You may also use the\n", + " `Int` `abs` method to obtain the absolute value of an integer (or\n", + " use your `abs` function above).\n", + "- You should not use any other `List` API functions including\n", + " `filter`, `map`, `foldLeft`, `foldRight`, etc. Plenty of time to\n", + " learn them properly later on.\n", + "- Do not try to convert your list to an array or vector so that you\n", + " can mutate it.\n", + "- If you are unable to solve the problem without violating the\n", + " restrictions or unsure, ask us.\n", + "- You will need to use `var` given the above restrictions.\n", + "\n", + "#### Hints\n", + "\n", + "- In Scala, pairs of integers have the type `(Int, Int)`.\n", + "- A list containing pairs of integers has the type `List[(Int, Int)]`.\n", + "- Recall from the notes, here is how one iterates over the elements of\n", + " a list in Scala:" + ] + }, + { + "cell_type": "code", + "execution_count": 64, + "id": "757f5f83", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "1\n", + "2\n", + "3\n" + ] + }, + { + "data": { + "text/plain": [ + "\u001b[36mlist\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m3\u001b[39m)" + ] + }, + "execution_count": 64, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val list = List(1, 2, 3)\n", + "\n", + "for (elt <- list) {\n", + " // do stuff with elt\n", + " println(elt)\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "e8155fd8-8f76-4131-86e7-3d9bc3f583b4", + "metadata": {}, + "source": [ + "- Append an element to the end of a list and update a `var`:" + ] + }, + { + "cell_type": "code", + "execution_count": 65, + "id": "d20926f0", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<div class=\"jp-RenderedText\">\n", + "<pre><code><span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">resultList</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">List</span></span>[<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span>] = <span style=\"color: yellow\"><span class=\"ansi-yellow-fg\">List</span></span>(<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">1</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">2</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">3</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span>)\n", + "<span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">elt</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span> = <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span></code></pre>\n", + "</div>" + ], + "text/plain": [ + "\u001b[36mresultList\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m3\u001b[39m, \u001b[32m42\u001b[39m)\n", + "\u001b[36melt\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m42\u001b[39m" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "var resultList = List(1, 2, 3)\n", + "val elt = 42\n", + "\n", + "resultList = resultList :+ elt" + ] + }, + { + "cell_type": "markdown", + "id": "5143c58d-3849-4d7c-ad58-7021e92a1a92", + "metadata": {}, + "source": [ + "- Or, append an element to the end of a list using list concatenation\n", + " and update a `var`:" + ] + }, + { + "cell_type": "code", + "execution_count": 66, + "id": "6b76748c", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<div class=\"jp-RenderedText\">\n", + "<pre><code><span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">resultList</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">List</span></span>[<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span>] = <span style=\"color: yellow\"><span class=\"ansi-yellow-fg\">List</span></span>(<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">1</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">2</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">3</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span>)\n", + "<span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">elt</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span> = <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span></code></pre>\n", + "</div>" + ], + "text/plain": [ + "\u001b[36mresultList\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m3\u001b[39m, \u001b[32m42\u001b[39m)\n", + "\u001b[36melt\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m42\u001b[39m" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "var resultList = List(1, 2, 3)\n", + "val elt = 42\n", + "\n", + "resultList = resultList ::: List(elt)" + ] + }, + { + "cell_type": "markdown", + "id": "0cf8d689-25e9-4899-b369-228fb4a60c06", + "metadata": {}, + "source": [ + "- Prepend an element and update a `var`:" + ] + }, + { + "cell_type": "code", + "execution_count": 67, + "id": "a223964a", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<div class=\"jp-RenderedText\">\n", + "<pre><code><span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">resultList</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">List</span></span>[<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span>] = <span style=\"color: yellow\"><span class=\"ansi-yellow-fg\">List</span></span>(<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">1</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">2</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">3</span></span>)\n", + "<span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">elt</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span> = <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span></code></pre>\n", + "</div>" + ], + "text/plain": [ + "\u001b[36mresultList\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m42\u001b[39m, \u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m3\u001b[39m)\n", + "\u001b[36melt\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m42\u001b[39m" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "var resultList = List(1, 2, 3)\n", + "val elt = 42\n", + "\n", + "resultList = elt :: resultList" + ] + }, + { + "cell_type": "markdown", + "id": "7cadcb01-c735-4b13-8c34-ed06fefe0e39", + "metadata": {}, + "source": [ + "- *Warning*: The `:+`, `:::`, or other operations appending operations\n", + " take linear $O(n)$ time where $n$ is the length of the (left) list.\n", + " Thus, we will often try to avoid using these operations, but it is\n", + " ok to use it for this particular part.\n", + "\n", + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 68, + "id": "40a6d538", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "c9601d100de72d011a23f82aa2e58a37", + "grade": true, + "grade_id": "q4_1", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 6\u001b[0m\n", + "\u001b[32mcmd68$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mfilterPairsByBound\u001b[0m\n", + "\u001b[32m- should test1\u001b[0m\n", + "\u001b[32m- should test2\u001b[0m\n", + "\u001b[32m- should test3\u001b[0m\n", + "\u001b[32m- should test4\u001b[0m\n", + "\u001b[32m- should test5\u001b[0m\n", + "\u001b[32m- should test6\u001b[0m\n", + "\u001b[36mRun completed in 9 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 6\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 6, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n" + ] + }, + { + "data": { + "text/plain": [ + "\u001b[36mres68\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@d75bc07" + ] + }, + "execution_count": 68, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " \"filterPairsByBound\" should \"test1\" in {\n", + " val lst1 = List((1,1), (-1,1), (1,-1))\n", + " assertResult( List((1,1)) ){ filterPairsByBound(lst1,1) }\n", + " }\n", + "\n", + " it should \"test2\" in {\n", + " val lst2 = List((1,2), (2,1), (1,0), (0,1), (1,1))\n", + " assertResult( lst2 ){ filterPairsByBound(lst2,1) }\n", + " }\n", + "\n", + " it should \"test3\" in {\n", + " val lst3 = List((1,5), (5,1))\n", + " assertResult( Nil ){ filterPairsByBound(lst3,1) }\n", + " }\n", + "\n", + " it should \"test4\" in {\n", + " val lst4 = List((2,5), (1,2), (-5,-4), (4,1))\n", + " assertResult( List((1,2), (-5,-4)) ){ filterPairsByBound(lst4,1) }\n", + " }\n", + "\n", + " it should \"test5\" in {\n", + " val lst5 = List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )\n", + " assertResult( List((1, 5), (15, 14), (18, 19), (0,0)) ){ filterPairsByBound(lst5,4) }\n", + " }\n", + "\n", + " it should \"test6\" in {\n", + " val lst6 = List((1, 2), (2, 1), (1,0), (0,1), (1,1))\n", + " assertResult( List((1,1)) ){ filterPairsByBound(lst6,0) }\n", + " }\n", + "})" + ] + }, + { + "cell_type": "markdown", + "id": "5712b57c-1bd3-41a8-9c55-722b85829805", + "metadata": {}, + "source": [ + "### Q4.2: Write a function `filterPairsByBoundLinearTime`\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 69, + "id": "fadb020d", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "8725d2da34598302b7ff7ab5876da03b", + "grade": false, + "grade_id": "q4_2_code", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mfilterPairsByBoundLinearTime\u001b[39m" + ] + }, + "execution_count": 69, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def filterPairsByBoundLinearTime(list: List[(Int, Int)], k: Int): List[(Int, Int)] = {\n", + " // helper function to recursively process appropriate elements in list\n", + " def filterHelper(remaining: List[(Int, Int)], result: List[(Int, Int)]): List[(Int, Int)] = remaining match {\n", + " case Nil => // Nil represents empty set - do nothing\n", + " result\n", + " // iterate through list beginning at start (or rather current) element\n", + " case (n1, n2) :: tail =>\n", + " if (abs(n1 - n2) <= k)\n", + " // if necessary condition is met, prepend to result\n", + " filterHelper(tail, (n1, n2) :: result)\n", + " else\n", + " // otherwise continue to next element\n", + " filterHelper(tail, result)\n", + " }\n", + " filterHelper(list, Nil).reverse\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "0fa83488-63be-43d5-9905-3f2b4706318d", + "metadata": {}, + "source": [ + "If you followed the hint and ignored the linear-time warning in the\n", + "previous part\n", + "<a href=\"#sec-filterPairsByBound\" class=\"quarto-xref\">Section 4.1</a>,\n", + "then you would have used the `:+` or `:::` operation to append an\n", + "element to the end of a list at each step.\n", + "\n", + "``` scala\n", + "for (... <- list) {\n", + " // iterate over a loop\n", + " ...\n", + " newList = newList :+ newElement // This takes O(length of newList).\n", + "}\n", + "```\n", + "\n", + "Each `:+` or `:::` operation requires a full list traversal to find the\n", + "end of `newList` and then append to it. The overall algorithm thus\n", + "requires $O(n^2)$ time where is the length of the original `list` (also\n", + "the number of loop iterations).\n", + "\n", + "To illustrate, cut-and-paste and then run this code in a new test cell.\n", + "Just remember to delete that cell before you submit. It will take a long\n", + "time to run.\n", + "\n", + "``` scala\n", + "// Create a list of 1,000,000 pairs\n", + "val longTestList = (1 to 1000000).map(x => (x, x - 1)).toList\n", + "// Run the function you wrote\n", + "filterPairsByBound(longTestList, 1)\n", + "// This will take a long time to finish.\n", + "```\n", + "\n", + "In this problem, we wish to implement a function\n", + "`filterPairsByBoundLinearTime` that solves the exact same problem as the\n", + "previous part\n", + "<a href=\"#sec-filterPairsByBound\" class=\"quarto-xref\">Section 4.1</a>\n", + "but takes time linear in the size of the input list.\n", + "\n", + "To do so, we would like you to use the `::` (read “cons”) operator on a\n", + "list that prepends an element to the front of a list, instead of `:+` or\n", + "`:::` that appends to the back of a list.\n", + "\n", + "You will want to use the `List` `reverse` API method:" + ] + }, + { + "cell_type": "code", + "execution_count": 70, + "id": "e3731008", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36mlist\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m5\u001b[39m, \u001b[32m6\u001b[39m, \u001b[32m7\u001b[39m, \u001b[32m8\u001b[39m)\n", + "\u001b[36mr\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m8\u001b[39m, \u001b[32m7\u001b[39m, \u001b[32m6\u001b[39m, \u001b[32m5\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m1\u001b[39m)" + ] + }, + "execution_count": 70, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val list = List(1, 2, 5, 6, 7, 8)\n", + "val r = list.reverse" + ] + }, + { + "cell_type": "markdown", + "id": "6f9f4725-99b1-41e4-88a5-174ad8818a50", + "metadata": {}, + "source": [ + "The `r` has the reverse of `list`, and it works in linear time in the\n", + "length of `list`.\n", + "\n", + "The restrictions remain the same as the previous part\n", + "<a href=\"#sec-filterPairsByBound\" class=\"quarto-xref\">Section 4.1</a>,\n", + "but we would like you to focus on ensuring that your solution runs in\n", + "linear time.\n", + "\n", + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 71, + "id": "90d2d800", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "c1afc073bb37fd79685ece1caf82e854", + "grade": true, + "grade_id": "q4_2", + "locked": true, + "points": 7, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 6\u001b[0m\n", + "\u001b[32mcmd71$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mfilterPairsByBoundLinearTime\u001b[0m\n", + "\u001b[32m- should test1\u001b[0m\n", + "\u001b[32m- should test2\u001b[0m\n", + "\u001b[32m- should test3\u001b[0m\n", + "\u001b[32m- should test4\u001b[0m\n", + "\u001b[32m- should test5\u001b[0m\n", + "\u001b[32m- should test6\u001b[0m\n", + "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 6\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 6, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n" + ] + }, + { + "data": { + "text/plain": [ + "\u001b[36mres71\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@41a47f32" + ] + }, + "execution_count": 71, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " \"filterPairsByBoundLinearTime\" should \"test1\" in {\n", + " val lst1 = List((1,1), (-1,1), (1,-1))\n", + " assertResult( List((1,1)) ){ filterPairsByBoundLinearTime(lst1,1) }\n", + " }\n", + "\n", + " it should \"test2\" in {\n", + " val lst2 = List((1,2), (2,1), (1,0), (0,1), (1,1))\n", + " assertResult( lst2 ){ filterPairsByBoundLinearTime(lst2,1) }\n", + " }\n", + "\n", + " it should \"test3\" in {\n", + " val lst3 = List((1,5), (5,1))\n", + " assertResult( Nil ){ filterPairsByBoundLinearTime(lst3,1) }\n", + " }\n", + "\n", + " it should \"test4\" in {\n", + " val lst4 = List((2,5), (1,2), (-5,-4), (4,1))\n", + " assertResult( List((1,2), (-5,-4)) ){ filterPairsByBoundLinearTime(lst4,1) }\n", + " }\n", + "\n", + " it should \"test5\" in {\n", + " val lst5 = List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )\n", + " assertResult( List((1, 5), (15, 14), (18, 19), (0,0)) ){ filterPairsByBoundLinearTime(lst5,4) }\n", + " }\n", + "\n", + " it should \"test6\" in {\n", + " val lst6 = List((1, 2), (2, 1), (1,0), (0,1), (1,1))\n", + " assertResult( List((1,1)) ){ filterPairsByBoundLinearTime(lst6,0) }\n", + " }\n", + "})" + ] + }, + { + "cell_type": "markdown", + "id": "9c75c291-9711-4901-92f6-ef093fb92a6a", + "metadata": {}, + "source": [ + "## Submission\n", + "\n", + "#### Submission Instructions\n", + "\n", + "If you are a University of Colorado Boulder student, we use Gradescope\n", + "for assignment submission. In summary,\n", + "\n", + "- [ ] Work on a copy of this Jupyter notebook.\n", + "- [ ] Submit it to the corresponding Gradescope assignment entry for\n", + " grading.\n", + "\n", + "#### GitHub and Gradescope\n", + "\n", + "We use GitHub Classroom for assignment distribution, which gives you a\n", + "private GitHub repository to work on your assignment. While using GitHub\n", + "is perhaps overkill for this assignment, it does give you the ability to\n", + "version and save incremental progress on GitHub (lest your laptop fails)\n", + "and makes it easier to get help from the course staff. It will also\n", + "become particularly useful when more files are involved, and it is never\n", + "too early to get used to the workflow professional software engineers\n", + "use with Git.\n", + "\n", + "To use use GitHub and Gradescope,\n", + "\n", + "- [ ] Create a private GitHub repository by clicking on a GitHub\n", + " Classroom link from the corresponding Canvas assignment entry.\n", + "- [ ] Clone your private GitHub repository to your development\n", + " environment (using the `<> Code` button on GitHub to get the\n", + " repository URL).\n", + "- [ ] Work on the copy of this Jupyter notebook from your cloned\n", + " repository. Use Git to save versions on GitHub (e.g., `git add`,\n", + " `git commit`, `git push` on the command line, via JupyterLab, or via\n", + " VSCode).\n", + "- [ ] Submit to the corresponding Gradescope assignment entry for\n", + " grading by choosing GitHub as the submission method.\n", + "\n", + "You need to have a GitHub identity and must have your full name in your\n", + "GitHub profile in case we need to associate you with your submissions." + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Scala", + "language": "scala", + "name": "scala" + }, + "language_info": { + "codemirror_mode": "text/x-scala", + "file_extension": ".sc", + "mimetype": "text/x-scala", + "name": "scala", + "nbconvert_exporter": "script", + "version": "2.13.14" + } + }, + "nbformat": 4, + "nbformat_minor": 5 +} |