Thursday, 18 July 2019

AVL Tree in Java

I have not blogged for some time, but there is something new:  AVL Tree in Java. Code on github: https://github.com/lion137/Java .
Thanks, enjoy! 

Monday, 4 March 2019

Fundamental Algorithms: Parse to RPN

Another one, Parsing to Reverse Polish Notation. Why it's so important? For example, typing to the first calculators, one had to do it in RPN! It's very easy to find a value of an expression in RPN. Deadly simple, having one, like:
3 2 + 4 3 * +
It's enough to take en empty LIFO stack, go through it and:
1 When we see a number push it on stack.
2. Seeing operand, pop stack twice, perform the operation and push result.
3. When done pop stack - this is result!

Parsing is not such easy, but is explained in details, for example, here.
Code on github.
Whole Series.

Thank you!

Fundamental Algorithms: Links

Links to whole series:
1. Order Statistics - C++
2. Polynomial GCD, Polynomial Division - Python
3. Recursive Permutations, All the Subset of Set and Variations With Repetitions - C++
4.Parsing (and evaluating) to RPN

Wednesday, 27 February 2019

Fundamental Algorithms III

Three more fundamental algorithms in the series. Today, recursive permutations, subsets of the given set and variations with repetitions. The all written in C++ (non generic, I used std::vector). Code (hope it's self explanatory, any questions ask). 
Whole series.
Thank you.

Sunday, 3 February 2019

Fundamental Algorithms: Polynomial GCD

Another one in the series on fundamental algorithms; today: polynomial division. We assume, that polynomial is over some field, this is good thing, we have lots of nice properties in those; explicitly, if a and b are in the field and b is not zero, than there always exists an element of the field, c, such that a = bc.
So, division is easy, just "push it" over the field, like division in base, or multi precision division.
Algorithm, Knuth "The Art Computer Programming Vol 4" and the others:

# input: coefficients of polynomials as a lists u, v != 0
# in order u[0] = free coefficient of u(x), ....
# returns polynomials q, r such that u = vq + r(rest)
# length u >= length v >= 0
def poly_divide(u, v):
 m =   len(u) - 1
 n =   len(v) - 1
 q = [0] * (m - n + 1)
 lim = m - n
 for k in range(lim, -1, -1):
  q[k] = u[n + k] / v[n]
  for j in range(n + k - 1, k - 1, -1):
   u[j] = u[j] - q[k] * v[j - k]
 return q, u[:n]

Having division, we can compute the Great Common Divisor, showing, that Euclidean Domain is larger than expected:

def poly_gcd(u, v):
 if not any(v): return u
 else: return poly_gcd(v, poly_mod(u, v))

poly_mod  it's just a rest returned from division algorithm. I think it's beautiful, don't you?
The code, as usually on github , (division.py). Thank you, see you next time!