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.

Math Circle Session 4: Ciphers

Today saw the fourth session of our math circle. Attendance was down, and there was a sombre mood, due to a tragic event to hit the the school community today.

We went ahead with the three children who came, looking at ciphers. Following the guidance and resources in Rozhkovskaya’s book, we looked at the following activities:

We started with some plaintext words and one ciphertext word, and the kids very quickly spotted, without any help, which plaintext word corresponded to the ciphertext word, on the basis that both had a double letter in a certain place and they had the same number of symbols.
We showed how a coding wheel can be used to produce a Caesar shift cipher, and got them to actually build such a wheel.
We queried how many possible ciphers could be constructed with such a wheel. Interestingly, this was not obvious to the children at first, and a common answer was “infinite”. On questioning, this is because they were considering all integer shifts, i.e. mapping the letter $n$ to the letter $n+k$ for some key $k$ , and forgetting the modulo arithmetic in play, despite having the wheel in front of them.
We got them to produce coded messages to each other using the wheel, which they seemed to enjoy. Our initial plan was to have them pass the message and the key to the next child to decode. However, they immediately attempted to decode without they key by looking for patterns, so we didn’t stop this. One key pattern they spotted included the limited number of two letter words in English, allowing them to enumerate possible keys on two-letter words in the ciphertext. Another was the limited number of letters in the alphabet that can appear twice consecutively in an English word, again allowing for enumeration.

There’s a lot more that can be done with ciphers, and I expect we’ll continue this for another session.

Review: Three Views of Logic: Mathematics, Philosophy, and Computer Science

I read this book largely by accident, because I was attracted by the title. As an academic in (or rather, on the edge of) computer science, I come across logic regularly, both in teaching and research. Mathematics underpins almost everything I do, and I’m certainly interested in whether a mathematician’s view of logic differs significantly from that of a theoretical computer scientist (as a keen reader of mathematics, I’m well aware that standard mathematical practice of proof differs quite strongly from the formal approach studied in computer science, but this isn’t quite the same thing!) I once had a strong interest in philosophy, most significantly in epistemology, which is being rekindled by my involvement in education at the school level, and so combining all these factors, the title was very appealing. What I actually discovered when I started reading wasn’t exactly what I expected. But this book turns out to be an excellent, crystal clear, textbook suitable for undergraduates and those with just a limited level of mathematical maturity. The book is explicitly partitioned into three sections, but in practice I found that the first two sections, proof theory and computability theory (the “maths” and the “computer science”) were very familiar material for any computer scientist, and from my perspective there was no very clear difference in approach taken, just a difference in the range of topics covered.

Part 1, by Loveland, covers propositional and predicate logic, with a particular focus on automated proof by resolution. I found the description of resolution to be very clear, with a particular focus on the difference between resolution for propositional and predicate logic, and with one of the clearest descriptions of completeness results I’ve seen.

Part 2, by Hodel, covers computability theory. Again, the clarity is exemplary. The first chapter discusses concepts informally, the second precisely defines two machine models in a way very accessible to a computer engineer (effectively one supporting general recursion and one supporting only primitive recursion) and discusses their relative computational power. The insistence of an informal discussion first makes these distinctions come to life, and allows Hodel to frame the discussion around the Church-Turing thesis. The focus on compositionality when preserving partial recursiveness, and the emphasis on the ‘minimalisation’ operator (bounded and unbounded) was new to me, and again very clearly presented. Most introductory texts I’ve read only tend to hint at the link between Gödel’s Incompleteness Theorem and Church’s Undecidability Theorem, whereas Hodel makes this link precise and explicit in Section 6.6, Computability and the Incompleteness Theorem.

