text:
(This blog post is an extended treatment of a talk I recently gave. To see the slides for the talk, click here.)

## Intro

We're going to explore the difference between what I term "traditional" neural network (NN)-based classification and so-called "zero-shot" (or "few shot") classifiers that rely on embedding semantically meaningful features as clusters in space by means of contrastive losses. These "zero-shot" (or "few shot") or "contrastive loss" methods are increasingly prevalent in the literature, and have the nice property that, unlike traditional ML classifiers, they don't need to be re-trained whenever new classes are introduced. If we want to understand these embedding-based / zero-shot / contrastive loss methods, it will be helpful to first consider traditional classification as an embedding method of it own.

There is also a strong pedagogical point that I wish to make in this post. Often in teaching ML, many authors will spend some time on binary classification via logistic regression (see my post "Naughty by Numbers: Classifications at Christmas") and then jump immediately into multi-class classification where the number of classes is 10, or 1000, or 1000 and up. There is an opportunity that is being passed over. The opportunity is visualization, and what is being passed over is the special case of three classes. (Or, as we'll see, we can squeeze an extra 4th class.)

## Viz Matters

Visualization is an important part of the teaching process as well as for researchers wanting to understand their data. Much of my own teaching work has involved building data visualization apps for students to use in learning acoustics, and seeing Yang Hann Kim's speech when he received on Rossing Prize in Acoustics Education for his visualization efforts only further inspired me to continue developing such tools for students and instructors. (cf. The Physics Teacher featured my "Polar Pattern Plotter" app on the cover of its February 2018 issue.)

Humans cannot visualize beyond 3 dimensions, so problems involving more than 3 semantic features invariably rely on projection methods such a Principal Component Analysis (see my blog post, "PCA from Scratch") or nonlinear embedding methods like t-SNE or UMAP. The problem with PCA is that projected data points tend to overlap, and with the latter methods twist and distort the space so much that the global structure is completely obfuscated. But in 3D the representations are exact!

Math point, for those who are interested:When we move from two classes to more than two, we typically switch from the logistic sigmoid activation and Binary Cross Entropy loss to softmax activation and Cross Entropy (~ K-L divergence) loss. Softmax contains more complexity than sigmoid (even if the latter is just two-class softmax with a coordinate transformation, and along each axis softmax acts like a sigmoid), yet for the case of 3 classes softmax contains all the complexity of higher numbers of classes, while still being visualizable.

We're going to make use of a little code library I'm in the process of putting together called mrspuff! It's geared toward teaching via visualization and running on Google Colab, and (increasingly, as I learn) built to work on & with fast.ai.

## Dimensions and Embeddings

People who are not mathematicians, physicists, data scientists, etc. may be unaccustomed to this talk of "dimensions" when dealing with data. Let's dive in to the specific case of three-class classification. Say we're developing a computer program to guess ("predict") whether a given image contains a cat, a dog, or a horse. Traditionally the "ground truth" or "target" values are expressed as "one hot encoded" vectors, such as...

   cat: (1,0,0)           dog: (0,1,0)         horse: (0,0,1)

Then given an image of an animal, our neural network model will produce a set of 3 probabilities for each class, say...

import numpy as np
from mrspuff.viz import *
from mrspuff.utils import *
from mrspuff.scrape import *

labels = ['cat','dog','horse']
data = np.array([[0.7,0.2,0.1],[0.15,0.6,0.25],[0.05,0.15,0.8]])
for i in range(3):
image_and_bars(data[i], labels, CDH_SAMPLE_URLS[i]).show(config = {'displayModeBar': False})
print("")

...the goal (of training the neural network model) is to get the predicted values to match up with the target values.

Note: we’ll be using image-based examples, but for everything you’ll see in these posts, similar methods have been applied to audio, text, and tabular data.

These numbers can be viewed as the strength of an attribute in an image, e.g. measures of cat-ness, dog-ness, and horse-ness (or measure of the likelihood of being a cat, dog, or horse, respectively), where a value of 1 means 100% of that property. Notice in each case, the three "class" probabilities add up to 1. This is always the case: probabilities always have to sum up to 1, i.e. 1 is "100% certainty" that gets split among the 3 classes. (This summing to 1 is an important property that we'll come back to in a bit.)

One thing that scientists like to do is take different variables and view them as coordinates of a single point in a multi-dimensional space. So for 3 classes we have 3 coordinates for 3 dimensions. We could make the "cat-ness" prediction probability be the "x" coordinate, and "dog-ness" be the "y" values, and "horse-ness" could be along the "z" axis. Then instead of drawing bar graphs, we could plot points in 3D space, where the coordinates of each point tell us the predictions:

All the 3D plots in this post can be rotated & zoomed with the mouse or your finger. Try it!

(Here we also used the 3 class probabilities to set the R,G,B color values of the points. There's no new information contained in this; it just looks cool.)

What scientists tend to do is, even in cases where there are more then 3 variables (say, 10), we regard these as dimensions in some fancy abstract mathematical space where the laws may or may not conform to those of our universe -- for example, the idea of "distance" may be totally up for grabs. In cases where the number of values is infinite (say, as coefficients in a infinite series, or as a function of a continuous variable) we might even work in infinite dimensions! Often when we talk like this, it doesn't mean that we're actually picturing geometrical spaces in our heads -- we can't, for anything beyond 3 dimensions -- but it's a handy way of encapsulating a particular way of viewing the data or functions involved. And sometimes we do try to see what kinds of geometrical insights we can glean -- which is what we're going to do here!

Remember when we said that the individual class probabilities have to add up to 1? Look what happens when we plot a lot of such points...

prob, targ = calc_prob(n=400)
TrianglePlot3D_Plotly(prob, targ=None, labels=labels, show_bounds=False).do_plot()

Note: Even though these are points in 3D space, they make up a triangle which lies along a plane -- a 2D :subspace" of 3D. This is a consequence of having the "constraint" that all class probabilities add up to 1.
We can color the points by their expected class values by choosing the triangle point (or "pole") that they're nearest to -- i.e. by which "bar" is largest among the class probabilities. And we can include the boundaries between classes:

TrianglePlot3D_Plotly(prob, targ=targ, labels=labels, show_bounds=True).do_plot()

## Showing (3D) 3-Class Classification in 2D

Since these points lie along a plane, we can change coordinates and just use a 2D plot instead of a 3D plot.

(Optional) Math Trivia: Typically this would involve calculating a coordinate transformation either by hand or using something like PCA to do it for us, but in this case there's a simple "hack" transformation that will get us from $x$, $y$, and $z$ in 3D to our 2D coordinates $x'$ and $y'$:> $$x' = y - x,\ \ \ \ \ \ \ y' = z$$

In a 2D version of our triangle plot, we can even enable "image tooltips" so that when the mouse hovers over a datapoint, you can see the image it represents:

urls = exhibit_urls(targ, labels)
TrianglePlot2D_Bokeh(prob, targ=targ, labels=labels, show_bounds=True, urls=urls).do_plot()

## How Traditional NN Classification Training Proceeds

When we start training our classifier, the data (points) get mapped all over the place; it's a big jumble. The classifier will ultimately be scored by how many points lie on the "correct side of the line" for the class boundaries, but that's a discontinuous (either-or) criterion that's no good for training neural networks. So instead we use a loss function and a gradient descent on this loss function to try to minimize the distance from the mapped point to the "pole" of the target class point. In other words, training proceeds by trying to collapse all the data points onto the 3 (or 4) points corresponding to 100% certainty about each class prediction: The following a cartoon example time-lapse of ten training steps (we'll show real NN training in Part 2 of this blog series):

from ipywidgets import interact, interactive, fixed, interact_manual
import ipywidgets as widgets

probs, tmp = calc_prob(n=400, s=2.2)
targs = np.random.randint(3,size=probs.shape[0])
targs_3 = one_hot(targs)   # not used for plotting but for compiting gradients
maxsteps = 10

def sequence(step):
lr, grad = 1/maxsteps, targs_3-probs
TrianglePlot2D_MPL(probs+step*lr*grad, targ=targs, labels=labels, show_bounds=True, comment=f'Step {step+1}:').do_plot()

# Could be interactive fun in Jupyter/Colab, but not easy to do in the blog:
do_interact = False
if do_interact:
print("Move the slider below to advance the training step.")
print("(Note, this is just a 'cartoon' for now; to see actual NN training steps, wait until post Part 2.")
interact(sequence, step=widgets.IntSlider(min=0,max=19,step=1,value=0));
else:
for step in range(maxsteps):
sequence(step)

As the training proceeds, it tries to get the groups of data points to collapse to single locations at each target "pole".

## Loss vs. Accuracy

This method of visualization also allows us to visually "see" the concepts of loss and accuracy. For 3-classes with a softmax activation and categorical cross-entropy, the loss is nearly linear in the difference between the prediction and the target, i.e.:

Loss:~distance from target This is a continuous variable, which makes it suitable for training models via gradient descent.

In contrast to loss, accuracy is how many classifications the model gets correct, expressed as a percentage of the total number of data points. This is determined by what side of the decision boundary each prediction is on.

Accuracy:% of points on the correct side of decision boundary (discontinuous)
It is instructive to view two configurations of data points with nearly identical loss values but wildly different accuracies:

Nearly identical losses:

# generate and save images that we'll load in the next cell
!mkdir images
import numpy as np
import matplotlib.pyplot as plt

# generate data along boundaries
def gen_bound(x, y, z, n=20, ind0=1): # ind0=1 skips the "first point"
return np.linspace(np.array([x[0],y[0],z[0]]), np.array([x[1],y[1],z[1]]), num=n+ind0)[ind0:]

def gen_bound_data(n_per=20, ind0=0):
bdata = np.zeros((n_per*3,3))
bdata[:n_per] = gen_bound(x=[0.333,0.5], y=[0.333,0.5], z=[0.333,0], n=n_per, ind0=ind0)
bdata[n_per:2*n_per] = gen_bound(x=[0.333,0], y=[0.333,0.5], z=[0.333,0.5], n=n_per, ind0=ind0)
bdata[-n_per:] = gen_bound(x=[0.333,0.5], y=[0.333,0], z=[0.333,0.5], n=n_per, ind0=ind0)
return bdata

def gen_near_bound_data(n_per=50, scale=7, eps=0.01):
bdata = gen_bound_data(n_per=n_per)
lower, right, left = bdata[0:n_per,:], bdata[n_per:2*n_per,:], bdata[-n_per:,:]

# shift data a bit
lower_catty = softmax( scale*(lower+np.array([eps,0,0])) )
lower_doggy = softmax( scale*(lower+np.array([0.0,eps,0])) )

left_catty = softmax( scale*(left+np.array([eps,0,0])) )
left_horsey = softmax( scale*(left+np.array([0,0,eps])) )

right_horsey = softmax( scale*(right+np.array([0,0,eps])) )
right_doggy = softmax( scale*(right+np.array([0,eps,0])) )

return np.vstack((lower_catty, lower_doggy, left_catty, left_horsey, right_horsey, right_doggy))

# move boundary a bit toward the "correct" side
eps = 0.007
acc_data = gen_near_bound_data(eps=eps)
btarg = np.argmax(acc_data, axis=-1)
TrianglePlot2D_MPL(acc_data, targ=btarg, show_bounds=True, labels=labels, comment='100% Accuracy:').do_plot()
plt.savefig("images/acc_100.png")

# move boundary a bit toward the "wrong" side (keeping labels the same as before)
inacc_data = gen_near_bound_data(eps=-eps)
ibtarg = btarg.copy()
TrianglePlot2D_MPL(inacc_data, targ=ibtarg, show_bounds=True, labels=labels, comment='0% Accuracy:').do_plot()
plt.savefig("images/acc_0.png")

Thus visualization can serve as a valuable teaching tool.

Furthermore, by letting us track which points are "not where they should be" on a plot, we can "see" the "confusion matrix" typically provided as a classification metric. More on that in Part 2.

### Aside: Even 4 Classes?

Just as 3 class probabilities form a triangular 2D subspace (in 3D) that we can then plot in 2D, so too 4 classes form a tetrahedron (a pyramid made up of triangles), which is a 3D shape embedded in 4D space! So if we restrict our attention to this 3D subspace and use a 3D plotting program then we can actually represent 4 classes. Say we add another animal class, say "bird" symbolized by dark-colored points. Then our diagram could look like this:

prob4, targ4 = calc_prob(n=500, s=2.7, dim=4)       # 4d probabilities
TrianglePlot3D_Plotly(prob4, targ=targ4, labels=labels+['bird'], show_labels=True, show_axes=False, add_poles=True).do_plot()

## Metric-Based Embedding Methods

In contrast to all this, metric-based embedding methods don't try to collapse all the data to a predefined set of 3 (or 4, or more) "poles." Rather, they try to get similar data to end up as points that are near each other, and dissimilar data points far away from each other. This tends to produce "clusters" but they are not (typically) along the "axes" of the space, they're just "somewhere out there."

Deep Learning experts Raia Hadsell, Sumit Chopra, and Yann LeCun described it this way (I'm paraphrasing): Imagine all the data points are connected to each other via special kinds of springs. Similar kinds of points are connected by attractive springs that pull them together. Dissimilar kinds of points are connected by repulsive springs that push them further away from each other --- except these repulsive springs are special in that they only apply a force when they're close together; beyond a certain distance (called the "margin"), no repulsion occurs. (Why this special property is stipulated is a fine point we can get to later).

This picture of springs is the essence of a "contrastive loss" function. Unlike traditional NN classification where the loss is based on the "distance" to a "target" (or "ground truth") value, with these metric-based methods we send in two (or even 3) data points together, and then either let them attract or repel each other, and we do this over and over and over until we reach some stopping criterion. Eventually, what we'll have is a space that contains clusters of similar points, separated by a "margin" distance that we specify.

### Contrastive Loss Cartoon Demo

Below is a JavaScript animation of the "springs" cartoon above:

Tip: You can think of the margin as the amount of "push."
Note: (A computational aside) In this scenario, we don’t try to connect every point to every other point at the same time, as in some kind of N-body simulation. That could be computationally expensive and require something like a Barnes-Hut/octtree algorithm to make it efficient. Rather, we’re just randomly pairing two points at a time. Also, other metric learning schemes using "triplet loss" will group three points, setting one to be the "anchor" and then grabbing a positive and a negative example. For more on that, see a recent paper or some code from a couple years ago. Update: You’ll see that I just added a "Triplets" checkbox above! Note that it will internally drop the number of steps by a factor of 2 for "honest" comparison with the non-triplet case.

The cool thing about these methods is that the embedding that gets learned tends to work for classes the method has never seen before. So, for example, the embedding learned for grouping images of cats, dogs, and horses together would map images of birds to nearby points in the space. Then "all we have to do" if we want to predict a class is see whether a new instance is "nearby" (according to some distance measure we decide) to other similar points. We could even look at the "center points" of various clusters and regard these as the "class prototype" and use that in the future.

This fits (somewhat) with the notions of "prototypes" in human classification advanced by Eleanor Rosch in her revolutionary psychology work in the early 1970s. We can say more about this later. ;-)

This same method of contrastive losses and metrics is used not for classification per se but for things like photographic identity verification (an example that is given in Andrew Ng's Machine Learning course on Coursera): Say you want to have a facial recognition system (highly problematic for ethical reasons but it's a good example of the method so bear with me) for a company where there can be turnover in employees: You probably don't want to train a traditional classifier with separate a class for each employee because then you'd have to re-train it every time someone joins or leaves the company. Instead, you can store an image of each employee, and then when they appear in front of a camera for identity verification, you could compare the "distance" between the embedded data point for the new photo from the data point for the stored photo(s). If the distance is small enough, then you can have confidence it's the same person.

This is the idea behind a "Siamese Network", so called because like Siamese twins, it uses two identical branches consisting of the same network (or just the same network run twice):

Example of a Siamese Network (source: Sundin et al)

So in using metric-based learning for classification, we're essentially adopting this identity-verification app and applying it to entire classes instead of individuals.

What's nice about this is that, after you've trained your embedding system, it can typically still be used to measure similarity between pairs of things it's never seen before, because in the process of training it was forced to learn "semantically meaningful" ways of grouping points together. This use of the linguistic work "semantic" is not accidental: the language model systems that rely on "word embeddings" can learn to group similar words together, and even have mathematical-like relationships in analogies (e.g., gender: "king - man + woman = queen", or countries-and-capitals: "Russia - Moscow + France = Paris") by treating the embedded data points as vectors that point from the origin of the coordinate system to the data point. We can say more about this and the distance metric they use ("cosine similarity") another time.

## How well do they work?

So, how do traditional ML classification and metric-based zero-shot methods stack up? Which one is more accurate?

Well, depends on what you want it for, but for example in 2016, a group of researchers scored pretty high on a Kaggle competition for classification using "entity embeddings." They said:

"Entity embedding not only reduces memory usage and speeds up neural networks compared with one-hot encoding, but more importantly by mapping similar values close to each other in the embedding space it reveals the intrinsic properties of the categorical variables. We applied it successfully in a recent Kaggle competition and were able to reach the third position with relative simple features."

As far as our own demonstrations, we'll explore that in Part 2. As a teaser, here's an image from my own Contrastive Loss Modification of the FastAI tutorial on Siamese Networks:

...the model achieved an accuracy of 88 to 90% in identifying pet breeds -- here's the kicker -- that it had never seen before. The model was trained on a completely different set of breeds, which would have stumped a traditional NN classifier, but the similarity-based embedding method was able to apply the "semantically meaningful" representations learned during training to group new pet breeds by similarity!

There's an important point / "confession" that needs to be made here: These "pet breeds" results were obtained using way more than 3 dimensions -- 128 dimensions to be exact. In the real world, such high dimensions are typically necessary. In Part 2, we'll explore more carefully how the dimensionality of the embedding can affect our accuracy.

## Summary

The "Joy of 3D" referred to in this blog post is about 3D as a teaching tool to motivate our understanding of both traditional NN classification and contrastive-loss based metric learning as both being types of embeddings.

The types of "triangle plots" introduced here give students a visual interpretation of "where the data points are" in terms of...

1. prediction/probability values (via locations of dots)
2. losses (~ distance from target)
3. accuracies (which side of "the line" they're on).
• Thus it also gives you a visual representation of the "confusion matrix".
4. You can inspect the data points by mousing over the dots to see the images.
• Thus it allows you to track "top losses" visually, i.e. points that are "not where they're supposed to be".

Next time, in Part 2, I'll walk you through the specifics and show you some real training examples (that you can run on your own) with these sorts of "triangle plots", via my new FastAI callback VizPreds (that I learned how to write)!

## Acknowledgements:

Special thanks to Zach Mueller, Tanishq Abraham and Isaac Flath for assistance in interfacing with fastai!

## References:

(c) 2020 Scott H. Hawley


text:
# Is the function $e^{x^2/2} \Phi(x)$ monotone increasing?

Hello,

Here is an interesting problem. It looks elementary, but it has taken me some efforts without solving it. Let

$$h(x) = e^{x^2/2} \Phi(x),\qquad \text{with}\quad \Phi(x):=\int_{-\infty}^x \frac{e^{-y^2/2}}{\sqrt{2\pi}} dy.$$

The question is whether the function $h(x)$ is monotone increasing over $R$? Are there some work dealing with such function?

It seems a quite easy problem. By taking the first derivative, we need to prove that

$$h(x)' = h(x) x + \frac{1}{\sqrt{2\pi}} \ge 0.$$ which again, not obvious (for $x<0$). Some facts, that might be useful, are:

$$\lim_{x\rightarrow -\infty} h(x) =0, \quad \lim_{x\rightarrow -\infty} h(x)' =0.$$

Thank you very much for any hints!

Anand

We can write $h(x)=\frac 1{\sqrt{2\pi}}\int_{-\infty}^x \exp\left(\frac{x^2-y^2}2\right)dy$. Now put $t=x-y$. We get \begin{align} h(x)&=\frac 1{\sqrt{2\pi}}\int_0^{+\infty}\exp\left(\frac{x^2-(x-t)^2}2\right)dt\\\ &=\frac 1{\sqrt{2\pi}}\int_0^{+\infty}\exp\left(xt-\frac{t^2}2\right)dt. \end{align} We can differentiate under the integral thanks to the dominated convergence theorem. We get $$h'(x)=\frac 1{\sqrt{2\pi}}\int_0^{+\infty}t\exp\left(xt-\frac{t^2}2\right)dt\geq 0.$$ Added later: we don't need to diffentiate. If $x_1\leq x_2$ then for $t\geq 0$ we have $e^{tx_1}\leq e^{tx_2}$ therefore $h(x_1)\leq h(x_2)$.

• Nice argument... – Igor Rivin Oct 3 '11 at 10:09

This is just an alternative argument to Davide's nice one.

First, note that $h' = e^{x^2/2}(x \Phi + \Phi')$.

Since $\Phi'' = -x \Phi'$, monotonicity of the integral yields $$x \Phi(x) \geq \int_{-\infty}^x u \Phi'(u) \mathrm{d}u = -\Phi'(x).$$ So, $h' \geq 0$, and we are done.

I haven't actually done the computation, but it seems to me that integrating the $\Phi(x)$ term by parts ad nauseam, you get a nice power series for $h(x).$

EDIT @Davide's argument is obviously the complete answer to the question as asked, but just as a coda, the series for $h(x)$ is quite cute:

In the odd part, the coefficients of $x^{2k+1}$ is $1/p(k)$ where $p(k)$ is the product of the first $k$ odd integers, while in the even part, the coefficient of $x^{2k}$ is $\sqrt{\pi/2}/q(k),$ where $q(k)$ is the product of the first $k$ even integers.

• Thanks Igor Rivin, I am afraid of series, especially if you multiply two series, one is of $e^{-x^2}$ and the other is of $\Phi(x)$. Since Davide has given a nice solution, I am very content now. Thanks again.:-) – Anand Oct 3 '11 at 10:18
• I am glad you are content, but you might want to get over that series phobia (although the series is not useful for answering your question, it seems...) – Igor Rivin Oct 3 '11 at 10:22

A useful inequality is $$$$\tag{1} \frac{1}{\sqrt{2 \pi}} \frac{x}{x^2+1} \mathrm{e}^{-x^2/2} \le \frac{1}{\sqrt{2\pi}} \int_x^\infty \mathrm{e}^{-y^2/2} \, \mathrm{d} y \le \frac{1}{\sqrt{2 \pi}} \frac{1}{x} \mathrm{e}^{-x^2/2}$$$$ for $$x >0$$, which can be shown by elementary arguments (see below). For example, one can prove the law of the iterated logarithm (for the Browian motion) by means of this inequality. By symmetry, we have for $$x <0$$ that $$|x \mathrm{e}^{x^2/2} \Phi(x)| = \frac{|x|\mathrm{e}^{x^2/2} }{\sqrt{2\pi}} \int_{|x|}^\infty \mathrm{e}^{-y^2/2} \, \mathrm{d} y \le \frac{1}{\sqrt{2\pi}}$$ and this proves $$h'(x) \ge 0$$.

The second inequality in $$(1)$$ can be proven by using $$\exp(-y^2) \le y/x \exp(-y^2)$$ for $$y \ge x$$ and the first one in $$(1)$$ follows by applying partial integration in the form $$\begin{equation*} \frac{1}{x^2} \int_x^\infty \mathrm{e}^{-y^2/2} \, \mathrm{d} y \ge \int_x^\infty \frac{1}{y^2} e^{-y^2/2} = \frac{1}{x} \mathrm{e}^{-x^2/2} - \int_x^\infty \mathrm{e}^{-y^2/2} \end{equation*}$$ and properly rearranging.

format: plain


text:
[texhax] How I do This ? ["autocorrect"]

Uwe Lueck uwe.lueck at web.de
Wed Nov 15 14:29:22 CET 2006

At 00:12 14.11.06, wa2n wrote:
> When I type for example. "TypeSomethingHere" can I have the result is
> "Type Something Here"
>
> The point here is can I use Latex to autocorrect ?
> Adding space after have character following with Caps ?
> or doing something that similiar with that ?

Nice question.

I doubt that this can be done with LaTeX only.
I know a way doing it with TeX -- see below --
and some other people reading this mailing list
will know well how to do this.
One running gag is "making ... characters active"!.

what kind of problem you are concerned with.
Please tell something more than that you need help.

Best,

Uwe.

\documentclass[12pt]{article}

\begin{document}

\newcommand{\ensureinterwordspace}{%
\ifhmode \ifdim\lastskip>0pt \else \space \fi \fi}
%% <- Sometimes this must be overridden.
%%    Use the following command for this.
%%    Place it so that it is executed immediately
%%    before \ensureinterwordspace is expanded.
\ifhmode \nobreak\hskip1sp \fi}
\let\thecapitala=A \catcode\A=\active
\defA{\ensureinterwordspace\thecapitala}
\let\thecapitalb=B \catcode\B=\active
\defB{\ensureinterwordspace\thecapitalb}
%% <- So please note: there are two lowercase occurrences
%%    and three uppercase occurences that must be changed
%%    for each letter. One might render this more comfortable
%%    by some \RefineCharacter macros, yet this is so difficult
%%    that you wouldn't understand it (without TeXpertise).
%%    Some silent readers of the list probably can do this
%%    more elegantly.
%%    And note: after doing this, you can't define macros
%%    whose names contain uppercase characters. Indeed this
%%    fact makes the procedure so difficult (using lowercase
%%    letters for storing uppercase letters).

