COMP302 OCaml HW1
## Introduction
Copyright By PowCoder代写 加微信 powcoder
Welcome to the Learn-OCaml automated grading platform! Your homeworks will be supplied on this website for the duration of this course.
The questions you will be given in the assignments will generally consist of two parts: writing tests and writing code. For each problem to solve, you will first be asked to write up tests, written as a list of `(input, output)` pairs. That is, each element of the list has to be a pair, with the first element being a tuple of arguments for the function you want to test, and the second element the answer you expect the function to return on those arguments. You can see some examples of this in the code we have provided for you.
It is important that you design these tests **before** writing your code: the goal of these exercises is for you to think about the problem and design test cases that represent a sufficient range of possible inputs to thoroughly eliminate any bugs in your implementation. The grader will also tell you whether or not your test cases are correct, so you can use this to make sure that you understand what kind of values your function should return. Until you have written a sufficient set of test cases, we will not show you our own test cases that we are running on your code.
We will evaluate the test cases you create by running the given inputs on slightly incorrect versions of the function in question: we then expect that at least one of the `(input, output)`pairs you provide will not be matched by the buggy code. If the buggy version passes all of your tests (that is, given those inputs, the buggy version produces outputs identical to the ones given), your test list will be deemed insufficient to expose the bug. This is known in the software development industry as mutation testing.
Following the writing of tests, you will need to implement the function or behaviour in question. This is very straightforward coding. However, remember that you should not rely on your knowledge of other programming languages or paradigms, but instead use what you are taught in this course. For example, you should never be solving the question in a different language and then translating it to OCaml, and you should not be using programming constructs that have not been discussed in class.
The Learn-OCaml platform provides you with the following tools to help you out:
– The **Compile** button runs syntax- and type-checking. If this returns errors, most other functionalities will not work for you. Use the red highlights of the line numbers to see where your errors are.
– The **Grade** button evaluates your code against our tests and solutions, and returns a grade. Remember to run this at least once to get a grade! The **Report** tab then explains where you received — or failed to receive — your points.
– The **Toplevel** tab allows you to interact with OCaml, providing you with a read-eval-print loop (REPL) system. Entering an expression in the bottom text box and pressing Enter will evaluate it. You may do line breaks by pressing Ctrl-Enter (Cmd-Enter on a Mac).
– The **Eval code** button loads your code into the Toplevel, without you copying and pasting it into the text box. Convenience!
## Question 1 : Fix Me
Three functions have been implemented *incorrectly* in the provided template code:
– `fact: int -> float`: Given a number n≥0, return n!, that is, n⋅(n−1)⋅(n−2)⋅…⋅1. The result should be returned as a floating-point number.
– `binomial: int -> int -> float`: Given a number n≥0 and a number n≥k≥0, the binomial coefficient, is defined as n!k!(n−k)!. The result should be returned as a floating-point number.
– `distance: (int * int) -> (int * int) -> float`: Given two points (x1, y1) and (x2, y2), return the Euclidean distance between the two points, equivalent to the length of a straight line segment connecting the two points. The result should be returned as a floating-point number.
First, write up some tests for these three functions. Write tests for the function `fact` in the list named `fact_tests`, the ones for `binomial` in `binomial_tests`, and the ones for `distance`in `distance_tests` respectively. Some example test cases are provided for the `fact` function, but they are incorrect; you should fix them.
**Note**: you should *only* write test cases for valid inputs, i.e. you should *not* write tests for negative numbers for this question.
Then, correct the various syntax, type and logical errors contained in both functions’ implementations. Use the **Compile** button at the top-right to help yourself find syntax and type errors, then use the **Grade** button to analyze the logical errors.
## Question 2 : Prime Number
Implement the function `is_prime : int -> bool`.
This can be done naively as follows: to test whether given `n` (where `n > 1`) is prime, we try to find a number that divides `n` by checking for each number `x` where `x * x <= n` whether it divides n. For inputs `n <= 1`, you should raise the exception `Domain` A given integer n may have many factors or very few. Note that 1 and n are always factors of n. In some cases (if n is prime) these are the only factors. As above, first write tests (for `n > 1`) in the corresponding list, then implement the function.
## Question 3 :
To continue on the topic of famous unsolved problems, one such problem is the . While it has to do with complex numbers and infinite sequences, we will instead attempt to evaluate the connected Riemann zeta function at real-valued arguments.
Did you know?
The is one of 6 remaining Millenium problems; solving any one of them grants incredible prestige as well as $1,000,000! [[5\]](https://www.claymath.org/millennium-problems/millennium-prize-problems). It also was one of the 23 problems that famous mathematician put forth in 1900; only 4 of those, including the Riemann hypothesis, are definitely unresolved presently. [[6\]](https://en.wikipedia.org/wiki/Hilbert’s_problems#Table_of_problems)
The Riemann zeta function is an infinite sum:
ζ(k)=∑n=1∞n−k
Your job is to implement a function `approx_zeta` that approximates the value ζ(k) for a given `float` k, as well as an accuracy value `acc`. As this is about adding more and more terms, your function’s job is to stop once the next term to add is below `acc`. As usual, first write up some tests in the list named `zeta_tests`. One way you can get the expected outputs for any inputs for your tests is via WolframAlpha; search for “zeta function at s = 3” for example.
We use `epsilon_float` as the desired accuracy, which in OCaml is the difference between `1.0`and the smallest exactly representable floating-point number greater than `1.0`.
Note that we made `approx_zeta` a local function to be defined inside the function `zeta k`. This function also makes sure that your function receives values of k larger than 2 – while this function is well-defined for k even for numbers between 1 and 2, the evaluation would take too long for such arguments.
## Question 4 : Fibonacci Sequence
In this question we will implement the `fib` function tail recursively. Recall the Fibonacci sequence (indexed at 0):
1, 1, 2, 3, 5, 8, …, fib(n−1)+fib(n−2)
1. First write a good set of test cases for `fib_tl`. Remember that you should *only* write tests for cases where n≥0.
2. Then, implement `fib_tl` by writing a tail-recursive helper function `fib_aux: int -> int -> int -> int`. Note that this helper function needs *two* accumulators.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com