Mashed Articles

It’s easy to take education for granted, especially when you consider that every child in the UK has access to a computer, whether it’s at home or at school. But what most people forget is that 1 billion children in the developing world have little access to education, and no access to computers, which is where a burgeoning non-profit organisation called One Laptop per Child (OLPC) comes in.

Nigerian school children get their hands on the XO and immediately start learning how to use it.

The organisation hit the headlines in 2007 when it developed a low cost laptop called the XO, which was designed to be bought cheaply by governments of developing countries and distributed among school children. The XO was originally dubbed the $100 laptop, and although three years on it still hasn’t achieved its target price, it has been purchased by 21 developing countries and distributed to 1,284,500 children across the world. However, while the organisation has helped so many children around the world, it has courted controversy, created rifts with the world’s biggest technology companies, and spearheaded the biggest consumer technology trend in the last decade.

One Laptop per Child was the realisation of an altruistic dream by a MIT director and professor Nicholas Negroponte. In 2005 he unveiled his plan to see a laptop given to every child in the developing world, to aid their education, and offer them the similar advantages in the digital age as children in the developed world. The idea was based on the creation of something completely unique: A laptop which was durable enough to withstand the stresses and strains of life in a developing world, cope with the challenges of intermittent power and internet availability, and cost just $100.

The design of the XO PC was outstanding, and should be regarded as a feat of computer engineering. Against the back drop of the prices of technology in 2005, before low cost and low power components were prevalent, Negroponte designed a laptop with a 433MHz processor, 256MB RAM, a 7.5” LCD display and wireless networking. This may not sound impressive, but its base cost of £199 was unheard of at the time, it had enough power to drive its bespoke Linux operating system dubbed Sugar, it could function as a laptop, ebook reader, had a screen which was clearly visible outside in direct sunlight, had 12 hours of battery life and was completely shock-proof, waterproof and dust-proof.

While the XO preceded the market in terms of design, its biggest challenges were to overcome the rigours of a life in the hands of children in developing countries. Availability and reliance on power was a problem for Negroponte, and the XO could not succeed if it was too power hungry. They also had to iron out the biggest failing point on consumer laptops: Hard disc crashes. The XO introduced flash drives, which eliminated the mechanical wear and tear of traditional spinning disc drives. What’s more, the XO featured a revolutionary new screen, which used a dynamic LED backlight, which reduced operating wattage down to 3W under normal conditions. This put battery life at 12 hours, far beyond that of normal consumer laptops, and made the XO a force to be reckoned with.

A new kind of PC

The XO laptop caused such a stir, that it’s credited with spearheading the resulting netbook craze, which is still the only PC sub-market which is growing. Once OLPC had mastered the low power components, screen and size, it started selling them in the US. They retailed the laptop as part of the Give One Get One campaign, where a US consumer would purchas a laptop for $400, and donate one to a child in a developing country at the same time. It’s this that Wayan Vota, editor of OLPC News, an independent community of OLPC supporters, believes caught the eye of companies such as Asus and Acer.

The XO PC is waterproof and dustproof, making it ideal for children in the developing world.

“The real threat of OLPC introducing a “$100 laptop” was enough to spur technology companies into action. And they had to act fast. OLPC sold 160,000 XO laptops at $400 for two- and you didn’t even get both. That had Asus rightly excited when they launched the EeePC line to amazing success,” he said.

Once ASUS made a commercial success of their EeePC, the whole market had to catch up, and within six months, every laptop manufacturer was shipping its own netbook version. In 2009 there were 33.3 million netbooks sold globally, and the sector achieved a 72% growth in sales, compared to a 13% decline in amount of notebooks sold. If its supporters are correct, One Laptop per Child caused one of the biggest technology sensations of the decade.

“The creation of the netbook market is largely, and appropriately credited to OLPC,” says Ed McNierney, Chief Technical Officer of OLPC. “We wouldn’t have $300 netbooks in the consumer market if that push from OLPC hadn’t happened.
Consumer product companies in the technology world are not known, in general, for their risk-taking behaviour,” he told PC Plus.

When asked for a comment, an ASUS spokesman told PC Plus that the XO had no bearing or effect on the creation of the EeePC 701 which launched in 2008, and that the company would have come to market with a similar product even if the XO hadn’t been invented.

Competition

