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.

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

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!

Useful Graph Algorithms

Just from experience and knowledge of graph theory ...

Dijkstra's algorithm: Computes shortest paths in a graph with non-negative edge weights.

Floyd-Warshall: Solves the all pairs shortest path problem in a weighted, directed graph.

Prim: Finds a minimum spanning tree for a graph.

Kruskal: Finds a minimum spanning tree for a graph.

Boruvka: Finds a minimum spanning tree for a graph.

Johnson: All pairs shortest path algorithm in sparse weighted directed graph.

Ford-Fulkerson: Computes the maximum flow in a graph.

Edmonds-Karp: Implementation of Ford-Fulkerson.

Bellman-Ford: Computes shortest paths in a weighted graph (where some of the edge weights may be negative).

Hungarian: Algorithm for finding a perfect matching.

Coloring algorithm: Graph coloring algorithm.

Topological sort: Sort a directed acyclic graph in such a manner that each node comes before all nodes to which it has edges (according to directions).

Nearest neighbour: Find nearest neighbour (Travelling salesmen problem).

Tarjan's off-line least common ancestors algorithm: Compute lowest common ancestors for pairs of nodes in a tree.

For more graph theory algorithms, please visit this.

Dijkstra's Algorithm Runtime:

CCC 2009 Wireless

The Canadian Computing Competition is a prestigious programming competition for high school students with considerable programming experience willing to take on a challenge.

For over a year now, I have been rather struggling to solve the last problem from the 2009 senior section, Wireless. The reason I have been struggling was not that my solution didn't generate the correct outputs, but that the algorithm was not efficient enough to pass the SPOJ online judging system, with a rather strict time limit.

My original solution which was just straight forward 2D array processing, with an O(N log N) algorithm complexity failed to pass the judge as it exceeded the time limit. Mind you, this was implemented in Java, which I realize now is horrible for online competitions. Perhaps another time I will post my thoughts on Java vs C/C++.

Anyways, after several failed attempts, I decided to change my language to C++, and while talking with one of my friends, I came up with a rather odd sort and count solution that at the time I didn't think was sufficient enough.

Here is an outline of how it works:

On every row, all wirelesses have a (possibly empty) range of columns it covers.
This is translated into a set of commands for that row, consisting of a column number and the change in bitrate, with every wireless leading to two commands:
An increase in rate at the start of the range, and a similar decrease at the end of the range. By combining the commands and considering them in order of column number, the cumulative bitrates can be calculated over the range of the whole row.

NOTE: With N rows and K wirelesses, the complexity of this implementation is O(N*K*InK), the K*InK factor arising from the fact that a simple Quick sort is used to sort the commands, plus the fact that a Binary search is used to find the ranges within each row (Pythagoras). Better algorithms may be possible.

Once I coded this, to my surprise, it finally got accepted!
Time: 11.25 sec
MEM: 2.6 M

Now I have to prepare for the upcoming regional ECOO programming contest held at York University. Usually the problems are very trivial, so i'm not worried at all.

My SPOJ account

2009 CCC Wireless Solution C++