Wednesday, August 11, 2010

God's Number is 20

As many of my friends know, I am a competitive speedcuber (one can search up my WCA profile).

I love solving puzzles, and more importantly, I love the mathematics behind it. For some time now in the cubing world there has been some progress made into solving an algorithm which produces a solution having the least possible number of moves, the idea being that an omniscient being would know an optimal step from any given configuration. This is known as God's algorithm. The number of moves this algorithm would take in the worst case is called God's Number.

Recently
Morley Davidson, John Dethridge (also a TopCoder), Herbert Kociemba, and Tomas Rokicki proved that God's Number for the standard 3x3x3 Rubik's Cube is exactly 20.

Why is this a great leap forward for cubers? Simply put, imagine constructing an algorithm to optimally
solve all 43,252,003,274,489,856,000 positions of the cube. Easy, no? It took 3 decades to get to this stage ..

Here's the
article for further reading.

Monday, August 9, 2010

P != NP ?

Stumbled upon this interesting article today on the famous P versus NP problem. Thought I should share it with my fellow CS enthusiasts.

For more, please visit here.

(Aug. 9) -- News that Hewlett-Packard employee Vinay Deolalikar may have solved one of computer science's most confounding mathematical problems -- known as P = NP or P versus NP -- is buzzing around the smart side of the Internet. The problem was formulated by Stephen Cook and Leonid Levin in 1971, according to the Clay Mathematics Institute, which has been offering a $1 million prize for its solution. Now, mathematicians are in the process of scrutinizing Deolalikar's proof, released on Friday, which says that P is not in fact equal to NP.

P versus NP
Roughly, the mathematical problem asks if "questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure," according to the Clay Mathematics Institute. In other words, are there really problems whose solutions can be easily verified but not easily solved?

To illustrate the type of problem that could occur if this were true, Clay imagines a college housing scenario wherein 400 students have applied for rooms at a college that can only accommodate 100 of them. A selection of 100 students must be paired together in rooms, but the dean of students has a list of pairings of certain students who cannot room together. The total possible number of pairings is ridiculously large -- more than the total number of atoms in the universe -- but the solutions, i.e. the list of pairings finally provided to the dean, is easy to check for errors: If one of the dean's prohibited pairs is on the list, that's an error.

If P = NP, then problems that appear hard to solve (as the one above) actually have very easy solutions. Deolalikar says he has proven that P does not equal NP -- as many mathematicians have believed -- meaning problems do exist that are easier to solve than to verify.

P
In the equation P = NP, P stands for "polynomial time" and refers to a set of problems whose solutions are easy to find.

NP
NP, meanwhile, stands for "non-deterministic polynomial time" and refers to a set of problems whose solutions are hard to find, but easy to verify.

Algorithm
A set of instructions used to solve a problem. We use them without thinking about it in everyday life, such as when trying to figure out why a lamp doesn't turn on.

N
The number of elements involved in an algorithm. The time it takes to execute many common algorithms is proportional to N or N raised to a power. For example, to determine why a lamp is not working, we might consider three elements:
1. The lamp is not plugged in.
2. The light bulb is burnt out.
3. The lamp is broken.
With only three elements to consider, our algorithm will not take very long to complete. But, if we are trying to determine why our computer won't turn on, we are presented with more elements to consider: Is it plugged in? Is it frozen? Does it need to be rebooted? Does the operating software need to be re-installed? Is it broken? And so on.

Polynomial time
Refers to a "fast" or "efficient" amount of time needed to execute an algorithm, as in N or N raised to a power. Problems classified by "P" in P = NP are those whose solutions can be solved in polynomial time. Problems classified by "NP" can be verified in polynomial time but require exponential time (in other words, far, far more time) to solve.

NP-Complete
The set of NP problems (the majority of NP problems, in fact) that could be solved by adapting a single, easy solution, if an easy solution were possible.

Read more about P = NP on
MIT's website.
pnp12pt

Friday, July 30, 2010

Inception

... It's weird how I can tell if a movie is good just by looking at the trailer.

Inception was absolutely brilliant. Watched it the first day it was released, along with Despicable me and The Sorcerer's Apprentice. Reviews on those movies perhaps at a later time, or not at all.

From the director of the The Dark Knight, Nolan has crafted a movie that's truly beyond genius, and layered both narratively and thematically. Believe me, you have never seen anything like Inception, though many say it is similar to Matrix, it is not. You'll want to see it again and again.

"You’re waiting for a train; a train that will take you far away. You know where you hope this train will take you, but you can’t be sure. But it doesn’t matter – because we’ll be together."