X\par AB

\end{document}


text:
# [Bro-Dev] Empty log fields

Matthias Vallentin vallentin at icir.org
Tue Nov 29 17:54:21 PST 2011

On Tue, Nov 29, 2011 at 5:11 PM, Slagell, Adam J <slagell at illinois.edu> wrote:
> $\{\phi\}$ for the empty set

The correct LaTeX symbol for the empty set is actually $\emptyset$. Let's have
UTF-8 logs so that we can use "∅" (U+2205) for the empty set ;-).

SCNR,

Matthias


text:
Kattis

# Pet

In the popular show “Dinner for Five”, five contestants compete in preparing culinary delights. Every evening one of them makes dinner and each of other four then grades it on a scale from 1 to 5. The number of points a contestant gets is equal to the sum of grades they got. The winner of the show is of course the contestant that gets the most points.

Write a program that determines the winner and how many points they got.

## Input

Five lines, each containing 4 integers, the grades a contestant got. The contestants are numbered 1 to 5 in the order in which their grades were given.

## Output

Output on a single line the winner’s number and their points, separated by a space. The input data will guarantee that the solution is unique.

Sample Input 1 Sample Output 1
5 4 4 5
5 4 4 4
5 5 4 4
5 5 5 4
4 4 4 5

4 19

Sample Input 2 Sample Output 2
4 4 3 3
5 4 3 5
5 5 2 4
5 5 5 1
4 4 4 4

