SciLearn

peak detection

2009-03-08T18:37:00.000-04:00

I have been recently working on a Python program that detects peaks in an oscilloscope trace. With help from this post I found, I managed to find the best algorithm to deal with my situation.

Mathematically, finding the peaks (local maxima) of any graph is straightforward, as long as the function is simple enough. All one has to do is to find the x-values where the first derivative is zero, and then apply the second derivative test to differentiate the maxima (peaks) from the minima (troughs).

However, real data tend to be rather coarse, so peak detection can be rather difficult. From the article I mentioned earlier, this issue can be resolved by "derivative smoothing". The typical way of estimating the derivative of a function represented by a set of discrete points is by taking every pair of points and calculating the gradient. Derivative smoothing involves taking more than two points to calculate the derivative. The article says this can be achieved by taking a group of points and calculating the gradient using just the first and the last points in this group, but I decided to try something different: making a linear fit on this group of points and find the gradient of this fit.

I don't know if this is more accurate or appropriate, but I tried it out anyway, and so far it's working well. The only downside is that the calculations are much slower since fitting a set of data points is computationally intensive. In any of these peak detection methods, the precision of the peak is always limited by the discreteness of the values; to improve this precision, one can attempt to fit the peak itself with a fit curve, say a Gaussian (if symmetric), and use the fitted parameters to find a more precise value for the peak.

commutative power

2009-01-02T15:00:00.011-05:00

The power operator ("a raised to the power of b") is certainly not commutative, i.e. in general a^b ≠ b^a. This should be no surprise, e.g. 2³ ≠ 3².

What I am interested is find pairs of natural numbers, in which a^b does equal b^a. I already know one pair: 2⁴ = 4² (in addition to the trivial pairs, e.g. 3³ = 3³), so I need to find out what's so special about this pair of numbers.

To do this, I break the equation into a series of steps:
2⁴ = 2^2×2 = (2²)² = 4².
Now the relationship becomes clear; I want a pair of numbers such that:
a^b = a^c×a = (a^c)^a = b^a
where c is another natural number that satisfies:
b = c×a and b = a^c
I can combine these equations into one:
c a = a^c
So how many (nontrivial) pairs of natural numbers satisfy this equation? By nontrivial, I exclude cases where c = 1.

Now, to solve this equation:
c a = a^c
c a - a^c = 0
(c - a^{c - 1}) a = 0
Either a = 0 (which is trivial) or c - a^{c - 1} = 0. Consider the latter nontrivial case:
c - a^{c - 1} = 0
c = a^{c - 1}
c^{1/(c - 1)} = a
Therefore, if a value of c is known, a can be found by taking the (c - 1)^th root of c. If c = 2, then a = 2^{1/(2 - 1)} = 2, and therefore b = c a = 4; this shows why 2⁴ = 4². For any other c > 2, (c - 1)^th root of c will not be an integer, so there are no other nontrivial natural-number combinations of a, b and c.

Well, looks like that answered the question. It seems 2⁴ = 4² is pretty special case, after all.

iron's odor

2008-12-19T20:28:00.000-05:00

Well, just a short post on an interesting finding. I was curious why iron tends to produce strange metallic smells (it occurs to some other metals as well as blood), and it looks like a quick Googling gives me a neat explanation of this phenomenon. Go check it out.

It's funny that some common phenomena can be so easily ignored, and we never get to appreciate the science behind it.

numerical pendulum

2008-12-06T12:10:00.006-05:00

There was this "flash of idea" that I could solve "any" differential equations numerically, which implies I could "simulate" Maxwell's differential equations using a computer program. Sadly, that was too tall an order, so I could only manage to simulate the most basic of differential equations.

So far I managed to derive a simple method to simulate pendulums directly using the rigid pendulum equation (c is a negative constant)m

I do know Euler's method, which is really simple. But how do I apply it to second derivatives? That's the trick here.

I found that if I broke this equation into two by defining a variable ω,

I can easily apply Euler's method using the finite differences approximation,

Therefore, I can convert this into a form useful for programming,

This is easily done by iteration; simply keep track of the index i and the values of ω and θ. By choosing the Δt to be small, one can approximate the pendulum with some precision. I have tested the method and it seems to be quite stable, though I'm not sure how good the precision.

101 posts?

2008-11-24T23:19:00.000-05:00

Hey, I just realized that the last post was the 100^th one.

Happy Thanksgiving!
(Hopefully, I can write a full SciLearn post on Thursday.)

wave interference

2008-11-15T14:31:00.049-05:00

This post deals with the interference of light.

Light is a strange thing. It's made of photons, yet most of the time, it behaves as a wave. Now I won't go into the quantum mechanical details of light; I'm just going to talk about one particular nature of light: interference, which occurs whenever light behaves as a wave. I'll provide a systematic summary of wave interference and slit interference patterns.

The first step to interference is to begin with the basic equations of wave motion. Let's pick a simple sine wave in 1 dimensions:

d(x, t) = a sin ϕ = a sin[kx - ωt + ϕ₀]

where:
d = displacement;
a = amplitude;
k = angular wavenumber;
x = position;
ω = angular frequency;
t = time;
ϕ = phase;
ϕ₀ = initial phase.

When two waves interfere, their displacement superpose on each other, so they can simply be added to produce the resultant wave (for simplicity, amplitude of both waves are equal):

where
ϕ₁ = k₁x₁ - ω₁t + ϕ_0,1;
ϕ₂ = k₂x₂ - ω₂t + ϕ_0,2;
Δϕ = ϕ₁ - ϕ₂;
Σϕ = ϕ₁ + ϕ₂.
⟨ϕ⟩ = Σϕ / 2
The above equation involved the use of a "sum-to-product" trigonometric identity.

There are special scenarios under which the above equation simplifies:

Standing wave:
x₁ = x = x₂
k₁ = k = k₂
-ω₁ = ω = ω₂
ϕ_0,1 = 0 = ϕ_0,2
The displacement equation is:

The boundary conditions for a standing wave is that the ends, at x = 0 and x = L, are fixed discontinuities (i.e. the ends of the standing wave cannot move):

D(0, t) = D(L, t) = 0 (for any t).
Solving this equation yields the allowable wavenumbers and wavelengths (λ) for standing waves:
Coherent interference:
k₁ = k = k₂
ω₁ = ω = ω₂
The displacement equation is:

The condition for destructive interference is:

Similarly, for constructive interference:
Beat interference:
x₁ = x = x₂
k₁ = k = k₂
ϕ_0,1 = ϕ₀ = ϕ_0,2
The displacement equation is:

where ω_mod is the modulation angular frequency.

Now, at last, I can show the general equations (approximations) for multiple-slit interference.

For single-slits, the minima angles (θ_min) can be found using:
a sin θ_min = n λ where n is a positive integer and a is the slit width.

For double-slits, multiple-slits, or diffraction gratings, the primary maxima angles can be found using:
d sin θ_max = n λ where n is zero or a positive integer and d is the slit separation.

The two results actually apply to any slit interference: θ_min will be the primary minima angles and θ_max will be the primary maxima angles. The shape of the intensity plot will always have an envelope curve that is shaped like the intensity curve of a single-slit diffraction, and the minima of this envelope curve is the "primary minima".

So that was my brief summary of light interference.

reciprocal distribution

2008-11-01T17:31:00.023-04:00

Here's another post on math stuff, although it's also implicitly related to computing.