Part 3, by Sterrett, covers philosophical logic. In particular, Sterrett considers the existence of alternatives to (rather than extensions of) classical logics. She focuses on the logic of entailment aka relevance logic introduced by Anderson and Belnap, into which she goes into depth. This logic comes from rethinking the meaning ascribed to the connective, $\rightarrow$ , logical implication. In classical logic, this is a most confusing connective (or at least was to my students when I taught an introductory undergraduate course in the subject long ago). I would give my students examples of true statements such as “George is the Pope” implies “George is Hindu” to emphasise the difference between the material implication of classical logic and our everyday use of the word. It is exactly this discrepancy addressed by Anderson and Belnap’s logic. I was least familiar with the content of this part of the book, therefore the initial sections came as something of a surprise, as I found them rather drawn out and repetitive for my taste, certainly compared to the crisp presentation in Parts 1 and 2. However, things got exciting and much more fast moving by Chapter 8, Natural Deduction, where there are clear philosophical arguments to be had on both sides. In general, I found the discussion very interesting. Clearly a major issue with the line of reasoning given by my Pope/Hindu example above is that of relevance. Relevance might be a slippery notion to formalise, but it is done so here in a conceptually simple way: “in order to derive an implication, there must be a proof of the consequent in which the antecedent was actually used to prove the consequent.” Actually making this work in practice requires a significant amount of baggage, based on tagging wffs with relevance indices, which get propagated through the rules of deduction, recalling to my mind, my limited reading on the Curry-Howard correspondence. The book finishes with a semantics of Anderson and Belnap’s logic, based on four truth values rather than the two (true/false) of classical logic.

I can’t emphasise enough how easy this book is to read compared to most I’ve read on the subject. For example, I read all of Part 1 on a single plane journey. I will be recommending this book to any of my research students who need a basic grounding in computability or logic.

Math Circle Session 3: Knots

Today saw the third session of the primary school math circle we’ve been running for kids in Year 2 to Year 6. (I was absent for Session 2, where my wife covered mathematical card tricks.)

Today we looked at knots, drawing inspiration from Rozhkovskaya’s book as well as Adams’ introduction to knot theory. In particular, we covered the following points:

(Medial) graph representations of knot projections, moving backward and forward between them (see http://en.wikipedia.org/wiki/Knots_and_graphs)
The importance of assigning an (under/over) decision to crossings
Getting the kids to think of their own ideas for what knot equivalence might mean (shape, size, rotation, deformation – of what type) etc.

The key innovation we used here, which I think really brought the session to life, was to get the kids actually physically making the knots using Wikkistix, wax-coated string which allowed them to make, break, and remake their knots.

The kids really ran with this, and made their own discoveries, in particular:

One child discovered that some knots corresponding to the graph $K_3$ could be manipulated to produce the unknot, some could not.
A child discovered that it is possible to produce two interconnected knots, forming a link. Another child came to the same conclusion from the graph representation.
Consider the graph with vertex set $\{v_1,\ldots,v_n\}$ and edge set $\{\{v_i,v_{i+1}\} | 1 \leq i \leq n-1\}\} \cup \{\{v_n,v_1\}\}$ (is there a name for these graphs?). One child completely independently found that for $n$ even, this corresponds to a link of two knots, whereas for $n$ odd, it corresponds to a single knot.

I certainly had a lot of fun this afternoon – I hope they did too!

Where High Performance Reconfigurable Computing Meets Embedded Systems

I have just returned from attending HiPEAC 2015 in Amsterdam. As part of the proceedings, I was asked by my long-time colleague Juergen Becker to participate in a panel debate on this topic.

Panels are always good fun, as they give one a chance to make fairly provocative statements that would be out of place in a peer review publication, so I took up the opportunity.

In my view, there are really two key areas where reconfigurable computing solutions provide an inherent advantage over most high performance computational alternatives:

In embedded systems, notions of correct or efficient behaviour are often defined at the application level. For example, in my work with my colleagues on control system design for aircraft, the most important notion of incorrect behaviour is would this control system cause the aircraft to fall out of the sky? An important metric of efficient behaviour might be how much fuel does the aircraft consume? These high level specifications, which incorporate the physical world (or models thereof) in its interaction with the computational process, allow a huge scope for novelty in computer architecture, and FPGAs are the ideal playground for this novelty.
In real time embedded systems, it is often important to know exactly how long a computation will take in advance. Designs implemented using FPGA technology often provides such guarantees – down to the cycle – where others fail. There is, however, potentially a tension between some high level design methodologies being proposed and the certainty of the timing of the resulting architecture.

