# My handwriting

Tidying up a few things at home, I came across all my documents from previous years. I thought it would be nice to document how my handwriting evolved over the year. I have been to school between the ages of 6 and 18 (12 years). We were asked to write script (i.e. cursive, without breaks between letters) in elementary school. In secondary education I recognized that nobody cared for our style of writing, so I switched back to block letters. My writing was much more readable immediately.

In lecture-free times I am taking only small notes on paper, meaning I write ~5% on paper and 95% on my computer. When lectures are going on at university, I guess the ratio is like 50% written (math is much easier to study handwritten) and 50% on my computer (lecture notes).

# An empty clause represents a contradiction

##### The problem

I have just gone through many CNF files and come across the following file:

```p cnf  150  400
-3      -2      -1 0
3       2      -1 0
2       1      -3 0
[...]
150     149      98 0
150    -149     -98 0
149    -150     -98 0
98    -150    -149 0
0
```

available as pret150_25.cnf and originally authored by Daniel Pretolani.

To those unfamiliar with DIMACS CNF files, this file represents the boolean formula defined as

f(x1, x2, …, x150) =
(-x3 ∨ -x2 ∨ -x1) ∧
(x3 ∨ x2 ∨ -x1) ∧
(x2 ∨ x1 ∨ -x3) ∧

(x150 ∨ x149 ∨ x98) ∧
(x150 ∨ -x149 ∨ -x98) ∧
(x149 ∨ -x150 ∨ -x98) ∧
(x98 ∨ -x150 ∨ -x149)

So `0` terminates clauses which are disjunctions (denoted with `∨`) of literals.
However, the trailing 0 triggers the question whether the boolean function actually ends with

∧ (x98 ∨ -x150 ∨ -x149) ∧ ()

or as before:

∧ (x98 ∨ -x150 ∨ -x149)

##### Rationale

If the former is satisfied, the question is raised, what an empty clause means. Considering that

(x98 ∨ -x150 ∨ -x149)
= (x98 ∨ -x150 ∨ -x149 ∨ ⊥)
= (x98 ∨ -x150 ∨ -x149 ∨ ⊥ ∨ ⊥ ∨ ⊥)

where ⊥ denotes boolean value false, this should apparently mean

()
= (⊥)
= (⊥ ∨ ⊥ ∨ ⊥)

This is the rationale why an empty clause should represent the boolean value false (in my humble opinion). Thus rendering the CNF file above with the former notation and specifically the problem unsatisfiable.

# Buchtipp: “Simple Guide to Japan – Customs & Etiquette”

This booklet was published in the third edition in 1997 and authored by Helmut Morsbach. It features 80 pages in total with illustrations and a medium font size. So you should be finished in few hours. I definitely need to compare it with “Darum nerven Japaner” (engl. “Why Japanese Are Annoying”), which I read recently. However, for the latter no English translation is available.

In my humble opinion, “Why Japanese Are Annoying” does a better job at presenting Japanese habits, because it contains humorous remarks to make it more enjoyable. Due to its length (compared to the booklet) it is also more exhaustive and goes to a philosophical point of view, which is entertaining also for a non-European audience. This booklet sticks to a basic comparison of European and Japanese habits. On the other hand it comes straight to the point and introduces more basic Japanese words/phrases compared to the humorous book.

In the end you will read 10 chapters:

1. Introduction by Ronald Dore
2. Foreword
3. In General
4. Wining & Dining
5. The Japanese Home
8. Conversation & Communication
10. Useful Phrases & Vocabulary

The final pages contains a collection of Japanese words used in the booklet, facts about Japan and an index. A nice read for an afternoon. I cannot verify its content, because I have not been to Japan, but one disclaimer remains: In some ways outdated.

# Paper: “Engineering a Sort Function”

“Engineering a Sort Function” by John L. Bentley and M. Douglas McIlroy gives a nice insight how theoretical algorithm design is applied in software engineering. I think I came across the paper, because Go’s sort function implementation is based on the described algorithm.

The paper outlines how the unstable sort algorithm has evolved over several iterations during development. It is based on Quicksort, but uses insertion sort for arrays of size ≤7. The solution to Dijkstra’s Dutch national flag problem gives the partition method for QuickSort. Pivot elements are selected with the median of 3 (array size >40) or median of 9 (array size ≤40). You can also see how cost models are applied such that asymptotic behavior becomes less important compared to the expense of particular operations. I think it is interesting, because cost models are not taught here at University of Technology, Graz, whereas asymptotic behavior is focused. However, this model fails where the comparison function can be arbitrary according to the interface and so the actual expense of comparison cannot be estimated.

