Problem Set #5: Parallel Programming

Objective

During this activity, students should be able to:

Solve problems that require parallel programming in Clojure.

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.

Create a namespace called parallelism and place all your code there.

For each problem do the following:

Write a sequential function that uses only one thread of execution.
Write a parallel function that uses at least $p$ threads of execution, where $p$ is the number of logical CPU cores available on your system. Parallelization should be achieved by utilizing the pmap function. You can get your system’s logical core count by using the following Clojure expression:
```
(.availableProcessors (Runtime/getRuntime))
```
Test repeatedly the sequential and parallel functions with data that takes more than a few hundred milliseconds to process. Measure and record their execution times ($T_1$ and $T_p$) and compute the corresponding speedup $S_p$.

IMPORTANT: Place the results of your measurements and speedup calculations within comments in your source file.

The factorial of a positive integer number $n$ is defined as follows:
$$ n! = \prod_{i=1}^{n}i=1 \times 2 \times 3 \times \cdots \times (n-2) \times (n-1) \times n $$
Write a Clojure function that takes $n$ as input and returns the number of bits equal to 1 from the binary result of the factorial of $n$. So, for example, if $n=6$ the function should return 4 because $6!=720$, and $720_d = 1011010000_b$ where the binary value has 4 bits that are equal to 1.

TIP: The following function can be used to count the number of bits equal to 1 in the binary representation of any integer value $x$:
```
(defn bits
  [x]
  (.bitCount (biginteger x)))
```
Numerical integration is a method of computing an approximation of the area under the curve of a function, especially when the exact integral cannot be solved. For example, the value of the constant $\pi$ can be defined by the following integral:
$$ \pi = \int_{0}^{1}\frac{4}{1+x^2}\mathit{dx} $$
However, rather than solve this integral exactly, we can approximate the solution by use of numerical integration. The following C code is an implementation of the numerical integration midpoint rectangle rule to solve the integral just shown. To compute an approximation of the area under the curve, we must compute the area of some number of rectangles (n) by finding the midpoint (mid) of each rectangle and computing the height of that rectangle (height), which is simply the function value at that midpoint. We add together the heights of all the rectangles (sum) and, once computed, we multiply the sum of the heights by the width of the rectangles (width) to determine the desired approximation of the total area (area) and the value of $\pi$.
```
double compute_pi(long n) {
    double sum = 0.0;
    double width = 1.0 / n;
    for (long i = 0; i < n; i++) {
        double mid = (i + 0.5) * width;
        double height = 4.0 / (1.0 + mid * mid);
        sum += height;
    }
    return width * sum;
}
```
Write an equivalent Clojure function. In general, you should get a better approximation of $\pi$ for larger values of n. Compare your results with the first 20 decimal places of $\pi$:
$$ 3.14159265358979323846 \ldots $$
Have in mind that 64-bit double precision floating point numbers are accurate up to sixteen decimal places but after multiple calculations have been done there may be some rounding errors to account for.
If you convert the number 17 to binary and hexadecimal you get $10001_2$ and $11_{16}$, respectively, which happen to be palindromes (a sequence that reads the same backward as forward). Other numbers that have this same property are: 0, 153 and 255. Let’s call these numbers bin-hex-palindromes.

Write a Clojure function takes a positive integer number $n$ as input. This function counts the total number of bin-hex-palindromes that are less than $2^n$. So, for example, if $n=7$ the function should return 11, because $2^7 = 128$, and there are 11 bin-hex-palindromes that are less than 128 (0, 1, 3, 5, 7, 9, 15, 17, 51, 85, and 119).

TIP: An easy way of converting a number to binary or hexadecimal is using the corresponding Java methods:
```
(Integer/toBinaryString 17)
⇒ "10001"

(Integer/toHexString 17)
⇒ "11"
```
Implement a hybrid recursive sort function that sorts a list of numbers in ascending order the following way:
- It the list has less than 100 elements, it performs a conventional insertion sort.
- Otherwise, it splits the list in two sublists of (roughly) equal length, sorts these two sublists recursively, and joins them afterwards using the merge algorithm.

Deliverables

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

;----------------------------------------------------------
; Problem Set #5: Parallel Programming
; Date: April 19, 2023.
; 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 parallelism.clj, ingresa los siguientes datos:

Solicitar NIP

Only one team member needs to upload the file.

Due date is Wednesday, April 19.

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.