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.])