2 17


text:
## Saturday, July 27, 2013 ... /////

### John Dalton: an anniversary

...and also Baron Loránd Eötvös...

This CV looks ordinary but it is an experiment. ;-)

John Dalton was born to a family of a weaver (and Quakers, independent Christians dissatisfied with the existing denominations) in Northwest England on September 6th, 1766.

He died on July 27th, 1844 i.e. 169 years ago.

He is known for insights on color blindness (Daltonism), atomic theory (that we will discuss in detail), chemistry, and meteorology (the Dalton minimum of solar activity is named after him, too). He also wrote a book on English grammar in 1801. ;-)

He died in 1844 after his third stroke.

As a kid, he was already helping his brother to run a Quaker school. Elihu Robinson, a competent Quaker experimental weather scientist, inspired John to study the weather. Dalton did quite a lot of original work in meteorology that was mostly ignored. Later, John Gough, a blind philosopher and polymath, also taught John Dalton a lot of other science and helped him to become a teacher of maths and natural sciences in Manchester.

Color blindness

He was actually the first man who scientifically talked about color blindness in 1794, in his paper for the Manchester "Lit & Phil" (not to be confused with Lit Crit!) society. It was a pioneering contribution but his theory was wrong, as he learned in his lifetime. He thought that the eyeball liquid was discolored in color-blind people.