Despite my best attempts to stir up controversy, there seemed to be very few dissenters to this view from other members of the panel, combined with a general feeling that the world is no longer one of “embedded” versus “general purpose” computing. If indeed we can draw such divisions, they are now between “embedded / local” and “datacentre / cloud”, though power and energy concerns dominate the design process in both places.

Starting a Math Circle

I’ve been intrigued for a couple of years by the idea of math circles. Over Christmas I finally plucked up the courage to start one at a local primary school with my wife, a maths teacher. The school was happy, and recruited six pupils from Year 2 to Year 6 to attend.

Armed with a number of publications from the American Mathematical Society’s Mathematical Circles Library, our first task was to find a suitable topic for Session 1. Our primary goal was to find a topic that was clearly not everyday school maths, preferably as far away from the National Curriculum as possible, and ideally including practical activities.

In the end, we decided to look at Möbius strips. In the traditional of journal keeping for Mathematical Circles, I thought I would report the experience here in case anyone else wants to give it a go. In particular, we took the following approach:

Make zero half-turn bands (loops) and colour the outside in one colour. Then colour the inside in a different colour.
Repeat with a one half-turn band. This caused some surprise when it became apparent that one colour coloured the whole band.
Predict what would happen if you cut the zero half-turn band down the centre (prediction was universally that you’d get two zero half-turn bands). Try it.
Now predict for the one half-turn band. Children were less sure about this case, but the most popular prediction was two half-turn bands. More surprise when it turned out to create a single four half-turn band. One child then went off on his own exploring what happened when you cut one of these four half-turn bands (two four half-turn bands).

By this time some of children were already off under their own steam, trying out their own experiments. This was great, but even with only six children and with two adults, I found it hard to pull together the outcomes of these experiments in any systematic way in real time.

Eventually we discovered together that:

If the initial number of half-turns is odd, cutting gives you one larger band with more half turns. (I was hoping we’d be able to quantify this, but it turns out to be very difficult to count the number of half-turns in a strip – even for me, let alone for the younger children!)
If the initial number of half-turns is even, cutting gives you two interlinked bands with the same number of half-turns.

This took up pretty much the whole 50mins we had for Session 1, though I did briefly try to show them an explanation of why this might be the case, following the diagrammatic representation in this document from the University of Surrey. I probably didn’t leave enough time to do this properly, and they were anyway keen on cutting and exploring by that time, so with hindsight I probably should have just left them to it.

What delighted me was the child who wanted to take home his Möbius strip to show his dad. So, not a bad start to the Math Circle. Let’s see how we get on!

Overclocking-Friendly Arithmetic Needn’t Cost the Earth

This week, the FPT conference is being held in Shanghai. My PhD student, Kan Shi, will be presenting our work (joint with David Boland), entitled Efficient FPGA Implementation of Digit Parallel Online Arithmetic Operators.

In a previous paper, we’ve shown how the ideas of Ercegovac‘s “online arithmetic” – an arithmetic where computation proceeds from most significant digit to least significant digit, in contrast to the usual way we think about adding and multiplying – can be applied in the brave new world of clocking circuits faster than they “should” be able to run. The basic idea is simple: although sometimes beneficial, overclocking normal arithmetic – when it hurts – hurts bad, because errors tend to occur in the more significant digits. But if the flow of information were reversed, from more to less significant digits, then the error should hurt less too.

And so it did. But with one problem: to allow most significant digits to be generated first requires a redundant number system – a way of representing numbers where each number has more than one representation, for example, where there are two different ways of writing “10”. This redundancy cost a lot of silicon area.

