Saturday, May 29, 2010

SPOJ - Flower Growing

Recently solved problem #4477 - FLOWGROW.

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

Solution - Combinatorics

The hard part is to calculate the number of possibilities to fill one row of flowers; to obtain the final answer, raise this number to the number of rows.

Let S(c,n) be the number of ways to fill n columns with exactly c colours, when only c colours are available:

S(1,n) = 1

S(2,n) = 2n-2xS(1,n)

S(3,n) = 3n-3xS(2,n)-3xS(1,n)

S(4,n) = 4n-4xS(3,n)-6xS(2,n)-4xS(1,n)

S(5,n) = 5n-5xS(4,n)-10xS(3,n)-10xS(2,n)-5xS(1,n)

S(6,n) = 6n-6xS(5,n)-15xS(4,n)-20xS(3,n)-15xS(2,n)-6xS(1,n)

S(7,n) = 7n-7xS(6,n)-21xS(5,n)-35xS(4,n)-35xS(3,n)-21xS(2,n)-7xS(1,n)

The factors being numbers from Pascal's triangle.

To calculate T(c,n), the number of ways to fill n columns with at least c colours from all 7 available colours:

T(7,n) = S(7,n)

T(6,n) = T(7,n)+7xS(6,n)

T(5,n) = T(6,n)+21xS(5,n)

T(4,n) = T(5,n)+35xS(4,n)

T(3,n) = T(4,n)+35xS(3,n)

T(2,n) = T(3,n)+21xS(2,n)

T(1,n) = T(2,n)+7xS(1,n)

The factors being numbers from the seventh row of Pascal's triangle.

When there are less than 7 columns, some of the calculations are skipped; the second part is only carried on as far as needed.

Faster optimizations are possible.
Note, "Time limit: 0.100s - 1.5s".

Woohoo! 60 problems!

Sunday, May 23, 2010

From Strings to Ekpyrosis

I have been recently reading Neil Turok & Paul Steinhardt's new book "The Endless Universe - Beyond the Big Bang" which I bought at the Quantum to Cosmos festival held at Waterloo a few months ago. This book provides a fascinating glimpse into the process of cosmological and theoretical physics research. Both authors recount their personal history, their introduction to cosmology, and how they became involved in research related to the Big Bang theory. Overall, a great read for those anxious of physics related advancements since the 2000s. Here is a snippet of one of my favourite chapters.

Let’s talk physics history. An ever-so exciting tale of young physicists that changed the mindset of physics for decades to come since the late 1960s.

“Make everything as simple as possible but not simpler.” – Albert Einstein.

Nowhere was the optimism of particle physicists in the early 1980s more evident than at the annual Workshop on Grand Unification, known by the acronym WOGU (pronounced “whoa-goo”). Each spring the leading physicists, their postdoctoral fellows, and their students would gather at a different site to discuss the latest experimental breakthroughs and theoretical advances. Every year, the exciting presentations at WOGU seemed to engender new confidence that quantum field theory and grand unification were on track … until the fourth WOGU, when a soft spoken young theorist politely suggested that a sharp turn in the current thinking might be needed.

The meeting took place in April 1983 at the University of Pennsylvania, in Philadelphia, about fifty miles from Princeton, New Jersey, the home of Edward Witten. Only thirty-two years old at the time, he was already recognized as a theoretical physicist of great vision. For years, he had been a much admired pioneer in exploring the theoretical underpinnings of grand unification.

When Witten was invited by one of WOGU’s organizers to give a presentation, surprisingly, Witten was reluctant to accept. He explained that he was working on something new and was not sure the topic would be appropriate for a meeting on grand unified theories. That only made the prospect more intriguing, and so with persistence, Witten finally agreed to speak.

When the time came for Witten to talk, the last of the meeting, the auditorium was packed to standing room only. In his characteristic calm and gentle voice, Witten began by noting ways in which the current attempts at grand unification were failing. The most dramatic prediction, the instability of protons, had been tested, but no decays had been seen. The predictions of the masses of matter particles had also turned out wrong. Physicists could adjust the models to evade these problems, but only at the cost of adding ugly complications that made the whole framework implausible.

Witten then suggested that it might be time to consider a totally new approach. He proposed three guiding principles. First, the new approach should include gravity from the outset. Particle physicists were used to ignoring gravity because the gravitational attraction between elementary particles is normally negligible. However, when particles were smashed together at high energies, their collective mass rises in accordance with Einstein’s famous equations E = mc2, and the effects of gravity become stronger and stronger. At the very high energies where the strong and electroweak forces seem to merge into a single unified force, gravity is nearly as strong. For this reason, Witten argues, gravity has to be included in any theory of unification.

Dealing with gravity would be no easy task. Einstein had developed his theory of gravity in the early part of the twentieth century, at the same time that quantum theory was emerging. Despite all attempts, the two strands of physics had never been successfully joined. Einstein’s theory works tremendously well on large scales for describing gravity on the Earth, the solar system, and in the universe. But just like electromagnetism and light, gravity must be formulated in a way that is consistent with the laws of quantum physics in order to make sense on microscopic scales. For the other three forces, the quantum field approach had been spectacularly successful. But for gravity, every attempt to quantize Einstein’s theory had failed, leading to infinities, negative probabilities, or, at best, an infinite number of indeterminate parameters. A totally new approach was needed, one that would give a sensible answer.

Everyone in the audience knew about these difficulties in building a quantum theory of gravity. So all in attendance were naturally anxious to learn what Witten had in mind. Witten emphasized that he did not deserve credit for the idea he was going to suggest. Hard work had been done by a small, intrepid group of theorists working largely unnoticed and unappreciated. But Witten was now advocating, as his second principle, considering their daring proposal: a conceptual framework known as string theory.

Many in the auditorium had heard of string theory before, but most knew little about its history because it had had little impact on mainstream particle physics or cosmology up to that point. String theory had been developed in a rather roundabout way.

