Métodos computacionales

Problem Set #4: Higher-Order Functions

Objective

During this activity, students should be able to:

This activity helps students 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

Solve with your team the Clojure exercises described in this problem set. Make sure each function passes all the unit tests.

Create a namespace called higher-order-functions. At the begining of the file add the following code in order to declare the namespace and import the required external functions:

(ns higher-order-functions
  (:require [clojure.test :refer [deftest is run-tests]])
  (:require [clojure.algo.generic.math-functions
             :refer [abs approx=]]))

and at the end add:

(run-tests)

All the code you write should go between these two instructions.

  1. The argswap function takes as input a two argument function \(f\) and returns a new function that behaves like \(f\) but with the order of its two arguments swapped. In other words:

    $$ ((\texttt{argswap} \; f) \; x \; y) \equiv (f \; y \; x) $$

    Unit tests:

    (deftest test-argswap
      (is (= '(2 1)
             ((argswap list) 1 2)))
      (is (= -7
             ((argswap -) 10 3)))
      (is (= 1/4
             ((argswap /) 8 2)))
      (is (= '((4 5 6) 1 2 3)
             ((argswap cons) '(1 2 3) '(4 5 6))))
      (is (= '(1 0 4 25 100)
             ((argswap map) '(-1 0 2 5 10) #(* % %)))))
    
  2. The function there-exists-one takes two inputs: a one argument predicate function \(\textit{pred?}\) and a sequence \(s\). Returns true if there is exactly one element in \(s\) that satisfies \(\textit{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))))
    
  3. The function linear-search takes three inputs: a vector \(\textit{vct}\), a data value \(x\), and an equality function \(\textit{eq-fun}\). It sequentially searches for \(x\) in \(\textit{vct}\) using \(\textit{eq-fun}\) to compare \(x\) with the elements contained in \(\textit{vct}\). The \(\textit{eq-fun}\) should accept two inputs, \(a\) and \(b\), and return true if \(a\) and \(b\) should somehow be considered the same value, or false otherwise.

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

    IMPORTANT: Make sure that for a vector of size \(N\) the time complexity of your implementation is \(O(N)\).

    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)))))
    
  4. 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 input, and returns a new function that takes \(x\) as input, 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 (approx= 75 (df 5) 0.05))
      (is (approx= 30 (ddf 5) 0.05))
      (is (approx= 6 (dddf 5) 0.05)))
  5. Newton’s method is a 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 inputs, 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 (approx= 10.0
                   (newton (fn [x] (- x 10))
                           1)
                   0.00001))
      (is (approx= -0.5
                   (newton (fn [x] (+ (* 4 x) 2))
                           1)
                   0.00001))
      (is (approx= -1.0
                   (newton (fn [x] (+ (* x x x) 1))
                           50)
                   0.00001))
      (is (approx= -1.02987
                   (newton (fn [x] (+ (Math/cos x)
                                      (* 0.5 x)))
                           5)
                   0.00001)))
  6. 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 inputs \(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))))))))
  7. The function binary-search takes three inputs: a vector \(\textit{vct}\) with its elements sorted in ascending order and with no repetitions, a data value \(x\), and a less than function \(\textit{lt-fun}\). It implements the binary search algorithm, searching for \(x\) in \(\textit{vct}\) using the \(\textit{lt-fun}\) to compare \(x\) with the elements contained in \(\textit{vct}\). The \(\textit{lt-fun}\) should accept two inputs, \(a\) and \(b\), and return true if \(a\) should somehow be considered less than \(b\), or false otherwise.

    Note that \(\textit{lt-fun}\) can be used to perform each and every relational comparison that you might eventually need:

    (lt-fun x y)                          ; Equivalent to: x < y
    (lt-fun y x)                          ; Equivalent to: x > y
    (not (lt-fun x y))                    ; Equivalent to: x >= y
    (not (lt-fun y x))                    ; Equivalent to: x <= y
    (or (lt-fun x y) (lt-fun y x))        ; Equivalent to: x != y
    (not (or (lt-fun x y) (lt-fun y x)))  ; Equivalent to: x == y

    The binary-search function returns the index where \(x\) is found in \(\textit{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.

    IMPORTANT: Make sure that for a vector of size \(N\) the time complexity of your implementation is \(O(\log N)\).

    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 (student ID and name) within comments. For example:

;----------------------------------------------------------
; Problem Set #4: Higher-Order Functions
; Date: March 31, 2022.
; Authors:
;          A01770771 Sylvie Laufeydottir
;          A01777771 Loki Laufeyson
;----------------------------------------------------------

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))

Instrucciones para subir archivo

Para entregar el archivo higher_order_functions.clj, ingresa los siguientes datos:

Solicitar NIP

Only one team member needs to upload the file.

Due date is Thursday, March 31.

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.