On ה', 2005-11-03 at 01:26 +0200, Amit Aronovitch wrote: > * Do you have some ideas for self reading/self exercising for the week > between the first and second lesson? Maybe some pen & paper experiments, > extending the "robot" demo? > > For example, you can describe a small size labyrinth as a grid where > each cell is either "wall" or "path", with an single "entry" and "exit" > points on the otherwise closed border. > The robot can see the cell in front, can turn left, right or move > forwards. You write a "program" describing the decision to make for each > step. One possibility is having them write the "wall follower" algorithm > (lookup "Mazes" in wikipedia), maybe in a guided way (this might be too > hard). Another is: > (1) supplying the algorithm > (2) asking them to "run" it on a simple maze to see it solves it > (3) asking them to find a labyrinth that the program can't solve (or > just supplying one with a loop, and asking them to run it there) > (4) now, you say the robot also knows for each cell whether it was > visited before or not (e.g. - each cell is either wall, visited > passage, or unvisited passage). You can now ask to use this extra input > to write a program that can solve the maze from (3) - Tremaux's > algorithm (see Mazes in wikipedia), probably supplying hints. > I still remember the first Pascal lesson in school. The teacher didn't start by talking about how computers work, what's a programming language, etc. She started by presenting Dijkstra's shortest-path algorithm! Simplified a bit - she explained it for a maze, taking all distances to be 1 - it can be explained in a couple of sentences to people with no idea about computers:
Start from the target. Mark all neighbours of the target with 1. Mark all umarked naighbours of 1's with 2, and so on. This gives you have the shortest distance to the target from any point. Now starting from the source point, every time take a step to the neighbour with lowest marking. I think she than mentioned the generalization for cities and roads of arbitrary length. Only then she started talking about what programming is like, etc. And the following lessons became boring Pascal. But later when we got to work in the lab, my friend wrote a pacman-like game utilizing this algorithm and I wrote the maze editor for it. And I think others remembered this algorithm too. What I wanted to say is that Dijkstra's algorithm is simpler to think about and to implement than wall-following (why it works is less obvious; facing direction and walls require careful implemention) or Tremaux's algorithm (not really recursive but still a bit tricky). Of course Dijkstra's alg. is for another problem - when you can look at the map - but we can pick any problem we like. It's also more representative of computer algorithms and invites nicely to the data structures book...