His own eyeball was preserved and it turned out that he had a rare type of color blindness in which the "green" (medium wavelength) cones are completely missing. Imagine that you see #RR00BB instead of #RRGGBB in the red-green-blue notation. This disorder is called deuteroanopia: see his "rainbow". In most cases of color blindness, these "green" cones are not quite missing but they have a mutated pigment.

I won't talk about the Dalton minimum and sunspots here because the climate is not supposed to be the main focus of this text. Instead, let us look at:

Atomic theory

First, in 1800 when he became a secretary of the "Lit & Phil" society, he began to study pressure of liquids and gases. A few years before the official discoveries, he verbally (and vaguely) formulated Gay-Lussac's and/or Charles's law about the expansion of liquids.

In 1801, he stated his Dalton's law: partial pressures of individual gases should be added to get the total result. Note that this law, one that can be given experimental evidence, strongly suggests that the different gases may "overlap" i.e. they should occupy different parts of the volume. That is already a strong hint of the atomic theory.

More importantly, he formulated the law of multiple proportions: when chemical elements combine, the ratios of their "amounts" are given by rational numbers with small numerators and denominators. We have CO and CO2 but not CO1.8. The "amounts" must be measured in moles: however, the actual term "mole" was only introduced in 1893, almost a century later.

For each compound, one mole corresponds to a different mass so we must choose different units in which the "amounts" are integer-valued. (But if you evaporate them, one "mole" always corresponds to the same volume under the same pressure and temperature. I don't quite understand whether Dalton was aware of this correct normalization: probably not.)

At any rate, in some proper units, the mixing ratios are rational. This strongly suggests a discrete underlying structure: atoms. He was not the first one to talk about this concept: Democritus and Lucretius did it millenia ago. But Dalton's picture was somewhat more modern. He also introduced a terminology for molecules that wasn't quite modern: the compounds with 2,3,4 atoms were called binary, ternary, quaternary compounds: see his picture of a new system of chemical philosophy.

He understood the following points properly:

1. Elements are made out of atoms
2. All atoms in the same element are identical
3. For different elements, the atoms are different and have different atomic weights
4. Atoms can combine to create compounds which have fixed rational ratios of the number of atoms
5. Atoms can't be created or destroyed: chemical reactions only regroup them
There was also one point that wasn't so good:
• When atoms only combine in one ratio, it must be binary (1:1)
He clearly assumed that things had to be "simple" and he has cut his throat by Occam's razor in this case ;-) because he had to believe that water was HO (not H2O) and ammonia was NH (not NH3). Well, Nature is obviously not the "simplest one" in this particular sense even if your chemical "philosophy" would lead someone to believe such a principle. In fact, when he determines that the ratios should be given by integers, it would be extremely stupid if Nature didn't prefer other integers beyond the number 1, at least in some cases. :-) Nature would be wasting its possibilities: there are many good reasons why the number of legs is 2 or 4 and not 1 all the time.

Of course, Dalton neglected nuclear physics in his principles: atoms of the same element may differ by the number of neutrons (isotopes) and other reactions, nuclear reactions, can also change the identity of the atoms. But we shouldn't ask for too much from a thinker in 1800.

Testability

I want to add some comments about the testability of ideas and the time-dependence of the amount and character of evidence in favor of the atomic theory. In the ancient Greece, comments about atoms were pure philosophy that was scientifically as good (or bad) as other conceivable philosophies.

But during Dalton's life, things were already very different. The law of partial pressures and especially the rational mixing ratios were extremely powerful weapons that could falsify or at least strongly disfavor many specific enough models that contradicted the existence of atoms. These laws surely didn't tell us everything we wanted to know about the structure of matter: however, they certainly told us something - a lot, in fact - and only scientific dilletantes could think otherwise.

Once the moles were introduced, people could verify new consistency checks about the atoms. Finally, the scientific enemies of the atoms evaporated in 1905 when Einstein correctly explained the Brownian motion (in work also independently pursued by Marian Smoluchowski in 1906). The alternative theories that would explain the chaotic motion of particles in liquids had to be extremely contrived, especially if they wanted to achieve the "distance goes like square root of time" power law for the random walk.

It had to be a random walk and its typical constants were pretty much universal so they had to prove some discrete collisions of basic and rather universal building blocks of all materials: the atoms and molecules. The coefficients told us something about the size of the atoms, too. All these things occurred long before we could actually "see" atoms just a few decades ago. The people who say that they must first see quarks or strings before they take the theory seriously don't tell us anything valuable about science: the only thing these people reveal is that they're narrow-minded, uncreative, slow idiots.

Baron Loránd Eötvös de Vásárosnamény: 165th birthday

Baron Loránd von Eötvös was born in Buda into an aristocratic family connected with Vásárosnamény, Hungary - a town near Ukraine - 165 years ago, on July 27th, 1848.

Fortunately, Lóránd wrote both in Hungarian and German which is why most of the world can learn about his results (and forget about his full Hungarian name, Vásárosnaményi Báro Eötvös Lóránd). He focused on surface tension of liquids and gravity.

His father József was a statesman, educator, and novelist who was also a friend with Franz Liszt, the composer. When Lóránd was born, his father was a minister in the 1848 revolutionary government for a while. Gusztáv Keleti, a painter, was chosen as Lóránd's tutor, and the young future physicist turned out to be real good in drawing (especially on his trips) and poetry. Later, he became one of Europe's best mountaineers (and took a lot of photographs on his trips). He has also climbed a few peaks in the Dolomites so that one of them (in the middle of the picture below) is even named after him!

He studied many subjects at school. His interest in maths and physics clashed with the family tradition. So he entered the University of Pest in 1865 to study the law and become a politician. (The city was merged with Buda into Budapest in 1872.) Lóránd was taking private math lessons from Otto Petzval. His father accepted that it was science, not the law, that his son should pursue.

Lóránd worked in a chemistry lab before he moved to Heidelberg in 1867 (under Kirchhoff who taught him to make accurate measurements and Helmholtz who showed him the power of personal discussions - and others) where police cautioned him just because he was loudly singing on the street with his friends! :-)

Incidentally, the current students of the Eötvös Loránd University clearly follow his example.