Suppose I generate a random real number X between 0 and 1 with a uniform probability distribution. Let Y = 1/X. What is the probability distribution of Y? What is the expected value of Y?

To solve this question (which I asked myself), I would start by finding the probability distribution of X.

For me, the main problem is that this is a continuous probability distribution rather than a discrete one. Therefore, it makes no sense to ask the probability of getting, say, exactly 0.5. In discrete probability distributions, we can describe a function called "Pr" or the probability function. Let's take a dice distribution as an example. A dice can have 6 possible values: D = {1, 2, 3, 4, 5, 6}. Each value has an equal probability of 1/6. We can define a probability function for it easily:

Pr(D = d) = 1/6 (this is read as: "the probability of random variable D getting a specific value of d is 1/6")

This is a discrete uniform distribution, because the probability is the same for every d. The equivalent way of saying this is:

While this form is rather redundant, it does explicitly show that we can define a specific probability for every value of d. For a continuous distribution, it no longer makes sense to assign a probability to every possible value, since there is now an infinite number of possible values (continuous).

However, it still makes sense to define a probability for every "chunk" of values. Consider the random real number X between 0 and 1. It is absurd to ask for the probability of getting X = 0.5, but it still makes sense to ask for the probability of 0.45 ≤ X < 0.55. This is a range of possible X values from 0.45 to 0.55. The width (Δx) of this range is 0.55 - 0.45 = 0.1. We can make use of something called probability density function, f(x), as follows:

This is in many ways similar to the frequency density used in histograms.

Since the probability is defined by the integral of the probability density function (i.e. area under the f(x)), the total area under the probability density graph must be 1 in order for the total probability to be 1. This is done by normalizing the function using a constant multiple.

For example, a continuous uniform distribution between x = 0 and x = 1is rather simple:

It's easy to see that this graph is already normalized since the area is just a 1 by 1 square. This is just the distribution of the variable X in the question posed in the beginning of this post. Now that we know the probability density of X, how can we find the probability density of Y?

Suppose I pick 2 values a and b (and a < b) What is the probability of X between these two values? It is simply Pr(a ≤ X < b). By intuition, it should make sense that the probability of Y between 1/b and 1/a (I swapped the order because 1/b < 1/a) should be equal to the probability of X between a and b, since x = a implies y = 1/a and x = b implies y = 1/b. Therefore, we have the equation:

Using the integral form:

where f(x) and g(y) are the probability densities of X and Y respectively. Differentiate both sides with respect to a and simplify the expression:

Explanation:
Step (2) left side: swap the limits of integral, thus swapping the sign.
Step (2) right side: use chain rule to get the differentiation with respect to 1/a instead of a.
Step (3) left side: apply fundamental theorem of calculus.
Step (3) right side: differentiate 1/a and apply the fundamental theorem of calculus to the integral part.
Step (4): multiply both sides by -a².
Step (5): substitute a = 1/y so that g is in terms of y (the y here does not have much to do with the y in (1) and (2)).

Now we have an expression of g(y), in terms of f(x) (which is the same as f(1/y), since x = 1/y). Since f(x) is a uniform distribution with f(x) = 1 for all values of x within [0, 1], we can define g(y) for all values of y within [1/1, 1/0), or [1, ∞), to be 1/y². Because f(x) is zero elsewhere, g(y) is zero elsewhere as well. So this is the formula of g(y):

While not obvious from the equation, this function is definitely normalized, and can be easily proven to be so using improper integrals.

So, the aim was to find an expected value for the distribution. What is the formula for a continuous distribution? The expected value for a discrete random variable X is defined by:

Therefore, by analogy, the expected value for a continuous random variable (with probability density f(x))should be:

So the next step would be to evaluate this integral for Y:

Explanation:
Step (2): Split the integral into 2 parts, one for x ≥ 1 and one for x < 1. This is done because g(x) is defined piecewise.
Step (3): Integral of zero is zero. Simplification.
Step (4): Integral of 1/y is divergent because the natural logarithmic function is unbounded.

It looks like the expected value is infinite. What does that mean? Basically, if one were to simulate this on a real computer program (tried that myself) to calculate expected value, one could get utterly random values stretching from very small to very large.

The expected value of g(y) is infinite - this is a boring conclusion, isn't it? Well, over the steps listed here, I have found a technique that allows me to derive the probability density of one variable based on a formula that links two continuous variables, with the second variable given. So it was not a complete waste of time. This is the general solution for a variable Y linked to X by a formula x = u(y):

where f(x) is the probability density of X and g(y) is the probability density of Y. The formula does not work if u(x) is multivalued. Still, I think this formula should work under ordinary conditions. If there's any mistakes in this post, feel free to leave a comment.

Ajax snippets

2008-10-25T11:28:00.031-04:00

I decided to post a few snippets from my recent Ajax programming. There are quite a few snippets out there on the Web, but the one's I found were imperfect, so I thought I should post some tricks of my own.

Firstly, declare an xmlHttpRequest object and create it:

var xmlHttpRequest = false;
if (window.XMLHttpRequest)
xmlHttpRequest = new XMLHttpRequest();
else if (window.ActiveXObject)
xmlHttpRequest = new ActiveXObject('Microsoft.XMLHTTP');

Next, here's a nifty function that allows you to send POST commands:

// url = URL you are posting to
// data = data to be posted, e.g. 'variA=1&varB=2'
// action = pointer to a function that is executed
// when posting is complete; it must accept
// arguments: errorCode & response;
// errorCode will be 0 if no error
function ajaxPost(url, data, action) {
    xmlHttpRequest.open('POST', url, true);
    xmlHttpRequest.setRequestHeader('Content-Type', 'application/x-www-form-urlencoded');
    xmlHttpRequest.send(data);
    xmlHttpRequest.onreadystatechange = function() {
        if (xmlHttpRequest.readyState == 4) {
            if (xmlHttpRequest.status == 200) {
                action(0, xmlHttpRequest.responseText);
            } else {
                action(xmlHttpRequest.status, '');
            }
        }
    };
}

Now, the hard part - this is a piece of code that searches recursively throughout a <form /> element, so that all the data fields (e.g. <input />) are collected into the POST request:

// node = HTML element, usually <form />
function getFormData(node) {
    var data = '';
    switch (String(node.tagName).toLowerCase()) {
    case 'input':
        switch (String(node.type).toLowerCase()) {
        case 'checkbox':
            data += node.name + '=' + escape(node.checked ? node.value : '') + '&';
            break;
        case 'hidden':
            data += node.name + '=' + escape(node.value) + '&';
            break;
        case 'radio':
            if (node.checked)
                data += node.name + '=' + escape(node.value) + '&';
            break;
        case 'text':
            data += node.name + '=' + escape(node.value) + '&';
        }
        break;
    case 'select':
        data += node.name + '=' + escape(node.options[node.selectedIndex].value) + '&';
        break;
    case 'textarea':
        data += node.name + '=' + escape(node.value) + '&';
        break;
    default:
        for (var i = 0; i < node.childNodes.length; i++)
            if (node.childNodes[i].nodeType == 1)
                data += getFormData(node.childNodes[i]);
    }
    return data;
}

The hardest part was to actually prevent the infinite loop that kept happening as a result of this iteration. Later, I realized that the var in the for loop was essential for it to work - if only JavaScript had complained that i was undefined or something. Sigh.