In 1968, Gabriele Veneziano at the European Organization for Nuclear Research (CERN) had proposed a formula for describing the scattering of nuclear particles interacting via the strong nuclear force. In 1970, Yoichiro Nambu at the University of Chicago, Holger Nielsen at the Niels Bohr Institute in Copenhagen, and Leonard Susskind, then at Belfer Graduate College in Israel and now at Stanford University, showed that Veneziano’s formula could be interpreted as a model of vibrating one-dimensional strings. Unfortunately, it was soon discovered that the model had various pathologies, such as a tachyon, a physically impossible particle that moves faster than light. But this problem was cured as people realized that string theory was much more than a theory of nuclear particles. First, Joel Scherk at the Ecole Normale Superieure in Paris and John Schwarz at the California Institute of Technology showed that string theory included a particle behaving like a graviton, the troublesome quantum of Einstein’s theory of gravity. Then, by incorporating matter particles using a powerful new quantum symmetry called super-symmetry, Scherk with David Olive and other physicists managed to construct a completely consistent model with no tachyon.

In this way, the theory originally designed to describe the strong nuclear force was suddenly transformed into a unified theory with the potential to describe all the forces and particles in nature, including quantized gravity. But these developments went largely unnoticed. The 1970s were the heyday of quantum field theory, and string theory was seen as a speculative backwater. A few lonely theorists continued to struggle to develop the theory and iron out its remaining mathematical difficulties. This was a daunting and slow process, since few people were willing to risk working on the subject.

Witten’s talk went on to describe the advantages of reinterpreting elementary particles as tiny spinning bits of string. Just as Einstein pictures three-dimensional space as an elastic substance that can be stretched and distorted, you can think of string as a geometrical curve with no width that can bend and turn in all possible ways, like an infinitely thin strand of rubber. The string is perfectly elastic, so it can shrink to a point or be stretched out to an arbitrary length. If you stretch a piece of string out in a straight line, the free ends pull together with a fixed force called the string tension.

Some of the properties of string are actually very similar to those of cosmic strings. But whereas cosmic strings are really twisted-up configurations of fields with a minuscule but finite width, fundamental strings are ideal one-dimensional mathematical curves.

The string picture is beautiful in that one basic entity – string – can potentially account for the myriad of elementary particles observed in nature. Bits of string vibrate and spin, in certain specific quantized motions. Each new quantized state has a set of physical attributes: mass, charge, and spin. The little pieces of string describing photons, electrons, or gravitons are far too tiny to be seen, much less than a trillionth the diameter of a proton. To us, they appear like pointlike particles. But if string theory is correct, the masses, charges, ad spins of these little bits of string should precisely match the physical properties of all of the particles ever discovered.

Witten was especially attracted to this picture because it included gravitons as a hidden bonus, as Scherk and Schwarz had first shown. Bits of string with two free ends could account for all known types of matter particles. But the mathematics of string also allows for closed loops, like tiny elastic bands. When vibrating and spinning in just the right way, these loops have the same properties as gravitons, the quanta of the gravitational field. Even better, while calculations assuming pointlike particles and gravitons give nonsensical, infinite answers, calculations for stringy particles and loopy gravitons produce sensible, finite results. Although not designed for the purpose, string theory appears to automatically incorporate a theory of quantum gravity without infinities.

The reason string theory works where the particle description of quantum field theory fails can be explained by simple geometry. If two pointlike particles collide, their energy is concentrated at a point. Such pileups of energy cause a large gravitational field, curving space and drawing even more energy into the region. A runaway process ensues in which space curls up irretrievably into a tinier and tinier knot: a singularity. This catastrophe leads to mathematical infinities signaling a breakdown of the theory. On the other hand, if particles are tiny vibrating strings, their energy is spread out. If a collision causes a momentary pileup of energy, the string rapidly wriggles away and spreads out the energy, preventing the gravitational distortion from concentrating in one spot. Calculations of what happens when two bits of string collide, join, and break apart again give sensible, finite results. There are no singularities, and no infinities.

Witten’s third guiding principle dealt with the major hitch theorists had previously discovered about string theory. The equations describing the quantized vibrations of strings give sensible answers only if the number of spatial dimensions is nine. Nine!? To most physicists, this seemed absurd. Why study a theory that predicts six extra dimensions of space that have never been seen?

Witten addressed the problem of extra dimensions head-on: Learn to live with them, he said. Just accept the six extra dimensions of string theory; they are an essential aspect of the geometry of the universe. He reminded the audience that back in the 1920s the Swedish physicist Oskar Klein, building on the work of the German physicist Theodor Kaluza, had dreamed up a way of linking Maxwell’s electromagnetic theory with Einstein’s theory of gravity, in a model of the universe where one extra dimension of space was hidden from view.

To see how this works, consider the surface of a long soda straw. From a long distance away, it appears to be one-dimensional because you cannot detect its thickness. But up close, you can see the surface of the straw. To prove to yourself that the surface is two dimensional, slit the straw along its length and flatten it out. You will get a rectangle, a shape that is obviously two dimensional because it has both length and width.

Klein supposed that in addition to the three familiar dimensions of height, width, and length, there is a fourth dimension of space that is curled up in a circle so tiny that it cannot normally be seen. Kaluza and Klein’s remarkable discovery was that Einstein’s theory of gravity in four space dimensions, with one of the dimensions curled up as described, contained both Einstein’s theory of gravity in the remaining three extended dimensions and Maxwell’s theory of electromagnetism. Electric and magnetic fields arise, in this picture, from a “twisting” of the small extra dimension as you move along one of the large everyday dimensions.

According to Witten, theorists simply had to adapt Klein’s idea to the six extra spatial dimensions in string theory. There is no problem having strings wiggle in nine spatial dimensions, so long as six of the spatial dimensions are too small to be seen.

