<div style="text-align: right">
316507, 309995, 300862, 298154, 300245<br>
Group 43
</div>

# Exercises 1

## Problem 1: Introduction to Concurrency

### Question 1

Yes, the two properties hold in a sequential environment.

### Question 2

If we have multiple threads acting on the same `from` account, his final sold could be negative. The amount of money in the bank will stay constant.
Indeed, if for example, `thread 1` checks the balance, then `thread 2` checks the balance, then they both take off the money. It could be that the `from` account does not have enough money for both transfers, but the threads both already entered the `if`.

### Question 3

**Variant 1**

* **Property 1:** Does not hold
* **Property 2:** Holds
* **Deadlock:** Not vulnerable

**Variant 2**

* **Property 1:** Holds
* **Property 2:** Holds
* **Deadlock:** Vulnerable

**Variant 3**

* **Property 1:** Holds
* **Property 2:** Holds
* **Deadlock:** Not vulnerable

## Problem 2: Parallel Reductions

### Question 1

**Sequential version**

import scala.math._

def minMax(a: Array[Int]): (Int, Int) =
  if (a.size == 0)
    throw new IllegalArgumentException
  if (a.size== 1)
    (a.head, a.head)
  else
    val b = minMax(a.tail)
    (min(a.head, b._1), max(a.head, b._2))

minMax(Array(1, 99, -36, 4)

**Parallel version**

val maxDepth = 8; // limits number of threads
val threshold = 2; // don't create new task under a certain threshold 

def minMaxPar(a: Array[Int], from: Int, to: Int, depth: Int): (Int, Int) =
  if (depth > maxDepth || to - from < threshold)
    minMax(a: Array[Int], from, to)
  else
    val mid = floor((from - to)/2)
    val result = parallel(minMaxPar(a,from, mid, depth + 1),
                          minMaxPar(a, mid,  to, depth + 1))
    (min(result._1, result._1), max(result._2, result._2))

### Question 2

def minMax(a: Array[Int]): (Int, Int) =
  (a.reduce((x, y) => min(x,y)), a.reduce((x, y) => max(x, y)))

### Question 3

`f` needs to be be associative, that is, we want to showm that
$$\max(a,\max(b, c))\iff\max(\max(a,b),c),\ \forall\ a,b,c\in \mathbf{Z}$$

We procede by proving 6 subcases:
* $a\leq b\leq c$
* $\max(a, \max(b, c)) = \max(a, c) = c$
* $\max(\max(a, b), c) = \max(b, c) = c$
* $a\leq c\leq b$
* $\max(a, \max(b, c)) = \max(a, b) = b$
* $\max(\max(a, b), c) = \max(b, c) = b$
* $b\leq c\leq a$
* $\max(a, \max(b, c)) = \max(a, b) = a$
* $\max(\max(a, b), c) = \max(a, c) = a$
* $b\leq a\leq c$
* $\max(a, \max(b, c)) = \max(a, c) = c$
* $\max(\max(a, b), c) = \max(a, c) = c$
* $c\leq b\leq a$
* $\max(a, \max(b, c)) = \max(a, b) = a$
* $\max(\max(a, b), c) = \max(a, c) = a$
* $c\leq a\leq b$
* $\max(a, \max(b, c)) = \max(a, b) = b$
* $\max(\max(a, b), c) = \max(b, c) = b$

Because all triplets $(a,b,c)$ belong to one of those cases, we proved that the $\max$ function is associative for any $(a,b,c)\in \mathbf{Z}$.

We can easily develop a similar reasoning for the $\min$ function.