DiCaprio was in my opinion the perfect lead for this movie, as he captured the role flawlessly. “If you’re going to perform inception, you need imagination.” Inception requires so much exposition that a lesser director would have forced theaters to distribute pamphlets to audience members in order to explain the complicated world he’s developed. No wonder it took him over a decade to write the script. Even I can't explain the plot in depth, as the movie required total concentration on what is happening (perhaps I shouldn't have gone out for snacks during the movie). Why is it so difficult to explain the plot in depth? First, I don’t want to spoil you. Secondly, the film layers dreams on top of dreams to the point where a unique keepsake called a “totem” is required in order to inform a character as to whether or not he or she is still dreaming. Then you have people in particular roles like “The Architect”, “The Forger”, and “The Chemist” in order to pull off the job. Furthermore, dreams have rules: dying in a dream forces the dreamer to wake up, delving too deeply into a mind can cause an eternal slumber called “Limbo”, using memories to construct dreams is dangerous because it can blur the line between dreams and reality. In addition, intruding in the dreams of another will cause the dreamer’s “projections” (human representations created by the dreamer) to attack the intruders like white blood cells going after an infection. And these explanations only represent a fraction of the terminology, rules, exceptions, or details that are necessary for creating the world of Inception. With set pieces so intricate, so jaw-dropping, and so breathtaking, you’ll already be swept up in the whirlwind.

There’s a lot to take in, but the imaginative and thoughtful delivery of exposition keeps the viewer riveted despite the amount of information required in order to understand the premise, setting, and plot. It’s not a confusing movie if you provide it with your full attention.

“Dreams feel real while we’re in them. It’s only when we wake up that we realize something was actually strange.”

I'm more active in my dreams than in real life. It's a wonderful place to be. The idea here is - what if you can control your dreams? Other people's dreams? A concept so powerful, it'll be a shame if it doesn't get an Oscar.

Rating: 9/10




As a physics student, I am astonished by the set of laws inception breaks, but remains logical at the same time. I'm going to research more on the physics behind dreams. Should be an interesting topic.

Saturday, July 17, 2010

World Cup 2010

IN PAUL WE TRUST

Well, it's over - Spain deserved it.
South Africa was a great host, but it was a horrid world cup. Which proves my point why nothing compares to Champions League glory.
Let's just hope Brazil 2014 will do futbol justice.

Saturday, July 10, 2010

SPOJ - JEDNAKOST

Getting back to more programming after an inspirational summer camping trip. Saw one of my friends attempting this problem, thought I should give it a shot.

Recently solved problem #3752 - JEDNAKOS.

If you want to solve the problem yourself - stop reading now.

Solution - Recursion + Memoization

Easy problem really

1) Treat numbers starting with zero as special cases.

2) Let minplus[sum][pos] be an array that is the minimum number of pluses required to obtain the value 'sum' using the postfix starting at 'pos', then it's just simple recursion.

3) To avoid initialization, the array stores the number of pluses plus one.

Thursday, July 1, 2010

On the G20 protests

Quick post on something that should be expressed by a Torontonian.

For all these years that I have lived in Toronto, I have never been more disappointed in our people than I am now. I applaud the police for using force with tear gas and rubber bullets against those who have caused tax payers millions of dollars in damages.

It's quite a disgrace to think vandals such as the Black Bloc
would deface such a city for no particular reason at all.

Freedom of speech is something that should be treasured in this nation, peaceful protesters however got little media coverage while numerous news casts broadcasted the events surrounding these vandalisms, and therefore did not get their message's across the nation on issues that actually mattered.

People can be very stupid.

~Happy Canada Day

... Sigh

Wednesday, June 23, 2010

Great People In History II - Leonardo Da Vinci

Leonardo Da Vinci, the great Italian renaissance man who changed our views of both art and science in such a way that modern civilizations still adore and admire his work. His accomplishments are unprecedented, a worldly known brilliant polymath whose unquenchable curiosity was equaled only by his powers of invention. There is no doubt that he is perhaps the greatest person in history, the only man to have attempted to know everything there is to know. His influences encompassed the world of arts, science & technology, and even invented new mechanisms that have revolutionized mankind. Astonishing feats of engineering were established 500 years ago, perhaps surpassing that of our modern era. He is a portrait of a genius of extraordinary diversity.