This new paper shows that, in modern FPGA architectures, with careful design, the cost can be reduced significantly for adders. For multipliers, most significant digit first arithmetic has the important benefit that if you only want the most significant digits of the result, you don’t need to compute the least significant digits. In multiplication this is often the case, often in regular binary arithmetic we compute the 2n-bit result of an n by n-bit multiplication only to throw away the bottom n bits. We show in this paper that by judicious design, the area penalties of the redundant arithmetic can be eliminated in this case.

This work removes one of the last remaining hurdles that stops online arithmetic being industrially viable.

How (not) to Assess Children

Last month, the UK’s Department for Education launched a formal consultation to replace the statutory assessment in primary schools throughout England. The consultation is still running, and can be found at https://www.gov.uk/government/consultations/performance-descriptors-key-stages-1-and-2, and runs until the 18th December. Everyone can respond, and should respond. In my view, this proposal has the potential to seriously damage the education of our children, especially those who are doing well at school.

Currently, English schools report a “level” at the middle of primary school and the end of primary school in reading, writing, maths and spelling, punctuation and grammar. At the end of primary school, typical levels reported range from Level 3 to Level 6, with Level 4 being average. The new proposals effectively do away with reporting a range of attainment, simply indicating whether or not a pupil has met a baseline set of criteria. In my view this is a terrible step backwards: no longer will schools have an external motivation to stretch their most able pupils. In schools with weak leadership and governance, this is bound to have an impact.

I have drafted a response to the consultation document at https://www.scribd.com/doc/246073668/Draft-Response-to-DfE-Consultation.

My response has been “doing the rounds”. Most recently, it was emailed by the Essex Primary Heads Association to all headteachers in Essex. It has also been discussed on the TES Primary Forum and has been tweeted about a number of times.

I am not the only one who has taken issue with this consultation: others include http://thelearningmachine.co.uk/ks1-2-statutory-teacher-assessment-consultation/ and http://michaelt1979.wordpress.com/2014/11/13/primary-teachers-a-call-to-arms/.

Please add your say, and feel free to reuse the text and arguments made in this document.

Review: The Learning Powered School

This book, The Learning Powered School, subtitled Pioneering 21st Century Education, by Claxton, Chambers, Powell and Lucas, is the latest in a series of books to come from the work initiated by Guy Claxton, and described in more detail on the BLP website. I first became aware of BLP through an article in an education magazine, and since found out that one of the teachers at my son’s school has experience with BLP through her own son’s education. This piqued my interest enough to try to find out more.

The key idea of the book is to reorient schools towards being the places where children develop the mental resources to enjoy challenge and cope with uncertainty and complexity. The concepts of BLP are organised around “the 4 Rs”: resilience, resourcefulness, reflectiveness, and reciprocity, which are discussed throughout the book in terms of learning, teaching, leadership, and engaging with parents.

Part I, “Background Conditions”, explains the basis for BLP in schools in terms of both the motivation and the underlying research.

Firstly, motivation for change is discussed. The authors argue that both national economic success and individual mental health is best served by parents and schools helping children to “discover the ‘joy of the struggle’: the happiness that comes from being rapt in the process, and the quiet pride that comes from making progress on something that matters.” This is, indeed, exactly what I want for my own son. They further argue that schools are no longer the primary source of knowledge for children, who can look things up online if they need to, so schools need to reinvent themselves, not (only) as knowledge providers but as developers of learning habits. I liked the suggestion that “if we do not find things to teach children in school that cannot be learned from a machine, we should not be surprised if they come to treat their schooling as a series of irritating interruptions to their education.”

Secondly, the scientific “stable” from which BLP has emerged is discussed. The authors claim that BLP primarily synthesises themes from Dweck‘s research (showing that if people believe that intelligence is fixed then they are less likely to be resilient in their learning), Gardner (the theory of multiple intelligences), Hattie (emphasis on reflective and evaluative practice for both teachers and pupils), Lave and Wenger (communities of practice, schools as an ‘epistemic apprenticeship’), and Perkins (the learnability of intelligence). I have no direct knowledge of any of these thinkers or their theories, except through the book currently under review. Nevertheless, the idea of school (and university!) as epistemic apprenticeship, and an emphasis on reflective practice ring true with my everyday experience of teaching and learning. The seemingly paradoxical claim that emphasising learning rather attainment in the classroom leads to better attainment is backed up with several references, but also agrees with a recent report on the introduction of Level 6 testing in UK primary schools I have read. The suggestion made by the authors that this is due increased pressure on pupils and more “grade focus” leading to shallow learning.

