Math Circle Sesion 12: Eulerian Circuits

Yesterday we turned our attention to Eulerian circuits in math circle. This was a completely “homebrew” session.

We started by asking the children to solve the classical puzzle of drawing this “house” without taking pen off paper, and without retracing your steps.

Surprisingly, they hadn’t seen it before, but it didn’t take long for them to solve, and also to discover that the path was not unique. We then asked whether it is possible to draw the same shape, following the same rules, but ending up at the end of the drawing back where you started. The children made many attempts at this. Nobody could find a way, but nobody suggested a reason why it wasn’t possible. One child noticed that if you remove the bottom most edge, the problem has a solution.

As a result, we began to enumerate all the connected graphs with one vertex, with two vertices, with three vertices, and with four vertices. For each graph, children quickly solved the problem where it had a solution. For small enough graphs, where there wasn’t a solution, they could see this through complete enumeration of paths.

One child suggested that there may be a link between the parity of the number of vertices in the graph, and whether or not an Eulerian circuit exists, but I demonstrated this to be false by reference to the two houses – the complete one and the one with the missing floor.

I suggested we look at the act of entering and exiting a vertex, using two edges each time. That, combined with drawing the order on each vertex of each of the graphs we’d enumerated, resulted in the conjecture from one of the kids that Eulerian circuits can only exist when all vertices have even order, and we together constructed an argument why this should be the case.

I then posed the (much harder) converse question: does an Eulerian circuit exist for every connected graph with even order vertices. I am not sure the children clearly understood the difference between this and the previous question; since they had shown that every graph with an Eulerian circuit has even order vertices, I think this seemed “obvious” to them (we must look at logic during one session – any reader with a child-friendly introduction to logic, please let me know!) I asked them to try to produce a graph with even order vertices that does not admit an Eulerian circuit, and they tried for some time before suggesting it is not possible, though none were clear why.

In a step towards trying to answer this question, I wanted to demonstrate that every graph with only even order vertices contains a circuit. I had them first try to construct graphs where each vertex has even order but the graph contains no circuit. Some elaborate failed attempts ensued, but then one child made the following remarkable claim: “it’s possible if the number of vertices is infinite”. I queried this child, and he drew the following “graph”:

His argument was that all these vertices have order two, yet the graph clearly contains no circuit. I thought this a fairly remarkable construction for a 7 or 8 year old! After restricting ourselves to finite graphs (infinity crops up so often, and absorbs so much interest, we should have a session on infinity also!) we all agreed that every graph with even order vertices contains a cycle.

From that point it was a small step to prove by induction that every graph with even order vertices admits and Eulerian circuit. I think they understood this, but I don’t think I had time to properly emphasise the inductive nature of the proof, and again proof by induction is something we must revisit in the future.

As a final exercise, I had them find an Eulerian circuit in what I had imagined to be a complex case: a pentagram inscribed inside a pentagon, with vertices at all points of intersection. They solved this easily, after which my infinity-inspired child noticed that there is a small pentagon formed by the pentagram, and asked what would happen if we put a pentagram inside this pentagon, and so ad infinitum, forming a fractal graph: would the property still hold?

Lots of things to pick up in future sessions, I think! If I were to change anything when redoing this session, it would be to make the problems more concrete, e.g. using towns as vertices and roads as edges, as my wife had suggested before the session! I think the children “got” it without this, but it might have captured the imagination slightly more.

An Interlude: Is Infinity Odd or Even?

During the session, when infinity came up, I was asked a direct question by one of the younger children: “is infinity odd or even?” At a lull in the main session, I decided we should use this question as a way to talk about the importance of definitions once more. All children had presupposed an arithmetic in which infinity plays the same role as any “other number”, and therefore already had in their minds that, for example, $2 \times \infty = \infty$ and $\infty + 1 = \infty$ . I didn’t question these suppositions (again – a possible topic for another session!) but instead decided to work with them. I asked for a definition of even, and got:

Definition: A number is even if it is two times a whole number.

I asked for a definition of odd, and got:

Definition: A whole number is odd if it is not even.

To which I added an additional alternative definition:

Definition: A whole number is odd if it is one more than an even number.

Children then quickly worked out for themselves that by their definition (and under their arithmetic) infinity is even. By the first definition of odd, infinity is not odd, but by the second definition, infinity is both odd and even! Thus the two definition of odd coincide for integers but not for their version of arithmetic with infinities. We left that as a talking and discussion point about the importance of definitions, rather than trying to draw any strong conclusions.

Run Fast! (When You Can): Data-Dependent Pipelining

This week sees the IEEE International Symposium on Field-Programmable Custom Computing Machines hosted in Vancouver, BC, Canada. I have sent my PhD student, Junyi Liu, who is presenting some work we’ve done together with my former research fellow, now a member of staff at Xilinx, Sam Bayliss.

Junyi and I are interested in memory accesses about which we know something at compile time, but not quite enough to be able to have a complete picture of what they’ll be at run time. This means that existing analyses of code containing these accesses will typically result in suboptimal behaviour at run time.

The case we study in this paper is that of affine loop nests containing memory accesses whose addresses involve indeterminate variables that do not change value as the loop executes. The value of these variables can completely change the dependence structure of the loop, meaning that for some values, the loop can be highly pipelined and run extremely fast whereas for other values, the loop must run very slowly. We give the trivial example below in the paper:


for( int i=LB; i<=UB; i++ )
  A[i] = A[i+m] + 1;

The variable m does not change as the loop executes. For some values of m, each iteration of the loop must start execution when the previous one finishes. For other values of m, we can pipeline the loop so that iterations overlap in time. So how to discover this and take advantage of it automatically?

We present an approach based on an extension of the polyhedral model to parametric polyhedra, where the parameters are these parameters, like m, unknown at compile time. My former PhD student Qiang Liu (no relation), colleague Kostas Masselos and I were some of the first people to bring the polyhedral model to FPGA-based computation in our FCCM 2007 paper (Qiang is now an associate professor at Tianjin University) but to the best of my knowledge, parametric polyhedra are relatively understudied in this area.

The basic idea of this new work is simple: use static analysis to identify regions of the parameter space where you can run the loop fast, and synthesise light-weight detectors of these regions for runtime checks on entry to the loop nest. Since my original work with the polyhedral model, high level synthesis has become a commercial reality, so we build on top of Xilinx VivadoHLS, implementing our tool as a source-to-source transformation engine. This automatically inserts the appropriate VivadoHLS pragmas as well as the extra code for the runtime checks.

The results are very promising: some of our benchmarks show a 10x speedup in initiation interval (the time you need to wait before executing another iteration of the loop).

Math Circle Session 11: More Platonic Solids

Tuesday saw the next installment of our math circle. In the previous session, we had been investigating Platonic solids, and the aim of this session was to build up to a proof that there are exactly five such solids.

Since in the previous session the children had produced a lot of their own definitions, I produced a sheet summarising their definitions as well as standard mathematical definitions of some of the concepts we had been dealing with during the previous session. Below you can see the summary sheet of the children’s definitions, which was laid alongside the standard definitions. Names have been changed for privacy reasons.

Definition: Line-Shape

A line-shape is any shape made by a finite number of straight lines.

(Note the Thomas-Adrian Condition: The number of lines used by the shape must be finite, because an infinite number could lead to “curvy shapes”.)

Definition: Eve-Regular

An Eve-Regular line-shape is one whose sides all have the same length.

Definition: Line-Shape-Shape

A line-shape-shape is any 3D shape made by a finite number of line-shapes.

(Note the Christopher Convexity Test: Place a pencil on the object so it rests on at least two points; if you cannot create a space between the pencil and the object between these two points, the object is convex.)