After some time in Königsberg (where Franz Neumann taught him a lot about potentials and theoretical physics in general), he received a PhD in Heidelberg in 1870 (the thesis was about Fizeau's problems, one of the early steps that helped special relativity).

Once his dad died in 1871, he returned to Hungary and inherited the dad's title and a chair in the upper house of the Hungarian Parliament in 1872. In politics, he would later do some things related to education and research - for example, he founded the Mathematical and Physical Society, later named after him. But let's return to 1871. Lóránd instantly became a privatdozent of theoretical physics and added experimental physics a few years later. He married Gizella Horváth, a politician's daughter and a skillful pianist with a cool handwriting who spoke French well. Their daughters - see/click the picture on the left - became celebrities as athletes.

He returned to the problem of surface tension (from his student years in Königsberg) in 1876 and spent a decade with it. He measured it accurately and showed that its temperature dependence is universal for all liquids (Eötvös rule):${\rm SurfaceTension} \times {\rm MolarVolume}^{2/3} =\\ = {\rm EötvösConst} \times ({\rm TemperatureCritical} - {\rm Temperature})$ In 1886, he fully focused on gravity which was his big scientific topic until the end of his life in 1919. And of course, he is most famous for his experiments that I will discuss in the rest of this text:

Torsion balance experiments

How did he begin to study this problem? Well, the University of Göttingen offered a prize for someone who would improve the experiments initiated by Galileo that show that the acceleration in the gravitational field is universal for all materials. And Lóránd was the right one to recycle and update the design of Henry Cavendish's experiment from the late 18th century and to improve the accuracy behind the weak equivalence principle to 5 parts per billion, much better than what Newton and Bessel have achieved previously.

In the Eötvös experiment, two different masses are attached to the ends of a horizontal rod, hung from a thin string. The rotation of the rod is monitored by looking at a mirror attached to the rod (or string) through a telescope.

If the inertial and gravitational masses were different, the Earth's gravitational acceleration (proportional to the gravitational masses) would act on the masses differently than the centrifugal "radius times omega squared" force from the Earth's spin (proportional to the inertial masses). I assume that I can afford a simple jargon because you know how to calculate these things and I don't have to introduce more accurate concepts such as the "centripetal force". This mismatch would make the rod rotate which could be seen pretty well through the telescope.

Of course no mismatch of this sort has ever been measured - even though the experimenters in the 21st century such as those in the Eot-Wash group in the Washington state are almost 1 million times more accurate than their old Hungarian colleagues.

Consequences

The weak equivalence principle demonstrated by this experiment is, of course, one of the key principles behind the general theory of relativity. General relativity satisfies this principle: it was, in fact, historically constructed by Einstein who assumed this principle once he appreciated its strength. Newton's theory agreed with this principle by choice. However, unlike general relativity, it didn't explain the principle because one could have written down a similar theory where the masses are different.

This old-fashioned, classical principle is a huge problem for all speculative physicists who try to invent a theory of "emergent" gravity where the gravitational force results from something else than the curvature of space and time - such as new kinds of superconductivity. If you can't find a reason why the description of gravity at long distances in your theory is going to be exactly equivalent to the curved spacetime as envisioned by general relativity, it is pretty much guaranteed that your theory doesn't satisfy the principle exactly.

The probability that your theory satisfies the principle approximately and it is compatible with the experimental bounds on the violation of the principle is equal to $10^{-16}$ or less, a number related to the accuracy of the experimental tests of the equivalence principle. If there's no good reason for the double ratio of inertial and gravitational masses of protons and neutrons to be equal to one, a generic theory is going to predict this double ratio to be a "random number different from one". And the probability that such a random number differs from one by less than $10^{-16}$ is comparable to $10^{-16}$. Different materials, with different proportions of protons and neutrons, will respond differently and twist the torsion gadget.

In other words, people like Robert Laughlin are pretty much screwed.

How does it work in string theory? In perturbative string theory, you may derive gravity through the interactions caused by the exchange of gravitons which are closed strings in a particular vibrational state. At the beginning, you don't see any equivalence principle over here and you might be afraid that string theory is going to follow the fate of Laughlin's or Smolin's theories of gravity and go glub, glub, glub to the bottom of the sea before they even get a chance to put them out there. ;-)

However, when you study the theory more carefully, you will be able to prove that the presence of an additional graviton - a particular closed string - in any particular scattering process has an indistinguishable physical impact from a modification of the background geometry where all the strings propagate: see
Why string theory includes gravity
More precisely, the amplitudes in the original - e.g. flat - space including additional gravitons are equal to the derivatives of the amplitudes without the graviton in a general curved space, differentiated with respect to the curvature and evaluated at the original geometry. The amplitudes of particles not including gravitons at arbitrary curved backgrounds are the generating functionals for all amplitudes at a chosen background with an arbitrary number of gravitons. These words are probably useless if you don't know the formulae, anyway.

At any rate, the equivalence principle is exactly satisfied by string theory even though some descriptions of string theory are able to obscure the reasons and make the principle look like a miracle to a physicist who hasn't studied physics of the theory intensely enough. But if the reasons behind a feature of a theory are obscured, it is just the theorist's potential problem or a complication: it is not a problem of the theory itself. What matters for the fate of a theory is whether its propositions are true, as checked by observations, not whether they are easy to see. And for string theory, it is the case: its predictions related to the equivalence principle are right.

Matrix theory and AdS/CFT obscure the reasons, too. These two approaches don't even allow you to start with a general curved background, at least not in a simple way. Also, you can see the physical polarizations of the gravitons only: the pure gauge polarizations are absent from scratch. However, one can still prove that all the general facts about gravity that normally follow from general relativity are exactly satisfied because these theories - e.g. Matrix theory and AdS/CFT - can be shown to be exactly equivalent to other descriptions where the equivalence principle is manifest.

So if a theory has any chance to describe gravity as we know it today, the metric tensor must be demonstrably present in its low-energy limit and it must be possible to see that other kinds of matter depend on this metric tensor in the same way as they depend in general relativity. Because the metric tensor without anything else can't lead to finite amplitudes at higher energies, we also need some additional players in the story.

The physical phenomena and backgrounds connected in the rich network that we continue to call string theory are the only mathematically possible quantum solutions to the combined problem of finiteness and equivalence principle. It's the only framework where the curved geometry is sufficiently emergent to tame the infinities and to tell us about the inner nature of the force but also sufficiently manifest to agree with the equivalence principle as tested by the experiments initiated by this Hungarian nobleman.

And that's the memo.

#### snail feedback (7) :

Dear Luboš, I love experiments! So what should I expect to happen to me now that I read these biographies? ;)

A simple JavaScript program to see how Dalton would see a colour: https://www.khanacademy.org/cs/new-program-how-would-dalton-see-the-colour/1837201509

A nice avatar as an example. ;-)


text:
# Galilean invariance

Galilean invariance or Galilean relativity states that the laws of motion are the same in all inertial frames. Galileo Galilei first described this principle in 1632 in his Dialogue Concerning the Two Chief World Systems using the example of a ship travelling at constant velocity, without rocking, on a smooth sea; any observer doing experiments below the deck would not be able to tell whether the ship was moving or stationary.

## Formulation

Specifically, the term Galilean invariance today usually refers to this principle as applied to Newtonian mechanics, that is, Newton's laws hold in all frames related to one another by a Galilean transformation. In other words, all frames related to one another by such a transformation is inertial (meaning, Newton's equation of motion is valid in this frame). In this context it is sometimes called Newtonian relativity.

Among the axioms from Newton's theory are:

1. There exists an absolute space, in which Newton's laws are true. An inertial frame is a reference frame in relative uniform motion to absolute space.
2. All inertial frames share a universal time.

Galilean relativity can be shown as follows. Consider two inertial frames S and S' . A physical event in S will have position coordinates r = (x, y, z) and time t; similarly for S' . By the second axiom above, one can synchronize the clock in the two frames and assume t = t' . Suppose S' is in relative uniform motion to S with velocity v. Consider a point object whose position is given by r' (t) = r(t) in S. We see that