The extra dimensions would exist at every point in three-dimensional space. As an analogy, I’m going to use a rather famous one - consider a pile carpet made of woolen loops. To us, looking from above, it appears as a two-dimensional surface. But to an ant it seems like a huge forest of loops. At any point, the ant can choose to run along the direction of the floor, that is, along one of the two extended dimensions, or around one of the woolen loops that describe the curled-up dimension. In the same way, the extra dimensions in Kaluza and Klein’s approach are invisible, because their tiny size is too small to be seen. But in principle, with a very powerful microscope using very short wave-length radiation, one would be able, like the ants on the pile carpet, to see the convoluted structure of the extra dimensions on tiny length scales.

Witten framed his lecture carefully and peppered it with qualifications, but his message was clear. In a mere forty minutes, he made a compelling case that theories of grand unification were incomplete and that gravity, strings, and extra dimensions ought to be considered. Research on the fundamental laws of physics could be headed toward a revolution, he quietly suggested. You could have heard a pin drop in the auditorium as many physicists described. The audience was stunned, unsure how seriously to take Witten’s remarks.

Through the remainder of 1983, there were few signs that anything was going to change. During the Aspen summer workshop that year, for example, the talk was almost all about grand unification and field theory. But, sure enough, Witten’s lecture was the harbinger of a revolution that would soon sweep the world. The “first string revolution,” as it has been called, was ignited a year later at the 1984 Aspen workshop when Michael Green, then at Queen Mary College, London (now at Cambridge), and John Schwarz overcame a key mathematical roadblock in the construction of realistic string theories.

Until that point, there were many versions of string theory with different ways of folding the extra dimensions, but they all seemed to be fatally flawed. Witten had recently shown that many versions of string theory are unacceptable because they violate the conservation of energy through a quantum effect known as an anomaly. Green and Schwarz’s breakthrough was the identification of a special version of string theory that had realistic matter particles and no anomalies. Now, for the first time, one could point to a quantum theory that incorporated gravity and other forces and gave finite, sensible answers.

Working at Princeton, David Gross, one of the leading pioneers of unified quantum field theories (now director of the Kavli Institute for Theoretical Physics in Santa Barbara), along with Jeffrey Harvey and Emil Martinec (both now at the University of Chicago) and Ryan Rohm (now at Boston University) produced a compelling example known as heterotic string theory. The word heterotic, meaning hybrid, was added because it combined different versions of string theory to obtain one that has more of the ingredients needed to make a realistic theory of elementary particle physics. (A later, further improved form, heterotic M theory, was the stimulus for the Cyclic model of the universe.) These successes, and others that followed in rapid succession, captivated the international community of theoretical physicists. Almost overnight, it seemed, the focus of research shifted from particles to strings. And the merger of fundamental physics and cosmology that had seemed imminent in 1983 was put on hold.

On an unrelated note, i'm going to be posting less often as exam season is approaching. Oh the suspense ... Hooray for new banner & layout!

Saturday, May 22, 2010

SPOJ - Rectangles Counting

Recently solved problem #3890 - MRECTCNT.

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

Solution

Count the number of pairs
(a,b), a ≤ b and a + b - GCD(a,b) = squares.

Note: Monkey counting is fast enough.

My SPOJ account

Champions League Finals 2010 & Missing World Cup Stars

If you know me, you would know I am a major football fanatic - on & off the field. I also enjoy American football, however, it is football season now, and the 2010 FIFA world cup is just around the corner. Excited?

Today was the final match of the UEFA Champions League between Bayern Munich and Inter Milan. Though I am not a great fan of either clubs, I was rooting for Inter Milan mainly because it took them another 45 years to make the finals, which was quite inspirational.

The match was spectacular, and in the end Inter Milan won 2-0 as Jose Mourinho wrote his name into the history books as Diego Milito inspired Inter Milan to Champions League glory against Bayern Munich at Bernabeu stadium. The MVP of the game is no doubt Diego Milito, whom scored both goals, and with several other assists throughout the game. I believe the main reason why Inter Milan won was of their great defense system, rivaling that of Bayern Munich's strong offensive - the secret weapon being Arjen Robben.


Inter Milan celebrate their first European Cup victory since 1965

A classic rivalry and great match up. For more visit here.

World Cup 2010

If you are a fan of football, you would know by now that a number of great players will not be attending the 2010 games. Some of them being:
This is very disappointing, as my favourite player (Ronaldinho) will not be able to go even though he is at his prime.

I'm not sure how great this years world cup will be, but i'll remain optimistic nonetheless.

Therefore, I am now certain Argentina will be a top contender to win this years world cup. Why? Lionel Messi of course! I could be wrong though.

On an unrelated note, Nike has made yet another spectacular commercial for this special occasion. Enjoy:


I hope to post regular thoughts & opinions on the World Cup 2010 matches when it begins on June 11th. Stay tuned!

Tuesday, May 18, 2010

Exploring The World

It's early in the morning and i'm currently working on an essay based upon the great renaissance man, Leonardo da Vinci. Being me however, I got sidetracked due to my imagination.

One of my life long dreams is to one day get the opportunity to travel around the world. And yes, so do 6 billion other people. But let's see how this is gonna go ...

Ever since I was a kid, my father told me stories of him going around the world and the experiences he had with different cultures. I was inspired and eager to one day do the same.

Now, when one usually says "I want to travel around the world", automatically, thoughts of iconic monuments, sculptures, landscapes, and cultural people come to mind. And sure, those are all great things to experience, but I want to go beyond ordinary travel experience and understand the differences and similarities between each unique lifestyle. The world is truly a utopia, and being encompassed in one region, one cannot appreciate & explore the beauty that is beyond ones 'borders'. I want to meet people of all cultures, explore foreign lands, and experience what my life would be like had I not been fortunate enough to be here. There is a whole other universe out there, and I want to observe & be awed by the nature surrounding it.