The first part of the session was then taken up comparing these definitions to more standard ones. In particular, I pointed out that the standard name for Eve-Regular polygons is equilateral, and that polygons that are both equilateral and equiangular are referred to as regular. This approach seemed to work very well, especially with the younger children, who were very excited to see their names in print as part of a definition! Fortunately, I had been able to include the names of all children who had been present in the previous session, as all had been able to contribute.

After reminding the children of the {n,m} notation for the Schläfli symbol of a Platonic solid, I led them towards trying to systematically enumerate the solids. They were able to quickly tell me that the minimum values of n and m must be 3. We then worked our way through all possible Schläfli symbols until they found that m is bounded from above for each n, due to the need for the internal angles to add to a value strictly less than 360 degrees. By physically building each polyhedron as they went, they were able to show that every allowable m does indeed lead to a polyhedron, and we were able to construct all 5, showing that there were indeed only 5 of them in the process: the tetrahedron, the cube, the octahedron, the dodecahedron, and the icosahedron.

In case they finished early, my plan was to have them compute the Euler characteristic for each Platonic solid, and then try to build other polyhedra to see whether the value held, however the proof of five solids took up the whole session. After two sessions building polyhedra with Polydron, some of the children may have reached the limits of their interest in the topic for now, so if we do explore Euler characteristics for polyhedra, it will be in a later session.

Math Circle Session 10: Platonic Solids

Today was the 10th session of our math circle, and the first session I’ve led without the support of my wife. I had asked the school headteacher whether he could attend, so I was not alone faced with five children, and he thankfully agreed!

Today we explored three dimensional geometry. Over the Easter break, I’ve been reading a book by Kaplan and Kaplan on their experiences with their math circles (review to come in a future blog post), and this inspired me to try something different. We would spend a considerable time on definitions (which are the heart of mathematics, and often lost in trying to make mathematics appeal to primary school pupils) but these would – often – be definitions that the children themselves came up with through discussion and refinement. I was pleasantly surprised that even the “jumpiest” math circle members seemed to be OK with this approach, and contributed to the process of forming definitions.

We started by looking at 2D shapes. I drew some polygons on the board and one curvy shape and asked what the general name for the polygons was, expecting one of the older children to suggest the name “polygon”. However, this was not forthcoming. So we began discussing the differences between the shapes. Here we hit the second unexpected perspective: one of the children – rather creatively – suggested that “every” 2D shape is a polygon, because if you zoom in enough then the boundary becomes straight. We thus took a brief informal detour into limits, and ended up by concluding that this child had made a great contribution by ensuring “straight” and “finite” ended up in any definition they came up with. Since they were unsure what these shapes were called, following Kaplan and Kaplan, I suggested they find a name for them, and they settled on line-shape. Their final definition was: a line-shape is any shape made by a finite number of straight lines.

During the discussion on naming, two of the younger children suggested the word regular for those 2D shapes made from straight line segments. The older children disagreed, because they had seen regular polygons before, and instead insisted that a regular shape is a shape where the sides have the same length. (Nobody mentioned angles.)

Extending to 3D shapes, the children also did not naturally suggest the word “polyhedron“, however I was very impressed by the reasoning of one child, who suggested the term line-shape-shape “because if line-shapes are 2D shapes made of lines, then line-shape-shapes should be 3D shapes made of line-shapes!” After exploring these definitions a little more, I revealed the names polygon and polyhedron, and suggested we use them to avoid my own confusion!

I then had children make polyhedra using Polydron. As expected, they made a wide variety of weird and wonderful polyhedra. The oldest child had seen a (regular) icosahedron before and wanted to build one, but was trying to do so by constructing its net blind, unsuccessfully. All the polyhedra they constructed were convex, so I built a non-convex polyhedron and asked the children what made it different. They all agreed that it was because it “went in”, but I challenged them to figure out how they would convince someone else that this polyhedron “went in”. Eventually, I took a pencil and placed it on the polyhedron, at which one of the children noticed that there is a part of the pencil between the two touching points which is not itself part of the polyhedron. Thus we came to an agreed understanding of convexity.