It’s not often that a non-profit organisation courts competition and controversy, but the technology industry can be an unpredictable world, and it wasn’t long before OLPC found itself embroiled in a war of words with Intel. The world’s biggest chip maker had seen the market potential of the developing world and built its own low cost laptop, the Classmate PC, soon after the announcement of the OLPC XO- a move which incensed Negroponte. He called Intel ‘predatory’ in a lecture at MIT, accused the company of “hurting the [OLPC] mission” on the CBS news show 60 minutes, back in 2007. If this wasn’t enough, Negroponte then accused Intel of selling its Classmate PC to the same governments he was trying to persuade to take up orders of the XO, but “dumping” them at a loss making sum, scuppering his project.

Children in Nigeria recieve a traditional lesson from their teacher, but use the OLPC XO laptop to support their learning.

In the face of widespread criticism, Intel joined forces with OLPC in December 2007, in an uneasy alliance, which caused public disconcertion from AMD, who was a founding partner of the OLPC project. While the Intel – OLPC partnership promised a new beginning, the reality was very different. Less than six months later Negroponte dropped Intel representatives from OLPC’s board of directors, demanding that Intel dumped its Classmate project if the two companies continued to work together. With the money Intel has invested in its own project it was never going to can the Classmate PC project, and the relationship ended.

Since 2007, both laptops have seen their share of success and failure, with Intel shipping 1 million Classmate PCs to Venezuela and 150,000 to Libya. OLPC has saturated Uruguay and Peru with approximately 1 million XO laptops, as well as completing smaller orders from Colombia, Rwanda and Mexico. Whether Intel’s Classmate PC project hurt the OLPC effort is still the subject of debate, but Wayan Vota, editor of OLPC News, an independent community of OLPC supporters, doesn’t think so. He believes that the enthusiasm created by the XO and Classmate PC made Negroponte’s dream a reality: “I’ve heard from Intel insiders that the XO laptop moved the netbook revolution forward by a few years. Intel would’ve come out with a Classmate-like device, but not as soon as they had to with OLPC’s pressure. For this, both organizations should be thankful because netbooks are the only bright spot in the laptop business,” he told PC Plus.

However, the bright spot of technology might not look so good for OLPC. It’s not been able to get its cost down to the desired $100, and orders have been far from overwhelming. What’s more, the consumer market has caught up, and it’s possible to buy standard netbooks at cost as cheaply as an XO. While they’re not built as ruggedly with the developing world in mind, they do feature fully functional operating systems, such as Windows, which some say would better prepare children for a connected future.

An ‘irresponsible strategy”

Despite its rocky road to success, OLPC still has a long way to go before it can claim any kind of success. Its intention to deliver PCs into the hands of the world’s poorest children is admirable, but experts have called its methods in question, warning that the charity risks wasting the hard work and achievements by equipping communities with laptops and then leaving them to work out how to use them for themselves- a criticism which Walter de Brouwer, European CEO of One Laptop per Child flatly rejects. “The charge is false,” he told PC Plus in an exclusive interview. “Typically, teachers and schools receive a two-week introduction not only to the machine and its technical features and operation, but more critically on how to integrate it into the learning experiences,” he said. De Brouwer continued: “OLPC works with the country to develop a team that works with the schools. The team supports the schools, technically and pedagogically. This team also works to develop capacity at the schools and locally in the communities.”

In the UK schools require entire departments to keep their networks and PCs in running order, and the use of IT in classrooms as a key part of teacher’s training. Wayan Vota, an outspoken supporter of the OLPC project, has questioned the level of support provided by OLPC called their deployment strategy “irresponsible.”

“OLPC has always maintained distance from actual implementation, claiming it was the country’s responsibility to integrate XO laptop into their educational system. That might work for Uruguay, a stable, advanced country. But it’s irresponsible in lesser developed countries. OLPC has the responsibility to educate countries on what they are buying – an XO laptop should be one small part of a whole educational system change,” he said. “Just handing off the XO laptop, like it’s a self-installing app, leads to Ethiopian teachers banning them from classrooms as a plague on education.”

Last year, teachers and parents in Ethiopia criticised the deployment of the XO, claiming that it was a distracting toy for the children, and could not be a worthwhile tool in their education system built around memorising from a blackBoard and then passing the national test. Without teacher training to implement the laptops, the XO couldn’t fulfil its function. While self-learning is an important part of the XO’s purpose, it’s clear that there’s a serious risk that the laptops will either not be used effectively, or fall into disrepair.