In the end, I think it is a nice read for 2 hours assuming you are familiar with basic algorithm design.

“[…] This algorithm is easy to describe, and also easy to get wrong—Knuth tells horror stories about inefficient partitioning algorithms.”

“The key to performance is elegance, not battalions of special cases.”

# Using namespaces with lxml.etree

I need to admit, when I initiated and released ruledxml for the first time, I didn’t care much about namespaces. The usecase was not prevalent in my setting. This changed now.

Time to implement it properly and so I need to look at handling XML namespaces with python’s lxml.etree in more detail. In the following you can see a cheatsheet how you achieve a certain XML namespaced output with `lxml.etree.Element` instances.

The following table always shows a desired result following by the python source code to generate it.

`<a><b/></a>`
```>>> a = lxml.etree.Element('a')
>>> b = lxml.etree.Element('b')
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<a><b/></a>'```
```<a xmlns="http://example.org/">
<b/>
</a>```
```>>> a = lxml.etree.Element('a', nsmap={None: 'http://example.org/'})
>>> b = lxml.etree.Element('b')
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<a xmlns="http://example.org/"><b/></a>'```
```<a xmlns:ex="http://example.org/">
<ex:b/>
</a>```
```>>> a = lxml.etree.Element('a',
...   nsmap={'ex': 'http://example.org/'})
>>> b = e('{http://example.org/}b')
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<a xmlns:ex="http://example.org/"><ex:b/></a>'```
```<ex:a xmlns:ex="http://example.org/">
<ex:b/>
</ex:a>```
```>>> a = lxml.etree.Element('{http://example.org/}a',
...   nsmap={'ex': 'http://example.org/'})
>>> b = e('{http://example.org/}b')
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<ex:a xmlns:ex="http://example.org/"><ex:b/></ex:a>'```
```<ex:a xmlns:ex="http://example.org/" ex:attr="value">
<ex:b/>
</ex:a>```
```>>> a = lxml.etree.Element('{http://example.org/}a',
...   nsmap={'ex': 'http://example.org/'})
>>> a.attrib['{http://example.org/}attr'] = 'value'
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<ex:a xmlns:ex="http://example.org/"
ex:attr="value"><ex:b/></ex:a>'```
```<ex:a xmlns:ex="http://example.org/example"
xmlns:org="http://example.org/organization"
ex:attr="value">
<org:b ex:example="value1" org:example="value2"/>
</ex:a>```
```>>> a = lxml.etree.Element('{http://example.org/example}a',
...   nsmap={'ex': 'http://example.org/example',
...          'org': 'http://example.org/organization'})
>>> a.attrib['{http://example.org/example}attr'] = 'value'
>>> b = lxml.etree.Element('{http://example.org/organization}b')
>>> b.attrib['{http://example.org/example}example'] = 'value1'
>>> b.attrib['{http://example.org/organization}example'] = 'value2'
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<ex:a xmlns:ex="http://example.org/example"
xmlns:org="http://example.org/organization"
ex:attr="value">
<org:b ex:example="value1" org:example="value2"/></ex:a>'```
```<a xmlns:ex="http://example.org/" xml:lang="ja">
<ex:b/>
</a>```
```>>> a = lxml.etree.Element('a',
...   nsmap={'ex': 'http://example.org/'})
>>> a.attrib["{http://www.w3.org/XML/1998/namespace}lang"] = 'ja'
>>> b = lxml.etree.Element('{http://example.org/}b')
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<a xmlns:ex="http://example.org/" xml:lang="ja"><ex:b/></a>'```
```<a xmlns:ex="http://example.org/" xml:lang="ja">
<ex:b xml:lang="en"/>
</a>```
```>>> a = lxml.etree.Element('a',
...   nsmap={'ex': 'http://example.org/'})
>>> a.attrib["{http://www.w3.org/XML/1998/namespace}lang"] = 'ja'
>>> b = lxml.etree.Element('{http://example.org/}b')
>>> b.attrib["{http://www.w3.org/XML/1998/namespace}lang"] = 'en'
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<a xmlns:ex="http://example.org/" xml:lang="ja"><ex:b
xml:lang="en"/></a>'```

# Buchtipp: “Darum nerven Japaner”

Der Autor Christoph Neumann erklärt erst im Nachwort wie er dazu kam dieses Buch zu schreiben. ここがヘンだよ日本人 (laut dem Autor mit “Die spinnen, die Japaner!” frei nach Asterix & Obelix zu übersetzen) ist eine populäre japanische TV-Sendung, in der er auftrat. Dort diskutieren die Anwesenden die Gewohnheiten der Japaner und hinterfragen deren Sinnhaftigkeit. Als Spin-Off dieser Auftritte schrieb er das Buch, welches zu einem der bekanntesten seines Genres wurde.

