# Dots

{\displaystyle {\begin{aligned}x&={\begin{bmatrix}1\\0\end{bmatrix}}\\v&={\begin{bmatrix}v_{1},v_{2}\end{bmatrix}}\\R&={\begin{bmatrix}\cos(\theta )&-\sin(\theta )\\\sin(\theta )&\cos(\theta )\end{bmatrix}}\\Rx&={\begin{bmatrix}\cos(\theta )\\\sin(\theta )\end{bmatrix}}\end{aligned}}}

...

{\displaystyle {\begin{aligned}dot(Rx,v)-|v|&=0\\v_{1}\cos(\theta )+v_{2}\sin(\theta )-{\sqrt {v_{1}^{2}+v_{2}^{2}}}&=0\\v_{1}\cos(\theta )+v_{2}\sin(\theta )&={\sqrt {v_{1}^{2}+v_{2}^{2}}}\\(v_{1}\cos(\theta )+v_{2}\sin(\theta ))^{2}=v_{1}^{2}+v_{2}^{2}\\v_{1}^{2}\cos ^{2}(\theta )+v_{2}^{2}\sin ^{2}(\theta )+v_{1}v_{2}\cos(\theta )\sin(\theta )&=v_{1}^{2}+v_{2}^{2}\\v_{1}^{2}\cos ^{2}(\theta )+v_{2}^{2}\sin ^{2}(\theta )+v_{1}v_{2}\cos(\theta )\sin(\theta )-v_{1}^{2}-v_{2}^{2}&=0\end{aligned}}}

...

{\displaystyle {\begin{aligned}F(v_{1},v_{2},\theta )&=v_{1}^{2}\cos ^{2}(\theta )+v_{2}^{2}\sin ^{2}(\theta )+v_{1}v_{2}\cos(\theta )\sin(\theta )-v_{1}^{2}-v_{2}^{2}\\DF(v_{1},v_{2},\theta )&={\begin{bmatrix}2v_{1}\cos ^{2}(\theta )+v_{2}\cos(\theta )\sin(\theta )-2v_{1}\\2v_{2}\sin ^{2}(\theta )+v_{1}\cos(\theta )\sin(\theta )-2v_{2}\\(2v_{2}^{2}-2v_{1}^{2})\cos(\theta )\sin(\theta )+v_{1}v_{2}(\cos ^{2}(\theta )-\sin ^{2}(\theta ))\\\end{bmatrix}}^{T}\end{aligned}}}

Not solvable when:

{\displaystyle {\begin{aligned}(2v_{2}^{2}-2v_{1}^{2})\cos(\theta )\sin(\theta )+v_{1}v_{2}(\cos ^{2}(\theta )-\sin ^{2}(\theta ))=0\end{aligned}}}

# Monotonically Increasing

Given a sequence of n numbers:

${\displaystyle S=\{s_{1},s_{2},\ldots ,s_{n}\}}$

Want to find the longest monotonically increasing subsequence.

Define the function ${\displaystyle \textstyle L(n)}$ as the length of the longest monotonically increasing subsequence in the first n elements.

${\displaystyle L(n)={\begin{cases}1&\quad {\mbox{if }}n=1\\\max _{i=1}^{n-1}(L(n-i))+1&\quad {\mbox{where }}s_{n}\geq s_{i}\end{cases}}}$

## Algorithm

Algorithm MonotonicIncrease(S, n)
Input
S - A sequence of numbers ${\displaystyle \scriptstyle \{s_{1},s_{2},\ldots ,s_{n}\}}$.
n - The length of the sequence S.
Output
A monotonically increasing subsequence of S of maximal length.
Begin
L <- An array of n integers with L[k] is the length of the longest monotonic
subsequence in ${\displaystyle \scriptstyle \{s_{1},s_{2},\ldots ,s_{k}\}}$.
D <- An array of n integers where D[k] holds the index of the previous
number in the longest monotonic sequence in ${\displaystyle \scriptstyle \{s_{1},s_{2},\ldots ,s_{k}\}}$
ending with ${\displaystyle \scriptstyle s_{k}}$.  Initially filled with 0's.

// Build the dynamic program
L[1] <- 1
for ${\displaystyle \scriptstyle i=2\ldots n}$
longest <- 0
for ${\displaystyle \scriptstyle j=1\ldots i-1}$
if ${\displaystyle \scriptstyle S[n]\geq S[j]}$
if ${\displaystyle \scriptstyle L[j]\geq L[longest]}$
longest <- j
D[i] <- longest
L[i] <- L[longest] + 1

// Find the endpoint of the longest sequence
f <- 1
for ${\displaystyle \scriptstyle i=1\ldots n}$
if ${\displaystyle \scriptstyle L[i]>L[f]}$
f <- i

// Print the solution
PrintMonotonicIncrease(S, D, f)
End


Algorithm PrintMonotonicIncrease(S, D, f)
Input
S - A sequence of numbers ${\displaystyle \scriptstyle \{s_{1},s_{2},\ldots ,s_{n}\}}$.
D - An array of n integers where D[k] holds the index of the previous
number in the longest monotonic sequence in ${\displaystyle \scriptstyle \{s_{1},s_{2},\ldots ,s_{k}\}}$
ending with ${\displaystyle \scriptstyle s_{k}}$.
f - The index of the final integer in the solution.
Output
The optimal sequence.
Begin
if ${\displaystyle \scriptstyle D[f]>0}$
PrintMonotonicIncrease(S, D, D[f])
print S[f]
End



## Test Work

Try this out...

${\displaystyle S=\{1,4,2,7,8,4,5\}}$

o---o---o---o---o---o---o---o
| 1 | 4 | 2 | 7 | 8 | 4 | 5 |
o---o---o---o---o---o---o---o
| 1 | 2 | 2 | 3 | 4 | 4 | 4 |
o---o---o---o---o---o---o---o


And this...

${\displaystyle S=\{1,3,3,7,2,6,4,5,6,1,8,3,2,6\}}$

o---o---o---o---o---o---o---o---o---o---o---o---o---o---o
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14|
o---o---o---o---o---o---o---o---o---o---o---o---o---o---o
| 1 | 3 | 3 | 7 | 2 | 6 | 4 | 5 | 6 | 1 | 8 | 3 | 2 | 6 |
o---o---o---o---o---o---o---o---o---o---o---o---o---o---o
| 1 |1 2|2 3|3 4|1 2|3 4|3 4|7 5|8 6|1 2|9 7|3 4|5 3|9 7|
o---o---o---o---o---o---o---o---o---o---o---o---o---o---o