JetCracker

Life-time learner's blog

Category Archives: References

Constrained Cubic Spline Interpolation in Java

Representation of numeric data is a very common problem. On PC we usually use different data visualisation software from Microsoft Excel or OpenOffice Calc to more advanced utilities for charting, such as QtPlot or Origin. These apps are designed for processing of data and you can easily draw a printable scatter plot or a pie chart. But what if you need to draw a plot in your own application?

Example of charts in CardioMood

There are plenty of libraries that can draw different kinds of charts. To draw charts in the web, you might use Google Charts API, or jQuery Flot for example. In my Android app, I use GraphView and ShinobiCharts.

Spline overshoot example

Line charts look nice when they are smooth. The most popular way to make your chart look smooth is to apply a cubic spline interpolation. This type of interpolation is very common and you have it already implemented in many open source mathematic libraries. However a simple cubic spline has a few flaws.

The result function is smooth (it is actually very smooth – twice continuously differentiable), but it tends to overshoot, especially in places where you don’t expect. This is illustrated in the picture above. When we draw a line chart, we usually have some knowledge about the process we are trying to visualise. For instance, the resulting function must be monotonic, or the function value should never be negative. If this information is critical, we must use more advanced interpolation algorithms.

If the function is monotonic, in Android you can just use MonotoneCubicSpline:

import android.util.Spline;

