The Tourist Problem

Prologue: The Tourist Problem was "my invention" way-back in June 1987 when I first came to NUS, Singapore. They are the first set of transparencies I wrote for the course "CS203: Data Structures". Since then, I have used it for a large variety of settings. Recently, I moved it to powerpoint, updated it, added "Hands-On-Activities" and more pedagogical enhancements.

In Week 2 of UIT2201, I covered a fast-track version of "The Tourist Problem".

The Big Picture:  The big goal is to illustrate computational problem solving in computer science, problem statement, problem analysis, problem modelling, problem solving and so on.

Along the way, I wanted to illustrate several things -- (a) asking questions, (b) giving simple, obvious solutions where they exists, and (c) analyzing the solutions; (c) asking more questions to address the problems, and so on. The point is that, if we keep doing this, then at some point, we arrive at interesting version of the problem and can work on interesting solutions.

And, I wanted to debunk the myth that to do interesting computer science, you must do programming.

The Specifics: After sufficient modeling, the problem of scheduling bus trips for the tourists is modelled as a graph colouring problem.  (...post to be continued...)

UIT2201: Lecture 2 (Week 2)

Lecture 2 (Week 2), 19-Jan-2010

Please read ahead for next lecture -- ppt for Topic 1 (Introduction), and under Topic 2 (Fun Stuff, the Tourist Problem). Enjoy and see everyone next week.

So, I covered the Introductory lecture, talked about the capable computer, one-data, multiple-views, and told the "computer-science-shampoo" joke. Also, used Scratch to illustrate algorithms for summing 1-to-100, and the story of Gauss and his formula.

Then, in the second part, we did a fast-track version of "The Tourist Problem". There is a separate blog entry on this. We did not quite finish it and we left it at a good point where the students can do some reflecting on their own.

For-fun: I collected all the origami pieces done by the students (UIT2201 Sp2010) and took a picture of it. And the result was the above -- the "Origami Collection for UIT2201 Spring 2010".

OK, it's now over to all of you students (UIT2201) to post questions, seek clarification, post follow-up discussion (for example, the one on "ant behaviour" raised by Zhou Zhong [ZZ: Please help post it as comments to this blog entry.])

UIT2201: Tutorial 1, Week 1

T1 (Week 1), 15-Jan, 2010

Tutorial 1 for UIT2201 is always an interesting experiment for me as it is always difficult to predict the reaction of the students to the unexpected questions that they see being asked and discussed. However, I must say that it went very well indeed! And I must thank all the students for doing that part and going with me on the journey to put on an "IT-thinking" or "computational thinking" hat during the tutorial with me. I threw a question at them, "How many ways are there to find out how many people there are in this room? in this lecture theatre? or in general, in any big groups of people? We went on to talk about divide and conquer (good ways to do it and also bad way to do it) and other creative solutions. (This reminded me of an old writeup about a similar problem. I will find it and post a link later.)

We had interesting discussions on "how to give instructions" (and the many different ways in which to give them as witnessed from the students' contributions) and upon further exploration, it became more obvious that it was not an easy task at all to give "precise and concise instructions". [After classes, I just though of the term "universally executable instructions".] We also explored the question of what level of abstraction should be adopted, discussed divide-and-conquer in this context -- breaking the instructions into big chunks, and giving further details as necessary. We then found similar issues when tackling T1-D3 (automating a process), for many different processes.

Also, one student (was it YingDan?) wanted to try out the 9-ring puzzle, so I will "reset" it and pass it to her next week. Also, I was in a hurry to go to the next appointment. Overall, I was happy with tutorial 1, I hope everyone enjoyed it and learned something too.

UIT2201: Lecture 1 (Week 1)

This semester, I was a little surprised my class size was bigger than usual (almost double that of last year)*. I had prepared a roster on Friday with 25 students, but on Monday morning, that went up to 30!

In this first lecture, I want to set the tone, to get people comfortable with each other and me and to start asking questions. It was useful that one of the students, Tomithy, added in a post in the forum to get things going. As of now, we already have an interesting thread going on the issue of "iteration vs recursion"!! (woW!)
The first lecture went well, it was also good that in the UIT2201 Alum FB group, various people have put up their personal reflections (and some photos)! I am excited with the class and I hope the students are equally excited too.

One of the photos (from Juliana) on the FB group is of the 9-ring puzzle and so I brought the 9-ring puzzle to class. At least one student has solved it before. I promised to buy the whole class coffee if by the end of the semester, at least half the class knows how to solve it! This will be a massive coffee award.

Over the past month or so, I thought about using Scratch as the common platform for algorithm demo and for student projects. It was only last week that it was finally decided that, "Yes", we will go with Scratch. So, over the weekend, we (me and a secret helper friend) worked on sample Scratch code to demo the algorithm in Week 1 lecture notes. We had a meeting yesterday and talked about other Scratch features (and also features that are not directly supported). It appears Scratch will be a good platform. I was glad that when I show the Scratch homepage, the first audibles that came from the class was "cute".

I did not cover as much as I wanted to, but it was a good first class and I think the people have warmed up and are feeling comfortable, at least the vibes are good. There were healthy questions and discussions. My FB status update after the lectures was: [[ ...UIT2201 first lecture today. People asked about 9-ring puzzle, about recursion, about mini languages (with few primitives). Actually, the 3-things are intimately related to each other, even though these questions came from different parts of the lecture!!! "There are only 2 primitives in 9-ring puzzle, and to solve it we keep applying two recursive procedures!" Great, love it. ]]

Regards, --hon-wai
* upon further checks, it was partly due to reduced supply (fewer modules on offer during the semester).

Starting up a Blog (afresh)...

Starting a module blog (afresh*) and did not want to use the NUS blog space, so I chose to use blogspot instead. Actually, had been thinking for a while about doing this although I did not really start. But lecture 1 of UIT2201 this semester and the comments and questions from the students after that help pushed me to do this.

Initially, this will be largely a UIT2201 blog (blog for UIT2201 students and staff and I encourage and welcome comments and follow-up from students in UIT2201, present and past). However, over time, it will also be a blog about my teaching, courses, and outreach workshops and talks.

So, now it is off to start putting in messages...

Regards, --hon-wai
* Some of you saw my previous module-blog back in 2008 that was discontinued (no longer supported).