The "pencil test" for convexity — The “pencil test” for convexity

These definitions were sufficient for me to (incorrectly at first!) define a Platonic solid as a convex polyhedron whose faces are regular polygons of the same shape and size.

I asked children to construct as many Platonic solids as possible, and they quickly came up with a tetrahedron and a cube. One child also came up with a decahedron consisting of two pentagonal-base pyramids joined, at which point I realised I had forgotten to include “and with the same number of faces meeting at each vertex” in my definition of a Platonic solid!

I introduced the children to Schläfli symbols {n,m} for a Platonic solid with m n-gon faces meeting at each vertex, and asked them to explore other Platonic solids. One child quickly discovered that hexagons cannot form the faces of a Platonic solid (because they tessellate three around a vertex, tiling the plane – in the words of the child “because of the angles”), but just moved onto another search rather than highlighting this important negative result; luckily I spotted it and queried him!

Hexagons can't form the faces of a Platonic solid because they tessellate the plane — Hexagons can’t form the faces of a Platonic solid because three around a vertex tessellate

The school headteacher found {3,4}, the octahedron (identified immediately as ‘the shape of a d8’, i.e. an 8-sided die, by one of the children). The child who had previously tried to construct the icosahedron found that {3,6} does not exist, and therefore conjectured that {3,5} would be the missing icosahedron, which it was, much to her delight. The Schläfli symbol provided the extra information to enable her to make it, and she asked for permission to take a photo of it at the end “to show my dad!”

I was hoping to get to a proof that there are exactly five Platonic solids, but I will postpone this for next time, I think. And in the mean time, I will produce a worksheet summarising the definitions and results from this session.

Math Circle Session 9: Parity

Today’s session was inspired by a different math circle book: that by Anna Burago, which is targeted at slightly older children.

We started with 7 coins, and asked the children to place them so that 4 were heads up and three tails up. The rules of the game are as follows:

in each turn, you can pick any two coins of your choice
you must turn both those coins over

Your aim is to get all 7 coins facing heads up.

The task is impossible, but the children didn’t see so immediately. One child even thought he had found a solution, but was unable to repeat it. One child noticed that he could get them to all tails, but not to all heads. Very quickly, children of all ages noticed that “odds” and “evens” had something to do with this difficulty.

One of the older children offered a partial explanation: by turning over two heads, the number of heads-up coins decreases by 2; by turning over two tails, it increases by 2; by turning over one head and one tail, it stays the same. So the only possibilities after one move are to have 2, 4, or 6 heads face up, and all these are even.

I helped the children to generalise this to “an even change in the number of heads up” after any number of moves. Unexpectedly, one child objected to zero being considered an even number, which led me to take a detour. One serious concern I have with typical primary school mathematical education, which I share with Hung-Hsi Wu, is the absence of clear definitions. So I viewed this as an ideal opportunity to get the children to formulate the definition of an even number. I received these suggestions from the children:

a number that you can divide by two
a number that is a multiple of two
a number that ends in 0, 2, 4, 6 or 8

One child objected to the first definition, “because I can divide 1 by 2, to get 0.5”. So after some prompting, the children changed the first definition to “a number that you can divide by two and the answer is a whole number”.

We then worked through each definition in turn, testing it for whether zero was an even number. The oldest child provided a clear verbal proof that the first two definitions were equivalent, and a proof that any number meeting the third criterion also met the other two (but not vice versa).

The child who had objected to zero being even seemed to accept that by these definitions zero was even, but suggested that this would make $\frac{0}{0} = 2$ , “which is not the case because $\frac{0}{0} = 0$ “. I paused this question, writing on the board to return to, because we were in danger of getting too far off track.

