Tutorial 3a - Functional Patterns in action

8. Tutorial 3a - Functional Patterns in action#

The object of this tutorial is to solve one or more computational problems using algorithms that, where appropriate, employ some of the patterns introduced in Lecture 3a - Functional Patterns.

Try to employ some of the best practices below if you can

8.1. Pseudo Code in Markdown#

You might find the following example markdown code useful

Algorithm parameters: step size \(\alpha \in (0 , 1] , \epsilon > 0\)
Initialize \(Q ( s, a ), \ \forall s \in S^+ , a \in A ( s ),\) arbitrarily except that \(Q ( terminal , \cdot ) = 0\)

Loop for each episode:
\(\quad\)Initialize \(S\)
\(\quad\)Loop for each step of episode:
\(\qquad\)Choose \(A\) from \(S\) using some policy derived from \(Q\) (eg \(\epsilon\)-greedy)
\(\qquad\)Take action \(A\), observe \(R, S'\)
\(\qquad Q(S,A) \leftarrow Q(S,A) + \alpha[R+\gamma \max_a(S', a) - Q(S, A)]\)
\(\qquad S \leftarrow S'\)
\(\quad\) until \(S\) is terminal

8.2. Pseudo Code in LaTeX#

If you want to write pseudo code in LaTeX then the information here provides a good starting point.

8.3. Tasks#

8.3.1. Task 1#

Design an algorithm that solves the following computational problem

Inputs

a continuous monotonically strictly increasing function \(f : \cal{R} \rightarrow \cal{R}\)
\((x_{a},x_{b}) \in \cal{R} \times \cal{R} : x_{a} < x_{b} , f(x_{a}) < 0 < f(x_{b})\)
\(\delta \in \cal{R} : \delta \gt 0\)

Ouput

\((x_{a},x_{b}) \in \cal{R} \times \cal{R} : x_{a} < x_{b} , f(x_{a}) < 0 < f(x_{b})\) and \(f(x_{b}) - f(x_{a}) < \delta\)

Implement your algorithm in code.

Describe your algorithm using pseudo code.

8.3.2. Task 2#

Design an algorithm that solves the following computational problem

Inputs

a monotonically increasing function \(f : \cal{R} \rightarrow \cal{N}\)
\(n \in{\cal{N}}\)
\((x_{a},x_{b}) \in \cal{R} \times \cal{R} : x_{a} < x_{b} , f(x_{a}) \leq n \leq f(x_{b})\)

Ouput

a value \(x \in{\cal{R}}\) such that \(f(x) = n\)

Implement your algorithm in code.

Describe your algorithm using pseudo code.

8.3.3. Task 3#

Are there any similarities between your solutions to Task 1 and Task 2 ?

Are there any differences ?

Can you use any functional patterns to “abstract out” any commonalities between the algorithms ?

8.3.4. Task 4a#

Design an algorithm that solves the following computational problem

Inputs

a monotonically increasing function \(f : \cal{R} \rightarrow \cal{N}\)
\(n \in{\cal{N}}\)
\(\delta \in \cal{R} : \delta \gt 0\)
\((x_{a},x_{b}) \in \cal{R} \times \cal{R} : x_{a} + \delta < x_{b}, f(x_{a}) \leq n \leq f(x_{b})\)

Ouput

a value \(x \in{\cal{R}}\) such that \(f(x) = n\) and \(f(x + \delta) > n\)

Implement your algorithm in code.

Describe your algorithm using pseudo code.

8.3.5. Task 4b#

Some functions that form inputs to the computational problem in Task 4a may take a significant amount of time to compute. Is there anything you could do to mitigate the effects of this ? Could you use a functional pattern to help ?

8.3.6. Task 5#

Are there any similarities between your solutions to Task 3, Task 4 and Task 4b ?

Are there any differences ?

Can you use any functional patterns to “abstract out” any commonalities between the algorithms ?

8.3.7. Task 6#

You want to keep track of, amongst other things, how many times a function is being called when used in your algorithm from Task 4b. Can you do this without need for any modifications to your function or the implementation of your algorithm ? What patterns, if any, might be useful for this ?

8.3.8. Task 7#

You have a function \(f : \cal{R} \times \cal{N} \rightarrow \cal{N}\) where the second element of the domain is a parameter \(n\) say. You wish to use your function as an input to your algorithm from Task 4b over a range of values for the parameter \(n\). Using a small example function, demonstrate how you might do this. If you had to this for a large number of parameters what patterns might be useful ?