Problem Set #3

Objectives

During this activity, students should be able to:

Write higher-order functions using the Clojure programming language.

This activity helps the student develop the following skills, values and attitudes: ability to analyze and synthesize, capacity for identifying and solving problems, and efficient use of computer systems.

Activity Description

Individually or in pairs, solve the following set of programming exercises using Clojure. Place all your functions and unit tests in a file called problemset3.clj.

Note:

The tests in problems 3, 5, and 6 require comparing floating point numbers. In order to avoid rounding problems, we need to define the following function called aprox=:

(require '[clojure.math.numeric-tower :refer [abs]])

(defn aprox=
  "Checks if x is approximately equal to y. Returns true
  if |x - y| < epsilon, or false otherwise."
  [epsilon x y]
  (< (abs (- x y)) epsilon))

The function there-exists-one takes two arguments: a one argument predicate function pred and a list lst. Returns true if there is exactly one element in lst that satisfies pred, otherwise returns false.

Unit tests:

(deftest test-there-exists-one
  (is (not (there-exists-one pos? 
                             ())))
  (is (there-exists-one pos?
                        '(-1 -10 4 -5 -2 -1)))
  (is (there-exists-one neg?
                        '(-1)))
  (is (not (there-exists-one symbol?
                             '(4 8 15 16 23 42))))
  (is (there-exists-one symbol?
                        '(4 8 15 sixteen 23 42))))

The function my-drop-while takes two arguments: a function f and a list lst. It returns a list of items from lst dropping the initial items that evaluate to true when passed to f. Once a false value is encountered, the rest of the list is returned. Function f should accept one argument. Do not use the predefined drop-while function.

Unit tests:

(deftest test-my-drop-while
  (is (= () (my-drop-while neg? ())))
  (is (= '(0 1 2 3 4)
         (my-drop-while
           neg?
           '(-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4))))
  (is (= '(2 three 4 five)
         (my-drop-while
           symbol?
           '(zero one 2 three 4 five))))
  (is (= '(0 one 2 three 4 five)
         (my-drop-while
           symbol?
           '(0 one 2 three 4 five)))))

The bisection method is a root-finding algorithm which works by repeatedly dividing an interval in half and then selecting the subinterval in which the root exists.

Suppose we want to solve the equation $ f(x) = 0 $. Given two points $ a $ and $ b $ such that $ f(a) $ and $ f(b) $ have opposite signs, $ f $ must have at least one root in the interval $ [a, b] $ as long as $ f $ is continuous on this interval. The bisection method divides the interval in two by computing $ c = \frac{a+b}{2} $. There are now two possibilities: either $ f(a) $ and $ f(c) $ have opposite signs, or $ f(c) $ and $ f(b) $ have opposite signs. The bisection algorithm is then applied to the sub-interval where the sign change occurs.

Write the function bisection, that takes a, b, and f as arguments. It finds the corresponding root using the bisection method. The algorithm must stop when a value of $ c $ is found such that: $ \left | f(c) \right | < 1.0\times 10^{-15} $.

Unit tests:
```
(deftest test-bisection
  (is (aprox= 0.0001
              3.0
              (bisection 1 4 (fn [x] (* (- x 3) (+ x 4))))))
  (is (aprox= 0.0001
              -4.0
              (bisection -5 0 (fn [x] (* (- x 3) (+ x 4))))))
  (is (aprox= 0.0001
              Math/PI
              (bisection 1 4 (fn [x] (Math/sin x)))))
  (is (aprox= 0.0001
              (* 2 Math/PI)
              (bisection 5 10 (fn [x] (Math/sin x)))))
  (is (aprox= 0.0001
              1.618033988749895
              (bisection 1 2 (fn [x] (- (* x x) x 1)))))
  (is (aprox= 0.0001
              -0.6180339887498948
              (bisection -10 1 (fn [x] (- (* x x) x 1))))))
```

The function linear-search takes three arguments: a vector vct, a data value x, and an equality function eq-fun. It sequentially searches for x in vct using eq-fun to compare x with the elements contained in vct. The eq-fun should accept two arguments, $a$ and $b$, and return true if $a$ is equal to $b$, or false otherwise.

The linear-search function returns the index where the first occurrence of x is found in vct (the first element of the vector is at index 0), or nil if not found.

Unit tests:

(deftest test-linear-search
  (is (nil? (linear-search [] 5 =)))
  (is (= 0 (linear-search [5] 5 =)))
  (is (= 4 (linear-search
             [48 77 30 31 5 20 91 92
              69 97 28 32 17 18 96]
             5
             =)))
  (is (= 3 (linear-search
             ["red" "blue" "green" "black" "white"]
             "black"
             identical?)))
  (is (nil? (linear-search
              [48 77 30 31 5 20 91 92
               69 97 28 32 17 18 96]
              96.0
              =)))
  (is (= 14 (linear-search
             [48 77 30 31 5 20 91 92
              69 97 28 32 17 18 96]
             96.0
             ==)))
  (is (= 8 (linear-search
             [48 77 30 31 5 20 91 92
              69 97 28 32 17 18 96]
             70
             #(<= (abs (- %1 %2)) 1)))))

The derivative of a function $ f(x) $ with respect to variable $ x $ is defined as:
$$ f'(x) \equiv \lim_{h\rightarrow 0}\frac{f(x+h)-f(x)}{h} $$
Where $ f $ must be a continuous function. Write the function deriv that takes f and h as its arguments, and returns a new function that takes x as argument, and which represents the derivative of $ f $ given a certain value for $ h $.

The unit tests verify the following derivatives:
$$ \begin{align*} f(x) &= x^3 \\ f'(x) &= 3x^2 \\ f''(x) &= 6x \\ f'''(x) &= 6 \\ f'(5) &= 75 \\ f''(5) &= 30 \\ f'''(5) &= 6 \end{align*} $$
Unit tests:
```
(defn f [x] (* x x x))
(def df (deriv f 0.001))
(def ddf (deriv df 0.001))
(def dddf (deriv ddf 0.001))

(deftest test-deriv
  (is (aprox= 0.05 75 (df 5)))
  (is (aprox= 0.05 30 (ddf 5)))
  (is (aprox= 0.05 6 (dddf 5))))
```
Newton’s method is another root-finding algorithm that is used to find successively better approximations. It can be summarized as follows:
$$ x_n = \begin{cases} 0 & \text{ if } n=0 \\ x_{n-1}-\frac{f(x_{n-1})}{f'(x_{n-1})} & \text{ if } n > 0 \end{cases} $$
A few things worth noting:
- $ f $ must be a differentiable real-valued function.
- Larger values of $ n $ produce better approximations.
- $ x_0$ is the initial guess, which is recommended to be a value that is close to the solution. This allows getting sooner a better approximation. Yet, for simplicity, we always assume here that $ x_0 = 0$.
Write the function newton that takes f and n as its arguments, and returns the corresponding value of $ x_n $. Use the deriv function from the previous problem to compute $ f' $, with $ h = 0.0001$.

Unit tests:
```
(deftest test-newton
  (is (aprox= 0.00001
              10.0
              (newton (fn [x] (- x 10))
                      1)))
  (is (aprox= 0.00001
              -0.5
              (newton (fn [x] (+ (* 4 x) 2))
                      1)))
  (is (aprox= 0.00001
              -1.0
              (newton (fn [x] (+ (* x x x) 1))
                      50)))
  (is (aprox= 0.00001
              -1.02987
              (newton (fn [x] (+ (Math/cos x)
                                 (* 0.5 x)))
                      5))))
```
Simpson’s rule is a method for numeric integration:
$$ \int_{a}^{b}f=\frac{h}{3}(y_0 + 4y_1 + 2y_2 + 4y_3 + 2y_4 + \cdots + 2y_{n-2} + 4y_{n-1} + y_n) $$
Where $ n $ is an even positive integer (if you increment the value of $ n $ you get a better approximation), and $ h $ and $ y_k $ are defined as follows:
$$ h = \frac{b - a}{n} $$ $$ y_k = f(a + kh) $$
Write the function integral, that takes as arguments a, b, n, and f. It returns the value of the integral, using Simpson’s rule. The unit tests verify the following single and double integrals (with n = 10):
$$ \int_{0}^{1} x^3\textit{dx} = \frac{1}{4} $$ $$ \int_{1}^{2} \int_{3}^{4} xy \cdot \textit{dx} \cdot \textit{dy} = \frac{21}{4} $$
Unit tests:
```
(deftest test-integral
  (is (= 1/4 (integral 0 1 10 (fn [x] (* x x x)))))
  (is (= 21/4
         (integral 1 2 10
           (fn [x]
             (integral 3 4 10
               (fn [y]
                 (* x y)))))))) 
```

The function binary-search takes three arguments: a vector vct sorted in ascending order and with no repeated elements, a data value x, and a less than function lt-fun. It implements the binary search algorithm, searching for x in vct using the lt-fun to compare x with the elements contained in vct. The lt-fun should accept two arguments, $a$ and $b$, and return true if $a$ is less than $b$, or false otherwise.

The binary-search function returns the index where x is found in vct (the first element of the vector is at index 0), or nil if not found.

Binary search consists in searching a sorted vector by repeatedly dividing the search interval in half. You begin with an interval covering the whole vector. If the value being searched is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Unit tests:

(def small-list [4 8 15 16 23 42])

(def big-list [0 2 5 10 11 13 16 20 24 26
               29 30 31 32 34 37 40 43 44
               46 50 53 58 59 62 63 66 67
               70 72 77 79 80 83 85 86 94
               95 96 99])

(def animals ["dog" "dragon" "horse" "monkey" "ox"
              "pig" "rabbit" "rat" "rooster" "sheep"
              "snake" "tiger"])
(defn str<
  "Returns true if a is less than b, otherwise
   returns false. Designed to work with strings."
  [a b]
  (< (compare a b) 0))

(deftest test-binary-search
  (is (nil? (binary-search [] 5 <)))
  (is (= 3 (binary-search small-list 16 <)))
  (is (= 0 (binary-search small-list 4 <)))
  (is (= 5 (binary-search small-list 42 <)))
  (is (nil? (binary-search small-list 7 <)))
  (is (nil? (binary-search small-list 2 <)))
  (is (nil? (binary-search small-list 99 <)))
  (is (= 17 (binary-search big-list 43 <)))
  (is (= 0 (binary-search big-list 0 <)))
  (is (= 39 (binary-search big-list 99 <)))
  (is (nil? (binary-search big-list 12 <)))
  (is (nil? (binary-search big-list -1 <)))
  (is (nil? (binary-search big-list 100 <)))
  (is (= 5 (binary-search animals "pig" str<)))
  (is (= 0 (binary-search animals "dog" str<)))
  (is (= 11 (binary-search animals "tiger" str<)))
  (is (nil? (binary-search animals "elephant" str<)))
  (is (nil? (binary-search animals "alligator" str<)))
  (is (nil? (binary-search animals "unicorn" str<))))

Deliverables

The program source file must include at the top the authors’ personal information (name and student id) within comments. For example:

;----------------------------------------------------------
; Problem Set #3
; Date: October 04, 2019.
; Authors:
;          A01166611 Pepper Pots
;          A01160611 Anthony Stark
;----------------------------------------------------------

Also, each function should include a documentation string (docstring) with a brief description of its behavior. For example:

(defn max2
  "Returns the largest of the two numbers x and y."
  [x y]
  (if (> x y) x y))

Upload Instructions

To deliver the problemset3.clj file, please provide the following information:

Request PIN

Only one team member needs to upload the file.

Due date is Friday, October 4.

Evaluation

This activity will be evaluated using the following criteria:

-10	The program doesn't contain within comments the author's personal information.
-30	A docstring is missing in one or more functions.
10	The program contains syntax errors.
1	The program was plagiarized in whole or in part.
10-100	Depending on the amount of exercises that were solved correctly.