Nippashish

Dots

${\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}}$

...

${\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}}$

...

${\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:

${\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:

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

Want to find the longest monotonically increasing subsequence.

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

$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 $\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 $\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 $\scriptstyle \{s_{1},s_{2},\ldots ,s_{k}\}$
       ending with $\scriptstyle s_{k}$.  Initially filled with 0's.

  // Build the dynamic program 
  L[1] <- 1
  for $\scriptstyle i=2\ldots n$
    longest <- 0
    for $\scriptstyle j=1\ldots i-1$
      if $\scriptstyle S[n]\geq S[j]$
        if $\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 $\scriptstyle i=1\ldots n$
    if $\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 $\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 $\scriptstyle \{s_{1},s_{2},\ldots ,s_{k}\}$
      ending with $\scriptstyle s_{k}$.
  f - The index of the final integer in the solution.
Output
  The optimal sequence.
Begin
  if $\scriptstyle D[f]>0$
    PrintMonotonicIncrease(S, D, D[f])
    print S[f]
End

Test Work

Try this out...

$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...

$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