Tuesday 30 August 2011

A Nerdy Day Out: Maze Algorithms

Every August bank holiday, me and my family take a visit to the Wistow Corn Maze in Leicestershire. It's a huge maze made, humorously, of maize. The design changes every year, and this year (spoiler alert) it was designed like a bee.

 Photo used with kind  permission from the owner of the maze

Now it might not surprise you to hear that my family are all big geeks. Neither of my parents did maths A level, but they're both a product of an experimental system called "New Maths" which was where the curriculum suddenly completely changed in the 1970s and 6 year olds were learning set theory. My parents both know some basic group theory, and claim to have been taught Boolean algebra in year seven. My parents seem to know *everything*. They're the cleverest people I know.

One of my brothers did Physics at uni so is a slightly different kind of geek from me. The other one pretends not to be a geek with his cool metal band and all that, but he so is.

What happens when a family of geeks takes a trip to a maze? The first time we went, we took one step inside the maze, and instantly agreed we'd follow the left-hand rule algorithm. We stuck unfalteringly to this path, and looked upon families who were randomly meandering (or worse, reading the map!) with equal parts pity and disdain.

There are 12 boards hidden around the maze with pictures on, and the aim is to find these 12 boards and draw the pictures, then convert the pictures into letters at the end, to spell out a word. Naturally, my family takes this part very seriously.

Let's have some maths, shall we?

Maze Algorithms

The Left (or Right) - Hand Rule (Wall Follower Algorithm)

As long as the walls of the maze are simply connected (every wall is touching the outside wall, so there are no islands), then placing your left (or right) hand on the wall and never letting go as you walk will mean you will always be able to find an exit, or if there isn't one, the entrance. This works because (topology alert) the maze can be deformed (stretched and squished) into a circle, and obviously this rule works on a circle.

This rule fails when there are bits that aren't connected.

Pledge Algorithm

This is the only other algorithm I know (wow, how well-researched is this post!) and it works when the wall-follower algorithm doesn't (on disconnected mazes). This is how you do it: you choose a random direction and walk that way. When you hit an obstacle (a wall), you do the right-hand rule with it and count how many times (or what angle) you turn around it. When you have turned a full 360 degrees (or 0 degrees, or 720, or, ... basically when the angle sum is zero) and you are facing the direction you were when you started (not necessarily the same thing) then you stop doing the right-hand rule and continue to move in the original direction (before you stopped at the obstacle).

So what did my family do this year? Well as usual we started with the left-hand rule. My "cool" borther protested that it would make the maze less fun. But his protests lacked conviction and were easily batted away. He knows deep down that he is one of us. After about twenty minutes, we ended up back at the entrance. Darn. Follow my family's route on the map if you like.

 This is the map you're given when you come in. Excuse the crumpledness.

Wistow maze is always a disjoint maze, with an inside track and an outside track. It has two bridges at opposite ends (shown on the map) for you to get from the outside to the inside and vice versa. But as you can see (if you can be bothered), following the left-hand rule means walking past the bridge in the NE but not walking across it. This is why our algorithm failed us. So we had to back track (easily done using the right-hand rule) to the bridge and go across it. Then we resumed the left hand rule until we got to the Mid Point, which has picnic tables and is a good place to stop for a Werther's Original and/or a bag of crisps.

From the Mid Point, there are 6 paths you can take. One is labelled the "quick exit" (the West path) and we came from one of them (the NW path) so we had 4 more to explore. We took the North path because that's what the left-hand rule dictates.