One has to admire what Negroponte and OLPC has achieved in the last three years, battling adversity which would have overcome many other organisations. OLPC claims that attendance in schools improves with the introduction of the XO. OLPC is currently working on a new version of its laptop, the XO-1.5, which it hopes to start deploying later this year, and has released concepts of a $75 tablet PC which it aims to make a reality by 2012. No-one can argue that getting an internet connected laptop into the hands of children in the developing world is essential for those countries to grow and prosper. However, unless OLPC ask difficult questions of the XO’s recipients, it risks wasting an opportunity to really make a difference.

Concept of success

No-one can accuse Negroponte of not being ambitious and if his mission to put an internet connected PC into the hands of every child in the developing world wasn’t challenging enough, he wants to build a paper thin touchscreen tablet PC which will retail at under $100. This concept design is the OLPC XO-3 (pictured) and is the latest dream of OLPC founder Nicholas Negroponte. It’s to be based on the XO 1.75 spec, which will feature an ARM mobile processor, which will provide twice the speed of the XO-1 and operate at 25% of the power. However, the main difference is the form. Negroponte wants to move away from a standard laptop form, and go for a purely touchscreen device.

A vision of the future: Negroponte wants to launch a handheld tablet similar to this concept, costing less than $100, in 2012.

Whether or not the XO-3 can actually be achieved is another matter. Producing something similar to the iPad in form, in just two years and dropping the cost to under $100 seems ludicrous, and whether such a device could power an OS capable of supporting a child’s education is another matter. What’s more, whether this form factor is suited to education is another matter. It seems that Negroponte has learned a few things about the nature of the technology industry, in the last three years promoting the XO. While the threat of releasing a sub-$100 netbook spurred the rest of the industry to react is a seismic way, he’s hoping that the design of a low-cost tablet could have the same effect. He told Forbes: “We don’t necessarily need to build it, we just need to threaten to build it.”

If OLPC can use the industry to its advantage this time, rather than do all the leg work while the consumer market reaps the benefits, then the dream of getting tablet PCs into developing countries could become a reality.

Pentominoes, a simple educational toy, can reveal some surprisingly deep computer science. Although the first back-tracking solution to the puzzle was implemented in 1958, Donald Knuth devised an entirely new way of looking at the problem in 2000, and called the algorithm the Dancing Links algorithm (or more usually, DLX).
A pentomino set consists of 12 pieces, representing: all the different ways of joining 5 squares (hence pent-) along their edges to form an individual piece.

Be thankful you’re not assembling a set of 3D blocks. It’s even harder than the 2D version.

Figure 1 below shows the complete set, together with each piece’s usual name, a letter of the alphabet that most closely resembles it (F, I, L, N, P, T, U, V, W, X, Y, and Z). Since there are 12 pieces, each 5 squares in size, for a total of 60 squares, that means you could investigate solutions to fitting them all in a 3×20 rectangle, 4×15 rectangle, a 5×12 rectangle, or a 6×10 rectangle, as well as other, more fanciful, shapes.

Figure 1: The 12 pentominoes.

Back in my early teens, I was given a plastic set of Pentominoes arranged in a 6×10 box, presumably for my birthday or Christmas. I seem to remember then spending some inordinate amount of time over several months trying to find all the ways of arranging the pieces in the box. There are 2339 different ways, not counting rotations or reflections. I even used a notebook with squared paper to record the permutations I did discover (although I still have that pentomino set, the notebook has been lost in the mists of time). Needless to say, I did not find all 2339 ways.

Starting solutions

Figure 2 shows a solution for the 6×10 box (in fact, the solution I carefully kept with the box, since not knowing how to put them back would have been embarrassing), and if you look carefully, you’ll see that you can immediately generate another by swapping over T and F.

Figure 2: One of several possible solutions to the 6×10 pentomino puzzle.

After playing around with the pieces for a while, the natural question to ask is – well, natural if you are a programmer, that is – how can I write a program to generate all the solutions to a particular puzzle? Let’s look at what might be needed for a 3×20 rectangular board (there are 2 solutions to this particular puzzle, not counting rotations and reflections).

