Case Studies in Algorithms and Programming

Peter R. Whitehouse

Subject Coordinator, Information Technology Education
St. Joseph's College,
Gregory Terrace, Brisbane

p.whitehouse@mailbox.uq.edu.au

An emphasis in the Queensland BSSSS subject IPT (Information Processing and Technology) is systems analysis and nontrivial system development. Over the past 6 years, I have chosen to involve my students in the design and implementation of common games using a 3rd generation language - Pascal.

It can be argued that there is much to be learned from the playing of games - particularly the often exquisite decision pathways, branches, necessary to play a game effectively. More important than the game play, however, is the reasoning required to build a system that makes a dumb machine appear to be proficient at playing and managing a game in real time.

Such exercises are sufficiently engaging to interest a broad range of student abilities, whilst challenging enough to provide algorithmic complexity such that planning is vital to the success of the system. This exercise differs significantly from the trivial systems computer studies routinely offer to students to 'hone' their algorithmic reasoning.

Students are required to formally PROPOSE, DESIGN, IMPLEMENT and DOCUMENT their systems according to structured criteria. This ensures students are engaged in many forms of technical communication, yet have the system as their focus.

Whilst St. Joseph's College, a private catholic boys college, has no entrance prerequisites, it is generally the more able students who elect to study IPT. Saying that, however, we get a diverse range of student ability participating in this complex discipline.

As a MAJOR assessment item (10% of Exit), students are required to develop a gaming system for a target audience. In addition, they are required to provide user and technical documentation to support their product.

The assignment is divided into a number of discrete PHASES. Each phase must be completed, corrected and returned before the next phase is to be attempted. This phasing (or staging) of the assignment forces students to consider a production time line. Failure to keep to the phase time line incurs mark penalties for completion of that phase. Students unable to complete a phase are welcome to forego the marks in order that the phase is completed for them (in consultation with their teacher).

This assessment instrument involves the student in the many and varied tasks that typify system development, working either singly or in groups of up to 3. Considerable class time is devoted to this assignment, and it is expected that students at least match the amount of class time with their own time (most however choose to use more of their own time than has been allocated in class).

Students, either singly or in groups of up to 3, select a gaming topic from those supplied with the item. Should they wish to deviate from the set list, they are required to demonstrate clearly they understand the complexity of their choice and are required to feedback constantly during the development phases to ensure they haven't 'bitten off more that they can chew'.

Students get the assistance they ask for. It is my considered opinion that successful students know when they don't know something, and have the good sense to seek assistance when they need it. I will not, however, force help on a student that does not ask for it.

The Formal Proposal phase forces students to think clearly about their product BEFORE they build it. Most find this difficult, and they must rely on past experience of gaming, and look/feel of other systems as their best guide. Consideration during the proposal must be given to the interface, the target audience and the breadth of services that could be offered in the product.

If students are unsure whether a proposed system is within their capabilities, they are encouraged to pre-propose - that is submit their ideas (as complete as they know how) and they receive practical feedback as to the suitability, complexity and viability of the idea. Many students use this informal process to better select a system prior to the proposal deadline - thus minimizing lost time.

Should students have their proposals approved, they then proceed to the next phase, if the proposal is rejected, they reformulate and resubmit until they produce an acceptable project. Either way, should they successfully hand in their proposal by the due date, they receive completion marks for the proposal. Progression to the next phase, however, is conditional upon having a proposal approved.

The Design phase provides significant challenge for most students, and typically they couple this with testing of code fragments. Students are instructed in how to design algorithms using Structured Design Charts and Pseudo code, most students end up using a combination of both to describe the modules that will make up their system. Most students appear to develop code and plans simultaneously

The Implementation is where most students enjoy the most and least. Whilst coding their algorithms, students will find shortcomings in decision logic, processes omitted and new things they wish to add - they are required to update their plans as they go. By the time they are meant to be implementing their systems, the majority of the techniques they will want to use in their systems will have been covered practically in class.