The twelve boards we were trying to find are not usually marked on the map, but this time they were (they're the black crosses, not the numbers), probably to speed people up as it was a busy day. We allowed ourselves to diverge from our algorithm in order to get to a nearby board, but we returned to the original path *immediately*. The left-hand rule is not an algorithm that guarantees to cover every path in the maze. Is there an algorithm that does? Obviously it depends on the maze. In graph theory, I know that you can cover each edge in a graph exactly once as long as the graph has an even number of odd nodes. I'm not sure how to translate that into mazes at the moment. I need to have a think!

School Trip???

Wistow Maze welcomes school trips and even has a lesson pack that you can email to get. However, it's aimed at key stage 1 and 2, and won't have anything to do with maze algorithms. I personally think they are missing a trick there!

I think you could do a really cool school trip with higher level GCSE and A level pupils. When I did D1 there were questions on the exam (MEI) about maze algorithms, so it would be a nice accompaniment to that module. If your school is in Leicestershire or neighbouring counties, definitely consider taking a group there. The maze is open mid July until the end of September, so it would be a good end/start of term treat.

Have you ever been to a maze? Did you geek out about it or did you walk it like a normal person?

Emma x x x

Saturday 27 August 2011

This time last year I was feeling really excited about the start of my PGCE. The PGCE, for those of you who don't know, is the Post-Graduate Certificate of Education, which is a one-year course you do to get Qualified Teacher Status (QTS) in England and Wales. There are other ways to get QTS (like the GTP) but I think the PGCE is the most common. Our neighbours in Scotland do a similar course, but they call it the PGDE, because they just had to be different.

If you're about to start your PGCE, you might be wondering what to expect. My university gave me hardly any information about what the course was actually like before I started. Luckily, you guys have me to fill you in.

Expect to...
• Have loads of fun in the first few weeks. This will probably be university-based and, if it's anything like my experience, you will feel like you're back in seconday school again. I loved it, especially as I made lots of new friends (hi, if you're reading this!).
• Be asked to do lots of reading. My advice is this: don't do it. It's pointless. You learn nothing about teaching from books. You only learn from hearing other people's stories, or from being in a classroom yourself. If you get picked on during a seminar, use an anecdote from your own school experience as a pupil, rather than something from the book. The teacher will never know ;).
• Have lots of paperwork. When you get given a piece of paper, decide imediately which of the following categories it comes under: "important" (as in, to do with you getting your qualification), "seems important but is actually unnecessary" (the details could be typed into your phone so that you can throw the paper away, the information on it is somewhere on the university's website), "useful" (an idea for an activity, the name of a good book for your essay, a website to check out),  "they say it's important but honestly I'm never going to look at it again" (an article, a PowerPoint handout). As soon as you know what category it comes under, you will know what to do with it: file it, make a note of it then recycle it, ditto, recycle it immediately. **Edited to add** Start collecting articles and things that could be used in the masters essays right from the start. As Liz pointed out in a comment below, the "post-reading" that was set us was often very good for using in the masters essays.
• Be placed in a school far, far away from where you live. If you have a car, this means not too much inconvenience but a sudden huge rise in your petrol costs. For pedestrians like myself, it means catching the bus at 6:20am, and falling asleep on the bus on the way home. My advice: buy a bus pass, and if you're in the midlands, use Traveline's brilliant website.
• Spend about five hours planning your first lesson, only to have it turn out a complete disaster. Hey, it's a rite of passage!
 Our university sessions involved a disproportionate amount of origami.

 The task was to make something that will hold five ping-pong balls. Our group made origami bunnies.
I think my most important piece of advice is to make some friends within your subject and organise a Friday afternoon pub trip every week. It's great to be able to let off steam about how annoying the course is and how terribly your first lessons have gone. Without this, I don't know how I would have survived!

I think that's enough for the first half term (also known as the calm before the storm).Good luck to all new student teachers and enjoy it whilst you can. The NQT  (Newly Qualified Teacher) year is apparently a lot harder (gulp).

Emma x x x

Sunday 14 August 2011

Explaining the Fourth Dimension

Has a kid ever asked you what the fourth dimension is? What it looks like? Whether it could possibly exist?

No, no kid has ever asked me either. But I really wish one would one day.

Anyway, I was reading this book by one of my favourite authors, the hilarious Scottish crime writer Christopher Brookmyre. The book is called Pandaemonium and for goodness' sake don't recommend it to any of your pupils. The "c" word appears frequently, there's really really gross violence and gore, and it's just generally very offensive. If it was released as an audiobook, it would be read by Frankie Boyle.

I loved every page.

Anyway, I'll try and get to the point. There's this bit in it where CB explains the concept of a fourth dimension really nicely. I loved it so much I highlighted it and wrote a little note (I LOVE my new Kindle!!). I'll try and paraphrase it here:

Imagine there are some ants crawling across the duvet on your bed. They are only aware of two dimensions: walking forwards and walking sideways. There is no up or down for them. So if you picked one of the ants up and suspended it in the air, all the other ants would think the ant had vanished. They would have no idea where it went. And then if you put the ant back down a few centimetres from where you picked it up, the ants would all think it had teleported.

Maybe there's a higher dimension out there that we can't comprehend. Maybe there's something out there that could pick one of us up and put us down somewhere else, and it would look like we've teleported. If we could access this fourth dimension, think of the possibilities: we could perform surgery without breaking the skin.

Back to the ants on the duvet: imagine picking up two opposite corners of the duvet and bringing them together. The ants are still only moving in two dimensions, but now they can walk off one edge of the duvet and return at the opposite end, walking in the opposite direction. This involves moving their world around in three dimensions, but keeping it as a two dimensional world, and without them noticing. Could something similar happen to us? Could we walk off one "end" of the universe and end up on the other side? Is dying walking off the end? Does God live in the fourth dimension?

Well, I found it interesting.

Emma x x x

Saturday 6 August 2011

Khet - The Laser Game

Today I played Khet for the first time (and won, natch). It's a strategy board game similar to chess, which involves moving pieces with mirrored edges around the board, and firing a laser so that it bounces off your pieces and hits your opponent's.

Obviously, there's a lot of maths to be had here. Firstly, bouncing lasers off mirrors requires some understanding of angles. The mirrored edges are at 45 degrees to the grid of the board, so the laser always hits the mirrors at this angle. As the angle of incidence must equal the angle of reflection, the laser comes off the mirror at 45 degrees, which is 90 degrees from where it was hit. So the laser beam always moves in L shapes between mirrored surfaces.

The game also involves problem-solving, as you have to consider where to move your pieces in order to block your Pharoah (did I mention all the pieces are Egyptian-themed?) and to take out your opponent's pieces. It's similar to chess in that you have to be thinking several steps ahead at each point.

The game was a Mensa Select Award winner, so clearly it's a game that can involve a lot of intellectual stimulation. But it's easy for anyone to understand enough to at least have a go.

It would be impractical to have everyone playing this in a maths lesson, but you could give pupils a situation on a worksheet and ask them what their next move would be, or ask them where the laser would point if it was fired then. Like how in newspapers they often have a picture of a chessboard and you have to decide what your next move would be.

Khet would be great for an afterschool or lunchtime maths club. It takes about 10-30 minutes to play (according to Wikipedia) so you could easily fit in a game. Obviously the school would have to buy a few sets first. It is available in many places online, including Amazon.