${\displaystyle r'(t)=r(t)-vt.\,}$

The velocity of the particle is given by the time derivative of the position:

${\displaystyle u'(t)={\frac {d}{dt}}r'(t)={\frac {d}{dt}}r(t)-v=u(t)-v.}$

Another differentiation gives the acceleration in the two frames:

${\displaystyle a'(t)={\frac {d}{dt}}u'(t)={\frac {d}{dt}}u(t)-0=a(t).}$

It is this simple but crucial result that implies Galilean relativity. Assuming that mass is invariant in all inertial frames, the above equation shows Newton's laws of mechanics, if valid in one frame, must hold for all frames.[1] But it is assumed to hold in absolute space, therefore Galilean relativity holds.

### Newton's theory versus special relativity

A comparison can be made between Newtonian relativity and special relativity.

Some of the assumptions and properties of Newton's theory are:

1. The existence of infinitely many inertial frames. Each frame is of infinite size (the entire universe may be covered by many linearly equivalent frames). Any two frames may be in relative uniform motion. (The relativistic nature of mechanics derived above shows that the absolute space assumption is not necessary.)
2. The inertial frames may move in all possible relative forms of uniform motion.
3. There is a universal, or absolute, notion of time.
4. Two inertial frames are related by a Galilean transformation.
5. In all inertial frames, Newton's laws, and gravity, hold.

In comparison, the corresponding statements from special relativity are as follows:

1. The existence, as well, of infinitely many non-inertial frames, each of which referenced to (and physically determined by) a unique set of spacetime coordinates. Each frame may be of infinite size, but its definition is always determined locally by contextual physical conditions. Any two frames may be in relative non-uniform motion (as long as it is assumed that this condition of relative motion implies a relativistic dynamical effect -and later, mechanical effect in general relativity- between both frames).
2. Rather than freely allowing all conditions of relative uniform motion between frames of reference, the relative velocity between two inertial frames becomes bounded above by the speed of light.
3. Instead of universal time, each inertial frame possesses its own notion of time.
4. The Galilean transformations are replaced by Lorentz transformations.
5. In all inertial frames, all laws of physics are the same.

Notice both theories assume the existence of inertial frames. In practice, the size of the frames in which they remain valid differ greatly, depending on gravitational tidal forces.

In the appropriate context, a local Newtonian inertial frame, where Newton's theory remains a good model, extends to, roughly, 107 light years.

In special relativity, one considers Einstein's cabins, cabins that fall freely in a gravitational field. According to Einstein's thought experiment, a man in such a cabin experiences (to a good approximation) no gravity and therefore the cabin is an approximate inertial frame. However, one has to assume that the size of the cabin is sufficiently small so that the gravitational field is approximately parallel in its interior. This can greatly reduce the sizes of such approximate frames, in comparison to Newtonian frames. For example, an artificial satellite orbiting around earth can be viewed as a cabin. However, reasonably sensitive instruments would detect "microgravity" in such a situation because the "lines of force" of the Earth's gravitational field converge.

In general, the convergence of gravitational fields in the universe dictates the scale at which one might consider such (local) inertial frames. For example, a spaceship falling into a black hole or neutron star would (at a certain distance) be subjected to tidal forces so strong that it would be crushed. In comparison, however, such forces might only be uncomfortable for the astronauts inside (compressing their joints, making it difficult to extend their limbs in any direction perpendicular to the gravity field of the star). Reducing the scale further, the forces at that distance might have almost no effects at all on a mouse. This illustrates the idea that all freely falling frames are locally inertial (acceleration and gravity-free) if the scale is chosen correctly.[2]

### Electromagnetism

Maxwell's equations governing electromagnetism possess a different symmetry, Lorentz invariance, under which lengths and times are affected by a change in velocity, which is then described mathematically by a Lorentz transformation.

Albert Einstein's central insight in formulating special relativity was that, for full consistency with electromagnetism, mechanics must also be revised such that Lorentz invariance replaces Galilean invariance. At the low relative velocities characteristic of everyday life, Lorentz invariance and Galilean invariance are nearly the same, but for relative velocities close to that of light they are very different.

## Work, kinetic energy, and momentum

Because the distance covered while applying a force to an object depends on the inertial frame of reference, so does the work done. Due to Newton's law of reciprocal actions there is a reaction force; it does work depending on the inertial frame of reference in an opposite way. The total work done is independent of the inertial frame of reference.

Correspondingly the kinetic energy of an object, and even the change in this energy due to a change in velocity, depends on the inertial frame of reference. The total kinetic energy of an isolated system also depends on the inertial frame of reference: it is the sum of the total kinetic energy in a center of momentum frame and the kinetic energy the total mass would have if it were concentrated in the center of mass. Due to the conservation of momentum the latter does not change with time, so changes with time of the total kinetic energy do not depend on the inertial frame of reference.

By contrast, while the momentum of an object also depends on the inertial frame of reference, its change due to a change in velocity does not.


text:
• Create Account

### GameDev Marketplace

#### Warriors and Commoners Pack

$140$90

Like
3Likes
Dislike

# A Hobbyist Game Engine Post Mortem

By Paul Coppens | Published Oct 08 2008 01:28 PM in Game Programming

engine postmortem
 If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource

Context
After spending several years developing mostly 2D/3D small applications in different languages on different platforms, I decided to create ex-nihilo, an object-oriented game engine with 3D graphics. My main reasons for creating my own engine were:

• I already had existing code samples (graphic display, skeleton based model, sprite, …)
• When comparing with existing engines at that time, I thought they were lacking simplicity compared to the kind of programs I wanted to write and did not offer direct support for sprites, fonts and/or user-defined GUI.
I also wanted to learn how to develop a cross-platform engine with no external dependencies (except the Standard C++ Library). I was considering whether I should continue developing under Windows or switch to Linux and I didn’t want to have too much work porting the engine. I also wanted to improve my refactoring skills. This endeavour as a lone hobbyist game programmer took me a little more than 1500 man hours over two years. Here is the result of my developments.
What Went Right

1 - Focus
I wanted a cross-platform game engine to realize 2D/3D turn based strategy games or simple RPG games like Final Fantasy 7. As such the preliminary features were:

• OpenGL for cross-platform graphics at least v1.2.
• Object-Oriented Design
• Scripting: simple to change on-the-fly combat resolution, to code spell/weapon effects and game events
• Import/Export a few formats: the Milkshape 3D modeller text and binary format + my own internal format for sprites and models, TGA, BMP and light length-encoded bitmaps.
• Simple physics (basic collision detection of Axis Aligned Boxes and spheres; basic navmesh handling).
• Hardware vertex transform and lighting (T&L)
• Basic Texturing
• Skeletal Animation
• Special Effects: Billboarding, Particle Systems, Simple Terrain Rendering (Hex based and square based),
• Fonts and GUI support
• Sound system (mod player).
• Embedded logging system.
• Basic Multithreading availability
Each feature was simple enough to be realized and there existed an ample amount of documentation on the Net and in books. Moreover, I got a moral boost each time I completed a feature on that list.
2 - Planning
In my day-time job, I am used to writing software/process specifications and planning schedules. This made the process more natural to do as I knew how. Moreover, I knew what time I had available to me and planned in consequence. Even though my documents were less detailed than what I do at work (hey, that’s a hobby for me), I had defined goals to reach and found out it would require one year’s time to complete the project. I knew from the beginning it was no trivial task and was prepared for it.

Here is the simple planning I did:

• Design the architecture: 2 weeks
• Realize the core framework (interface for creating a blank Window + initialising OpenGL + basic helper functions and logging + basic multithreading interface): 3 weeks.
• Realize the basic core Renderer (frustum + renderer + math interface + Color and Light interfaces + texture manager): 6 weeks.
• Create the font engine (refactor bitmap and rendered font code, include default fonts, create font file format): 4 weeks.
• Create the basic Scenegraph (Scenegraph and basic volume generator): 4 weeks.
• Create the Mesh Model Node (refactor existing code and file loading, process animated and static models + model manager): 5 weeks
• Create the Sprite Model Node (refactor existing code and file loading, create billboarding code, process animated and static sprites + sprite manager): 3 weeks
• Create the Particle engine Node (create code, create interface): 3 weeks
• Create basic terrain rendering (refactor terrain generation code with hex and square cells, create file format): 2 weeks.
• Create the GUI interface (refactor existing code for buttons, dialog, text, progress bar, mouse widgets, create file formats for skinning and GUI loading): 5 weeks
• Create the scripting interface (refactor existing code for scripting): 2 weeks.
• Create the sound system (reuse DUMB and adapt with OpenAL): 10 weeks.
Note that to me, a week is composed of 1 to 2 hours of programming per day with 7 days in a week (at work during lunchtime for one hour + one or two hours in the evening). Each of the tasks planned were undividable but could be realized in any order (except the 5 first tasks).
3 - Careful design
Before committing to development I took time to polish my engine architecture. Contrary to small scale projects, this one needed to be carefully thought. It took me about 3 weeks to define a satisfying UML diagram of the engine. It did pay in the long run as each new feature integration neither broke nor frankly stressed the design. So no mid-project code overhaul or architecture redesign was ever needed. This also helped refactoring previous code as I knew the interfaces and how it should interact with the engine. This was another proof of a sound design adapted to my needs.

4 - Previous experience
I was able to capitalize on all my previous experience. I had already written simple expert systems, a forth interpreter, 2D graphics renderers, 3D mesh viewers including skeletal animation, basic multithreaded resource loaders… all simple applications in different areas of the game engine I wanted to develop. This gave a great boost to the realization of this game engine and improved my refactoring skills. This confidence is also reflected from the beginning in the planning where I knew with great confidence it was not uncharted areas. Good for the morale to know before hand that tasks won’t be that difficult to do.

5 - Iterative development
To me, what was of utmost importance was that each new feature and optimisation added did not add bugs to the engine or degrade performance. So I wrote a few samples using the engine (and even editors) and each time I modified the code, I compiled the engine against all examples to check that they perform as they were designed to. All examples were also improved each time to include the latest added features: they doubled as engine tests. I also ensured the engine and the examples worked the same way on all three different computers I use:

• an IBM ThinkCentre 8429 with no added graphics card using Windows 2000.
• a home-made Pentium 4 2Ghz with an old GeForce graphics card using Windows XP Professional edition.
• a laptop AMD processor with an internal GeForce 780X graphics card using Windows XP Home edition.
Plus I established the policy that bug resolution was to be done prior to any further development. I had activated the “signal all warnings” option on my compiler to be sure to catch bugs early on. Engine stability was really important. Discipline is the best friend of the developer. This iterative development led to a very robust engine and a very clean library.
6 - Engine documentation
As this was a really big scale project, I wanted to easily maintain code documentation for ease of reference in later developments using this engine. I learnt to use Doxygen and never went back. It really was simple to maintain documentation (instead of writing full descriptive documents under Word which were a pain to maintain). This also improved the reuse of the engine since I was able to develop samples two years after the beginnning of the engine development.

7 - Keeping track
I also manually kept a log of any changes I made to the engine in a simple text file. I also manually logged any bug encountered in another text file. Bug correction had higher priority than feature development. This log helped me to keep track of what I was doing and where I stopped (invaluable for a hobbyist programmer with little development time available) but also gave a moral boost when considering everything that was done and all steps ensuring the stability of the engine.

8 - Logging for debugging
When developing a multithreaded application, the only solution to trace a code or to time a code is through logging. I had explored the use of gprof for debugging purposes. Even though it is mandatory for single thread applications, I saw two drawbacks for multithread applications:

• often the debugger does not stop on the spot where the error occurred. Moreover the spot where it stops changes over some application execution.
• a few times the error was not stable when the debugger was on: the program could run normally without any bugs on one execution and crash on another.
The embedded logging system with different levels of logging available proved to be invaluable. Moreover, I added a trace method to some classes for easier debugging information on the engine internals. Debugging state changes for optimisation was easier. The logging system was also available when integrating this library in a project. It eased the optimisation of the display and the tracking of state changes (or identify faults when loading in resources).
What Went Wrong

1 - Creeping features
Even though I had carefully laid out my plans, I could not help adding a few more features. I added:

• To AI scripting system: basic subsumption and rule-based system.
• To texturing: multitexturing and bumpmapping.
• To rendering: render to texture interface.
• Faster font rendering.
• OFF mesh format processing.
• A XML file parser.
• A scenegraph file format.
• A curve generator using three different methods
I stopped myself before I added any more features: I then was considering mirror rendering and thinking about basic shadows. Creeping features always occurred when looking at/playing other games (a shame I tell you ? ). I wanted to add more chrome to my display (bump-mapping, render to texture), to diversify object loading for simpler game resource integration without using third party converters (PNG and OFF for example). I stopped myself when I understood I was thinking more in terms of engine elements than direct implementation. This proved to myself that I had finally come to understand how a graphics/game engine works and how I can extend such an engine, even if it is a third party engine.

2 - Not made here syndrome
Under the guise of learning things (or not having external dependancy), I discovered I was in fact writing code and reinventing the wheel. I wrote for example a file system which let me indifferently load a resource from a package or from a physical disc. Even though it worked, it was of lower quality than code available on the Net which was better realized, cross-platform and compatible with multithreading (like PhysicsFS by Ryan C. Gordon for file system abstraction).

After discovering this, I created interfaces for any features I wanted to integrate so that I could add third party elements and still provide a unified interface. This had an unintended good effect: it helped to isolate poorly designed 3rd party interfaces (which at compile time created a lot of warnings). Thus I learnt I could use third party libraries provided I designed an interface to isolate from my code (this also simplified testing third party libraries since all I had to do was implement the library using my own designed interface). I ended up using Audiere and IrrKlang libraries for the sound system part of the engine.

3 - Side development
This was a direct consequence from both previous problems. When I did not have existing code, I first realized a simple small application as a proof of concept. When the proof of concept was ready, I kept rewriting it until I was satisfied with its design and architecture. Once done, I refactored the code for integration within the engine. Some development went right (subsumption system), some went wrong (file system), and one went utterly wrong (sound system). I spent a lot of time rewriting the same kind of code over and over when I could have designed an interface and be done with it (which I ended up doing for the sound system to link with a 3rd party library).

4 - Cross-platform?
Cross-platform development is demanding and there is little information on the Net. Moreover, there was one obstacle I did not have time to overcome: to test the engine on a linux box. I used virtual machines to create linux boxes but I encountered many other problems like learning how to properly configure a linux system (moreover on a virtualized configuration). As a hobbyist, I did not have the time to both learn the linux side and develop the engine. So I used whatever information I had (taking care of endianness, strictly defining engine types, multiple header inclusion depending on preprocessor directive, …). Still, even though the code is very clean and follows my home-made rules for cross-platorm, it never was tested on a linux configuration.

5 - Planning
I had originally planned to develop this engine during one year as it seemed realistic. However, I forgot to include editors in my planning, which were sorely needed for creating resources for my samples, and of course additional features were not even planned at the beginning (more on the spot when I decided I needed that feature). Moreover, I had not taken into account the extensive debugging for cross engine bugs (e.g. when some state changes under OpenGL pollute the rendering of some scene nodes).

It took two years to develop the engine due to all the previous faults. Still that was quite tight since I was a hobbyist married with a kid and with a day-time job. But I did not want to quit before all the planned features were implemented and the engine stabilized. I am however glad that all added features were interesting in their own since I kept learning new areas I was not familiar with. Had it not been the case, I would have had a big morale problem. Managing ones morale is essential to progress in such a project.

6 - Personal objectives
Since I added new features to the list and created editors, this meant that the project was beginning to take a life of its own: I understood that I would only program to maintain and evolve an engine (interesting since you do learn a lot of things, mildly to not rewarding if you do not take care of your morale and if nobody use the engine). I had to choose between developing this engine or write small games and small code projects using more third party libraries.

Conclusion
I wanted to learn developing a cross-platform engine with no external dependencies. The goal is partly achieved: I learned how to develop, test, stabilize, maintain and document an engine. I also have completely implemented the original feature list. The engine however is not cross-platform until tested on a Linux box.

When comparing with the list of engines at Devmaster.net, I found out that it was quite a nice little engine that could be evolved and satisfy a few basic needs. Still, during the two years of my engine development:

• other engines also improved and are now more than sufficient to satisfy the needs I had.
• I developed all the necessary skills to understand and adapt these engines to my needs.
• New hardware architecture appeared (dual core 64-bit machines, and more to come). Even though I took some steps to ensure no side effect with ulterior compilation on 64-bit platforms, I cannot guarantee this. In fact this means more tests to do on different configurations and I cannot virtualize to insure the stability of my engine on 64-bit architectures.
Was it a waste of time? Definitely not. The knowledge I gained was invaluable (understanding quaternion, refactoring code, scenegraph optimization…). Can a lone programmer (even a hobbyist one) succeed writing an engine? Yes, provided she has previous succesful programming experience, she plans carefully and focuses on features that are within her reach. Success in realizing the plan brings enlightenment.


text:
It is currently 18 Oct 2017, 02:35

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

# There are 9 books on a shelf, 7 hard cover and 2 soft cover.

Author Message
SVP
Joined: 30 Apr 2008
Posts: 1867

Kudos [?]: 615 [0], given: 32

Location: Oklahoma City
Schools: Hard Knocks
There are 9 books on a shelf, 7 hard cover and 2 soft cover. [#permalink]

### Show Tags

19 Jul 2008, 17:48
This topic is locked. If you want to discuss this question please re-post it in the respective forum.

There are 9 books on a shelf, 7 hard cover and 2 soft cover. How many different combinations exist in which you choose 4 books from the 9 and have at least one of them be a soft cover book?

a) 126
b) 91
c) 84
d) 70
e) 108
_________________

