A solution to Exercise 35.2-5 in the book "Introduction to algorithms" by Cormen, Leiserson and Rivest.

Suppose that the vertices for an instance of the traveling-salesman problem are
points in the plane and that the cost c(u,v) is the euclidean distance between
points u and v. Show that an optimal tour never crosses itself.

 

If the optimal tour crosses itself then it can be in a manner shown in the attached picture. Thus, there are edges AC and DB (a tour with crossing) instead of AB and DC (optimal tour). The edge AC can be represented as a sequence of edges: AX and XC. The same can be done for edge DB, which can be represented as a sequence of edges: DX and XB. By the triangle inequality, AB < AX + XB (red) and DC < DX + XC (green). In this case, we can show that the optimal tour cannot cross itself, because: AB + DC < AX + XB + DX + XC = (AX + XC) + (DX + XB) = AC + DB. Now, we can generalize the case, and have a cross between more than two consecutive vertices, for example, A'C' and AC, but then we can see from the picture, that we will have to turn back at some point, for example from A to C (instead of going forward), which lengthen the path even more.

Bret Victor

That's really creative: http://worrydream.com/

Facebook, Youtube, LinkedIn and other CSS and JavaScript files from CDNs not loading on Ubuntu

I used to live in a dormitory in Warsaw. Many times there was a problem with a DNS server. It was broken regularly and it was blooming ridiculous as the building was a property of a technical university.

Anyway, there was a problem with DNS on my own router. It occurred that Ubuntu automatically assigned primary DNS setting to my router and it was broken. I found the solution here: http://bit.ly/17tDSQG Then according to my "standard" procedure changed the DNS settings for my local connection: http://bit.ly/1dvAuuP and "voila" it worked. Facebook, Youtube, LinkedIn and some other big players could load their CSS files and other resources!

My current settings:

The simplest RPC call ever in Python:

Server (file xmlrpc.py):
def fibonacci_naive(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci_naive(n-2) + fibonacci_naive(n-1)

import SimpleXMLRPCServer
server = SimpleXMLRPCServer.SimpleXMLRPCServer(('192.168.0.104', 8000))
server.register_function(fibonacci_naive)
server.serve_forever()
################################################################

$ python xmlrpc.py 

Client:
>>> import xmlrpclib
>>> server = xmlrpclib.ServerProxy('http://192.168.0.104:8000')
>>> print server.fibonacci_naive(10)
55

Pythonic

Pythonic
return multiple values from functions using tuples

Un­Pythonic 
output parameters

What is Pythonic? The answer can be found here:
http://blog.startifact.com/posts/older/what-is-pythonic.html


Take a look at these slides (they're worth reading):
http://jacek.web.cern.ch/jacek/courses/python-intro/course.html#slide0

My general presentation on databases for newbies

Hello everyone. My name is Adam. I’m a computer scientist and a specialist in databases. Today, I’ll speak to you about databases. I divided my presentation into 3 main sections:

First, I’ll give you a brief overview of the world of databases.

Secondly, I’ll tell more about different types of databases, including NoSQL databases.

At the end I’ll sum up the presentation and tell you about a special particle.

I’ll try to leave time for questions at the end.

So let me explain you the basics. Generally, databases are used to store and process data. The data is typically organized to model relevant aspects of reality. We can encounter databases everywhere. The exemplars of databases can be found in banks, where a large amount of data are stored and processed. The data about the balance on my account, about transactions and many other things have to be stored. The information about products in shops is stored in databases. What’s more? You can find databases even in your smartphones! Be aware that databases are in all kinds of devices. Outside the world of professional IT, the term database is sometimes used casually to refer to any collection of data, perhaps a spreadsheet in Excel.

There are at least 5 main kinds of databases.

- relational databases - represent a traditional approach to databases where data are stored in tables (the tables similar to that you know from Excel spreadsheet)

- object oriented databases - data are stored in objects. Nowadays, to write programs we use mainly object oriented programming and object databases’ main purpose is to make it easier to store data from objects in applications to objects in databases.

- NoSQL databases - these databases are used to store huge amount of data and are used mainly by companies, such as Facebook, Google, Amazon and even CERN.

- graph databases - the basic model is a graph with nodes and edges. This kind of databases suits best for modelling connections between elements, for example, what are the all railway connections is Poland

- hierarchical databases  - to model hierarchy of elements, for example, a hierarchy of people in an organisation.

- spatial databases - the queries on such data include location based queries, like "Where is the closest hotel in my area?".

Nowadays, there are many information systems that store data in databases. Databases were created to provide us with tools to store data efficiently and they cause that processing data is not burdensome anymore. The interesting thing is that after almost 40 years of reign of relational databases, which is something unusual in fast developing technology field, new movement of NoSQL databases emerged. I brought to you the particle of NoSQL databases from CERN.

Thank you. Are there any questions or comments?

Longer and better life? Yes, please.

The more inventions the longer and better life. Have you ever wondered if your your lifespan can be increased? Do you want to control your car with your brain and be in a nowhere near place at once? Let's consider inventions that could help us to achieve these goals.

A drug against ageing is on top of the list. We do want to live longer. Some scientists argue that a special region in our brain (the hypothalamus) is responsible for the ageing process and possible to be controlled. By applying a drug that could block chemical process in this region of the brain we would be able to lengthen our lifespan.

What about a helmet which would detect signals in your brain, process them to specific instructions and control machines around you. For example, instead of  a steering wheel in your car you could turn left using a thought in your brain. A pilot of a jet fighter could control the machine in a better way since movements of hands on a joystick are slower than brain signals communicating directly with an electronic follow up system.

The last but not the least invention is a supersonic individual transport. A novel way of transport in special capsules that could work like missals and have special start and stop docks. Much faster transport close at hand.

There is a long way to go to realise these plans. One thing we can be certain of is continuous progress that makes our life a little bit better every day.