For the last part of the session, I tried to get the children to reason algebraically, suggesting that – from their own definition – any even number can be written as $2n$ and, therefore because $4 + 2n = 2 \times 2 + 2n = 2(2+n)$ , we still have an even number after any number of moves. I think I overestimated the preparedness of the children for this form of reasoning. The older kids were fine with this, one of the middle kids who had obviously seen but not understood algebraic notation before, upon seeing the $n$ exclaimed “oh no, those numbers, I hate those numbers!” and the youngest had not met brackets in arithmetic expressions. Trying to cover all this at once was probably too much, but I hope we managed to get the basic ideas across.

Finally, I returned to the question, which I had rephrased, “what is zero divided by zero”. We looked at the equation $2 \times 0 = 0$ , and how – if the child who suggested it were correct, we could equally conclude from $3 \times 0 = 0$ that the answer was “3” and from $4 \times 0 = 0$ that the answer was 4. I suggested that there is no well defined answer, so we refer to it as undefined. Seemingly unsatisfied with this answer, one child left to get a calculator. I was hoping this to be my moment of triumph where the calculator reported “-E-“. Stupid calculator reported “0” (!) However, at least one child obviously could see what was going on, and asked whether 1 divided by zero would therefore be infinity. In the last few moments, I managed to explore this question with a subset of the children by looking at the growth of $\frac{1}{1/n}$ as $n$ increases in size, while the others packed away.

I’d view this as a mixed session. Lots of very interesting questions raised, not all answered satisfactorily, but at least most of the children were thinking mathematically.

Review: Love and Math by Edward Frenkel

I have a friend who thinks she does not understand maths (apologies to the American readers, I will use “maths” in this review rather than the “math” in the book title). She thinks maths is “all about numbers”. She thinks she’s not particularly good at it. She is wrong. Actually, I think she is remarkably gifted, primarily because she asks amazingly prescient questions. She has an inquisitive nature that I fear is often drilled out of most people by our “rigorous” schooling in the tedium of official school maths.

Over the past few months, I have spent quite a bit of time discussing maths with this friend, introducing her to set theory and trying to overcome a fear of algebra. (It is remarkable how many super bright people can reason about insanely complex general phenomena in their head without algebra in a way I never could, yet stumble over a simple equation!)

I saw this book reviewed elsewhere – I can’t quite remember where. It was a short but positive review, and the title is attractive to me, given my recent discussions. The author, Edward Frenkel, is a professor of mathematics at UC Berkeley, has made considerable contributions to mathematics himself, and also has a direct personal knowledge of many of the larger-than-life characters he talks about in the book. I knew nothing about his work, or his life, both of which turn out to be rather interesting, before reading this book.

The book is part autobiography and part introduction to the joy of mathematics. We learn about the author’s early career, the anti-Semitism he faced in Russia and his conversion as a teen from physics to mathematics, before the two come back together through quantum physics later in his career. We learn about his immersion in the Langlands Program.

As a book about “doing mathematics”, I think he does quite well at getting his feelings across. The detail of much of the mathematics is missing; sketches of subjects are given: Galois Groups, the Shimura-Taniyama-Weil Conjecture, Lie groups and Lie algebras, etc., but only very brief sketches. While this gives the reader insight into the depth of the subject areas covered by modern mathematics (and certainly helps to show the breadth of maths beyond school arithmetic) it doesn’t really show the reader mathematics. We read about proof, but we don’t experience proof. We read about revelation, but we don’t feel the revelation ourselves. We are told that mathematics rests on clear and unequivocal definitions, but these are absent from the book. Initially, this left me feeling unsatisfied. Slowly, I put aside my usual desire to understand everything I was reading, and began to enjoy the book as a novel, a love affair between the author and his subject, in which specific theorems appear only as partially sketched characters. From this perspective, the bulk of the book was very enjoyable, and provides insight not only into the beauty of mathematics, but also the ways in which mathematicians think. As an engineer, albeit one who has a lot of time for – and use for – pure mathematics, my way of thinking remains quite distinct from some of the methods and approaches outlined in this book. However, late in the book, where the author covers the links between this mathematics and quantum physics, I feel the unexplained mathematics again gets in the way. The author seems to acknowledge this, when he says (p.221), “All this stuff, as my dad put it, is quite heavy: we’ve got Hitchin moduli spaces, mirror symmetry, A-branes, B-branes, automorphic sheaves […] But my point is not for you to learn them all…”