Als Kenntnisse greift er damit auf seine Erfahrungen als Deutscher mit längerem Auslandsaufenthalt in Japan zurück. Er illustriert japanische Eigenheiten anhand seiner Erfahrungen und schreckt nicht davor zurück sie mit harten Worten in krassen Gegensatz zu europäischen Gewohnheiten zu setzen. Die diskutierten Themen illustrieren sich in den 19 Kapiteln des Buchs:

1. Vorwort: Dürfen Japaner nerven?
2. Regeln: Das Volk will belehrt werden
3. Schuhe: Das elfte Gebot: “Du sollst deine Schuhe ausziehen”
4. Essen: Die mit dem Bauch denken…
7. Mafia: Verbrecher, die keine sind
8. Warnungen: Achten Sie darauf, darauf zu achten!
9. Verhütung: Pille killen und Föten töten
10. Körpersprache: Das Gegenteil von Anmut
11. Yamanote: Mehr als nur eine S-Bahn-Linie
12. Spass: Kein Spass an der Freud
13. Schlafen: Bett? Nein, danke!
14. Diebstahl: Mein Geld, dein Geld – Geld ist für uns alle da
15. Gleichheit: Reich wie Scheich und dennoch gleich?
16. Fremdsprachen: Englisch hassen lernen
17. Urlaub: Die Suche nach dem Vertrauten in der Fremde
18. Müll: Parolen statt Mülleimer
19. Big Brothers: Ist Gott eine japanische Firma?
20. Flirt: Die Sau rauslassen, aber ordentlich

Ein netter gedanklicher 2-Tages Ausflug in den japanischen Alltag!

# Time management, an analysis

This semester I consciously decided to reduce my number of courses I take. As far as academic work is concerned I need to focus on finishing the first and second semester and finish my master thesis. I reduced the amount of work in associations, I do not take some law course (oh, that’s been some while!) and I don’t take any courses of higher semester.

I wanted to discuss the amount of time I want to invest into something. I fixed holes in my schedule and organized remaining time. I have several categories and every category as a minimum amount of time I invest per week. Good opportunity to document that for future reference:

• I consider 16 hours per day productive. So I have 8 hours of sleep per day.
• I invest 42.5 hours per week in attending lectures, tutorials, meetings, visiting the Aikido dojo and quality time.
• 69.5 hours are left. How do I use them?

There are 10 categories:

project:
programs I want to release, watch tutorials/videos, publishing content
university:
old courses I need to finish (exams, submissions)
A2:
course Analysis 2 and everything related
LA2:
course Linear Algebra 2 and everything related
FOM:
course Foundations of Mathematics
master thesis:
releasing subprojects for my master thesis, writing thesis document
JAP:
course Japanese Language and everything related
日本語:
learning Japanese on my own (especially Aikido & math)
日本:
exchange student year organization
GLT16:
upcoming Grazer Linuxtage – graphics work

And how much time do I invest into each category at minimum?
This sums up to 34 hours and I have 69.5 hours available, so this is flexible on purpose.
But it gives a relative measure for future reference:

project 3 hours per week 4 hours per week 5 hours per week 4 hours per week 1 hours per week 8 hours per week 3 hours per week 3 hours per week 2 hours per week 1 hours per week

# Boston Key Party: Graph 3-coloring with SAT solvers

The Boston Key Party was held between 4th and 6th of March 2016. A few colleagues of mine attended this event and asked for help with one particular problem:

Given a graph with 683 vertices and 1253 edges. Assign one of three colors to each vertex. No edge must connect two vertices of the same color.

Graph 3-coloring is a classic example of an NP-complete problem. So a SAT solver might be suitable for it as far as more efficient algorithms are not known.

Let’s solve this problem with an approach similar to an implementation I use in my master thesis: Generate the CNF using python, let a SAT solver do the hard work and parse the solver’s result back to python and print the assignment of colors to vertices.

The boolean logic is really simple: Every vertex gets assigned three boolean variables. We add the following constraints:

• Only one of three variables can be true.
• For every edge `(s, t)` we look up the corresponding colors for `s` and `t`: `r1,g1,b1` and `r2,g2,b2`. We claim not both `r1` and `r2` can be true. Not both `g1` and `g2` can be true. Not both `b1` and `b2` can be true.

In code it looks like this:

```def oneof3(w, a, b, c):

def notboth(w, a, b):

# constraints for colors of one vertex
for v, (red, green, blue) in graph.vertices.items():
oneof3(w, red, green, blue)

# constraint for edges
for (src, dst) in graph.edges:
r1, g1, b1 = graph.vertices[src]
r2, g2, b2 = graph.vertices[dst]
notboth(w, r1, r2)
notboth(w, g1, g2)
notboth(w, b1, b2)```

The final source code looked like this (you need to adjust the path to the SAT solver executable; you should use lingeling):

```#!/usr/bin/env python3

import re
import os
import sys
import logging
import tempfile
import itertools
import subprocess

# the output format is expected to be compatible with lingeling
SATSOLVER_EXECUTABLE = '/opt/lingeling-bal-2293bef-151109/lingeling'
SATSOLVER_TIMEOUT = None  # or specify an integer in seconds
VERTICES = 683

class Graph:
def __init__(self, nb_vertices):
self.edges = set()
self.nb_vertices = nb_vertices
self.vertices = {k: (3 * k + 1, 3 * k + 2, 3 * k + 3)
for k in range(nb_vertices)}

"""Read edges from a file containing '{src} {dest}' lines"""
with open(filepath) as fd:
for line in fd:
if line.startswith('#'):
continue
src, dst = [int(v) for v in line.split()]
assert 0 <= src < self.nb_vertices \
and 0 <= dst < self.nb_vertices, "vertex number invalid"

def get_assignment(self, model: set):
"""Given a set of positive or negative boolean variables,
return a dictionary assigning 1, 2 or 3 to every vertex
"""
ass = {}
for v, (r, g, b) in self.vertices.items():
assert (r in model) ^ (g in model) ^ (b in model)
assert (r not in model) | (g not in model) | (b not in model)
ass[v] = {r in model: 1, g in model: 2, b in model: 3}[True]
return ass

# storage/writer for CNF data

class CnfStorage:
def __init__(self, fd):
self.fd = fd
self.clauses = set()
self.nbvars = 0

self.nbvars = max(self.nbvars, max([abs(v) for v in ints]))

def finish(self):
self.fd.write('p cnf {} {}\n'.format(self.nbvars, len(self.clauses)))
for clause in self.clauses:
self.fd.write(' '.join([str(i) for i in clause]) + ' 0\n')
self.fd.flush()

# CNF primitives
#   Related: http://lukas-prokop.at/tools/truthtable/

def oneof3(w, a, b, c):

def notboth(w, a, b):

# constraints for colors of one vertex
for v, (red, green, blue) in graph.vertices.items():
oneof3(w, red, green, blue)

# constraint for edges
for (src, dst) in graph.edges:
r1, g1, b1 = graph.vertices[src]
r2, g2, b2 = graph.vertices[dst]
notboth(w, r1, r2)
notboth(w, g1, g2)
notboth(w, b1, b2)

# run the SAT solver

def run_solver(filepath):
"""Run SAT solver as subprocess. Return stdout"""
proc = subprocess.Popen(
[SATSOLVER_EXECUTABLE, filepath],
stdout=subprocess.PIPE, stderr=subprocess.PIPE)

try:
outs, errs = proc.communicate(timeout=SATSOLVER_TIMEOUT)
out = outs.decode('ascii')
except subprocess.TimeoutExpired:
proc.kill()
outs, errs = proc.communicate()
out = errs.decode('ascii')

if proc.returncode == 20:
raise RuntimeError('SAT solver returned UNSATisfiability')
if proc.returncode != 10:
errmsg = 'SAT solver returned error code {}: {}'
raise RuntimeError(errmsg.format(proc.returncode, errs))
return out

def interpret_output(out):
"""Read a model (set of positive/negative integers) from stdout"""
model = []
logging.debug(out)

something = False
for line in out.splitlines():
if line.startswith("v "):
matches = map(int, re.findall(" (-?\d+)", line))
something = True
for match in matches:
if match == 0:
# trailing zero
continue
assert -match not in model
model.append(match)

if not something:
raise RuntimeError("Model empty - most likely the SAT solver " +
"output is incompatible with lingeling")

return tuple(model)

if __name__ == '__main__':
if len(sys.argv) != 2:
print('usage: ./graph-3-coloring.py <edges.txt>')
sys.exit(1)

fd, filepath = tempfile.mkstemp(prefix='graph-3-coloring')

try:
# generate graph
graph = Graph(VERTICES)

# store CNF
w = CnfStorage(os.fdopen(fd, mode='w', encoding='ascii'))
w.finish()
logging.info("Finished generating CNF file")

# run SAT solver
out = run_solver(filepath)
model = interpret_output(out)
assignment = graph.get_assignment(model)

# print result
for vertex, color in assignment.items():
print('{}: {}'.format(vertex, color))
finally:
```