A few years later, when I was able to write and follow the globe, I began a list of all the places I would one day like to visit. I was a kid yearning for adventure. As the years passed, this list kept growing. This morning however, I don't know what came over me, but I decided to type it all out in a .txt file, and make a quick program to sort them. I believe I have a substantial knowledge of world geography & attractions, and so, here's a compiled a list (in alphabetical order) of places I would one day like to visit (excluding Canada - That's another list by itself):

  • Abu Simbel, Egypt
  • Agra, India
  • Ala Archa Gorge, Kyrgyzstan
  • Alhambra, California
  • Amsterdam, The Netherlands
  • Angor Wat, Cambodia
  • Antseranana, Madagascar
  • Area 51, Nevada
  • Athens, Greece
  • Atlanta, Georgia
  • Auckland, New Zealand
  • Auki, Solomon Islands
  • Austin, Texas
  • Bandar Seri Begawan, Brunei
  • Bangkok, Thailand
  • Batik, Morocco
  • Beijing, China
  • Bengal Jungle, India
  • Berlin, Germany
  • Boulders Beach, South Africa
  • Brisbane, Australia
  • Brussels, Belgium
  • Buenos Aires, Argentina
  • Cairo, Egypt
  • Cambridge, Massachusetts
  • Cape Town, South Africa
  • Cape of Good Hope, South Africa
  • Chakachino, Zambia
  • Chicago, Illinois
  • Chichen Itza, Mexico
  • Christmas Island, Australia
  • Chuuk, Micronesia
  • Cologne, Germany
  • Dubai, United Arab Emirates
  • Dublin, Ireland
  • East Jerusalem, West Bank
  • Easter Islands, Chile
  • Ephesus, Turkey
  • Galapagos Islands, Ecuador
  • Giant's Causeway, Northern Ireland
  • Golden Temple, India
  • Grand Canyon, Arizona
  • Great Barrier Reef, Australia
  • Great Wall Of China, China
  • Gurgaon, India
  • Half Moon Caye, Belize
  • Haute-Piccardie, France
  • Hawaii, USA
  • Hong Kong, China
  • Impenetrable Forest, Uganda
  • Istanbul, Turkey
  • Kilimanjaro Summit, Tanzania
  • Kish Island, Iran
  • Kjeragbolten, Norway
  • Kuwait City, Kuwait
  • Lancelin, Australia
  • Las Vegas, California
  • Lemur Island, Madagascar
  • Lisbon, Portugal
  • Lisse, The Netherlands
  • London, England
  • Los Angeles, California
  • Luang Prabang, Laos
  • Machu Picchu, Peru
  • Madrid, Spain
  • Male, Maldives
  • Mexico City, Mexico
  • Miami, Florida
  • Mokolodi, Botswana
  • Monte Alban, Mexico
  • Montreal, Quebec
  • Monument Valley, Arizona
  • Moscow, Russia
  • Mulindi, Rwanda
  • Mumbai, India
  • Munich, Germany
  • Mutianyu, China
  • Neko Harbor, Antarctica
  • Nellis Airspace, Nevada
  • New York, New York
  • Panama Canal, Panama
  • Paris, France
  • Paro, Bhutan
  • Persepolis, Iran
  • Petra, Jordan
  • Poria, Papua New Guinea
  • Prague, Czech Republic
  • Pretoria, South Africa
  • Princeton, New Jersey
  • Rio de Janeiro, Brazil
  • Rock Islands, Palau
  • Rome, Italy
  • Routeburn Valley, New Zealand
  • Salar de Uyuni, Bolivia
  • San Francisco, California
  • Sana'a, Yemen
  • Sao Paulo, Brazil
  • Seattle, Washington
  • Seljalandsfoss, Iceland
  • Seoul, South Korea
  • Shiraz, Iran
  • Siberia, Russia
  • Singapore, Singapore
  • Sossusvlei, Namibia
  • South Shetland Islands, England
  • Soweto, South Africa
  • Stockholm, Sweden
  • Stone Town, Zanzibar
  • Stonehenge, England
  • Suhbaatar, Mongolia
  • Sydney, Australia
  • Tagaytay, The Phillipines
  • Taipei, Taiwan
  • Tel Aviv, Israel
  • Teotihuacan, Mexico
  • The South Island, New Zealand
  • Thimphu, Bhutan
  • Tikal, Guatemala
  • Timbaktu, Mali
  • Tokyo, Japan
  • Tongatapu, Tonga
  • Tsavo, Kenya
  • Uluru, Australia
  • Vava'u, Tonga
  • Venice, Italy
  • Very Large Array, New Mexico
  • Victoria Falls, Zimbabwe
  • Wadi Rum, Jordan
  • Wainivilase, Fiji
  • Warsaw, Poland
  • Washington D.C, USA
  • Yangon, Myanmar
  • Yosemite National Park, Nevada

Note: I have already visited some of the places mentioned above. However, I'd like to visit them once more - Why not?

In 1971, a French ethnomusicologist recorded a traditional folk song in the Solomon Islands, near Papua New Guinea. The song, Rorogwela, was sung by a young women named Afunakwa. In 1992, Rorogwela was sampled by Deep Forest and used in a song called "Sweet Lullaby". The song became an international pop hit, selling over 3 million copies.

Enjoy this traditional folk song - it's really unique even if you don't necessarily understand it.



Though this dream is not a realistic option for me, I am somewhat of an optimistic environmentalist, and therefore, in the future I will do everything in my limited power to make this dream come true and explore all different kinds of environments and have a new grasp on how beautiful the world really is and why it should be preserved & protected.

Sunday, May 16, 2010

Great People In History I - Julius Caesar

I have always had a great instilled pride for my knowledge of history, and how human civilizations have advanced in such great measures throughout its course in time. I am currently taking a course on Ancient History (up to 1600's) and I had written a report on a rather famous Roman Leader. I'm hoping once in a while I can add other posts on "Great People In History" that have forever printed themselves in historical texts. Let this be the first in the series to come.

Julius Caesar was the most famous Roman leader of all, conquered more land than any other Roman, and had a celebrated love affair with the Egyptian empress Cleopatra. He had no need of a kingly title. He had the power, he had the trappings, he had everything he essentially wanted - He didn't need a mere word in order to satisfy his vanity.

For 2000 years, the name "Caesar" has meant "Majesty in Power". His life inspired the rulers of empires to call themselves Caesar, Czar, and Kaiser. Ruthless ambition fueled his cline to power. Caesar stopped at nothing to achieve his goals. Conquest and genocide were his political tools. His reign led to the death of a republic and the birth of an empire.

As a young man Caesar learned about the legendary founding’s of Rome. He was instilled with a deep pride for its history. King's had been overthrown, a republic created, and the cities of Italy sucked into an ever growing territory.

Caesar was born into a prominent Roman family, and was only 15 years old when he accompanied his father to the forum, the seat of government in ancient Rome. It was an early taste of a life to come. As a member of the Roman ruling class, a political career was his destiny.

In the 200 years before his birth, Rome had conquered Greece, Spain, modern day France, and vast tracks of North Africa. It had made Rome very rich, but the speed of change made Rome politically unstable and treacherous.

Even as a teenager, his steely determination shown through. The impression we get is that he is a very independent minded individual. Caesar was always very matriculate about the way he appeared, very vain in fact, his already dressing in an unusual way, setting himself apart from his contemporaries.

When he was just 16 Caesar came to the attention of Sulla, then dictator of Rome - An enemy of Caesar's family. Caesar had made a political marriage. It was a union Sulla violently opposed and one that could have caused Caesar his life. It was remarkable that he stood up to Sulla, whom is an extremely ruthless individual. This shows Caesar's astonishing determination.

Soon after the death of his wife, Marius, Caesar went into exile. In Asia minor Caesar used his exile to make his name in battle. Caesar returned to Rome when Sulla died in 78 BC. Increasingly renowned for his skill and bravery in battle, he was decorated with a corona sivica. It was time for Caesar to pursue his political ambitions. He deliberately cultivated key allies in the violent world of Roman politics. Caesar became a lawyer, and over the next few years championed the rights of ordinary Roman's. He knew that the votes of the people would be the key of his future success. He had his sights set on the first step on the political power liner, pontifex maximus, high priest of Rome. Once he secured that position, he became one of the elite leaders of Rome. He had hit big time.

However, Caesar knew military victory's was what really counted in Roman politics. Caesar won a lucrative posting as governor of Spain, where he conquered and subdued the north west of the province.

Back in Rome, Caesar was now famous both as a soldier and a speaker, and was elected as one of the two heads of Roman government. He truly set the standard of what a leader really is. Although Caesar's consulship generated a lot of controversy, he was rewarded with a nine year campaign, during which Caesar would make his name as a brilliant general. Caesar the consul became Caesar the Conqueror.

"Veni, vidi, vici" - "I came, I saw, I conquered".

Caesar's ambition was boundless, not content to just one region, but he wanted more. Northern Italy, modern day Switzerland, Germany, Belgium, and even Britain were all in his sights.

Command of an army came naturally to Caesar. His physical presence during battle inspired total confidence, and it was said the sight of his red cloak was the equivalent of another legion. He was a superstar, respected and highly popularized.

Caesar knew he now had the power to seize Rome by force. It was exactly what his enemies had dreaded, and something punishable by death.

What he did next is why legends exist to this day.

He stormed through Italy initially with one single legion. It was them vs. the world. Victory was quick to come by.

In 44 BC he was elected dictator - For life. He was issued coins with his face on it, statues of him that were adored like those of the gods, and even reformed the calendar and named the month of July after himself, along with the Julian calendar. As they say, "Caesar dictates when the sun rises, and when it sets".

On the 15th of March, 44 BC, three days before he was due to leave for military campaign in Syria, Caesar attended the senate, having no idea he was walking into a murderous conspiracy.

As a conspirator moved in to talk to him, it was the signal for attack, and dagger after dagger plunged into Caesar's flesh. And even as he died, he put the Toga over his head, still concerned of his status to his people.

Gaius Julius Caesar transformed Rome from a growing republic into a mighty empire, which encompassed most of the known world. As Caesar had said, "I have lived long enough, whether measured in years, or in glory".

His life became a legend that has continued undiminished for more than 2000 years.

David Cameron - New British PM

Though the hype was perhaps a bit exaggerated for any real opinions to be expressed, I have rather mixed feelings about David Cameron - now Britain's new Prime Minister and the head of Britain's first coalition government since WWII. A well educated Oxford graduate & a classic "progressive" conservative.

A few promises that he intends to keep:

1) Cut off $9 billion (six billion pounds) in government spendings. (Another Recession?)

2) Agreed to a national referendum on electoral reform.