And now, the sample code that actually uses these abstract functions:

// formId = id of the <form /> element
function submitForm(formId) {
    if (!xmlHttpRequest)
        return true;
    var formTag = document.getElementById(formId);
    ajaxPost(formTag.action, getFormData(formTag), showResponse);
    return false;
}

// display the response in a message box
function showResponse(errorCode, response) {
    alert(errorCode + ':' + response);
}

Simply place this function inside your onclick attribute of the "Submit" button in your form.

Thanks to these sources for teaching me basic Ajax (many of the snippets above are derived from what I found on these sites):

Feel free to comment, if I missed something or made a mistake.

problem-solving skills

2008-10-12T18:27:00.000-04:00

The following post pertains to most scientific word problems, i.e. physics, chemistry & math problems. It doesn't necessarily apply to humanities or other subjects. The information here is based on my own views and experiences. Science here refers to a generalized curriculum that also includes mathematics.

There is a thing that isn't taught frequently in schools: problem-solving skills. More often than not, people often understand the basic concepts that were taught during lectures/classes, but are unable to apply them to homework or test problems. Worse still, some students who couldn't understand a concept would be forced to "memorize" concepts, which doesn't work most of the time. Personally, I usually assume the responsibility of teaching how to understand concepts and work through problem to the instructor, but this is hardly true, mostly because of the lack of time and attention devoted to scientific curriculums. Unfortunately, this leads to more of a vicious cycle, because the lack of a solid scientific foundation in elementary school, middle school, and high school could only cause further problems upstream. And this is problem one reason why many students dislike science: to them, it's an exotic thing that they could never understand.

From the perspective of someone who knows science, I find in impossible to believe why people have such a difficult time with science. Neither do many of the science teachers. What they often do (and to my disappointment) is that they would try to teach things at a level that is beyond what the students are capable of. They often attempt to explain pure concepts and fail to establish links between what is being explained and what has already been explained. The most crucial link (as far as I believe) to understanding a concept is to link it do something that is already known. From a psychological perspective, this quite logical: a concept that is isolated - has not been linked to any other concepts - will be very difficult to remember. This is one reason why I'm not an advocate of using mnemonics. Many use mnemonics purely for fun and often do grasp the reason behind why things are. Of course, there are some things that do need blatant memorization, but in general, scientific topics often do not need them, because science is based on logic and empirical knowledge (however, there are things that are purely "conventional" [e.g. "7" colors of a rainbow, direction of a current, right-handedness of the 3D-Cartesian system, etc.] and students must know so.

In order for students to understand science, it would become necessary to show how problems should be tackled. One approach - which some instructors use - is to provide an "exhaustive" list of the ways in which a problem, based on some concept, could manifest itself in various different ways, and to teacher the students how those problems should be solved. An alternate approach is to provide a few examples of how problems are solved, and hope the students can extrapolate those skills. I personally find neither satisfying. The first approach is by no means exhaustive: there is an infinite variation in which problems could come, figuratively speaking, and this often requires the student to memorize unnecessary knowledge. The second approach expects the student to know how problem-solving skills can be extrapolated. But the problem is that some students may not even know how to solve a problem.

My suggestion is to actually teach the problem-solving skills in the most general way possible. And this is what this post will be about - the most general way (that I can think of) in which scientific problems can be solved. This makes it redundant to teach specific steps for solving each & every type of problem that may or may not be encountered, since a student can simply learn just the basic rules for problem-solving.

Clarify
The first step to any word problem is to strip the problem of useless information. In some sense, a word problem is really the convoluted version of something simple. Some types of information will be useful to solve one particular problem, while the same information may be useless in some other problem. So there's no general rule to determine which things to remove and which shouldn't be removed.

Other than removing redundant information, it is necessary to highlight important information, and - especially important - understand what the question is asking for.

Let's consider the following word problem:

A baseball falls from the rooftop in 5 seconds. Determine the height of the rooftop.

It's quite obvious that the falling object itself is not going to be useful here. So let's make that word problem a bit simpler:

object falls from rooftop;
time taken (t) = 5 s;
height (H) of rooftop = ?

I've removed some adjectives and verbs to make things especially clear (even though this problem itself might be pretty easy to understand for someone familiar with basic physics). Often, in science problems, numbers are quite important, although this is not necessarily always true, since some problem-writers tend to put in redundant numbers which aren't going to be used at all.

Sketch
When a problem has been simplified by removing redundant information, it becomes easier to sketch the problem. The usual way to do it is to start with a blank page, and start relating the information that you have read from the problem with knowledge and concepts learned during classes. Basically, try to construct a diagram of some sort (and don't be concerned about neatness) that describes the situation described in the problem. For example, in the problem discuss above, you might consider drawing an object falling from height = H to height = 0. This step is not absolutely necessary, but it will help you if you get stuck.

Divide & Conquer
When a problem is too big and contains too much information, it becomes necessary to convert it into smaller problems. This is how several equations can be chained together to find a single result using multiple variables. For example

A photon strikes an electron of a gaseous helium atom, causing the electron to be ejected. Given E_I(He) = 1520 kJ mol^-1, what is the wavelength of the photon?

Now this problem is actually quite involved. Let's start by clarifying the problem:

1 photon strikes 1 electron of 1 He_(g) atom;
electron ejected;
E_I(He) = 1520 kJ mol^-1;
photon wavelength (λ) = ?

So we are given ionization energy (E_I), and we are asked to find wavelength. Let's start by working backwards: how does one get the wavelength (as far as chemistry is concerned)? The equation that is usually used to find wavelength in chemistry problems is:
c = λ ν (c = speed of light, ν = frequency)
Which variables are known? c is known - no problem there. What is ν? What is the usual way of finding frequency (other than using the previous equation)? Which equation contains a frequency term? Here it is:
E = h ν (E = energy, h = Planck constant)
h is, again, a constant that can be found easily. But where does energy, E, come in? It seems that the problem has mentioned the word "energy" somewhere, but it's not in the right form: it's the ionization energy (of every mole of gaseous He). Did we ionize anything? Yes, we "ejected an electron" - that's ionization right there. How many moles of He did we ionize? One atom. How many moles is that? (These are a chain of questions that should be thought of while analyzing the problem, and don't have to be written down)

The relationship between atoms and moles is (to derive this, just look at the units of N_A, which is mol^-1, and compare that with the units of number of moles, which is mol; see how that cancels out so that the number of atoms has no units?):
(number of atoms) = (number of moles) × N_A
Since we have the number of atoms (just 1), and we know what N_A is, we can easily find the number of moles. With the number of moles at hand, we can use:
(ionization energy of n mol) = n mol × (ionization energy of each mol)
Again, this can simply be derived by looking at the units of ionization energy, which implies that we must multiply it by the number of moles to get rid of the mol^-1. Now, with the ionization energy of n mol (which in this case will be for 1 atom), we can equate this energy with the energy that we desperately needed for E = h ν. Now the problem is complete, we just need to plug in the numbers. This is a typical example of how a problem can lead to several smaller problems, and each individual problem must be dealt with separately