float x[] = ...
float y[[] = ...
Spline f = Spline.createMonotoneCubicSpline(x, y);

// this will evaluate y0 = f(x0)
float y0 = f.interpolate(x0);

If we want to avoid overshoot for an arbitrary function, we should find some other interpolation algorithm. One of the methods is called Constrained Cubic Spline Interpolation. It was proposed by CJC Kruger in his article: http://www.korf.co.uk/spline.pdf

The algorithms is based on a classic cubic spline algorithm. The key step in it is the calculation of the slope (first derivative) at each point. Intuitively, the slope will be between the slopes of the adjacent straight lines (can be a mean value of the two slopes), but it also should approach zero if the slope of either line approaches zero.

Unfortunately, I couldn’t find an implementation of the algorithm in Java. That’s why I decided to implement Constrained Spline for my project.

I use Apache Commons Math library. To make the interpolation compatible with my project, I’ve overridden UnivariateInterpolator class. Here is a full code of my implementation.

import org.apache.commons.math3.analysis.interpolation.UnivariateInterpolator;
import org.apache.commons.math3.analysis.polynomials.PolynomialFunction;
import org.apache.commons.math3.analysis.polynomials.PolynomialSplineFunction;
import org.apache.commons.math3.exception.DimensionMismatchException;
import org.apache.commons.math3.exception.NonMonotonicSequenceException;
import org.apache.commons.math3.exception.NumberIsTooSmallException;
import org.apache.commons.math3.exception.util.LocalizedFormats;
import org.apache.commons.math3.util.MathArrays;

/**
 * Constrained Spline Interpolation algorithm (CJC Kruger).
 * Source: http://www.korf.co.uk/spline.pdf
 *
 * Created by Anton Danshin on 24/12/14.
 */
public class ConstrainedSplineInterpolator implements UnivariateInterpolator {

    @Override
    public PolynomialSplineFunction interpolate(double x[], double y[])
            throws DimensionMismatchException, NumberIsTooSmallException, NonMonotonicSequenceException
    {
        if (x.length != y.length) {
            throw new DimensionMismatchException(x.length, y.length);
        }

        if (x.length < 3) {
            throw new NumberIsTooSmallException(LocalizedFormats.NUMBER_OF_POINTS,
                    x.length, 3, true);
        }

        // Number of intervals.  The number of data points is n + 1.
        final int n = x.length - 1;

        MathArrays.checkOrder(x);

        // Differences between knot points
        final double dx[] = new double[n];
        final double dy[] = new double[n];
        for (int i = 0; i < n; i++) {
            dx[i] = x[i + 1] - x[i];
            dy[i] = y[i + 1] - y[i];
        }

        final double f1[] = new double[n+1]; // F'(x[i])
        for (int i=1; i<n; i++) {
            double slope = dy[i-1]*dy[i];
            if (slope > 0d) {
                // doesn't change sign
                f1[i] = 2d / (dx[i]/dy[i] + dx[i-1]/dy[i-1]);
            } else if (slope <= 0d) {
                // changes sign
                f1[i] = 0d;
            }
        }
        f1[0] = 3d * dy[0] / (2d * (dx[0])) - f1[1]/2d;
        f1[n] = 3d * dy[n-1] / (2d * (dx[n-1])) - f1[n-1]/2d;

        // cubic spline coefficients -- a contains constants, b is linear, c quadratic, d is cubic
        final double a[] = new double[n+1];
        final double b[] = new double[n+1];
        final double c[] = new double[n+1];
        final double d[] = new double[n+1];

        for (int i = 1; i <= n; i++) {
            final double f2a = - 2d * (f1[i] + 2 * f1[i-1]) / dx[i-1] + 6d * dy[i-1] / (dx[i-1]*dx[i-1]);
            final double f2b = 2d * (2d * f1[i] + f1[i-1]) / dx[i-1] - 6d * dy[i-1] / (dx[i-1]*dx[i-1]);
            d[i] = (f2b - f2a) / (6d * dx[i-1]);
            c[i] = (x[i] * f2a - x[i-1] * f2b) / (2d * dx[i-1]);
            b[i] = (dy[i-1] -
                    c[i] * (x[i]*x[i] - x[i-1]*x[i-1]) -
                    d[i] * (x[i]*x[i]*x[i] - x[i-1]*x[i-1]*x[i-1])
            ) / dx[i-1];
            a[i] = y[i-1] - b[i]*x[i-1] - c[i]*x[i-1]*x[i-1] - d[i]*x[i-1]*x[i-1]*x[i-1];
        }

        final PolynomialFunction polynomials[] = new PolynomialFunction[n];
        final double coefficients[] = new double[4];
        for (int i = 1; i <= n; i++) {
            coefficients[0] = a[i];
            coefficients[1] = b[i];
            coefficients[2] = c[i];
            coefficients[3] = d[i];
            final double x0 = x[i-1];
            polynomials[i-1] = new PolynomialFunction(coefficients) {
                @Override
                public double value(double x) {
                    // bypass the standard Apache Commons behavior
                    return super.value(x + x0);
                }
            };
        }

        return new PolynomialSplineFunction(x, polynomials);
    }

} 

Feel free to use this in your own code! 🙂

Advertisements

EnglishSmacks – Real life English words and phrases

English Smacks logoThe-English-Patient.Com – a ground-breaking service for learning English – has recently released a preview of its brand new service: EnglishSmacks!

The app tests your English language skills! Just listen to the phrases and fill in the gaps typing the words missing in the transcript.

There are 5 levels of difficulty. Phrases are taken from world news (CNN, BBC), science movies, pop music etc. I am sure that you will enjoy gathering “tambourines”. Good luck!

Download EnglishSmacks from Google Play!

EnglisSmacks-sceenshotEnglishSmacks-screenshot2

Key features

  • Huge base of phrases
  • Daily updates of exercises
  • Reliable sources (CNN, BBC, movies)
  • Awesome phrases from real life situations

Feel free to download, rate and review the app!

TagsCool – Tag your photos online

TagsCool – Tag your photos online

http://www.TagsCool.com – Upload your photos, tag them and share!!!

You can also use it to store your school notes!

www.TagsCool.com

Demo: http://www.youtube.com/watch?v=4OC5kun9v9Y

[Java] Worker thread – thread-safe processing items one by one

Often we face the problem of online collecting and handling some data, abtained from various external systems and devices. In some cases it is more convenient to execute the processing code in a different thread. Here is how I usually solve this problem.

Assume the data are divided into chunks which are obtained one by one. The following class contains all necessary logic to process these chunks (*** updated according to the improvements suggested by Valeriy Ovchinnikov).

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.TimeUnit;

public abstract class WorkerThread<T> extends Thread {

    public static final long TIMEOUT = 200;
    private final BlockingQueue<T> queue = new LinkedBlockingQueue();

    @Override
    public void run() {
        while (!isInterrupted()) {
            try {
                T item = queue.poll(TIMEOUT, TimeUnit.MILLISECONDS);
                if (!isInterrupted() && item != null) {
                    processItem(item);
                }
            } catch (InterruptedException ex) {
                Thread.currentThread().interrupt();
            }
        }
    }

    public void put(T e) {
        queue.add(e);
    }

    public abstract void processItem(T item);
}

All you need is to extend this class and implement its abstract method processItem(T item). The example of it follows.

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.TimeUnit;

public abstract class WorkerThread extends Thread {

    public static final long TIMEOUT = 200;
    private final BlockingQueue queue = new LinkedBlockingQueue();

    @Override
    public void run() {
        while (!isInterrupted()) {
            try {
                T item = queue.poll(TIMEOUT, TimeUnit.MILLISECONDS);
                if (!isInterrupted() && item != null) {
                    processItem(item);
                }
            } catch (InterruptedException ex) {
                Thread.currentThread().interrupt();
            }
        }
    }

    public void put(T e) {
        queue.add(e);
    }

    public abstract void processItem(T item);
}

To use this class you need to create and start the thread and call put() whenever you want to process next data item.

HRDBWorker hrDBWorker = new HRDBWorker();
hrDBWorker.start();
...
htDBWorker.put(nextItem);

Hopefully, this is the useful piece of code. You are welcome to comment.

Reshaka.Ru – как всё начиналось

Promotion: Meet one of our projects! Reshaka.Ru is a service for students to solve problems. We also can help with your exam online!
Currently it targets Russian audience, but who knows, maybe we will expand to other countries. 🙂

sabirjun

История создания сервиса  Reshaka.Ru

 

Голодные студенты

В далёком 2010 году, когда мы были еще второкурсниками, нам частенько приходилось подрабатывать, решая различные примеры и задачки студентам и школьникам. Как сейчас помню периодические размещения на ответах mail.ru посты типа “решаю задачи по физике, математике, информатике недорого”.В интернете есть несколько сервисов, на которых можно разместить задачу, заплатить деньги и дождаться решения. Мы были зарегистрированными в нескольких из них в качестве решающих. Худо-бедно, но заказы приходили. Мы выполняли контрольные, задания по физике, теоретической механике, многим разделам математике, химии. Иной раз даже приходилось переводить статьи по английскому. А самый прибыльные деньки приходились на сессию! Мы вставали ранним утром и помогали на экзаменах удалённо студентам с нескольких часовых поясов нашей необъятной Родины! Порой за один день “участвовали” в 7-8 контрольных или экзаменах.

Разворачиваемся

Заказы поступали постоянно, но мы понимали, что их количество зависит от степени нашей “известности” как хороших решающих. Поэтому Александр организовал группу-визитку…

View original post 652 more words

Presentation: Academic Grading

Again, we have another presentation here. The topic for today is Education. Let’s see what presentation I created.

Education: Academic Grading

[Greeting] Good morning, everyone. My name is Anton Danshin. I’m a student of Moscow Institute of Physics and Technology.

In my today’s presentation I’m going to tell you about the academic Grading in different countries.

[Why?] The topic is very interesting and the information I’ll give you might be useful for those students who want to continue their education abroad.

[What?] There is an infinite variety of academic grading systems in different counties and there is no way to cover all these systems. And I will cover only common ones.

First of all, I’ll tell you what an academic grading is. Secondly, I’d like to tell a few words about the system that is used in Europe. Thirdly, I’ll familiarize you with the american grading system. Then I’ll tell a little bit about Russian system and systems used in the countries of CIS. And finally, I’ll highlight the main points of my presentation and make a conclusion.

[How?] The presentation won’t take long – just about 10 minutes. You may ask your questions at the end.

Lets get started!

What is an academic grading? The answer is quite obvious. The academic grading is the way of measurement of student’s knowledge and skills in a certain subject which he or she acquired during study at educational institution.

A perfect academic grading system should provide an objective assessment of the quality of student’s knowledge, rather than the quantity. Let’s see what functions a perfect grading system should fulfil.

  • Firstly, it should help to compare stated aims with results achieved by a student.
  • Secondly, it should reveal the main difficulties which students have.
  • Thirdly, it should determine the quality of teachers work.
  • And finally, a perfect grading system should motivate student to study.

Now that we know what academic grading is all about and what it stands for, we can move on to the next point of my presentation.

European Grading System: ECTS

In Europe the most common grading is so called ECTS – European Credit Transfer and Accumulation System. It is a standard for comparing the study attainment and performance of students of higher education across the European Union and other collaborating European countries.

For successfully completed studies, ECTS credits are awarded. One academic year corresponds to 60 ECTS-credits that are equivalent to 1500–1800 hours of study in all countries irrespective of standard or qualification type. To get bachelors degree it is necessary to have at least 180 – 240 ECTS-credits, and 300 credits for masters.  ECTS also includes a standard ECTS grading scale, intended to be shown in addition to local (i.e. national) standard grades. The ECTS grading scale is shown on the slide.

That’s all I wanted to say about European grading system. Now let’s pass over to the American academic grading system.

American academic grading

In the Unated States of America they also have letter grades scale but it is very different from European one. They use 4-points scale. In addition, there is not any rating system, the Grade Point Average (GPA) is calculated instead.

Most graduate schools require a 3.0 (B) average to take a degree, with C or C- being the lowest grade for course credit. Most undergraduate schools require a 2.0, or C average to obtain a degree with a minimum of D or D− to pass a course. But this all depends on laws of a certain state.

Russia

That’s all about the USA. Let’s move on to the next point and see what we have in Russia and some neighbouring countries. As we can see from the table, some countries from Eastern Europe tend to have 10-point scale. Our country still has 5 point scale, but is it enough to represent the knowledge of students? Or there is no difference? These (actually difficult) questions bring me to the end of my presentation.

Conclusion

Let’s go over the main points I covered.

  • Academic grading is a way to assess the quality of students’ knowledge and skills.
  • A perfect grading system has to fulfil a lot of functions and there is obviously no the perfect one.
  • There are a lot of different grading systems.
    • Europe: ECTS
    • the USA: 4-point scale + GPA
    • Russia: 5-point scale

It’s quite difficult to decide which one is the best. But I think that the main problem is not in the grading scale at all! The main problem is in student’s ability and desire to study.

As the proverb says: ‘You can bring a horse to the water. But you can’t make it drink’. In other words, you can design any kind of grading scale but the final choice to study or not is up to students.

Thank you very much for your attention. Now you can ask your questions.

Download

You can easily download my presentation from Google Docs:

Let me know if you find a mistake. Good luck with your English!

Anton Danshin

[Video] A Day Made of Glass

Hi there!

I found a very interesting video on YouTube recently. You should probably watch it and enjoy.

Learn English with BBC

I’ve been surfing the net and accidentally encountered an amazing website for learning English – BBC: Learning English.

BBC: Learning English

The web site is full of videos, news articles, grammar and vocabulary and other very interesting and useful materials. All – free! In addition, there are quizzes for those who want to check how well they learnt.

I hope this information is helpful. Enjoy!

English Tek

Conditionals in English

Good afternoon.

Our today’s lesson is about Conditionals in English. In grammar, conditional sentences are sentences discussing factual implications or hypothetical situations and their consequences. Languages use a variety of conditional constructions and verb forms (such as the conditional mood) to form such sentences. [wiki].

All conditional sentences can be divided into four different groups. (Of course, there are some other ways to classify different forms of conditional)

Zero Conditional

We use the so-called zero conditional or Real Conditional when the result of the condition is always true, like a scientific fact.

Consider the following situation: Take some ice. Put it in a saucepan. Heat the saucepan. What happens? The ice melts (it becomes water). You would be surprised if it did not. We can say: The ice melts if it is heated or: If we heat a piece of ice, it melts.

Formulae:

  • IfV,V.
  • V ifV.

We can also use when or as soon as instead of if, for example: When I get up late, I miss my bus

We do not put comma before if / when / as soon as in such sentences.  Using “if” suggests that something happens less frequently. Using “when” suggests that something happens regularly.

The verbs (V) can be in Present Continuous / Past Simple form. For example: If I went to a friend’s house for dinner, I usually took a bottle of wine or some flowers. I don’t do that anymore.  This form is called Past Real Conditional and describes what you used to do in particular real-life situations. It suggests that your habits have changed and you do not usually do these things today.

First Conditional

We are talking about the future (that’s why this form of conditional is also called Future Real Conditional). We are thinking about a particular condition or situation in the future, and the result of this condition. There is a real possibility that this condition will happen.

For example, it is morning. You are at home. You plan to play tennis this afternoon. But there are some clouds in the sky. Imagine that it rains. What will you do? In this situation we can say: If it rains, I will not play tennis.

Formulae:

  • IfV,will V
  • will V if V.

Sometimes, we use shallcan, or may instead of will, for example: If you are good today, you can watch TV tonight.

Both “if” and “when” are used in the Future Real Conditional, but the use is different from other Real Conditional forms. In the Future Real Conditional, “if” suggests that you do not know if something will happen or not. “When” suggests that something will definitely happen at some point; we are simply waiting for it to occur. Notice also that the Simple Future is not used in if-clauses or when-clauses.

Second Conditional

The second conditional is like the first conditional. We are still thinking about the future. We are thinking about a particular condition in the future, and the result of this condition. But there is not a real possibility that this condition will happen. For example, you do not have a lottery ticket. Is it possible to win? No! No lottery ticket, no win! But maybe you will buy a lottery ticket in the future. So you can think about winning in the future, like a dream. It’s not very real, but it’s still possible

Formulae:

  • If … V2, … would V
  • would V if … V2.

Notice that we are thinking about a future condition. We use the past simple tense to talk about the future condition. We use WOULD + base verb to talk about the future result. The important thing about the second conditional is that there is an unreal possibility that the condition will happen. That’s why this form is called Present Unreal Conditional.

Only the word “if” is used with the Second Conditional because you are discussing imaginary situations. “When” cannot be used. Sometimes, we use shouldcould or might instead of would, for example: If I won a million dollars, I could stop working.

Third Conditional

The first conditional and second conditionals talk about the future. With the third conditional we talk about the past. We talk about a condition in the past that did not happen. That is why there is no possibility for this condition. The third conditional is also like a dream, but with no possibility of the dream coming true. Consider the following situation. Last week you bought a lottery ticket. But you did not win. In this situation we would say: If I had won the lottery, I would have bought a new car.

Formulae:

  • If … had V3, … would have V
  • … would have V if had V3.

Notice that we are thinking about an impossible past condition. You did not win the lottery. So the condition was not true, and that particular condition can never be true because it is finished. We use the past perfect tense to talk about the impossible past condition. We use WOULD HAVE + past participle to talk about the impossible past result.

The important thing about the third conditional is that both the condition and result are impossible now, that’s why it is called Past Unreal Conditional. Sometimes, we use should havecould havemight have instead of would have, for example: If you had bought a lottery ticket, you might have won.

Summary

Form

Formulae Probability

Example

 Zero Conditional
  • If … V, … V.
  • … V if … V.
 ~ 100 % If the ice is heated, it melts

 First Conditional

  • If … V, … will V
  • … will V if … V.
 ~ 50 % If it rains tomorrow, I won’t play tennis.

 Second Conditional

  • If … V2, … would V
  • … would V if … V2.
 < 10 %  If I had a lot of money, I wouldn’t work.

 Third Conditional

  • If … had V3, … would have V
  • … would have V if … had V3.
 0 %  If I had won the lottery last week, I would have bought a new car

Links

  1. Conditional Sentences in English in Wikipedia
  2. English Conditionals at EnglishClub.com
  3. Conditional Tutorial at EnglishPage.com
  4. First and Second conditionals at EngVid.com
Thanks for visiting our website. Good luck with your English!
English Tek

Stative (State) Verbs

A stative verb is one which asserts that one of its arguments has a particular property (possibly in relation to its other arguments). Statives differ from other aspectual classes of verbs in that they are static; they have no duration and no distinguished endpoint. Verbs which are not stative are often called dynamic verbs. (Wikipedia)

There are plenty of articles on stative verbs on the Internet. I want to summarise a few articles.

At first, take a look at the video from engVid.com on stative verbs.

Original: English Grammar – Stative Verbs

This video by Ronnie is extremely enjoyable! I love it. Do you?

Secondly, check out the following video which I found on the Internet.

Original: Stative Verbs

To be honest, the second video is extremely boring! But anyway the article is very useful. That’s why I recommend that you look at the original post.

Overview

Some English verbs, which we call state, non-continuous, or stative verbs, aren’t normally used in continuous tenses (like the present continuous, or the future continuous). The most common ones:

like    love    hate    want    need    prefer

know    realise   suppose   mean   understand   believe  remember

belong    fit    contain    consist    seem    look (=seem)

Download PDF with the list of stative verbs and examples.

A verb which isn’t stative is called a dynamic verb, and is usually an action.

Some verbs can be either stative or dynamic depending on the situation.

To Be

be is usually a stative verb, but when it is used in the continuous it means ‘behaving’ or ‘acting’

  • you are stupid = it’s part of your personality
  • you are being stupid = only now, not usually

To Think

think (stative) = have an opinion

  • I think that coffee is great

think (dynamic) = consider, have in my head

  • what are you thinking about? I’m thinking about my next holiday

To Have

have (stative) = own

  • I have a car

have (dynamic) = part of an expression

  • I’m having a party / a picnic / a bath / a good time / a break

To See

see (stative) = see with your eyes / understand

  • I see what you mean
  • I see her now, she’s just coming along the road

see (dynamic) = meet / have a relationship with

  • I’ve been seeing my boyfriend for three years
  • I’m seeing Robert tomorrow

To Taste

taste (stative) = has a certain taste

  • This soup tastes great
  • The coffee tastes really bitter

taste (dynamic) = the action of tasting

  • The chef is tasting the soup
    (‘taste’ is the same as other similar verbs such as ‘smell’)

I hope this lesson on stative verbs is very useful. Thank you for visiting. Good luck with your English!

English Tek