The final chapter of the book takes a violent switch in direction as we learn of Frenkel’s artistic projects, in particular his film Rites of Love and Math. Had I known about this work beforehand, the book would have made a lot more sense! In this chapter, Frenkel provides his philosophical opinions on the nature of the material world, the world of our consciousness, and – in his view – the entirely separate Platonic world of mathematics. He says his approach to making the film was “let the viewers first feel rather than understand” – much the same could be said of this book.

The experience of reading this book has got me thinking in two directions.

Firstly, this is not the book I initially expected from the first few chapters. But how easy would it be to write a book which both conveys the joy of solving problems, say in Lie algebras, which Frenkel explores in some depth, and at the same time covers enough mathematics for a reasonably rigorous approach to the problem for a general reader? Perhaps such a task is impossible, and I ask too much. Does this mean that the beauty of modern mathematics is necessarily harder to access than than the beauty of modern art? Does this mean that we must necessarily pay the price of “boring maths” in order to be able to access “beautiful maths”? Or is there actually no “boring maths” and the prerequisite knowledge can also be described in a way that appeals and excites, even if not in one volume. I hope for the latter.

Secondly, the book has made me realise that I am far less certain of my own philosophical viewpoint on reality, Platonism, and knowledge than I used to be. It has made me want to explore these issues again and read more. Perhaps I will start with Penrose.

Is this the book I wanted for my friend? Probably not, but it’s certainly stimulated my thinking, and probably would also stimulate the thinking of others, regardless of their current level of mathematical maturity.

Math Circle Session 8: The Circle Game & Puzzles

Today was the 8th session of our math circle for primary school children. We only had four of the original six children today, for a variety of reasons, but it seemed to work well.

We first ran through a puzzle we set the kids to think about over the last week. The idea of the puzzle, taken from Martin Gardner’s book, is as follows. Take a piece of paper shown below. Imagine this is a map, that you have to fold up (I find folding up maps really hard!)

You have to fold only along the lines shown, and must form a folded “map” with the 1 on top, facing up. The next number down after the 1 must be the 2, after the 2 must be the 3, and so on until the 8 lies on the bottom.

Some kids had tried this at home, some had not (as a policy, we never make “homework” compulsory) but none had found the solution, so we covered this today.

We then moved onto the main part of the session, “The Circle Game”, adapted from Rozhkovskaya’s book. The kids were each given a worksheet consisting of 16 points equally spaced around a circle, and asked to play a game in pairs. The rules of the game are as follows:

take it in turns
on each turn, connect one point to another point with a straight line; any pair of points can be chosen, but no line drawn can cross another line already drawn

The last player to be able to draw a line is the winner.

The kids enthusiastically played this game, trying to outsmart each other. However, at the end of play, we had three games in which the first player to move had always won (though the points selected were different). I also asked the kids to count the number of moves made, which was found to be 29 in each game. The question was posed: “why does the first player always win?”

One child quickly pointed out that if the number of moves is an odd number, it must always be the first player who wins. Another child suggested that we should try 17 points around the circle as then “it would be an even number of moves and Player 2 would win”. I suggested that instead of making the game more complicated, we simplify it to the smallest possible number of points on the circle, which the children identified as two points.

Children very quickly found that two points would always result in one move, three points in three moves, and four points in five moves. At this point the child who suggested that 17 points would result in a win for Player 2 withdrew his opinion, and all children were convinced that the number of moves would always be odd and therefore Player 1 would always win.