Documentation is an ongoing exercise, and requires students to communicate at different levels, depending on the target audience. Their user manual is aimed at the target end-user, the technical appendices contain system specifications developed earlier. As students are required to computer generate as much of their hand-in as possible, much of this is useful in compiling their manual. In-program commentation is another level of documentation that is compulsory, with standards being set regarding what should be included in source code.

System manuals can either be conventional word processed documents, or more recently, HTML webs and Windows Help files, although these also need to be printed to satisfy BSSSS certification requirements for student folios.

Students attempt this item in Year 11, after approximately 2 terms of Algorithms and Programming. By this stage, students have had experience with data definition, input, output, decision logic, iteration, sub-programming and have begun to investigate compound data types (arrays, records and files). The assignment is delayed until such time as students are equipped with the appropriate skills to be able to confidently tackle most of it. Experience has shown that students will believe they can tackle anything, given enough time. I, on the other hand, would prefer to equip them well first so their progress through the project is as independent as possible.

The principle language used for this assignment is Pascal. Originally, Borland's Turbo Pascal, we have recently moved to Borland's Delphi v1.0. The move from 'text based' programming to the visually rich GUI-based Delphi has, in my opinion, not been an easy one - an opinion my students will probably not agree with. Students now are presented with a vast arrange of colourful prepackaged visual components, and it is possible to 'knock up' an impressive looking interface in very little time. Student's emphasis has shifted from what a system does to what a system looks like. There is a trap inherent in this shift - although students still need to know how the underlying logic works, they are presented with the illusion of being 'gifted' system developers - such is the two-edged sword that a RAD (Rapid Application Development) environment affords.

Students originally were encouraged to investigate text only implementations. For many, this proved too limiting, so concession (but no additional marks) was given to those students who wished to incorporate graphics into their systems. Turbo Pascal graphics are 'primitive' yet can greatly enhance the visual appeal of a system - many students were drawn to this fact. With the shift to Delphi, students are presented with the choice to develop a CRT (text) system, or move to an Event-Driven, graphical form-based systems. Most students now choose GUI systems.

The battle between what a system looks like and what it does is not a recent phenomenon. It has been my experience that male students will concentrate masses of their system development time to 'intro screens' and 'credit sequences', assuming that the game will be usable/entertaining/worthwhile so long as it starts up fancily - Unless they are forced to do otherwise. In the example section, you will find a mixed bag of systems, some that look pretty but do little, some that look awful but do much, and others that look and function well.

We have had, for a number of years, licence to Delta - a CASE Tool (Computer Aided Software Engineering). Delta allows the development of algorithms which can take the form of: Structured Design Charts (my preferred method), Flow Charts, and a number of other diagrammatic solutions. With the click of a mouse, algorithm plans can be turned into compilable code. Whilst I encourage students to use such methods to plan out their systems, I ask that they perform the coding manually, using the charts as a guide. I acknowledge that eventually, the necessity to code may disappear for all but the masochistic, but I believe the translation between conceptual and physical is a vital process - it is also the part of the project the majority of my students enjoy the most.

Students have access to large collections of 'clip-art' graphics and soundfx. Many students develop their own visual elements, and some 'borrow' elements from existing packages.

The following marking scheme (and weightings) have been applied to the assignment:

Phases 1 and 2

The 'Proposal' and 'Design' phases of the assignment are assessed using COMPLETION marks - that is, students are given a set of instructions and a deadline. Should they decide to complete the phase as per the instructions by the due date, they are awarded ALL of the marks for that phase. Should they decide not to do the above, then they forfeit the marks but must complete the phase anyway.

Phases 3&4

The 'implementation' phases of the assignment are CRITERIA BASED as shown above - here students are assessed on how well they completed each of the required elements in system building and documentation.

Group Work

Each student completes a PEER ASSESSMENT form on the other member(s) of the group. The form attempts to identify strengths, weaknesses and relative contribution to the various stages of the assignment made by each group member. That contribution is then used to allocate final marks to the assignment. Since close teacher monitoring has taken place, realistic peer evaluation is monitored, and mediated.

Examples