3) Agreed on fixed-term, five-year parliamentary terms – a pledge that, if Canada’s experience is any guide, may not be as firm as it sounds.

4) National Health Service, Britain’s version of medicare.

He certainly seems like the better choice than the centre-left politician Gordon Brown, to which he was PM since 2007, and a rather moderate one to say the least. And of course, the centrist to centre-left Liberal Democratic, Nick Clegg - Now the deputy PM, and fellow coalitionist.

He seems to be focusing on deficit reduction rather than employment growth. Only in time shall we see how the economic prospectus prospers, or utterly fails like that of the great depression.

Here is an interview of some of his hopes for Britain's new Coalition party:

Saturday, May 15, 2010

SPOJ - Brackets Parade

Recently solved problem #4202 - BRPAR.

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

Solution: Catalan numbers & number of permutations.

The number of ways to order n pairs of matching brackets is

i.e. The Catalan numbers.

The number of ways to order n things of m different types, where there are a1, a2,..., am things of each type is

i.e. The number of permutations.

When multiplying, we can divide out n! and have:
Numerator = (2n)!
Divisor = (n+1)!a1!a2!...am!

We can calculate both quantities using modular multiplication, calculate the modular inverse of the divisor and then the modular product is the required answer.

This modular inversion uses the fact that and applies repeated squaring to calculate the exponentiation. We could have used extended Euclid instead.