Algebra
Most of the time, one should not solve the problem without equations, especially for unfamiliar problems. Try to list every formula that might be related to the problem, and see which ones are applicable here (this is why when remembering formulas, do remember when they are applicable). For example, an object in free fall (the problem discussed above) will typically accelerate at a constant rate due to gravity (air resistance ignored). Therefore, the equations of motion for objects in free fall can be used here:
s = u t + 0.5 a t²
v = u + a t
v² = u² + 2 a s
In this problem, none of the variables are given directly. But some are given implicitly. For example, a = g = 9.81 m s^-2 (acceleration of gravity), while u = 0 m s^-1 (initial velocity) and t = 5 s (time taken). Hence, the first equation is most applicable because we have just one variable missing: s, which is the distance traveled by the falling object, i.e. the height of the rooftop. As you can see here, it is important to establish relationships between things that are already known (knowledge) and things that might vary from situation to situation (the problem). With sufficient practice, this will become very easy for known problems.

It is also important to realize that sometimes equations don't give the answer directly, or one may have to construct the equation using a set of known rules. For example:

The mean of 3 consecutive numbers is 5. What are these 3 numbers?

In this case, one should always start by constructing an equation in terms of unknown variables. Don't fear unknown variables. Without them, many complicated problems could go unsolved. So start by writing the equations in terms of them, and worry about finding them later.

In this problem, let's call the 3 consecutive numbers: a, b, and c. From the equation for mean:
(a + b + c) / 3 = 5
Because there are 3 different unknown variables, we need 3 non-equivalent equations (by that, I mean 3 equations that are not equivalent to each other). It's easy to construct a few more:
b = a + 1
c = b + 1
Now we have 3 equations. The next step would be to solve them, and this is why it is necessary to learn basic algebraic skills. (Be careful with equations, label the variables correctly: some variables may not be equal to another, so subscripts may be required to differentiate them.)

Skill
The process of solving problems is a skill that can only be acquired through practice. Therefore, it is necessary for a student to learn this skill from day one of science class. Over a sufficiently long period of time, a student should be capable of solving problems with ease. But this is by no means a short period of time. Thus, I would say that this skill is absolutely essential and should've been taught from the beginning. Once a student has grasped this skill even partially, practice and further practice will be able to allow the student to learn the skill even better (like a positive feedback loop). Somethings can only be acquired with hindsight - when a students learns a method of solving something from the instructor, hindsight and practice will be able to provide the foresight necessary to predict how a certain problem should be solved, without going through all these stages mentioned. At the optimal level, a students will be capable of solving problems without even thinking any of these steps. It will become a natural habit that always goes unnoticed.

addons for Firefox

2008-10-02T21:37:00.002-04:00

Okay, just a quick post. I've been using quite a few Firefox add-ons, and there are some I consider very useful.

These are my recommended add-ons (in alphabetical order):