Leonardo was and is best known as an artist, the creator of such masterpieces as the Mona Lisa and The Last Supper, the most well known paintings of all time. His astonishing works of beauty still captivate and inspire people worldwide. His paintings became famous, and only rivaled by Michelangelo’s creation of Adam. When drawing his masterpiece, the Mona Lisa, his dedication and perseverance in achieving perfection caused him 10 years of his life, only to have painted the lips. In 1466, at the age of fourteen, Leonardo was apprenticed to the artist Andrea di Cione, known as Verrocchio. Other famous painters apprenticed there include Domenico Ghirlandaio, Perugino, Botticelli, and Lorenzo di Credi. Leonardo’s earliest known dated work while there is a drawing in pen and ink of the Arno Valley, drawn on August 5th, 1473. He was commissioned to paint the Virgin of the Rocks for the confraternity of the Immaculate Conception, and The Last Supper for the Monastery of Santa Maria delle Grazie. In January 1478, he received his first independent commission, to paint an altarpiece for the Chapel of St Bernard in the Palazzo Vecchio and The adoration of the Magi in March 1481 for the monks of San Donato a Scopeto. On Octover 18, 1503, he spent two years designing and painting a great mural of the Battle of Anghiari, with Michelangelo designing its companion piece, the Battle of Cascina. In both theory and practice, Leonardo’s artistic influence in the 16th and 17th century Europe, notably France, Spain, Flanders, and Germany was immense, as to have dedicated numerous museums and organizations in his honour. To this day only 15 of his paintings have survived, which have inspired and captivated millions world-wide.

Leonardo’s scientific contributions are brilliant and revolutionary for his time. His new views of the universe and nature are very accurate according to modern science, which is without a doubt a staggering feat for a man who had little to go by. His vision of the world is essentially logic rather than mystery. His personal notebook, which was discovered all over Europe in pieces, reveals correct interpretations of the human anatomy, explanations of physical concepts such as inertia, and sketches for various engineering marvels, such as conceptualizations of a helicopter, a tank, concentrated solar power, a calculator, the double hull and outlined a rudimentary theory of plate tectonics. Additionally, there are compositions for paintings, studies of details and drapery, studies of faces and emotions, of animals, babies, dissections, plant studies, rock formation, and even whirl pools. As a child, Leonardo received informal education in Latin, geometry and mathematics but did not show any particular signs of aptitude. Leonardo’s approach to science was an observational one: he tried to understand a phenomenon by describing and depicting it in utmost detail, and did not emphasize experiments or theoretical explanation. In the 1490’s, while studying mathematics under Luca Pacioli, he prepared a series of drawings of regular solids in skeletal form to be engraved as plates for Pacioli’s book De Divina Proportione, published in 1509. A recent and exhaustive analysis of Leonardo as a scientist by Frtjof Capra argues that Leonardo was a fundamentally different kind of scientist from Galileo, Newton, and other scientists who followed him, whom were more of specialized rather than diverse.

During his lifetime, Leonardo was highly valued as an engineer & a gifted inventor. He created mechanisms never thought of that had influenced people of average status to soldiers in the military. One of his famous inventions, still in use today, is an everyday tool – the scissor. He greatly advanced the state of knowledge in the fields of anatomy, civil engineering, optics, and hydrodynamics. After knowing Ludovico il Moro, Duke of Milan, he went on to produce many different projects for him, including the preparation of floats and pageants for special occasions, designs for a dome for Milan Cathedral, and a model for a huge equestrian monument. When Ludovico was overthrown, Leonardo fled Milan for Venice, where he was employed as a military architect and engineer, devising methods to defend the city from naval attack. He devised a system of moveable barricades to protect the city from attack. While in that position, Leonardo went on to create several maps, which were extremely rare at the time and it would have seemed like a new concept, even though only a few handful of people had seen and known how to use a map. When he returned to the Vatican in Rome, he made a mechanical lion which could walk forward, then open its chest to reveal a cluster of lilies, and also designed wings and shoes for walking on water. Da Vinci also invented musical instruments, such as a keyboard instrument with strings, which made sound via a wheel, horsehair strap, and a bow – a lot like a modern violin. His list of inventions rivals that of Thomas Edison, and continued to do so when building hydraulic pumps, reversible crank mechanisms, finned mortal shells, and even the steam cannon. Big leaps in thought were established during this ‘Da Vinci’ era.

Born in Vinci, Florence on April 15 1452, Leonardo di ser Piero Da Vinci, a man born with remarkable talents that some say transcends from God, displayed infinite grace in everything he did and cultivated his genius so brilliantly that all problems he studied were solved with ease. As Giorgio Vasari once stated, all his actions seem inspired and indeed everything he does clearly comes from God rather than from human skill.” As a painter, sculptor, architect, musician, mathematician, engineer, inventor, anatomist, geologist, cartographer, botanist, and writer, his works and accomplishments speak for themselves, and through extensive research there is no doubt that he is perhaps the greatest man to have ever lived that has influenced people of such broad perspectives. His death on May 2nd, 1519 only marked the beginning of a new era that has forever changed mankind. In 2003, American author Dan Brown based a fiction novel entitled “The Da Vinci Code”, that sold 80 million copies as of 2009, and went on to be produced into a blockbuster movie.