The book then moves on to discuss BLP teaching in practice. There is a huge number of practical suggestions made. Some that particularly resonated with me included:

pupils keeping a journal of their own learning experiences
including focus on learning habits and attitudes in lesson planning as well as traditional focuses on subject matter and assessment
a “See-Think-Wonder” routine: showing children something, encouraging them to think about what they’ve seen and record what they wonder about

Those involved in school improvement will be used to checklists of “good teaching”. The book provides an interesting spin on this, providing a summary of how traditional “good teaching” can be “turbocharged” in the BLP style, e.g. students answer my questions confidently becomes I encourage students to ask curious questions of me and of each other, I mark regularly with supportive comments and targets becomes my marking poses questions about students’ progress as learners, I am secure and confident in my curriculum knowledge becomes I show students that I too am learning in lessons. Thus, in theory, an epistemic partnership is forged.

There is some discussion of curriculum changes to support BLP, which are broadly what I would expect, and a variety of simple scales to measure pupils’ progress against the BLP objectives to complement more traditional academic attainment. The software Blaze BLP is mentioned, which looks well worth investigating further – everyone likes completing quizzes about themselves, and if this could be used to help schools reflect on pupils’ self-perception of learning, that has the potential to be very useful.

In a similar vein, but for school leadership teams, the Learning Quality Framework looks worth investigating as a methodology for schools to follow when asking themselves questions about how to engage in a philosophy such as BLP. It also provides a “Quality Mark” as evidence of process.

Finally, the book summarizes ideas for engaging parents in the BLP programme, modifying homework to fit BLP objectives and improve resilience, etc.

Overall, I like the focus on:

an evidence-based approach to learning (though the material in this book is clearly geared towards school leaders rather than researchers, and therefore the evidence-based nature of the material is often asserted rather than demonstrated in the text)
the idea of creating a culture of enquiry amongst teachers, getting teachers to run their own mini research projects on their class, reporting back, and thinking about how to evidence results, e.g. “if my Year 6 students create their own ‘stuck posters’, will they become more resilient?”

I would strongly recommend this book to the leadership of good schools who already have the basics right. Whether schools choose to adopt the philosophy or not, whether they “buy in” or ultimately reject the claims made, I have no doubt that they will grow as places of learning by actively engaging with the ideas and thinking how they could be put into practice, or indeed whether – and where – they already are.

Insure yourself against your own inaccuracy

Last week saw the 19th World Congress of the International Federation of Automatic Control in Cape Town, South Africa. Three of my collaborators, Andrea Suardi, Stefano Longo and Eric Kerrigan, were there to present our joint paper Robust explicit MPC design under finite precision arithmetic.

The basic idea of this work is simple but interesting. Since we know we make mistakes, can we make decisions in a way that insures ourselves against our own faulty decision making? In a control system, we typically want to control a “real world thing” – an aircraft, a gas turbine, etc. Ourselves and others have proposed very sophisticated ways to do this, but since with each finite precision operation we might drift further away from the correct result, can we develop our algorithm in a way that provides a guaranteed behaviour?

We show that since control engineering provides tools to control systems with uncertain behaviour, it’s possible to incorporate the uncertainty of the control algorithm itself into the model of the system we’re controlling, to produce a kind of self-aware system design.

While the setting of this paper is in so-called explicit model predictive control, there’s no reason why this general philosophy should not extend to other decision making processes. It provides a rigorous way to think about the impact of decision quality on the overall behaviour of a system, since we can generally make decisions in any number of ways ranging from “quick and dirty” to “slow and thoughtful”, we could decide how to decide based on ideas like this.