A first idea might be the following algorithm: take the pieces in order, F to Z. Place F somewhere on the empty board and mark off the squares it covers. Place the I on the board, making sure that it does not cover any of the already covered squares, and mark off the squares it does cover. Place the L likewise. At some point you will find that you won’t be able to place the next piece, so you should backtrack and move one of the already placed pieces to another position (perhaps also by rotating or flipping it over), and then try again. Continue this process, with the realization that you might have to backtrack several times at any one check, and eventually you will discover all permutations.

The big problem with this particular solution is that it will take some time. There are 144 different places and orientations for the F in a 3×20 board, 48 for the I, 136 for the L, and so on, and many of them will be completely illegal (for example, the F cannot appear right at the ends of the board, since in doing so you will always leave at least one empty square). So, in all you’ll be trying out 144 * 48 * 136 * … different permutations. Not very fast at all.

A better implementation might be to switch it around a little. Consider the square at the upper left of the board. Select a piece that covers it, and then mark off the remaining 4 squares that are also covered by this piece. Find the next uncovered square (for this type of board, because it’s so narrow, it’ll be better to search down the narrow axis rather than the long axis). Try and find a piece that covers that and that can be placed legally. If not, backtrack again and change a piece you’ve already placed. Sometimes you might have to backtrack several steps.

Because you are more likely to identify impossible solutions much quicker (for example, there are only 2 possible ways to place the F to cover the top left square and both are shown to be illegal when considering what to place in the next square downwards), you’ll find that this algorithm is much more efficient at identifying valid solutions because you reject invalid positions much earlier.

If you try and implement either of the above solutions, you’ll possibly find yourself calculating the positions and which squares are covered by each of the individual pieces over and over again. It would be better to calculate them once and for all and put the values in some kind of table that you read and process as you try out various placements.

Before we discuss the best data structure for that table, let’s take an aside and consider what’s known as the Exact Cover Problem. Imagine the following scenario. You are given a matrix of ones and zeros; that is, whose cells are either 1 or 0. The first part of Figure 3 shows such a matrix. The problem you have to solve is to work out which rows of the matrix form a set that contain exactly one 1 in each column. There may be no such set of rows, there may be exactly one, or there may be more than one. A solution to this problem is known as an exact cover: a set of rows that exactly covers the columns. Take a moment to work out the exact cover for Figure 3.

Figure 3: An exact cover problem in part 1; partial steps to a solution in parts 2 and 3.

Despite the ease with which a visual inspection will provide the answer with this small matrix (rows 2, 3, and 5), it’s well known that this problem is extremely hard (it’s NP-complete, in computer science terms) the more rows and columns there are.
The algorithm for solving it is recursive. Let’s follow along with Figure 3. You’re given a matrix. Choose a column (say the first). Choose a row such that the cell at the intersection of the column and row is a 1 (let’s go for row 4). Add that row to our solution. Now since that row will have a 1 in column 1 we must remove all the other rows that have a 1 in column 1 (that would be row 5). Not only that, but we must also remove all the rows that have a 1 in the same column as this chosen row. For row 4 we hit the jackpot: We can get rid of row 5 (again), row 2 and row 6. We remove row 4 (since it’s in our possible solution) and the three columns that row 4 covered (there’s no need to recheck them since we’ve already covered them). Our matrix now looks like the second part of Figure 3.

Reduced matrix

We do the same thing with this reduced matrix. We choose row 3 as our row since it intersects with column 2 in a 1. Unfortunately, we then have to delete row 1 as well since there’s a clash in column 6, meaning that columns 5 and 7 never get covered and we failed to get an exact cover. So we backtrack. Maybe choosing row 3 was the mistake. However, there is no other possibility to cover column 2 in that particular reduced matrix, and so we must backtrack to our choice of row 4, way at the beginning. Since that choice led to no exact cover, we see if we can’t make another choice of row to cover column 1. Yes, there is: row 5. Selecting row 5 means we get rid of rows 4, 4 (again), and 1, as well as columns 1, 3, and 7 (since row 5 covers them). We’re left with the reduced matrix shown in part 3 of Figure 3.