------------------------------------
J Allen Morris
**I'm pretty sure I'm right, but then again, I'm just a guy with his head up his a$$. GMAT Club Premium Membership - big benefits and savings Kudos [?]: 615 [0], given: 32 Director Joined: 10 Sep 2007 Posts: 934 Kudos [?]: 338 [0], given: 0 Re: Combinations Problem - Books selected from a shelf [#permalink] ### Show Tags 19 Jul 2008, 18:07 1st Way: 1 soft cover, 3 hard cover = 7C3 * 2C1 = 7*6*5/3*2 * 2 = 70 2nd Way: 2 soft cover, 2 hard cover = 7C2 * 2C2 = 7*6/2 = 21 Total ways = 70 + 21 = 91 Answer B. Kudos [?]: 338 [0], given: 0 SVP Joined: 30 Apr 2008 Posts: 1867 Kudos [?]: 615 [0], given: 32 Location: Oklahoma City Schools: Hard Knocks Re: Combinations Problem - Books selected from a shelf [#permalink] ### Show Tags 19 Jul 2008, 20:13 You are all correct, OA is B! The way I did this was Total - invalid combinations = Correct Answer. $$C_9^4 = 126$$. Because we need to have at least 1 soft cover, we need to subtract out all of the instances when we have 4 of the 7 hard covers selected...this is $$C_7^4 = 35$$. 126 - 35 = 91. jallenmorris wrote: There are 9 books on a shelf, 7 hard cover and 2 soft cover. How many different combinations exist in which you choose 4 books from the 9 and have at least one of them be a soft cover book? a) 126 b) 91 c) 84 d) 70 e) 108 _________________ ------------------------------------ J Allen Morris **I'm pretty sure I'm right, but then again, I'm just a guy with his head up his a$$.

GMAT Club Premium Membership - big benefits and savings

Kudos [?]: 615 [0], given: 32

SVP
Joined: 28 Dec 2005
Posts: 1545

Kudos [?]: 178 [0], given: 2

Re: Combinations Problem - Books selected from a shelf [#permalink]

### Show Tags

21 Jul 2008, 11:21
jallenmorris wrote:
You are all correct, OA is B!

The way I did this was Total - invalid combinations = Correct Answer.

$$C_9^4 = 126$$. Because we need to have at least 1 soft cover, we need to subtract out all of the instances when we have 4 of the 7 hard covers selected...this is $$C_7^4 = 35$$. 126 - 35 = 91.

jallenmorris wrote:
There are 9 books on a shelf, 7 hard cover and 2 soft cover. How many different combinations exist in which you choose 4 books from the 9 and have at least one of them be a soft cover book?

a) 126
b) 91
c) 84
d) 70
e) 108

exact same way I did it ! Although Im always somewhat nervous about this approach because Im not always certain whether Ive accounted for all possibilities

Kudos [?]: 178 [0], given: 2

Director
Joined: 01 Jan 2008
Posts: 618

Kudos [?]: 198 [0], given: 1

Re: Combinations Problem - Books selected from a shelf [#permalink]

### Show Tags

21 Jul 2008, 12:01

jallenmorris wrote:
You are all correct, OA is B!

The way I did this was Total - invalid combinations = Correct Answer.

$$C_9^4 = 126$$. Because we need to have at least 1 soft cover, we need to subtract out all of the instances when we have 4 of the 7 hard covers selected...this is $$C_7^4 = 35$$. 126 - 35 = 91.

jallenmorris wrote:
There are 9 books on a shelf, 7 hard cover and 2 soft cover. How many different combinations exist in which you choose 4 books from the 9 and have at least one of them be a soft cover book?

a) 126
b) 91
c) 84
d) 70
e) 108

Kudos [?]: 198 [0], given: 1