Maybe one could have solved it by following the logical steps the problem outlined. Though I doubt it'll pass the time limit required. I, however, find this solution more fun.

My SPOJ account

Back to the future

Groing up, I have always pondered on what the future holds. What will the future bring? If the inflationary model is correct, all of us live on a planet that is lost in the multiverse. Almost nowhere, are the physical conditions like those we observe. And our rare pocket of the universe is running out of time. Dark energy has already overtaken all other forms of matter and radiation, and has taken command of the expansion of the universe.

In a trillion years, our home will be well on its way toward a vacuous oblivion. Virtually all the galaxies we see today will still exist, but the stars will be gradually burning out. There will in all likelihood still be stars, planets, and life. But the accelerated expansion due to dark energy will have spread out the galaxies so much that nothing beyond the Andromeda Galaxy be visible to us.

The surviving civilizations in the Milky Way will know from the historical record that the universe was once filled with billions of galaxies, which emerged from tiny fluctuations in a hot plasma uniformly spread over space. But all the observational clues available today will be long gone by then. It is hard to imagine that a newly emerging civilization could piece together cosmic history on its own. In the inflationary model, therefore, the present is a unique epoch in the evolution of the universe where we can see both substantial amounts of the matter and radiation that dominated our past and the dark energy that will dominate our future. At other epochs, only one or the other would be detectable.

The same trillion-year prospectus applies if the Cyclic model is correct, but it holds nearly everywhere in space, not just in isolated pockets. After a trillion years, however, the story changes dramatically. The branes begin to approach each other, the dark energy decreases, and expansion slowly grinds to a halt. There will be no galaxies or other distant sources that future observers can use to detect the expansion rate, unless the future civilizations send regular test probes beyond the Milky Way. Yet there will be some novel physical effects to indicate that the end of the cycle is near. First, many fundamental physical constants of nature, like the strength of gravity and the strong, weak, and electromagnetic forces, will begin to change noticeably because their values depend on the separation between the branes. They don’t change during earlier stages, like today, because the brane separation is frozen. That is why they are interpreted as constants of nature. However, once the branes start to rush toward each other, all the physical constants will start to change in concert. A number of sensitive experiments exist today that monitor these constants and search for time variation. So far, no conclusive evidence for change has been found. According to the cyclic model, physicists performing those same experiments during the last 10 billion years before the next brane collision would detect a large variation of the constants, whose rate would increase as the branes speed up. In the final moments before the crunch, the rapid changes would become dramatic: particles would lose their mass and the laws of nature would be restored to a much simpler and more symmetrical form.

In reality, what is happening is that something enormous is approaching fast along a dimension we cannot see. The realization will come in a flash when, suddenly, everywhere in space lights up with new matter and radiation from the collision. The temperature soars to 10^15 times the surface temperature of the sun, evaporating any remnant structures from the previous cycle. The quarks and gluons of which we all are made join the flood of new quarks and gluons created at the bang, and the cycle of the cosmos is renewed.

One Hundred Years

The cosmological debate between the inflationary and the cyclic models is only just beginning to simmer in the scientific community. Many cosmologists have not yet given the issue much consideration because they see no reason for thinking about an alternative until some observation or experiment contradicts the inflationary picture. Others are reluctant to consider a model so deeply rooted in concepts like extra dimensions or branes because they regard these ideas as too far-fetched, even though string theorists are finding these concepts to be essential for unifying our understanding of the fundamental forces. In fact, contemporary versions of the inflationary model are now using the same stringy building blocks.

The reluctance of some to introduce so many new elements into cosmology is understandable. Science usually advances through small variations on an established idea. Radically new directions are not considered unless the scientific case is compelling. For that to happen, the problems with the conventional picture (which might be swept under the rug if there were no competing idea) have to become recognized, and the novel components underlying the new approach have to become familiar. Historically, this conservative approach has served science well, enabling it to make steady progress without getting diverted. In cosmology, for example, the main elements of the current inflationary model – the big bang picture, inflationary expansion, dark matter, and dark energy – were all subject to the same resistance when they were first introduced, and it took many years for them to be accepted.

The cyclic model, if it is worthy, will require similar patience. As discussions and investigations of the cyclic picture continue over the next few years and some of the weaknesses of the inflationary model become more exposed, interest will grow. The fact that two such dissimilar models can predict such similar results is too intriguing to ignore. Creative experiments will feel compelled to mount the decisive test between the two views of cosmic history because the issues at stake are too captivating to be ignored.

In settling the debate, cosmologists will have come to grips with the most fundamental questions about space and our place in the cosmos; about time and our moment in cosmic history; and about nature and our ultimate ability to figure out its laws. The answers will be our legacy to future generations. One hundred years from now, they will be taught to every schoolchild. They will permeate human discourse and inform our philosophical and religious views. And they will motivate many of the scientific advances of the twenty-second century.

Every elementary science textbook will include the WMAP snapshot or some improved image of the cosmic background radiation across the sky. The authors of the textbook will point to it as one of the great achievements of the twenty-first century. What will they claim about its significance?

If the inflationary model is proven correct, they will write that the image shows primordial wrinkles created at the end of inflation, about 10^-35 seconds after the big bang, when the temperature of the universe was about 10^27 degrees. The universe had a beginning of some sort, perhaps the big bang, but the period of rapid expansion diluted all information about what happened before inflation. Because human-made particle accelerators cannot possibly reach the energies needed to probe conditions before inflation, there is a limit to how much we can learn through observations or experiments about the fundamental laws of the universe. If the inflationary landscape picture survives, it may be impossible to discover the secrets of the universe because everything we see, no matter how far we look, has little in common with the rest of the cosmos, which consists of a combination of inflating regions and pocket universes with different physical properties. As for our own island, the likely outcome is that we are approaching a vacuous, uninhabitable state that will last forever. Perhaps we live in a misanthropic universe.