Here we make the choice of row 3, which removes row 6, as well as columns 2 and 6. And this, as I’m sure you can see, leaves us with row 2 covering the remaining two columns. (To be pedantic, we select row 2 which removes the final two columns as well. Since there are no rows or columns left, we found a solution.) Hence our exact cover solution is rows 2, 3, and 5.

All fine and dandy but what does this exact cover problem have to do with pentominoes, and in particular defining the table of where a piece can be placed and which squares it covers? The answer is to set up the puzzle as an exact cover problem. Let’s define the columns first: the initial 12 columns will be the pentomino pieces, one column for each piece. The next 60 columns will be one per square from the board, say counting from top left across the top row (1–20), then the second row (21–40), then the final row (41–60).

Now we can define each row as being a single piece placed on the board in a particular position. Since it’s a single piece, we’ll have a 1 in only one of the first 12 columns, according to which piece it is. Now we put a 1 in each column of the next 60 that corresponds to the squares covered by the piece in that position. For example, if we take F in its “normal” orientation and place it abutting the left side, the row will have a 1 under the F column, and a 1 under columns for squares 2, 3, 21, 22, 42. All the other 66 columns for that row will be 0. (In fact, every row we add to the matrix will contain 6 1′s and 66 0′s.)

How many rows will there be? Well, we just sum all the different ways we can place each piece. For example, for F there are 18 positions for each of its orientations, and 8 orientations, making 144 distinct positions. I did the calculation and came up with the following number of positions for each piece: F 144; I 48; L 136; N 68; P 220; T 72; U 110; V 72; W 72; X 18; Y 136; Z 72. In other words, the puzzle matrix has 1168 rows. This is one huge matrix, but note that it is very sparse: only 1 in 12 cells is a 1. Now all we have to do is to find the exact covers for this 72×1168 matrix. Because we haven’t done anything to avoid solutions that would be rotations or reflections of other solutions, we’ll actually find 4 times as many solutions as expected.

The fun problem is how to actually solve the exact cover problem efficiently. I’ve already noted that it’s a non-polynomial problem (probably exponential), so, for some large matrix, it’ll all get very hard to nigh on impossible, but this particular sparse, not-that-large matrix actually can be solved pretty quickly.

The algorithm to do it is the one I mentioned above (Donald Knuth calls this algorithm, Algorithm X), however, keeping track of all the rows and columns you’re removing or adding back – the housekeeping, if you like ¬– is quite complicated. To aid in this housekeeping issue, Knuth came up with a refinement that he called Algorithm DLX for something like “Dancing Links implementation of Algorithm X” (you can get the paper from this link, it’s paper P159).

Dancing Links?

Consider a doubly linked list where each node has a Next and a Prev reference to the next and previous nodes in the list. Then, in order to delete a given node X, all we have to do is set X.Next.Prev to X.Prev and X.Prev.Next to X.Next. X will no longer be in the linked list. However, providing that we don’t alter X in any way, we can just as easily add it back into the list: set both X.Next.Prev and X.Prev.Next to X. In other words, although the linked list has no more references to X, X itself still has “knowledge” of where it was in the list.

Well, all that is very well, but so what? Consider our 72×1168 sparse matrix, how would we represent that in memory? What data structure would we use? We could just use a simple standard matrix of boolean values, so it would take 84,096 cells, but such a structure is too rigid. Better would be to use a linked list of cells containing a 1 along each row. Knuth went even further: not only are the 1 cells joined in a linked list along each row, but they are equivalently joined up and down in a linked list as well. The matrix becomes a tapestry of linked lists, with each 1 cell having a link to its left, right, up, and down neighboring 1 cells. 0 cells are not stored at all.

Figure 4: A linked list tapestry for the exact cover problem deomstarted in Figure 3.

Figure 4 shows the exact cover problem matrix that we saw in Figure 3 as a linked list matrix. Each column has a header cell and the header cells have their own single header cell. The linked lists are circular lists: the links off to the left join at the right (and vice versa) and the links off the bottom join at the top (and vice versa). Now that we have this woven data structure of linked lists, we can make use of the remove/add-back-again idea that I just introduced. To cover a column we unlink it from the column headers linked list using our code and we can easily unlink the rows it contains by the same method. If we need to backtrack, we can add the rows back, in reverse order, and finally add the column back in. The housekeeping of Algorithm X is done through this property of deleted nodes “knowing” where they came from. We don’t have to have any special additional data structure to hold the removed rows and columns: the nodes themselves keep track of all that automatically.