And how long did it take to run it? 0.9 seconds 😎
Thank you lingeling!

# Project nihon ni ryuugakusei (日本に留学生)

Starting with October 2016 I am going to Japan for 1 year with my girlfriend. Both of us got granted a student’s exchange year at the same place.

##### Setting
• I will attend classes as a math undergraduate.
• She attends classes as a math graduate student.
• I just took my first Japanese classes this February.
• She has more experience with the Japanese language (5 courses).
• Our studies will be financed by the University of Graz and University of Kōbe. The funds cover the difference in living costs between Austria and Japan (housing will be more expensive in Japan). Thanks to all those institutions!
##### Schedule until then
• Find appropriate classes I can attend at Kōbe University and ask for future recognition
• I will try to finish my first and (coming) second semester in Mathematics. And finish my computer science master’s degree at TU Graz.
• I will try to get my second course in Japanese during the summer term.
• I will apply for a summer job for 2 months (July & August).
• With September things get real. I will no longer live in my flat in Graz.
• On 3rd of October we will have our first regular day at Kōbe University [math department].
• I will return to Austria in August 2017 at the earliest (exams take place in July and August in Japan). It seems financially dull [to me] to come back to Austria at any point in time during this year.
##### Related work until then
• Suspend participation in local associations (GLT, Aikikai Graz, not sure about LaTeX@Graz)
• Reduce the amount of physical stuff I have here in Graz, store it somewhere and move out of the flat
• Lots of planning with her – thanks sweety!
##### Being in Japan
• My main focus one year abroad will be on Japanese writing, Japanese language, math and typesetting.
• Japanese classes will be very appropriate as they are designed for exchange students with various Japanese skills. But math classes will give me a hard time. All appropriate classes for me are in Japanese.
• I need to do at least 30 ECTS. The usual amount of ECTS per year at universities is 60 ECTS.
• I will try to attend Aikidō classes there. Getting into a real Dōjō is supposedly difficult. But it should be easy to get into the Kōbe university Aikido club.
• We will use the awesome train network in Japan to get around.
• We will keep you informed about information channels, so you can reach us. But we need to organize that in the coming months.

So again: Where is Kōbe? We are close to Ōsaka, to the west (a bit to the south) of Tokyō. It takes us 3 hours with Shinkansen to get to Tokyō. And for those of you who actually cared to read that much, I have that one for you:

This is truly a great opportunity for us!
Thanks for the support we received 🙂

# Paper: “Mastering the game of Go with deep neural networks and tree search”

Most recently, a paper “Mastering the game of Go with deep neural networks and tree search” was published in Nature. It describes a neural network architecture which for the first time won against a 2-dan professional Go player (Fan Hui) without handicaps achieving the title of the strongest Go engine existing. Between 5th and 15th of March 2016 a match between the engine – namely AlphaGo – and Lee Se-dol is scheduled. AlphaGo is pushed by Google.

It was difficult to me to follow the formal details lacking experience in machine learning. Here I would just like to cite the most interesting quotes:

[…] These games may be solved by recursively computing the optimal value function in a search tree containing approximately bd possible sequences of moves, where b is the game’s breadth (number of legal moves per position) and d is its depth (game length). In large games, such as chess (b ≈ 35, d ≈ 80) and especially Go (b ≈ 250, d ≈ 150), exhaustive search is infeasible, but the effective search space can be reduced by two general principles. First, […] position evaluation […] Second […] sampling actions from a policy p(a|s) that is a probability distribution over possible moves a in position s.

[…] evaluating positions using a value network, and sampling actions using a policy network.

We trained a 13-layer policy network […] from 30 million positions from the KGS Go Server.

We also tested against the strongest open-source Go program, Pachi.

The final version of AlphaGo used 40 search threads, 48 CPUs, and 8 GPUs. We also implemented a distributed version of AlphaGo that exploited multiple machines, 40 search threads, 1202 CPUs and 176 GPUs. […] The distributed version of AlphaGo was significantly stronger, winning 75% of games against single-machine AlphaGo and 100% of its games against other programs.

A policy p(a|s) is a probability distribution over legal actions a ∈ (s). A value function is the expected outcome if all actions for both players are selected according to policy p, that is, vP(s) = [zt|st = s, at…T ~ p].

Our rollout policy pΠ(a|s) contains less handcrafted knowledge than state-of-the-art Go programs.

Time controls for formal games were 1h main time plus three periods of 30s byoyomi.

The neural network architecture itself is described in the Methods Appendix. The (formal and informal) game results are provided as Data sheet. And in Methods/Evaluation a closing parenthesis is missing in the denominator of the logistic function 😉