If the cyclic model proves to be correct, the textbook authors will write that the image shows the splatter of matter and radiation created at the big bang itself. The big bang was not the beginning but the moment separating our current period of expansion and cooling from a previous one. They will explain that the universe has an extra dimension, that the extra dimension is bounded by branes, and that the branes collided with each other to create the bang. They will show how the image can be used to determine the collision speed of the branes and to check that all the matter and radiation we see was created by the collision.

They will write that the WMAP image is also a window on the previous cycle. The small wrinkles in distribution of matter and energy were created billions of years before by random quantum waves that spontaneously appeared on the surfaces of the branes. A similar effect is beginning now that will eventually give birth to new galaxies and new stars in the next cycle. Because conditions everywhere in the universe are similar to what we observe here and because we can collect observable and measureable traces from an entire cycle, the whole cosmos can be comprehended from our single vantage point.

In 2010, it is too early to say which, if any, of these models will appear in the textbooks of the next century. But all of us can watch as a new theory blossoms into maturity and a mature theory is reinvigorated by the challenge. We can have the fun of debating the two visions of the universe and weighing in with our personal convictions while the matter remains in doubt. And we can do all this secure in the knowledge that the debate will not be endless.

Sunday, May 9, 2010

Top 10 Beautiful Physics Experiments

This is why I prefer theoretical physics ...



Source

1. Double-slit electron diffraction

The French physicist Louis de Broglie proposed in 1924 that electrons and other discrete bits of matter, which until then had been conceived only as material particles, also have wave properties such as wavelength and frequency. Later (1927) the wave nature of electrons was experimentally established by C.J. Davisson and L.H. Germer in New York and by G.P. Thomson in Aberdeen, Scot.

To explain the idea, to others and themselves, physicists often used a thought experiment, in which Young's double-slit demonstration is repeated with a beam of electrons instead of light. Obeying the laws of quantum mechanics, the stream of particles would split in two, and the smaller streams would interfere with each other, leaving the same kind of light- and dark-striped pattern as was cast by light. Particles would act like waves. According to an accompanying article in Physics World, by the magazine's editor, Peter Rodgers, it wasn't until 1961 that someone (Claus Jönsson of Tübingen) carried out the experiment in the real world.



2. Galileo's experiment on falling objects

In the late 1500's, everyone knew that heavy objects fall faster than lighter ones. After all, Aristotle had said so. That an ancient Greek scholar still held such sway was a sign of how far science had declined during the dark ages.

Galileo Galilei, who held a chair in mathematics at the University of Pisa, was impudent enough to question the common knowledge. The story has become part of the folklore of science: he is reputed to have dropped two different weights from the town's Leaning Tower showing that they landed at the same time. His challenges to Aristotle may have cost Galileo his job, but he had demonstrated the importance of taking nature, not human authority, as the final arbiter in matters of science.



3. Millikan's oil-drop experiment

Oil-drop experiment was the first direct and compelling measurement of the electric charge of a single electron (1.602176487×10^−19 C). It was performed originally in 1909 by the American physicist Robert A. Millikan. Using a perfume atomizer, he sprayed tiny drops of oil into a transparent chamber. At the top and bottom were metal plates hooked to a battery, making one positive (red in animation) and the other negative (blue in animation). Since each droplet picked up a slight charge of static electricity as it traveled through the air, the speed of its motion could be controlled by altering the voltage on the plates. When the space between the metal plates is ionized by radiation (e.g., X rays), electrons from the air attach themselves to oil droplets, causing them to acquire a negative charge. Millikan observed one drop after another, varying the voltage and noting the effect. After many repetitions he concluded that charge could only assume certain fixed values. The smallest of these portions was none other than the charge of a single electron.



4. Newton's decomposition of sunlight with a prism

Isaac Newton was born the year Galileo died. He graduated from Trinity College, Cambridge, in 1665, then holed up at home for a couple of years waiting out the plague. He had no trouble keeping himself occupied.

The common wisdom held that white light is the purest form (Aristotle again) and that colored light must therefore have been altered somehow. To test this hypothesis, Newton shined a beam of sunlight through a glass prism and showed that it decomposed into a spectrum cast on the wall. People already knew about rainbows, of course, but they were considered to be little more than pretty aberrations. Actually, Newton concluded, it was these colors — red, orange, yellow, green, blue, indigo, violet and the gradations in between — that were fundamental. What seemed simple on the surface, a beam of white light, was, if one looked deeper, beautifully complex.



5. Young's light-interference experiment

Newton wasn't always right. Through various arguments, he had moved the scientific mainstream toward the conviction that light consists exclusively of particles rather than waves. In 1803, Thomas Young, an English physician and physicist, put the idea to a test. He cut a hole in a window shutter, covered it with a thick piece of paper punctured with a tiny pinhole and used a mirror to divert the thin beam that came shining through. Then he took "a slip of a card, about one-thirtieth of an inch in breadth" and held it edgewise in the path of the beam, dividing it in two. The result was a shadow of alternating light and dark bands — a phenomenon that could be explained if the two beams were interacting like waves. Bright bands appeared where two crests overlapped, reinforcing each other; dark bands marked where a crest lined up with a trough, neutralizing each other.

The demonstration was often repeated over the years using a card with two holes to divide the beam. These so-called double-slit experiments became the standard for determining wavelike motion — a fact that was to become especially important a century later when quantum theory began.



6. Cavendish's torsion-bar experiment

The experiment was performed in 1797–98 by the English scientist Henry Cavendish. He followed a method prescribed and used apparatus built by his countryman, the geologist John Michell, who had died in 1793. The apparatus employed was a torsion balance, essentially a stretched wire supporting spherical weights. Attraction between pairs of weights caused the wire to twist slightly, which thus allowed the first calculation of the value of the gravitational constant G. The experiment was popularly known as weighing the Earth because determination of G permitted calculation of the Earth's mass.



