Math Overflow.

Have a question about Mathematics, try Math Overflow.

Ashutosh Trivedi : 20 Oct 2009 11:55 |  Comments (0) |  Close comments |  Report a problem

Making Mac Remote work with Adobe Reader.

While delivering my presentation today, I realised the mac remote doesn’t work with Adobe Reader or for that matter even with Preview. It’s shame because that was the only reason I spent 20£ on this remote. After my presentation was over, I started searching on Google if the Mac remote was of any use and it indeed is.

There is the program called iRedLite which can be used to program Mac remote controller. If you are feeling lazy, you can read this blog to get so-called layer setting for this program, which makes handling adobe reader with keyboard much easier.

Ashutosh Trivedi : 26 Aug 2009 16:35 |  Comments (0) |  Close comments |  Report a problem

Fixed Point

In mathematics, a fixed point (sometimes shortened to fixpoint) of a function is a point that is mapped to itself by the function. [More]

The Banach fixed point theorem gives a general criterion guaranteeing that, if it is satisfied, the procedure of iterating a function yields a fixed point. The banach fixed point theorem statement is the following.

Let (X, d) be a non-empty complete metric space. Let T : X → X be a contraction mapping on X, i.e: there is a nonnegative real number q < 1 such that
d(Tx,Ty) \le q\cdot d(x,y), for all x, y in X.
Then the map T admits one and only one fixed point x* in X (this means Tx* = x*).
Furthermore, this fixed point can be found as follows: start with an arbitrary element x0 in X and define an iterative sequence by xn = Txn-1 for n = 1, 2, 3, ... This sequence converges, and its limit is x*.

The proof follows from the fact that for every x, the sequence (x, f(x), f(f(x)), ... ) is a cauchy sequence and hence convergent by completeness. The limit of the sequence is the fixed-point. It is easy to show that the fixed-point is unique.

By contrast, the Brouwer fixed point theorem is a non-constructive result: it says that any continuous function from the closed unit ball in n-dimensional Euclidean space to itself must have a fixed point, but it doesn’t describe how to find the fixed point.

The Knaster-Tarski theorem is somewhat removed from analysis and does not deal with continuous functions. It states that any order-preserving function on a complete lattice has a fixed point, and indeed a smallest fixed point. Formally the statement is the following:

Let L be a complete lattice and let f : L → L be an order-preserving function. Then the set of fixed points of f in L is also a complete lattice.

Since complete lattices cannot be empty, the theorem in particular guarantees the existence of at least one fixed point of f, and even the existence of a least (or greatest) fixed point.

Ashutosh Trivedi : 23 Oct 2007 11:25 |  Comments (0) |  Close comments |  Report a problem

Tourist Agency Problem

A tourist agency anonuces an interesting scheme for all tourist who are interested in having a tour of as many cities as possible in europe. Given an initial budget B , tourist agency works as follows.

Given the map of the cities and the prices between the cities are given as a weighted directed graph G = {V, E, p}. There are different cities V = {C_1, C_2, ..., C_n} and from every city there are some flight connections to some other cities (C_i, C_j) \in E and the price of the flights between cities is fixed in advance p(C_i, C_j). Starting from a city C_i and a budget B, tourist agency picks an amount d < B, such that there exists a city C_j such that p(C_i, C_j) = d. If the tourist agency can not choose such a number d and the remaining budget B is greater than 0, then toursit agency agrees to pay a high price as penalty to the tourists and thus toursit agency loses. Otherwise the tourists pick a city such that flight price to the destination city is d unit and take the flight. Tourist agency then updates the budget B to B-d and the tour continues. The aim of the tourist agency is to reach a city with 0 budget.

Given a map and an initial budget, find optimal strategy for the tourist guide and the tourists.

Ashutosh Trivedi : 29 Jan 2007 23:32 |  Comments (0) |  Close comments |  Report a problem

students == severely mentally impaired

Properties exempt from council tax

Some property is exempt from council tax altogether. It may be exempt for only a short period, for example, six months, or for a longer time.

Properties which may be exempt are:-

• property which is empty. It has to be unoccupied and substantially unfurnished. The exemption applies for a maximum of six months and the property has to be vacant for the whole of this period
• property which is vacant because it needs major repairs or alterations to make it habitable. The exemption applies for a maximum of 12 months whether the work is actually finished or not by then
• condemned property
• property which has been re-possessed by a mortgage lender
• property unoccupied because the person who lived there now lives else where because they need to be cared for, for example, in hospital (or with relatives)
• property which is unoccupied because the person who lived there has gone to care for someone else
• any property that only students live in. This may be a hall of residence, or a house
• a caravan or boat which is used as a main residence but which is unoccupied. This exemption lasts for up to six months. A holiday caravan or boat is exempt if it’s on a property where council tax is paid
• a property where all the people who live in it are aged under 18
• a property where all the people who live in it are either severely mentally impaired or are students or where there is a mixture of both
• a self-contained ‘granny flat’ where the person who lives in it is a dependent relative of the owner of the main property.