In essence, Algorithm DLX finds an exact cover if, during a recursive call, the header of headers node points to itself. It fails to find one if there are still column headers but they have no rows; we shall then need to backtrack. To Knuth, looking at all the breaking and making of links, the weaving of the lists, it reminded him of a dance, hence the term Dancing Links.

Some you win and some you lose. As it goes, Apple’s new iPad makes me feel like I’m first past the post. Not because it’s going to change anyone’s life for the better, but simply because it confirms what I’ve been saying for longer than I care to remember about mobile internet devices, or MIDs. Not to put too fine a point on it, MIDs are a bad idea. And make no mistake: the iPad is nothing more than a MID.

I could, of course, count the ways in which the iPad fails. I might wax proselytical about the oversized screen and how it bloats the device’s proportions unnecessarily. I could wail and gnash that the lack of support for Flash video is utterly bonkers in a device Apple claims is better for web browsing than a laptop.

Equally, there are legitimate complaints to be made regarding Apple’s decision to run a Mickey Mouse smartphone operating system – one that lacks proper multitasking support – on a far larger and supposedly more capable device. Likewise, the total absence of expansion-friendly ports, sockets and card readers is a galling limitation that smacks of control freakery. Whatever Steve Jobs claims, magical the iPad ain’t.

But ultimately, debating the pros and cons of the iPad’s weak execution is irrelevant and plays into the hands of Apple fanboys. It gives them the opportunity to point at the widespread criticism levelled at the first iPhone and confidently imply that the trash talkers have got it wrong once again. No, the real problem with the iPad isn’t poor execution: it’s the broken MID concept.

For starters, the fact that even a flawed MID such as the iPad is better for internet browsing than the best smartphone counts for nothing. You can’t slip the iPad or any other MID into a trouser pocket. To put it another way, MIDs neither replace nor compete with smartphones. As Apple itself says about the iPad, it’s a new category of device, not a replacement.

However, what MIDs do have to compete with, contrary to the preachings of his royal Jobness at the iPad launch event, are laptops in all shapes and sizes, including netbooks. It’s difficult to think of more than a small handful of distinctly niche applications for which the tablet or slate format factor is preferable to the classic fold-out screen and keyboard design.

Indeed, Apple’s promotional video for the iPad, replete with images of the hapless user contorted into a slouching, knee-high, feet-on-coffee table position, tells you all you need to know about the difficulties of the slate form factor. Anything other than perfunctory prodding at the screen is a royal pain in the backside.

Despite all that, don’t think I’ve come over all smug this month. Yes, I’m increasingly confident that I got it right regarding MIDs, but the launch of a certain new CPU has dropped a bomb on another of my forecasts. Not long ago, I predicted that 2010 would be the year that multicore computing got back on track. To an extent, that remains true. Both AMD and Intel plan to launch six-core PC processors soon, thereby increasing their core counts for the first time in a couple of years.

Nevertheless, I suspect that a humble dual-core processor will remain the most impressive chip launched in 2010. The CPU in question is Arrandale, Intel’s new mobile engine for laptops. Putting Intel’s baffling new branding scheme to one side, thanks to which Arrandale will be sold under not only the Core i3 and Core i5 banners, but also Core i7, this chip is a stunner. I’ve certainly never seen such an enormous leap in raw performance, generation to generation.

At any given clockspeed, I’d estimate it’s often in excess of 50 per cent faster than Intel’s existing Core 2 Duo mobile processor, which is no slouch itself. Add in Intel’s auto-overclocking Turbo feature and it only gets better. In fact, it’s so fast that it makes me doubt the need for quad-core processors in portable PCs. As if that’s not enough, my early testing suggests it delivers all that extra performance in return for almost exactly the same overall power draw as a Core 2 Duo.

That’s a particularly intriguing observation, because it doesn’t just mean you can have performance to rival Intel’s older quad-core chips in a relatively thin and light notebook. No, things get really interesting when you consider the low-voltage and upcoming ultra-low-voltage versions of Arrandale. With these, we’re likely to see performance on a par with full-power variants of the Core 2 Duo range, but in far smaller form factors. Bung in a decent solid-state drive and the result should be a desktop-class computing experience in an ultra-
portable PC. Now that’s what I call magical.