# Thoughts In Free Time

## Friday, 16 February 2018

### Numeric Algorithms

Been it busy for a while, but I haven't forgotten about blog. Started new repo with numeric algorithms in Python: code . Awaiting news here!

## Sunday, 27 August 2017

### Graph Connectivity in Python

Interested algorithm in Python Graps Repo, checking connectivity of two vertex in O(1) memory usage! Algorithm with description on github. Till the next time!

## Sunday, 20 August 2017

### Topological Sort in Python Graphs

Just 've added topological sort to my Python Graph algorithms!; updates here soon:)

## Thursday, 17 August 2017

### New Repository: Python Graphs!

I have a new repo on my github: Python-Graphs. There are just few very basic graph algorithms; in fact variations of one, say, Any First Search.

Depends what is plugged as a data_structure, we have dfs, bfs, or Minimum Spanning Tree algorithm, with some modification, of course. For example using data structure LIFO stack we have Depth First Search:

FIFO stack gave as Breadth First Search, etc..

Amount of problems which can be solved using graphs is huge, we even say: "If you have problem and can make graph from it, do it and problem solved":). Code as usually on github. Thats all, thank you, enjoy!

def afs(g, s): bag = data_structure() bag.add(s) while bag is not empty: tile = bag.pop() if tile is not marked: mark(tile) for x in adj_list(tile): bag.add(x)

Depends what is plugged as a data_structure, we have dfs, bfs, or Minimum Spanning Tree algorithm, with some modification, of course. For example using data structure LIFO stack we have Depth First Search:

def dfs(g, v): if v is not marked: mark(v) for w in adj_list(v): dfs(g, w)

FIFO stack gave as Breadth First Search, etc..

Amount of problems which can be solved using graphs is huge, we even say: "If you have problem and can make graph from it, do it and problem solved":). Code as usually on github. Thats all, thank you, enjoy!

## Thursday, 3 August 2017

### Java Rational

Hi all, I had an idea: create Rational, Bigrational and Complex(not done yet) classes in Java to allow exact computation - get rid of rounding errors. Rational can be initialized in various ways, for example using String; after the end of the computation, there are toDecimal methods, to print result as a decimal or BigDecimal in the case of BigRational. Ther is no overflow check, so we have to make a decision which class to use. Code as usually on github. Enjoy!

## Tuesday, 4 July 2017

### Unrolled List In Java

Hello!

Didn't write to much recently, being busy, but I got something for you: Unrolled Linked List in Java.

This is an Wikipedia article; in my implementation, there is no remove and insert function - it would complicate API too much, imo.

It has O(1) performance with: push, add, pop (removes the first) and popLast. Performance of:

- replace (updates element with the given index) and

- get (returns - not remove an element with the given index)

are O(n / [#of internal arrays]) - which is better (with max elements 1000 and n = million would be 500) than pure Linked List and obviously worst than Augumented Array.

There is a bigger memory overhead per node: an array of elements plus some helper fields; for million integers, there would be around 1600 bytes overhead plus whatever comes from arrays management.

Where to use it? Any queues, stacks, et cetera, especially when we do lots of insertions and lookups at the front - in that case ArrayList is much slower. Code as usually on github. Till the next time!

Didn't write to much recently, being busy, but I got something for you: Unrolled Linked List in Java.

This is an Wikipedia article; in my implementation, there is no remove and insert function - it would complicate API too much, imo.

It has O(1) performance with: push, add, pop (removes the first) and popLast. Performance of:

- replace (updates element with the given index) and

- get (returns - not remove an element with the given index)

are O(n / [#of internal arrays]) - which is better (with max elements 1000 and n = million would be 500) than pure Linked List and obviously worst than Augumented Array.

There is a bigger memory overhead per node: an array of elements plus some helper fields; for million integers, there would be around 1600 bytes overhead plus whatever comes from arrays management.

Where to use it? Any queues, stacks, et cetera, especially when we do lots of insertions and lookups at the front - in that case ArrayList is much slower. Code as usually on github. Till the next time!

## Wednesday, 21 June 2017

### Java Calculator 2

Following previous post, I've fixed this - now is not nessessery to use fully paranthized expression; the operator precedence is set and can be changed using paranthesis. Instead of binary tree, I parsed expression to postfix - Reverse Polish Notation Rocks :).

Code, of course, on Github. Till the next time!

Code, of course, on Github. Till the next time!

Subscribe to:
Posts (Atom)