AdBlock Plus - most of the time, I don't even notice this add-on. But I have to admit, the only reason why I didn't notice was that I didn't see any ads. I consider AdBlock to be a very useful extension, and the best thing is that you probably won't notice it.
Firebug - the most useful tool for analyzing webpages for any web developer. (If you aren't a web developer, then it may not be useful to you.) In general, you would rather look at the neatly generated HTML code in Firebug than to look at the HTML page source itself (which is usually messy), and it also provides tools to view the CSS style of each element. You can even dynamically change the webpage you are viewing with Firebug!
Foxmarks Bookmark Synchronizer - if you use bookmarks on various computers or OS's, then you might want this so that you can synchronizes your bookmarks across computers. Most of the time, it works pretty well at synchronizing, but from my experience, it is not a "perfect" solution (there are some weird "glitches" occasionally, especially if you don't know what you are doing). Still, it's really useful and definitely worth using.
FoxyProxy - this is really useful if you surf using proxies. If you use Tor often, and want Firefox to use Tor only when necessary, this can be a time-saver indeed. Once it knows your basic filters, it will automatically use the Tor proxy when you need it. If you want to turn it on temporarily, you can just click the icon on the right of the status bar. It certainly saves a lot of time. (If you don't use proxies, then this is not applicable to you.)
IE Tabs - this is my favorite way of viewing pages the require Internet Explorer. Instead of view IE in its own window, you just click and it creates a tab within Firefox that emulates IE. Again, a time-saver, and you don't even have to run Internet Explorer.

Note: This is not an ad of any kind (although my tone was a bit like that); I'm just suggesting add-ons that I personally consider useful.

error propagation

2008-09-18T21:48:00.001-04:00

Recently, I've been working on my physics lab reports. The main theoretical concerns are about error analysis. This means there's a lot of equations to mess around: specifically the propagation of errors.

The first time I learned about error propagation (under a different name) was at pre-college level high school (i.e. AS-Level). It sounded simply, and the basic equations were as follows (in summarized form):

Notice that:

is simply the fractional error of u, whatever u might be.

However, the above equations can be replaced with quadratures if the uncertainty is a standard error and the measurements are independent:

Here's the general formula that applies to any multivariable function f of a, b, c, etc:

Again, if quadratures are to be used (if uncertainties are standard errors and the variables are independent)

(Note: most of the above formulas are approximations)

electric field integral

2008-09-08T21:55:00.001-04:00

During my physics class, I had an encounter with a tough integral. I was trying to derive the electric field for an infinite line of charges, but got stuck because I couldn't integrate:
(y is a constant)
There are many sources about how the integral can be integrated, but none of them (as far as I have found) indicate how the final result was obtained. So here's one way of deriving the answer (credit: HallsofIvy at Physics Forums):

Okay, just a brief explanation:
In the 2^nd equation, substitute x = y tan θ and dx = y sec² θ
In the 4^th equation, simplify the equation with tan² θ + 1 = sec² θ
In the 8^th equation, simplify with:

E-potential / E-potential-energy

2008-09-05T17:28:00.001-04:00

Sigh, I haven't updated SciLearn for a while. Homework has been keeping me busy recently. Still, I decided to publish a short post about electrostatics.

Okay, today I encountered something that I never realized/thought of properly. What is the difference between electric potential and electric potential energy?

The main difference can be easily found by analyzing the units:

electric potential is a quantity in volts or - equivalently - joules per coulomb.
electric potential energy is energy, in joules.

The difference is just:

electric potential is electric potential energy divided by the charge of the test particle.

Ain't that simple?

You can draw a similar relationship between electric field (N C^-1) and electric force field (N) (since they are simply gradients of the electric potential and electric potential energy respectively).

Note: all of these also apply to gravitation.

differential table

2008-08-22T23:25:00.001-04:00

This is a table that lists everything in differentials, so it can be used for differentiation and integration at the same time.

I'm not sure if everyone can find this useful, since some might prefer non-differential forms because they are easier to understand and use - so I don't think this table would be suitable for calculus beginners.

Okay, here's what the symbols in my table means:

k is a constant;
f, g are functions of a variable t.

And here's the table (click the image if the equations get cropped):

You can tell me if this is useful or not.

trademark?

2008-08-16T20:16:00.002-04:00

Oops. While I don't think anyone uses 'SciLearn' as a blog name in its entirety, I just hope that no-one complains that I'm using it. Would you call that a trademark issue?

Changing the name of a blog won't be easy, even for a no-name blog that no-one knows. (This also means that the URL has to be changed, and that means: broken links.)

I just hope that I might come up with a catchier name than 'SciLearn' someday.

unspecified specs

2008-08-11T15:39:00.010-04:00

Recently I was looking all around the web for a good laptop to buy, so perhaps I should share some of the new knowledge I learned about laptop specifications.

There are tons of stuff that you should look out for in laptops, and it's hard to look at them all. So here are some basic specs to look out for. ("^" means the higher the better; "~" means the lower the better)

processor (a.k.a. CPU)

This is what determines basic performance of your computer, as in computational speed.

Factors to consider:
L2 cache (in MB)^
clock rate (in GHz)^

For normal uses, a laptop doesn't need an extreme high-end processor, unless you want to dedicate it to number-crunching and complex mathematical calculations. A moderate to fairly high speed CPU is good enough in most cases.

Typical brands: Intel, AMD.

graphics card

This determines how your computer will fare with heavy graphic-intensive applications, including 3D applications & games.

It's hard to determine the performance of graphics card by plainly looking at the specs. In general, the second digit is the one that determines speed, while the first digit is the generation of the graphics card. For detailed info, check this thread. Also, take note of the amount of dedicated graphics memory available (in MB)^. You can also use benchmarks as a guide, but remember that benchmarks only provide a rough comparison between graphics cards.

Typical brands: NVIDIA, ATI (AMD), Intel.

system memory

Factors to consider:
latency~
bandwidth^
size (MB)^

The minimum RAM nowadays is typically 512MB, so you should aim at something higher than that to achieve the best performance. Any addition of RAM, up to 2GB, will give a noticeable performance boost. Most laptops allow you to upgrade the RAM fairly easily. (Another detailed article)

hard drive

Factors to consider:
rotational speed (in rpm)^
size (in GB)^

The size of the hard driver mainly matters if you want to store a lot of stuff. However, the real bottleneck here is the rotational speed of the hard drive. Typical speeds include 5400rpm and 7200rpm. The reason is simple: swap memory uses the hard drive, which needs to be fast enough in order to serve its purpose. Otherwise, you may encounter considerable lag in performance.

These are the main and often most important things to consider when getting a laptop. Of course, there are plenty of other things that should be taken into consideration:

screen size & quality
CD/DVD and other optical media reader/writer
Ethernet & wireless cards
I/O systems (i.e. USB plugs, SD memory readers, FireWire, etc.)
built-in microphone, speaker & webcam

In all its glory

2008-07-27T21:51:00.010-04:00

While on a plane trip, I saw a strange phenomenon:

See it? Let's make that a little clearer by adding contrast.

Cool, ain't it? First, I thought it was just a reflection of the window on the other side of the plane, but then I guess it wasn't, since there wasn't a window open. The faint apparition-like halo may have been just an illusion. Maybe I was gazing too much at the window. Maybe not...

After some brief searching, I found the best explanation for it: Glory. It's a "glory", a refractive effect caused by the sun shining onto the clouds.

Codejamming

2008-07-20T12:14:00.003-04:00

I tried the Codejam Qualification Round a few days ago, and it feels pretty hard for my level. I managed to score 55/75, and the 20 points lost was because of a tiny error in my program for question C (at least that's what I believe should be the problem; I tried the new, fixed program on a test data and this time it worked).

If you want to see the questions, please go to Google Codejam. I can offer the solution for any readers (see note at the very bottom).

A. Saving the Universe
This one should've been really easy, but unfortunately I screwed a lot things up, and ended up submitted several incorrect entries before getting the right answer.

Here's how I solved this problem:
Go through every query, from beginning to end, and make the best switch that minimizes the total number of switches. Make sure a counter is used to keep track of how many switches are made.

The real question here is: what constitutes a "best switch"? Well, after some thought, I realized that the best switch was the switch that maximizes the number of queries processed before changing to another search engine. So all I had to do was to try switching to each search engine and check how many queries it can process before it has to switch to another search engine. That was easy: just a simple maximization problem.

B. Train Timetable
While this is supposed to be a fairly easy problem, my solution kinda overcomplicated things, and it took me a whole day to figure out where the "bug" was.

Before I go onto the solution, I would like to note that a simple way to incorporate the "turnaround time", T, into the solution is to just assume that each train arrives T minutes later than what the schedule says (or equivalently, each train needs to depart T minutes earlier than what the schedule says).

My solution was to simply simulate all the trains as they go from station A & B and back. At every critical moment in time (explained later), the total number of trains that leave a station is counted. If somehow, the number of trains left at some station X is negative, then that means there's a deficiency in the number of trains. This deficiency is then added to the "required number of trains at station X" (this is what the whole question is asking for!) and the number of trains left at the station X is reset to zero. At the end of the day (when all the critical moments are processed/simulated), the "required number of trains at station X" is then output.

Note that I use the term "critical" to differentiate between moments of time that are uninteresting (e.g. when a train is mid-way/at a station, and nothing is happening) and those that are worthwhile to process (e.g. when a train departs or arrives). The simulator only needs to simulate critical moments in time.

C. Fly Swatter
This one was actually fairly easy, until I realized that I forgot to make a certain check to process the area. Okay, first things first.

This question simply asks you to find the ratio of the fly swatter area to a circular area of radius R... Oh wait, no: it says the fly is a sphere (of radius f), not a point! This might make things confusing. Since the fly is a sphere and not a point, it actually makes the fly easier to hit.

After some thought, I realized that an equivalent situation is when the area of the fly swatter has been extended by a distance of f, yet the fly is point-sized (positioned at the center of the spherical fly).

Now finding the fly swatter area is not easy. Instead of finding the area that is covered by the fly swatter, I decided to find the area of the holes in the fly swatter (which are either just squares or squares that are cut by circular arcs).

The side-length of each square is nearly the same side-length as the ones drawn in the Google Codejam diagram, but it must be subtracted by 2f. In order to find the areas of the squares that aren't perfect squares but cut by circular arcs (I call them "pseudo-squares"), you should set up a coordinate system and use integration. Now don't just do numeric integration (it'll take forever to get 6 decimal places), because an integral like:

can actually be simplified so that it's in terms of square roots and arcsines, which is less computationally intensive. In order to simplify calculations, don't bother calculating the area of the squares of the other quadrants of the fly swatter, since one quadrant is enough (it is symmetric, as the question states). Beware of cases when the width or height of the squares (or "pseudo-squares") is negative, which is often as a result of subtracting the actual height or width of the squares (or "pseudo-squares") by 2f. In such a case, make sure you check for this situation, and treat the square's area as zero.

After that, the rest is pure logic and iteration. Just be careful with the signs and how you get all those coordinates, and the rest should be pretty easy.

Feel free to ask me to email a copy of my code (in Python) for any of these 3 questions. (The code for question C has been corrected already, by the way.) I'm fairly confident that they are correct, but you can verify them with the Google Codejam Qualification Round practice questions just to be sure. You can put requests in the comments.

Getting oriented with Ubuntu (for Windows users)

2008-07-10T05:15:00.005-04:00

Okay, just for the record here, I'm also a beginner, just-migrated-from-Windows kinda person. But still I think I should share some of my own thoughts and experience about Ubuntu - from a newbie's perspective.

Installation
First things first: Ubuntu installation. This is the easiest part actually: just follow the instructions. One of the things that was unclear for me (and just to make sure I didn't make any mistakes as a newbie) was the Linux partitioning process. You see, a Windows-adapted user would think that one partition is enough (and I thought NTFS was good enough), but it's not!

(For a detailed review of Ubuntu partitioning, just go to this neat article.) Ubuntu needs a minimum of 2 partitions (1 would still work, but not recommended).

One is the "/" partition, which is the root of the folder tree system. (Kinda like your ordinary "C:" drive, but not exactly the same.) This one should be moderately small, >5GB minimum, I think. (This drive is a must.)
The other is the swap drive, which is basically a partition used specifically as a swap memory (i.e. a "page file" as Windows calls it). This one is somewhat small, ~2GB maybe. (I chose 5GB, just in case I needed more.)
You can create an additional "/home" drive to store all your data files. If you choose to do so, just fill the remainder of your free space for this drive. (I did so myself.) The fact that the "/home" directory looks as if it's a subdirectory of the "/" root directory doesn't matter, since physically they are separate partitions.

After you understand things become easy. You can make the swap drive and "/home" drive as "logical drives" instead of "primary", if you want.

You might wonder if Ubuntu would support all your drivers. In my situation, things went fairly smoothly (referring to drivers). The only thing I had to do was to force the nVidia driver, which wasn't open-source, to be enabled (it's under System > Administration > Hardware Drivers). While it's true some things won't work here, like the QuickPlay buttons (rejoyce! that pesky QuickPlay won't work in Ubuntu!), or the Fingerprint Sensor (frankly, it started out useful, then became really annoying, because my arm sometimes touches it while typing, and hence activating the sensor unintentionally). Everything else seems to work: 3D acceleration, touchpad, mute and volume keys... Strangely easy.

Getting used to the interface
This part requires lot's and lot's of practice. Just to get people understand the basic interface, I'll explain this briefly. Note that "GNOME" is a word used to describe the kind of graphics Linux provides. Aside from the colorful GNOME interface, there's also what is called "KDE", although I've never seen that before (or I've seen it somewhere but didn't know).

The "bar" on top is the place where you:

Applications: load a program (or game, utility, accessory).
Places: open the File Browser to view files and folders/directories. (This is equivalent to opening the Explorer in Windows.) It also has some Networking stuff in there too.
System: manage settings and configuration stuff (i.e. "Control Panel" in the form of a menu). Most of them are fairly straightforward and user-friendly.
There should be some icons right after the three menu items, and you can drag and place your favorite icons here (kinda like a "Quick Launch").
On the far right, there's a panel that looks like the Windows "Notification Area". It has the clock and some miscellaneous icons.

Okay, then there's the bottom "bar", which is a bit like the "Taskbar". This "panel", as it is technically called, allows you to see all the currently loaded programs (within the same workspace, which I'll explain next). Also, you are allowed to divide your desktop into several workspaces (default is 2, one left and one right, I think). The workspaces are just to help organize stuff. The tiny workspace icon on the far right (but to the left of the Trash, i.e. "Recycle Bin") allows you to preview with a tiny thumbnail-like icon. You can switch between workspaces by using Ctrl+Alt+Left, Right, Up or Down (assuming you never modified the default keyboard shortcuts), or by focusing the desktop and scroll your mouse wheel.

Okay, aside from the interface difference, I think the rest of the interface are fairly easy to understand, like the windows etc.

Installing programs
This is going to be an essential, yet simple skill. It's not like Windows where you buy a disc or download a binary EXE installer file to install applications. All you need to know is that nearly all of the designed-for-Linux programs (free, open-source ones, of course) can be installed by simply visiting System > Administration > Synaptic Package Manager.

I think this program is specially designed for beginnerz who don't know a thing about the Linux file system or the command line (Terminal). So let's see how this thing works. First load it, then you'll see a list of weird-looking names. Those are the programs. Suppose you want to install Blender, then you just search for "blender", place a check-mark on the "blender" program that you found, and click "Apply" to install it. Note that you can't run all these 3 programs at the same time without having them conflicting:

Update Manager
Synaptic Package Manager
Add/Remove... (which is an even more beginner version of the Synaptic Package Manager, for installing or removing programs).

If you ever see something like:

sudo apt-get install [some-program-name]

then you should know that you are installing a package from the command line.
(Note: sudo is a command that gives you "root" permission [i.e. "Admininistrator" permissions])

There are slightly more complex ways of installing programs that you'll eventually have to learn, but don't be overwhelmed. The easiest way to solve them is to look for answers on the Web.

Using Ubuntu
I'd say the Ubuntu interface is really intuitive, so I don't think there would be too much trouble doing stuff. You might have to wander a little on the first few days, since you probably don't know where things are, but over time you would get used to things. There's the same windows control and similar keyboard shortcuts (mostly), so I think the transition would be smooth.

Just a reminder, Ubuntu's "Explorer" equivalent is called Nautilus (file system browser) and you should be able to access it simply from the Places menu (just click one of those items). The equivalent "Internet Explorer" is simply Mozilla Firefox.

Whining for wine
Ignoring the pun in the title, you should probably be aware of a program called Wine, since it can allow many kinds of Windows programs to run on Linux. While I don't think it's perfect, it's worth a shot if you really want an important Windows program to run on your Ubuntu. In most cases, however, you should settle for a free, open-source version of a program rather than to force a Windows program to run on Ubuntu, if possible.

Dragging energy

2008-07-04T04:29:00.023-04:00

If anyone noticed an error in the equations, feel free to contact me or report it in the comments.

Well, I didn't intend to turn this into a SciLearn post, but seeing as how I actually did a lot of working to get the answer, I might as well share the working and conclusion with everyone else. This is the question I was asking (I asked myself this question when considering whether cars burn more fuel when accelerating slowly or when accelerating rapidly):

Object A accelerates uniformly with positive acceleration a_a up to a speed V, traveling a distance of d_a.

An identical object B accelerates uniformly with positive acceleration a_b (such that a_a < a_b) up to the same maximum speed of V (part 1), and continues to travel at the same speed until the same total distance of d_a is reached (part 2).

Which object requires greater energy with (1) no drag forces, (2) a linear drag force, or (3) a quadratic drag force?

(By the way, I've finally resorted to using LaTeX for rendering equations. [ credits ])

Answer for (1)
The answer for (1) is simple and obvious: Both require the same energy, i.e. the kinetic energy at velocity. So for both objects, E = m V² / 2 where E is energy & m is the mass of each object.

Answer for (2)
(This is going to turn out to be a really long post.) The answer for 2 is a bit complicated. Start by considering object A:

Here, E_dragA is the energy needed to overcome drag (not work done by drag, which is why there's a negative sign) and D_A is the drag force.

Since drag is assumed linear:

where v is the speed of object A and k is a constant. v is a function of x, however, so it must be also substituted.

According to the uniform acceleration equation v² = u² + 2 a s:

Now we can put these equations back into our original drag energy equation.

Substitute the variables to find the drag energy:

This is how much energy object A requires to overcome drag.

For object B, the formula is the same, except the variables are slightly different:

Here, d_b is the distance traveled during part 1 of the motion.

For part 2 (during which object B also travels at constant speed until the total distance traveled is the same as that of object A), we need additional energy to mitigate the constant drag force that occurs at maximum speed V, until the total distance becomes d₁. Therefore, during this period, the object travels a distance of (d_a - d_b).

Using "energy = force × distance" for a constant drag force D over a distance of (d_a - d_b) gives:

(The negative sign is, again, because we are calculating energy required to mitigate drag; anyway, that's not important here.)

Applying the same v² = u² + 2 a s for object A and B (part 1):

The total drag energy for object B is therefore:

Now that's a weird equation. At least it looks right. If a_a = a_b then obviously E_dragA = E_dragB, which makes sense. What if a_a < a_b, as specified by the question? Well, from the equation here, it's obvious that E_dragA < E_dragB. So this is our answer to (2):

Object B requires more energy than object A.

You can easily find out how much more does it require by using the simplified equation above. (You might be urged to say that the conclusion is "obvious", but I really wanted to confirm this using math. After all I can't just say obvious and put a close to this question, which seems very interesting.)

Note: this equation cannot be used for a_a > a_b. If so, object B would have to go backward for part 2 of the motion, in order to negate the extra distance object B traveled as it slowly accelerated to V.

Answer for (3)
Alright, now onto question (3)! Okay, we are still using the same equations, except now we use a quadratic relationship between drag and speed:

Again, k stands for some constant.

For object A, start with the integral for E_dragA:

For object B, use the same procedure as for question (2):

Once again, the same conclusion can be drawn, which also answers question (3):

Object B requires more energy than object A.

In reality, drag works in a very complex way, but for a simplified situation, it seems that cars do burn more fuel when accelerating faster.

Disappointingly, I realized that, upon closer examination of the sketched graphs shown above, I realized that it was surprisingly obvious that object B would definitely require more energy than object A, but, at least, we now have some equations that actually describe how much more energy object B would require compared to object A.

Inscribed Pentagons

2008-06-30T06:30:00.000-04:00

One of the questions I was thinking when I was bored and looking at tiles for no reason was:

Is it possible to draw a rectangle that goes through every point of a pentagon?

For a regular pentagon, the answer is a definite yes. For any other pentagons, I wasn't so sure, but I still tried to draw one. Here's how I did it:

However, apparently it cannot be done for any kind of pentagon. Many can be done, but a lot of twisted abberations of pentagons may not be converted to a rectangle, unless you actually leave the drawing at stage 3 (shown in diagram above) and actually call those four red lines a "rectangle".

Still, it was fun to think of such a question, although I'm not sure if it's practical. By the way, do you notice that there will always be at least one side of the pentagon coinciding with a side of the rectangle?

Transformations

2008-06-25T06:06:00.005-04:00

Matrix transformations is a clean and somewhat simple way of performing simple transformations. (Don't get thrown off by the word "matrix" because it has nothing to do with movies here.)

I won't go into detail about Matrices, since they are basic high school math. Instead I'm going to talk about the important practical aspects relevant in geometry and computing. The kinds of transformation that I'm referring to here are called "affine" transformations, according to Wikipedia (which I realized just now). Suppose you have a simple rectangle. A matrix can be used to transform the rectangle by multiplying onto each and every point of the rectangle. That is, suppose the rectangle has four points A, B, C & D (all of which are vectors), then a matrix M can be used to transform onto a new rectangle A', B', C' & D' (notice the prime notation) by this formula:

A' = M A (notice that this is M times A)

B' = M B

C' = M C

D' = M D

This is a straightforward exercise for computers, as long as they are optimized for matrix multiplication (like some newer graphics cards are). Matrix don't just transform rectangles, though. They can applied to any set of points (in this example there were four of them).

There's another way to transform, which is used more often in computing. They are necessary because normal 2x2 matrices cannot perform "translation" upon 2D points. 3x3 matrices are used instead. However, 3x3 matrices can't multiply 1x2 column vectors, so we use a 1x3 column vector instead, with the first two values the same as the 1x2 column vector and the third value being 1. Now we can also translate vectors.

The diagram above shows some sample transformations, how transformation works and how 3x3 matrices can also transform. Remember that transformation is simply "multiplication" of a matrix with a column vector, and that for 3x3 matrices. Also notice that transformation matrices are really a combination of the transformed i-vector and transformed j-vector.

Apparently, it was really easy to use these matrices for transformations in my MJS Analyzer program. They would certain save a lot of trouble for me. However, note that computer matrix transformations are not exactly alike mathematical ones, since they use row vectors instead of column vectors, and thus, during multiplication, the matrix is placed after the vector instead of before. This can lead to some confusion, and the matrix used might look slightly different due to this. (For example, the matrix might be diagonally inverted, i.e., rows become columns and vice versa.)

Here's a tip that might be useful (although I have not proven the idea, I think it should be valid):

These two transformations are in fact equivalent:
1. Scale by factor N from center (a, b).
and
1. Translate by (-a, -b).
2. Scale by factor N from center (0, 0).
3. Translate by (a, b).
I found this useful since the .NET System.Drawing.Drawing2D.Matrix doesn't provide a scaling from center (a, b). Instead I had to use the second equivalent method since it only provided a scaling from origin.

AppData

2008-06-02T23:39:00.006-04:00

When I first got Vista, it took me a little while to adjust to it. Compared to Windows XP, there were quite a few changes to the directory system. (Note: the drive letters are intentionally left out; so \MyFolder should mean C:\MyFolder if your system is on drive C:)

For example, the default user directory in WinXP is normally \Documents and Settings\[user name]. Now, in Vista, it has been changed to:
\Users\[user name]
which is actually a lot simpler than it used to be. I never understood why a long folder name like "Documents and Settings" should be used anyway.

In WinXP, the personal files folder is called "My Documents". In Vista, it is called "Documents", perhaps for simplicity. This means that the new path is:
\Users\[user name]\Documents
The My Pictures, My Music, and My Videos folders have all been trasferred out of the Documents folder, straight into the default user directory, and they are now located at:
\Users\[user name]\Pictures
\Users\[user name]\Music
\Users\[user name]\Videos
Personally, I think it's a good change, since it makes things a lot simpler (and no more "My" words, which can be considered redundant).

The Favorites folder is still where it should be:
\Users\[user name]\Favorites
although I rarely use this folder at all since I'm using Firefox. (Maybe they should add a "Bookmarks" folder, but I doubt that'll happen.)
Same goes for the Desktop folder:
\Users\[user name]\Desktop

There are new folders as well, such as:
\Users\[user name]\Contacts (I'm not sure if this is new, maybe it was there in XP)
\Users\[user name]\Links ("Favorite Links" in the left sidebar of the Vista explorer)
\Users\[user name]\Saved Games (Stores saved Windows games)
\Users\[user name]\Searches (Stores searches)
Although I don't quite remember the last time I used any them.

Now for the hidden folders. In WinXP, I often had to tweak stuff in the \Documents and Settings\[user name]\Application Data or \Documents and Settings\[user name]\Local Settings folders, but I couldn't find them when I first got Vista. So here's where they are found now:

For \Documents and Settings\All Users\Application Data,
Go to: \ProgramData

For \Documents and Settings\[user name]\Application Data,
Go to: \Users\[user name]\AppData\Roaming

For \Documents and Settings\[user name]\Local Settings\Application Data,
Go to: \Users\[user name]\AppData\Local

There are some subtleties in this direct one-to-one mapping system I'm presenting here, but it'll suffice for those who are new to the Vista directory system. (If I made any mistakes, feel free to correct me.)

Anyone noticed that there are hidden, unopenable folders in the default user directory (i.e. \Users\[user name]) named "My Documents", "My Music", "My Pictures", etc.?

True & false

2008-05-24T23:06:00.004-04:00

"Person A says B is telling the truth; person B says C is telling a lie; person C says A is..."

I've seen a lot of questions like these. Often the wording can be so awkward that it confuses me, but eventually I realized that this is not only a logic problem, it can be converted into a simple algebraic problem. So I decided to share this little technique that I use to work out these problems.

We start by defining:
True = +1
False = -1

You might wonder why I chose the numbers this way and not the other way around. Don't worry, it'll be obvious in a second. Now let's figure out how a statement can be distorted by a "liar".

Suppose we know that person D, a "liar", has secretly taken a cookie. If we ask D, what would he say? He would say he has not taken a cookie (or, if he's absurd liar, he might say he has taken two cookies, but that's a more complicated situation that we won't consider). Let's define a variable called "IsCookieTaken" and set its value to "True". Now here's the critical idea: when a person lies (in a simple way, ignoring any complications), the variable, "IsCookieTaken" becomes "False", i.e. the inverse of the actual value "True".

Apparently, we can classify any Boolean response into a "True" value and a "False" value (by Boolean, I mean questions that have only two answers, "Yes" or "No", "True" or "False", Lying or Not Lying, Cookie Taken or Cookie Not Taken, etc.).

So let's define a variable called "d" whose value stands for whether person D is lying or not. If D is lying, we give the variable "d" a value of "False", or -1. If D is telling the truth, we give "d" a value of "True", or +1. (Assume we don't know if D is a liar.) What if D says to you, "I'm telling the truth"?

Now here's the tricky part: we want an algebraic expression that describes his statement "I'm telling the truth". The operator that is crucial here is the multiplication operator. Compare the following (X is just some variable):

Suppose X = -1, then a liar would say X = +1.
Suppose X = -1, then -1 × X = +1.

Notice statement 1 and 2 have the same result "+1", and notice how "a liar would say X" seems to correspond to "-1 × X" in the two sentences. Now look at next two sentences:

Suppose X = -1, then a truth-teller would say X = -1.
Suppose X = -1, then +1 × X = -1.

Now notice how "a truth-teller would say X" seems to correspond to "-1 * X".

If someone tells the truth about X, then the "displayed" value of X is the same. If someone tells a lie about X, then the "displayed" value of X is the opposite. By "displayed" I mean the value of X that can be directly quoted from the person's speech. Here's an example:

A liar says, "X = +1"["displayed" value],
then you would guess that X is actually -1[true value].
A truth-teller says, "X = -1"["displayed" value],
then you would guess that X is in fact -1[true value].

Now here's the harder-to-grasp part. What if we don't know if the person (say, person D) is lying or not? Well, we use the variable "d" that we defined before. Recall d = +1 for a truth-teller D, while d = -1 for a liar D.

D said, "I'm telling the truth". Now let's rephrase this into: D said, "d = +1". The rephrasing is exactly equivalent to the "I'm telling the truth" phrase, since d = +1 means that D is a truth-teller, but the quotation marks stress the fact that we do not really know that d = +1, but rather D said so (i.e. +1 is the displayed value of D, not the actual value). In other words, D may have "modified" the true value of D, resulting in the "displayed" value. The "modification" process can be considered as multiplication. Now we can form another algebraic expression for it:

d × d = +1

The initial "d ×" part stands for the modifier (i.e. the speaker, modifying the truth), while the second "d" part stands for the variable that is being modified.

Simplify the expression, and you get d² = +1. This means there are two solutions for d, +1 and -1. That is, D could be telling the truth, or he could be a liar, and one cannot determine which without additional information.

Sounds strange huh? But it D really says, "I'm telling the truth", he could be telling the truth about himself, but he could also be lying about himself. We don't know. But the algebraic way allowed us to get the answer mathematically.

Now suppose person E says, "I'm telling a lie." This time, the equation is e × e = -1 accordingly, and there is no real number solution for e. What does this mean? Well, it means what E said was a logical fallacy, and would result in contradictions. If E is telling the truth, then E can't say "I'm telling a lie." If E is lying, then E can't say "I'm telling a lie," since this would mean that E is saying the truth.

However, there are more complicated situations. Suppose:

Person A says, "B would say I'm telling the truth."
Person B says, "A would say A is telling the truth."
Only one of them is telling the truth, and their other is a liar.

Now isn't this confusing? Let's simplify these two statements into:

A says [B says (A is truth-teller)]
B says [A says (A is truth-teller)]
A is opposite of B

Apparently, there are two layers of "modification" instead of the usual one layer. Again, we convert this into algebraic form using variables "a" and "b" as well as multiplication.

a × [b × (a)] = 1
a × [b × (a)] = 1
a = -b (This statement implies that if one is negative then the other is positive.)

Simplify the equations to get:

a² b = 1
a² b = 1
a = -b

Apparently, equation 1 and 2 are the same, but with two equations remaining, we should still be able find a and b.

a² b = 1
a² b / a² = 1 / a²
b = 1 / 1 (Since a is either -1 or +1, a² must be +1.)
b = +1
a = -b = -1

So B was telling the truth, while A was lying, and without having to go through all the hassles and confusion, the algebraic method really makes solving similar problems easier.

Really all this is just a simplified version of Boolean algebra. There's even a whole article on this, but with a strange name (it's a little too specific, but then again, I don't even know what the real name of this kind of logic puzzle is).

There are lot's of questions like these, but this "simplified-Boolean" method does have limits. For example: of two people A & B, A says "Either I am a liar or B is a truth-teller." You can use "trial & error" for this question. (Answers will still be posted here.) A formal method to solve this question can be found here.

Base 64

2008-05-19T01:22:00.005-04:00

Apparently there's this really neat way of transferring information that I never even noticed: base-64.

Firstly, there's the great binary: 0 and 1.
Then there's the octal: 0 ~ 7.
And who could forget the decimal: 0 ~ 9.
Last but not least there's the hexadecimal: 0 ~ 9, A ~ F.

But now, the newcomer is base-64: A~Z, a~z, 0~9, +, /.
Apparently, a few days before I even saw this article, I had noticed that:
"with all the possible letters, capital and lowercase, and all the numbers, there are only 62 characters, so I need 2 more to make a perfect 64."

So now I see this come true (long before I even thought of this)... Anyway, the last two characters are merely by convention (MIME convention, to be exact). Now, I can, theoretically, encode any array of bytes into a string of keyboard-inputable characters. (Using characters like "âéïõù" simply won't do: most of us don't have those on our keyboards so they are hard to type.)

This is a really neat idea, except for one thing: one byte is 8-bits; one base-64 number is 6-bits. So there is the possibility of "left-over" bits at the end. No problem: this is handled by the "=" character.

For a simple string in which every character is a byte, each 3 bytes (3 × 8-bits = 24-bits) can be converted into 4 base-64 numbers (4 × 6-bits = 24-bits). Thus, there is the possibility of one or two bytes left over at the end of the string, unconverted. What happens now is that the remaining byte(s) required to cover three full bytes is filled in by a padding character, usually a 0x00 character. For example, suppose that one byte with a value of 0x20 remains after all the byte-triplets are converted. Then, two extra 0x00 bytes are appended, making the last triplet (0x20, 0x00, 0x00). This is then converted into base-64, as normal, but then two "=" characters are appended to indicate that two blank bytes are added, so that these bytes are removed when the string is decoded back into bytes. If, instead, two bytes remain, then one padding character is added and one "=" character is added to the end of the converted string.

Alright, that's my brief introduction (really brief) to base-64. For detailed info, see the Wikipedia article.

Does Python have an easy-to-use way of encoding a string into base-64 in the built-in modules?