We then looked at generalising the number of moves required for $n$ points. Children very quickly noticed that the number of moves increased by two for each new point added. Due to the significant difference in ages in the group, I wasn’t sure how comfortable children would be with an algebraic generalisation of the result, but it turns out that even the youngest was comfortable with the formula $moves = 2 \times points - 3$ , which they got to via my suggestion that if the numbers were going up by two each time, try looking at the relationship between $moves$ and $2 \times points$ .

I was surprised by how quickly we had reached this point in the session, so I rounded off the exploration by demonstrating an inductive proof of this formula in graphical form on the whiteboard (see, for example, Theorem 1.8 at http://press.princeton.edu/chapters/s9489.pdf).

One child was keen to play this game with his dad, and it was suggested that the “youngest goes first” rule should be applied, possibly after agreeing a prize for winning!

With the remaining spare time for the session, we set the following puzzle – also from Gardner’s book – to begin during the session and to continue to think about over the week. Consider the grid below.

The puzzle is to fill each empty cell with a single digit, so that the bottom row forms a number between $0$ and $10^{10}-1$ . The challenge is that the digit under the heading zero must equal the total number of zero digits in this number, the digit under the 1 must equal the total number of 1 digits in this number, and so on. I thought it might be hard for the kids to understand the puzzle, but actually they understood it quite easily. They were amazed when I told them that the answer is unique: there is only one of the 10 billion possible numbers that works! It was interesting to observe the different reactions to this: some kids decided they’d never be able to find the solution, and therefore decided not to put much effort into the task. Others decided this was a challenge, and kept plugging away. One child was determined to take it home so that his dad would help.

Overall, I think this session went very well.

Update: I received an email tonight from the school headteacher with the solution to this number puzzle. I love that he’s so into it!

Math Circle Session 7: Combinatorics, Pascal’s Triangle, and the Sierpinski Triangle Again

Today saw Session 7 of our math circle. No blog on Session 6, as I was away for work – my wife explored The Towers of Hanoi in my absence.

Today’s session was based on a combination of two sessions in Rozhkovskaya’s book. The idea is as follows. Imagine a maze at a tourist attraction. The maze is such that there is one entrance, but seven exits labelled 0 to 6. Imagine that you are standing facing north at the entrance. At this entrance, and at each intersection, you can move ahead-left on a bearing of 315 degrees by one unit or ahead-right on a bearing of 45 degrees by one unit until you meet the next intersection or exit. Thus the maze decomposes into 7 levels (including the entrance and exits). Now further imagine that you must roll a die at each decision point, taking the left route if you roll even and the right route if you roll odd.

The first question: If I were an ice-cream vendor, where should I place my van to capture most people coming out? Children had an intuitive feeling that most people would come out in the middle. Only one child (the oldest) offered a reasoned explanation for this: “we expect as many odd throws as even throws, which means the most likely exit would be the middle one”.

We got the children to experiment by rolling routes through the maze, and collected a tally of how many trials ended up at each exit, confirming this suspicion. Children naturally noticed that exits zero and seven were unlikely, as they would require rolling “all odd” or “all even”.

This naturally led onto the next part of the exercise, to annotate each decision point with the number of ways in which it could be reached. Children found this hard, and made many mistakes, because they were trying to count all the ways to reach a given decision point from the maze entrance from scratch for each decision point. I explained that there are only at most two ways to reach any decision point, so it is sufficient to sum the possibilities found to these two preceding points.

Thus, Pascal’s triangle was revealed. We asked the kids to sum the rows of Pascal’s triangle, and they discovered they summed to successive powers of two.

Finally, we had the kids colour all the even numbers in a large version of Pascal’s triangle (pre-printed). One of the kids immediately recognised a fractal-like shape. Once complete, we pointed out the resemblance to Sierpinski’s triangle, created in Session 7. Oddly (to me) this wasn’t immediately apparent, even to the kids who were there.

Overall, I was a little disappointed with today’s session. I think the material was good, but it was a sunny day, and two of the kids showed no sign of wanting to be there, inside after school. This meant I had to spend a lot more time than I ever imagined trying to get these kids on task, meaning a lot less time to discuss the mathematics of what we were seeing, which was a shame. My one rule for Math Circle was that the kids should want to be there and, for whatever reason, I don’t think this was true for 1/3 of them this time. I hope it’s a temporary blip, but I need to ask for views from primary school teachers; I was again reminded today how different kids are to the adults I’m used to!

Coherence When You Need It

This week, my PhD student Felix Winterstein presented our work (joint with Intel and MIT) on how to customise memory systems to support parallel applications, at the FPGA 2015 conference.

If you are working with FPGAs, you have a huge freedom to develop an arbitrary on-chip memory system to support your application. Tools are getting quite good at developing such systems for regular array based code. But pointer manipulating programs that build, operate on, and destroy memory structures on the fly will not pass through commercial HLS tools, let alone produce good quality results.

We’ve shown that this issue can be addressed using a tool we’ve developed based on the theoretical foundation of Separation Logic. The tool automatically figures out when functional units can have private on-chip caches, which functional units need shared coherent caches, and – in the latter case – when commands can be reordered to aid parallelisation. It uses this analysis to automatically produce C source code that will pass through commercial HLS tools, providing the necessary hints and pragmas to parallelise the code, and automatically generates the on chip caches to support the parallel datapath.

I’m really very excited about this work, I view it as a big step towards efficient automatic hardware implementation of full-featured C code.

Math Circle Session 5: Powers, Limits, and Fractals

Yesterday saw the next installment of our math circle with primary school children. Again, following but extending Rozhkovskaya’s book, we used fractals as an interesting way in to consolidate (and in the case of the younger pupils, introduce) powers of numbers, to explore the children’s intuition about infinite series, and to make some pretty pictures!

We started by producing a fractal tree. The rule is simple: after Year 1, the trunk has grown. At the end of Year 2, two branches have grown from that, after Year 3, two further branches from each existing branch, and so on. Children were quickly able to tell us that the number of branches doubled each year, some took great pleasure in calculating or reciting powers of two. The template for this exercise was taken from Rozhkovskaya’s book, and is quite clever: lines are drawn across the page heights of 8 squares, 12 squares, 14 squares, 15 squares, and 15.5 squares, and each successive year’s branches should be drawn to reach the corresponding height. A bird is drawn flying around 18 squares up. The question is posed: will the tree ever reach the bird?

The children had mixed views on whether the tree will reach the bird. The most common view was that it must. One of the older children was able to provide a line of reasoning: “Each time, the height of the tree increases. Since it is always increasing, even by small amounts, it must eventually reach any height.” We then looked at how much gap there is between the height of the tree and a line of height 16 as the years progress: 16 at the beginning, 8 at the end of Year 1, 4 at the end of Year 2, and so on. Children could see that there was always a positive gap between the height of the tree and the height 16, for any finite number of years. However, this clashed with several children’s intuition, and it took quite a lot of discussion before it was generally accepted that an infinite series can sum to a finite limit. One of the youngest children in the group asked some very probing questions, such as “is infinity a number”, which led to some useful side discussions. Random banter between children later in the session about “hacking” their siblings’ passwords led onto a consolidation of this discussion by asking the question “If you had to press an infinite number of keys on a keyboard, could you do it in a finite amount of time? No? What if the first key took 8 seconds to press, the next 4, the next 2, and so on…”

We then moved onto a practical activity of constructing a sequence of approximations to the Sierpinski triangle by sticking little white triangles on coloured paper (pictured). One of the children noticed quickly, and was able to clearly explain, that the number of white triangles was increasing in powers of three. At this point we ran out of time, and our session ended. I intend to pick up and use the Sierpinski triangle again soon in math circle, through Pascal’s triangle modulo 2.