Re: Combinations Problem - Books selected from a shelf   [#permalink] 21 Jul 2008, 12:01
Display posts from previous: Sort by


text:
# Backpacking - travelling with 'smart' clothes

I've heard the tips for keeping your clothes unwrinkled in general - rolling t-shirts, having those cell things for shirts in your bag, etc.

However, while those work pretty well for t-shirts and casual clothes, every so often I've had to travel with smart trousers, business shirts, or (recently) a suit!

I didn't risk it, and carried the suit separately, having had that go badly in previous times. However, I can't find an easy way to travel with a backpack and not have creases in my business shirts. IF the destination has an iron, that's all good. However they sometimes don't, and in deed last time for the first time, I burnt my shirt in the process (it was not a good start).

Any solid techniques for keeping clothes uncreased in a backpack?

-
What are those cell things for shirts? I'm interested... –  John Doe Feb 1 '12 at 15:45
Like this: kathmandu.com.au/Product/40326 - keeps them all together, and so when you unpack you just pick up the irrelevant cells, take them out of your bag, and open the one you need. –  Mark Mayo Feb 1 '12 at 20:01
Oh, you meant ditty bags... Didn't understand it initially. –  John Doe Feb 1 '12 at 21:37

Some suggestions:

1. In my experience, rolling worked fine for trousers, but for a shirt, it is not efficient enough.

2. Ankur's suggestion of wrinkle-free clothes is a must. Keep at-least one set of wrinkle-free clothes handy.

3. I normally keep my clothes in plastic bags, they are very good to avoid wrinkles. Just keep in mind that only one cloth should be kept in one plastic bag.

Lastly I came across this link http://www.onebag.com/pack.html. Though I have not practiced it yet, the person seems to know what he is talking about. I'ld be glad to know what you all think of it.

-

Attach a dedicated bag for your suit (flat packed of course) to the outside of your backpack? Seems like the only good way to do it, tbh, outside of having it couriered between places you need it.

-

Surprisingly, according to other business travellers, the answer - yet again - seems to be roll up your clothes:

At Midway Airport I got into a conversation with another traveler and I mentioned that my suit was packed in my carry-on bag. The guy couldn’t believe that I had a suit in my bag.

Not much luck with dress shirts though:

I don’t seem to have as much luck with dress shirts – I usually wind up ironing them at the hotel.

Regardless, I would suggest buying wrinkle-free shirts and trousers for such purposes. I had to pack a change of clothes in my backpack because I had to go for a company dinner after work (didn't want to go back home to change), and having flat-packed wrinkle-free clothes helped as they didn't look bad once unpacked.

-
+1 for wrinkle-free shirts. –  starsplusplus Feb 17 '14 at 16:28

I presume you're using a front loading backpack, right? If so, why don't you make a plastic or cardboard box that fits your smart clothes (add some straps inside to keep everything tight) and use it as a container for "keeping the wrinkles out". :D

Don't know about you guys but I usually never pack my backpack to the top and have enough room for about two or three winter vests (just an example) so that's where you DIY suit container can fit.

Not that you asked but there are travel irons that are neither heavy nor big so consider that as well if you don't carry your suit every time you travel.

-

Onebag.com at the end of the page dedicated to Clothes and Laundry advises to simply rent the suit when needed. But I presume that in a place without iron, such renting service will be hard to find.

-
and more expensive than taking a suit and having it dry-cleaned! –  Mark Mayo Feb 1 '12 at 20:02


text:
# Connection with system analysis and laplace&Z transform

Laplace&Z transform is just frequency analysis of a system with a multiplication of decaying exponential. We analyse frequency with varying Laplace Exponential, which can be seen in the formula below for laplace transfrom.

From my simple aspect I can't make the theoretical connection, how inspecting frequency with decaying exponential helps with understanding how system will behave? And how it helps with coping with differential functions for example "Analysis of Electric Circuits". And even with IIR filters.

What further surprises me the things laplace&Z transforms used. They seem to me completely different .But somehow multiplying the system with decaying exponential works for them all. The only similarity I see between; for example RLC curcuits and IIR filters is; these systems are not memoryless(output depends on prev. outputs).

When I search the net I see only laplace-table's, questions etc.. I don't want to solve a problem, I want to understand the problem. If somebody can explain or direct me to a link I will be thankful.

You are right that the (bilateral) Laplace transform can be interpreted as the Fourier transform of $e^{-\sigma t}f(t)$. However, I think that the significance of the Laplace transform only becomes clear when $s=\sigma+j\omega$ is viewed as a complex variable because then we can study the analytic properties of the system function. E.g., electrical networks are characterized by the poles and zeros (in the complex $s$-plane) of their system function.

The practical importance of the Laplace transform for the analysis of continuous systems lies in the fact that it transforms linear differential equations with constant coefficients into algebraic equations, which are obviously much easier to solve. This is achieved by the fact that in the Laplace transform domain, integration is equivalent to multiplication by $1/s$, and differentiation becomes multiplication with $s$.

Any linear time-invariant (LTI) system, such as the RLC-circuit you mentioned, will result in linear differential equations with constant coefficients. This is why any LTI system can be analyzed by the Laplace transform. Note that in practice usually the unilateral transform is used (where the integral starts at $t=0$ instead of $t=-\infty$), because practical systems are causal, and because in this way initial conditions (such as charged capacitors at $t=0$) can be easily taken into account. The unilateral Laplace transform is thus an appropriate tool to solve initial value problems.

Everything said so far carries over to the $\mathcal{Z}$-transform if you replace 'continuous system' by 'discrete system', and 'differential equation' by 'difference equation'. Linear time-invariant discrete systems consisting of adders, multipliers and delay elements are treated by the $\mathcal{Z}$-transform in the same way as LTI electrical networks are treated by the Laplace transform. And indeed, IIR filters are analogous to RLC circuits in the sense that both have an infinitely long impulse response and that both can be characterized by the poles and zeros of their system functions.

the exponential input:

$$x(t) = e^{s t}$$

is an eigenfunction to any Linear and Time-Invarient (LTI) system. that means if the input is $x(t)$ above, the output $y(t)$ is (for some constant $s$):

$$y(t) = h(t) \circledast x(t) = h(t) \circledast e^{s t} = H(s) e^{s t}$$

("$\circledast$" means convolution.)

$H(s)$ is a constant because it's a function of $s$ which is constant. so the output $y(t)$ is a scaled version of the input $x(t)$, so that's what makes $x(t)$ an eigenfunction of the LTI system that is fully described by either the impulse response $h(t)$ or transfer function $H(s)$. the transfer function $H(s)$ is the Laplace Transform of the impulse response $h(t)$.

$s$ can be anything, real (like $s=\sigma$), imaginary ($s=j \omega$), or complex ($s=\sigma+j\omega$).

it turns out that, due to some theorem in complex analysis, that it suffices to know how the system (if it's "analytic") responds to $x(t)=e^{j\omega t}$ for all real $\omega$ to fully describe the input/output relationship of the LTI system.


text:
# How to start with biaxial tensile strain and compressive strain in TMDCs using VASP?

Good morning!

I would like to test the biaxial tensile strain and compressive strain in a hexagonal material from the TMDC group (for example HfS2). How to get it into VASP? What are the best ways to optimize geometry? Can I fall into some traps?

HfS2
1.0
3.6389749050         0.0000000000         0.0000000000
-1.8194881106         3.1514448821         0.0000000000
0.0000000000         0.0000000000        22.8899211884
Hf    S
1    2
Direct
0.000000000         0.000000000         0.500000000
0.666666985         0.333332986         0.563098013
0.333332986         0.666666985         0.436901987

Could you help me with this as example?

• +1. Thank you Milosz for contributing your very nice question here. Could you please put the contents of your screenshot, into a code block instead of doing a screenshot? What you have done is not the right way to present your question here. Sep 1 '20 at 18:58

How to get it into VASP?

The key point is to generate different POSCAR files. Once you prepare input files, you can perform the calculation with VASP. I will assume you are considering monolayer T-phase HfS2 and show how to generate compressive and tensile structures.

• Initial structure:[HfS2.vasp]

HfS2
1.0
3.6389749050         0.0000000000         0.0000000000
-1.8194881106         3.1514448821         0.0000000000
0.0000000000         0.0000000000        22.8899211884
Hf    S
1    2
Direct
0.000000000         0.000000000         0.500000000
0.666666985         0.333332986         0.563098013
0.333332986         0.666666985         0.436901987

• Then you can apply the biaxial strain for this structure by changing the length of $$\vec{a}$$ and $$\vec{b}$$ at the same time. In detail, you can do this with the following python script:

import numpy as np

def bistrain(path1,path2,strain):

with open(path1,'r') as f1:

lattice = np.zeros((3,3))
for i in range(3):lattice[i,:]=list(map(float,lines[2+i].strip().split()))

lattice[0:2,0:2]=lattice[0:2,0:2]*strain

with open(path2+'strain_'+str(strain)+'.vasp','w') as f2:
f2.write(lines[0])
f2.write(lines[1])

for j in range(3):f2.write("%20.16f  %20.16f  %20.16f" %(lattice[j,0],lattice[j,1],lattice[j,2])+'\n')

for k in range(5,len(lines)):f2.write(lines[k])

#==================================================================
path1='./HfS2.vasp'
path2='./'
#strain=0.99   ## compressive strain
strain=1.01    ## tensile strain
bistrain(path1,path2,strain)

What are the best ways to optimize geometry?

When the POSCAR is prepared, you can relax the structure referring to this answer.

Can I fall into some traps?

For the initial structure, you should use fractional coordinates rather than Cartesian coordinates.

May it hopes.

Just to add to jack's answer. This is easily implemented in ASE.

Here is the same example which creates biaxial strain POSCARs from -5% to 5% strain in 1% increments.

from ase.io import read
from os import makedirs
import numpy as np

for strain in np.arange(0.95, 1.05, 0.01):