7. Eratosthenes' measurement of the Earth's circumference

At Syene (now Aswan), some 800 km (500 miles) southeast of Alexandria in Egypt, the Sun's rays fall vertically at noon at the summer solstice. Eratosthenes, who was born in c. 276 BC, noted that at Alexandria, at the same date and time, sunlight fell at an angle of about 7° from the vertical. He correctly assumed the Sun's distance to be very great; its rays therefore are practically parallel when they reach the Earth. Given estimates of the distance between the two cities, he was able to calculate the circumference of the Earth. The exact length of the units (stadia) he used is doubtful, and the accuracy of his result is therefore uncertain; it may have varied by 0.5 to 17 percent from the value accepted by modern astronomers.



8. Galileo's experiments with rolling balls down inclined planes

Galileo continued to refine his ideas about objects in motion. He took a board 12 cubits long and half a cubit wide (about 20 feet by 10 inches) and cut a groove, as straight and smooth as possible, down the center. He inclined the plane and rolled brass balls down it, timing their descent with a water clock — a large vessel that emptied through a thin tube into a glass. After each run he would weigh the water that had flowed out — his measurement of elapsed time — and compare it with the distance the ball had traveled.

Aristotle would have predicted that the velocity of a rolling ball was constant: double its time in transit and you would double the distance it traversed. Galileo was able to show that the distance is actually proportional to the square of the time: Double it and the ball would go four times as far. The reason is that it is being constantly accelerated by gravity.



9. Rutherford's discovery of the nucleus

When Ernest Rutherford was experimenting with radioactivity at the University of Manchester in 1911, atoms were generally believed to consist of large mushy blobs of positive electrical charge with electrons embedded inside — the "plum pudding" model. But when he and his assistants fired tiny positively charged projectiles, called alpha particles, at a thin foil of gold, they were surprised that a tiny percentage of them came bouncing back. It was as though bullets had ricocheted off Jell-O. Rutherford calculated that actually atoms were not so mushy after all. Most of the mass must be concentrated in a tiny core, now called the nucleus, with the electrons hovering around it. With amendments from quantum theory, this image of the atom persists today.





10. Foucault's pendulum

Last year when scientists mounted a pendulum above the South Pole and watched it swing, they were replicating a celebrated demonstration performed in Paris in 1851. Using a steel wire 220 feet long, the French scientist Jean-Bernard-Léon Foucault suspended a 62-pound iron ball from the dome of the Panthéon and set it in motion, rocking back and forth. To mark its progress he attached a stylus to the ball and placed a ring of damp sand on the floor below.

The audience watched in awe as the pendulum inexplicably appeared to rotate, leaving a slightly different trace with each swing. Actually it was the floor of the Panthéon that was slowly moving, and Foucault had shown, more convincingly than ever, that the earth revolves on its axis. At the latitude of Paris, the pendulum's path would complete a full clockwise rotation every 30 hours; on the Southern Hemisphere it would rotate counterclockwise, and on the Equator it wouldn't revolve at all. At the South Pole, as the modern-day scientists confirmed, the period of rotation is 24 hours.





On an unrelated note, my friend Yara has just started his own blog - "The Inquiring Mind". I have conveniently added a non-edible link to his blog on my "Blogroll" tab. Check it out!

Also, congratulations to my friends Brian & Cyril for making the official & unofficial teams of Canada for this years IOI, held in University of Waterloo. Sadly, Cyril missed the official team by one point. Check out their blogs too!

~ Happy Mothers Day! Words cannot express my love & appreciation for my mother.

Sunday, May 2, 2010

ECOO 2010 Concludes

This years ECOO Provincial programming competition was quite epic. I, along with 3 other grade 12 members represented our school and qualified for the final stage of the competition held at York University with anticipation of making it to the top 10 teams. Turns out, we did (9th!). However, it was not easy. The problems were harder than what we had expected because usually the problems are very trivial.

I have posted another thread on the Compsci forum here.

Problem 1: Connecting the Dots



Solution: Basic trigonometry. Store vertices in two separate 1D arrays, sort them counter clockwise (always in quadrant I), calculate the arctangent, and multiply the x,y coordinates accordingly. In java:

ECOO Problem 1

Problem 2: Beowulf's Flight



Not a Solution! We didn't get full marks on this problem, but we came up with a last minute greedy heuristic DP approach that got partial marks (4/5). In java:

ECOO Problem 2

According to the forum, the optimal solution is probably an A* search. However, due to time restrictions of the contest, not many teams had enough time to implement it. I'll probably post another solution for this problem at a later time.

Problem 3: Mod 10 Arithmetic



Solution: Classic permutation problem. In java:

ECOO Problem 3

Problem 4: Almost Amicable Numbers



Solution: Span outwards from sod(x) looking for a number y such that distance from x to sod(y) is smaller than the distance from y to sod(x). In java:

ECOO Problem 4

Thanks to my friend AJ for supplying a C++ solution for this problem:

ECOO Problem 4

Now that i'm done with 'school' programming contests for the rest of the year, I am now gonna focus on physics contests. Speaking of, this week will be filled with physics-related competitions! Starting with the yearly OAPT grade 11 physics contest on May 4th, followed by the prestigious Sir Isaac Newton Exam on May 6th, to which I did quite well on last year even though I was in grade 10 (94.92 percentile). To end the week off, on May 7th, our school physics department will have their annual excursion for the Wonderland Wondercoaster Contest that I qualified for in the technical merit category. However, why not have fun instead? Summer is just around the corner, and some roller coaster rides will definitely get you in the mood. Not to mention getting the opportunity to experiment with accelerometers! Every young enthusiastic physicists dream.

What a fun week it will be! Oh joy!