Ashutosh Trivedi : 02 Jan 2007 19:01 |  Comments (1) |  Close comments |  Report a problem

radio, as it should be.

Finally there is a radio, which you can surf, not according to those weird numbers with AM/FM/SW in front of them, but according to your mood. Give it a try.

Ashutosh Trivedi : 27 Dec 2006 16:00 |  Comments (0) |  Close comments |  Report a problem

pseudo–polynomial Vs. Strongly polynomial.

In algorithmic complexity, two other terms are heard frequently: strongly polynomial and pseudo-polynomial. A strongly polynomial-time algorithm is one whose running time is bounded polynomially by a function only of the inherent dimensions of the problem and independent of the sizes of the numerical data. For example, most sorting algorithms are strongly polynomial, since they normally require a number of comparisons polynomial in the number of entries and do not depend on the actual values being sorted; an algorithm for a network problem would be strongly polynomial if its running time depended only on the numbers of nodes and arcs in the network, and not on the sizes of the costs or capacities.

A pseudo-polynomial-time algorithm is one that runs in time polynomial in the dimension of the problem and the magnitudes of the data involved (provided these are given as integers), rather than the base-two logarithms of their magnitudes. Such algorithms are technically exponential functions of their input size and are therefore not considered polynomial. Indeed, some NP-complete and NP-hard problems are pseudo-polynomially solvable (sometimes these are called weakly NP-hard or-complete, or NP-complete in the ordinary sense). For example, the NP-hard knapsack problem can be solved by a dynamic programming algorithm requiring a number of steps polynomial in the size of the knapsack and the number of items (assuming that all data are scaled to be integers). This algorithm is exponential-time since the input sizes of the objects and knapsack are logarithmic in their magnitudes. However, as Garey and Johnson (1979) observe, “A pseudo-polynomial-time algorithm … will display ‘exponential behavior’ only when confronted with instances containing ‘exponentially large’ numbers, [which] might be rare for the application we are interested in. If so, this type of algorithm might serve our purposes almost as well as a polynomial time algorithm.” The related term strongly NP-complete (or unary NP-complete) refers to those problems that remain NP-complete even if the data are encoded in unary (that is, if the data are “small” relative to the overall input size). Consequently, if a problem is strongly NP-complete then it cannot have a pseudo-polynomial-time algorithm unless P = NP.

[Credit.]

Ashutosh Trivedi : 26 Dec 2006 19:16 |  Comments (0) |  Close comments |  Report a problem

KIWI: nice animation

I recommend watching this nice animation, done by some student (www.donysanimation.com) for his Master’s thesis. I liked the video, not only for the animation, but the story narrated in just 3 minutes really touched me.

I will not say anything about the story, as that will spoil your experience.

http://www.youtube.com/watch?v=sdUUx5FdySs

Ashutosh Trivedi : 14 Nov 2006 19:41 |  Comments (0) |  Close comments |  Report a problem

Jesus Christ and you: probability

What is the probability that the next breath you take contains a molecule expelled by Jesus Christ when he said “O Lord! Forgive them.”

A solution

Ashutosh Trivedi : 06 Nov 2006 10:58 |  Comments (0) |  Close comments |  Report a problem

another lame joke

source

A man is dining in a fancy restaurant, and there is a gorgeous redhead sitting at the next table. He has been checking her out since he sat down but lacks the nerve to talk with her.

Suddenly she sneezes, and her glass eye comes flying out of its socket towards the man. He reflexively reaches out, grabs it out of the air, and hands it back.

“Oh my, I am sooo sorry,” the woman says as she pops her eye back in place. “Let me buy your dinner to make it up to you,” she says.

They enjoy a wonderful dinner together and afterwards the theater, followed by drinks.

They talk, they laugh; she shares her deepest dreams, and he shares his. She listens.

After paying for everything, she asks him if he would like to come to her place for a nightcap… and stay for breakfast the next morning. The next morning, she cooks a gourmet meal with all the trimmings.

The guy is amazed. Everything had been incredible. “You know,” he said, “you are the perfect woman. Are you this nice to every guy you meet?”

“No, she replies, “You just happened to catch my eye.”

Ashutosh Trivedi : 25 Oct 2006 13:55 |  Comments (0) |  Close comments |  Report a problem