|
HL1 A Virtual Assembler/CPU Simulator
The students define a virtual machine with associated assembly code. On the rerun is shown diagrammatically the registers and (limited) memory of the virtual CPU. The user enters an assembly program directly into the displayed memory. The 'assembly program' is then run and the change in content of the memory locations and registers is displayed in real time.
Other Comments
A difficult program but it could be used to teach assembly/machine code and basic CPU architecture.
HL2 A Database
The students are asked to write a data management program. Typically an address book program. Their program must be able to add and delete records, and sort and search.
This is set to both higher and subsidiary level students. There is much scope for the highers to use more advanced programming techniques i.e. linked lists, binary trees, advanced sorts. At the same time the standard level students can write a partially adequate program with more limited techniques.
This is a popular and relatively straightforward problem for students at all levels of ability.
HL3 Queuing Simulation
The simulation can be of queues in a bank, traffic lights etc. Obviously dynamic data structures are easy to include. More challenging is to include data files but run data could be stored in a file - for example how many time steps the simulation is to run for, how many tills are to be open, how many cars are approaching each junction - organized with a record structure or, perhaps as a text file to be interpreted. A potentially challenging project as it can fail dramatically if not completed (not easy to do incrementally).
Consider using a fully object-oriented design.
HL4 A programmable calculator (infix, prefix or rpn)
Programs can be entered line by line and tested or stored in a file for later retrieval. Conversions from one form of expression to another can be done (use a tree). A simple editor is needed (line editor would do). A stack ADT could also be developed for the new program, first exams in 2006.
HL5 Travelling salesman
Routes between towns, shortest distance, shortest time,. Research on Dijkstra's algorithm vital - be aware of non-computable issues before starting!. Variations include planning transport routes (eg, create a bus route that picks up maximum passengers using least fuel).
HL6 Computer Performance Tester
A program to be run on different computers (with compatible operating systems) to test and display the performance of the machines at certain tasks, e.g. Read/Write to disk, floating point arithmetic etc. Could be used by someone wishing to compare price/performance of various computers on offer at a local store.
Other Comments
Also reinforces various aspects of the syllabus. May also ask student to put in net sorts and searches, recursive procedures. Results can be stored in a data file which can be manipulated by a second program if desired (eg, records can be updated, summary tables can be produced, searches can be made for the fastest etc).
HL7 Maze, again
Program the computer to find its way out of a maze. The maze should be displayed on the screen. The program must try a variety of paths until it finds one which exits the maze. The best solution will show the searching, and will eventually find the SHORTEST route out.
This is an excellent program for studying recursion. The students find it easy to understand that recursion is the simplest way to solve the problem, but it also deals with the tricky issue of ensuring that a recursive procedure does not produce an endless loop - the computer could try a circular path and get stuck.
The issue of how to store the maze and how to represent the routes can lead to use of pointers as well. If a variety of mazes are used, this can also lead to an interesting discussion of algorithm efficiency (big-O).
Hard to find a user unless you live in a corn-growing area!
HL8 Data Compression
How to shrink a file and grow it back to normal size again. The "real" algorithms used by professional programs like PKZIP are too complex for most students to program successfully. But some very simple algorithms exist - 8 bit to 7 bit shortening, a simple dictionary with pointers, counting repeated bytes in graphics files. Students should investigate the efficiency of the algorithm in detail, both experimentally and theoretically. They will have more success if they choose an algorithm which is good for a specific type of file - 8 to 7 bit for text files, counting repeated bytes for graphics files.
HL9 Scheduling
Train schedules and routes - recording them, reading them, planning a journey (routing)
How are train schedules - times and routes - recorded? What kind of data-types and data-structures are useful here? Once the schedules are available, how does a computer plan a journey for a customer? How does it find a possible route? Can it find the shortest route? If pricing data is available, how can it determine the cheapest route?
Other Comments
The routing question is a very difficult problem, but one which allows a lot of scope for Higher Level students to explore advanced data structures, pointers, and searching techniques. It leads to a discussion of computable and non-computable problems.
SL students might be able to deal with a simpler problem in the same real-world arena (see also problem SL13):
HL1O Spell-Check
Spell-check program - checks for correct spelling of words in an ASCII Text file.
All questionable words are flagged by inserting markers such as @ or -. The result is written in an Output file which can be corrected by the user.
Other Comments
This is a good problem for DESIGN BEFORE CODING. It also allows a lot of work with data structures. For example, how does one go about creating the reference dictionary? Where does one get a list of "correct words"? (Hopefully not by typing in 10,000 words!). How does the program break the source file into separate words?
A simpler version, using unsophisticated search techniques, can be done by SL students. A more elegant version, using data compression for the reference dictionary and a search tree, can be attempted by Higher Level students.
HL11 Mail Merge
A form letter is produced which uses "placeholders" like <name>, <video>, <days_overdue> and so on. Another file contains data records with actual names, video titles and numbers of days overdue. This data file can be updated by the user.
The problem is to replace the keywords with appropriate data from the file. This is a nice program for analysis since students can probably easily find manual examples of this (forms with blank spaces) and, of course, applications like ms Word which serve the same purpose.
A challenge would be to include dynamic data structures; the file maintenance part could include search functions with results being returned in a linked list.
HL12 Chess Puzzle
To have the computer interface with a user trying to complete a puzzle. The puzzle is to set up 8 queens in such a way that no queen will be able to capture another queen. There are only four possible solutions, and the computer must recognise the solution once the user has arrived at solving the puzzle. Moreover, the computer must recognise the solution once the user has arrived at solving the puzzle. Moreover, the computer must delete all queens which could be captured by the new queen.
Other Comments
In order for the computer to store a list of how many queens there are and where they are, lots of memory would be required, but not very much would be used all at once. (The arrays would only be full at the end). Along with a memory problem, would also come the problem of speed. The computer would have to search through multiple, sparse arrays. The logical advancement from arrays lies in the realm of linked lists. Linked lists are extremely economic in memory use. Once a pointer has been deleted, the memory taken up by it becomes free. This is in comparison to arrays where although the memory is not being used, it is still kept by the array.
Might be used by a student or teacher doing research into cognitive skills of younger and older children, males and females - test results (timings) can be stored, collated and summarised. Problems could be simpler if desired.
HL13 Suspect Database
The assignment is to write a program for a police department that has collected a database of information on various suspects for a given crime. Each suspect has a set of attributes, such as shifty eyes, a limp, or a parrot on his shoulder. The maximum number of such attributes for any suspect is not known. The program will accept commands to manipulate the database in order to narrow down the list of suspects, in the hope of pinpointing the villain.
INPUT:
The retained criminal information, generated by previous executions of this program, is input from file CRIMINAL.DAT at the beginning of each execution of the program. The User inputs commands from the keyboard, in the format shown below. Names and attributes are strings of no more than 20 characters. The program should not be case sensitive. To simplify the processing, one can assume that names are unique; that is, no two criminals use the same professional handle. The commands are discussed in detail in the Command Structure section above.
OUTPUT:
It should show the results of any PRINT commands in a text file called CRIMINAL.TXT. One may determine the format of the information in this file; it should be labelled and formatted clearly.
If any new suspects were added, file CRIMINAL.DAT must be rewritten to contain the updated collection of criminal information.
DATA STRUCTURES:
There is no upper bound to the number of suspects or number of attributes for a given suspect. Arrays cannot be used to store the suspects of the attributes for a given suspect. A dynamic, linked structure must be used.
The CHECK operation must be very efficient. Using a simple linked list to store the suspects will not be sufficient. One must use a binary search tree. Suspects must be actually deleted from the structure when they are eliminated by TIP information. Using a Boolean to mark the suspects who have been eliminated is not sufficient. Since one will be destroying the list of suspects, as suspects are eliminated by TIP information, each inquiry should work on a copy of the original data.
TIP is executed much less often than check and hence can be less efficient. It is acceptable if processing a TIP command requires searching the whole data structure of active suspects. Thus, a list of attributes can be stored with each suspect. It is not necessary to link all the suspects with the same attributes together.
HL14 Pharmacy/Drugstore
It is important to keep track of the drugs that are sold for prescription or over the counter - many countries have legal requirements for accurate records to be kept. It could be a standard stock control type program or could just archive records of sales. Students would be encouraged to visit real establishments as part of their fact-finding. Also suitable for SL students.
HL15 Internet Cafe
Increasingly favourite in well-travelled areas, these are a natural for computer-based records of computer usage and calculating billings based on time used. HL solutions can include a hierarchical composite data structure by having a time record/object as part of the main usage record. Really smart students could attempt a network-based program (although this ought to be an add on after the main part of the solution has been completed).
Back to top |
