Computer Science Teacher
Computer Science Teacher - Thoughts and Information from Alfred Thompson

June, 2008

  • Computer Science Teacher - Thoughts and Information from Alfred Thompson

    A Group Project – Create an Index File System


    Back when I first started writing code for commercial use I was working on a project on a small computer (about the size of a small refrigerator) that was also a very low cost computer (well under $100,000). Obviously a computer like that could not support a real database engine. Whoa! That sounds ridiculous in today’s world doesn’t it! Well in the mid 1970s it was true. Back then databases and even most good keyed ISAM (indexed sequential access method) file systems were very expensive and only ran on really large expensive computers. That didn’t last long of course but it was true for one of the first systems I worked on. So we had something that was home grown.

    Oh it was horrible. It was slow, inefficient, and complex to use. In fact they way it was set up when I started we had to create a set of custom subroutines for each new file we were going to use. The first thing I did was to create a single parameterized set of routines so I could reduce duplicate code and make the whole thing more maintainable, modifiable and supportable. I think that got me my first raise. It was also a great learning experience. Which got me to thinking recently.

    It occurs to me that students could reasonably be expected to duplicate this tool as a group project. There are a number of useful things it would teach plus it would be large enough that students working as a team could do it. This would promote that whole team work soft skill that is in such high demand these days. So let me explain how this system worked and how I think it could be used for a lot of discussion points.

    First off remember that this is a very inefficient tool. I know that. It makes it useful as a learning tool though as it automatically opens lots of doors for discussion. I’m also not looking to discuss the discussion questions below here on this blog. Rather I am suggesting them as useful in the classroom. With that said, this is how it worked.

    What we are talking about is an indexed access method file. The user (a program) enters a key and the record that matches that key is returned. If the record does not exist an error is returned. The system includes two files – an index file and a data file. The index file has a header record, a sorted key area and an overflow area. The header record has pointers to the first and last record in the sorted area and the first and last record in the overflow area. There is also a number that indicates the last possible record in the index file. The data file includes only data records which may or may not be sorted – and are mostly inserted in order that they were added in the first place. The key records include a key value, a pointer to the location in the data file where the data is and a flag that indicates if the record exists or has been marked for deletion. Note that in an alternative implementation the deleted flag could be in the data record rather than the key record. There you have your first discussion item – which is more efficient?

    The methods you would need in your program are:

    OpenFile – Open the key and data files. BTW let’s not allow shared files for now. Maybe later after more discussion about what that means.

    AddRecord – write the data record to the data file and write the key to the key file. If the key fits at the end of the sorted keys and there is room in the sorted key section add it there. If not, add it to the end of the overflow area.


    • What are the costs of sliding keys around to make the new key “fit” in the right place?
    • What about duplicate keys? Can they be allowed or do they complicate the system too much to be practical?
    • If the location we want is occupied by a record that is marked for deletion can we use it? If so do we add a new data record or just replace the existing “deleted” record?
    • What do we do if there is no more room in the file?
    • Is there a point where we should return a code that says “reorganize this file?” When is it?

    FindRecord – given a key do a binary search of the sorted area to see if it exists there. If if it not in the sorted area search the overflow area sequentially, If the key exists read the record from the data file and return it. If it doesn’t exist return a status or error code.


    • If the keys are all sorted we  could retrieve data in sequential order easily. What would a FindNext method look like and how would it work if the overflow is in use?
    • Error handling?

    UpdateRecord – Replace data in an existing record by re-writing it in the data file.


    • Do we just pass in the index of the data record as returned from a previous FindRecord call or should we use a key to call FindRecord to verify the address?
    • What errors could we have and how and where do we handle them?

    DeleteRecord – Set the deleted flag for the key/record.


    • How do we prevent deleting the wrong records? Do we delete based on a key search?
    • Should we over write the data in the data file? Why or why not?
    • Is this just a special case of UpdateRecord (which if might be if the deleted flag is in the record) or should be be completely separate?
    • Record not found? What other errors could there be?

    CloseFile – Close the open files and flush any buffers.

    Did I leave anything out?

    Now we probably also want three programs.

    • A test bed program to test the method created.
    • A reorganization program to run periodically. This program would recreate the key file by sorting keys including the ones in the overflow area and remove records that are marked for deletion. We probably want to recreate the data file to get back the space used by “deleted” records. Should we place the data in a sorted order? Why or why not?
    • A bulk load program. This program would take a flat sequential file, find the keys and create a new key/index file and a new data file. How that should work should be quite a topic of discussion. Should it require that the file be in sorted order for example?

    I’m not sure how long this should all take. I think it would depend on the number of students and their level of comfort programming. It would also depend on how much up front design work they do before they start coding. My gut tells me that more planning would result in a faster completion of a working project. The students will want to have all the method interfaces defined early as well and the internal structure of the files. Code re-use would be a time saver as well.

    Of course once it is done the next step is to find a much better system (have them look up B* trees [B star] for example) and see if the design they have allows them to completely change the file structure without needing to change the method calls for accessing data.

    I’d like to hear what others think of this as a project. Too much? Outdated by ease of using things like SQL, MySQL, Access, etc? Or is the learning and discussion of various issues worth the time themselves? If anyone tries it with a class I would really love to hear how it goes.

  • Computer Science Teacher - Thoughts and Information from Alfred Thompson

    Educational Games – A List


    I had a mixed experience using computer games in the classroom the year I was an elementary/middle school computer teacher. I used Oregon Trail with one class. The kids loved it but at one class session a week continuity was a problem. Plus I was not coordinating with the social studies teacher at all. In short I was doing about everything wrong that I could do. But the kids did seem to be learning something and it seemed to stick. In another class, in another school at the same time (I was part-time at two schools) I tried out the Incredible Machine as a reward for completing other work. Again the kids loved it and they seemed to start thinking about real problem solving. The overall experience left me leaning towards the idea that computer simulations could be good learning experiences. So I found this list of educational simulations and games rather interesting and thought that it might be useful for others.

    The College @ Home website (about which I know very little right now) posted  a list of “25 Best Sims and Games For the Classroom.” This is the most complete list of such games and simulations I have seen in quite a while. The descriptions should help parents and teachers to get an idea about what games may be worth a closer look. A simulation may be the thing for the kids to play during bad weather in the summer or perhaps even support education during the school year.

    In the long term I hope we seem more simulations (playable as games) to teach more things. Not just history and geography. Not as boring short attention span “drill and kill” games but opportunities for deeper understanding, problem solving and hopefully retained learning. Are these those games? Some maybe. Some maybe not. But they are a start. And if you know someone who thinks they are ready to write the next great educational simulation/game I’ve written about the tools for doing so using the game programming tag and the XNA tag.

    Of course in terms of teaching some programming using fun tools three that come to mind are Alice, Scratch and Popfly – especially with Popfly’s game creator in beta. Alice and Scratch have versions for several operating systems while Popfly is all online using a web browser like Internet Explorer or Firefox. And of course they are all free.

  • Computer Science Teacher - Thoughts and Information from Alfred Thompson

    May Posts in Review


    May was an interesting month for me in several ways. One area that I struggled with though was blogging. Perhaps it is because the school year is winding down but I could not seem to stay on a roll. Still there were a couple of posts that received a lot of traffic. XNA was big because of the Zune announcement. And people seemed to be interested in projects for use in their classrooms. I have a long post about a good sized group project that I want to propose. It will be coming later this week if I finish writing it. The top discussion item was on code optimization.

    Speaking of the Zune and XNA connection that post was here. In a bit of irony a lot of the traffic seemed to come from the trackback to the XNA blog announcement where there is really more original information. Though to be fair to myself I did link to other sources of information.  Speaking of more links, information about an online tutorial for Zune/XNA is here.

    In the area of computer science programming project ideas I had one post (here) that linked to a number of good projects by someone else. But I also had a complete description of a code breaking program that got a lot of traffic. Lots of that came from search engines but even more of it game from Dzone. My thanks to the person who listed it and the others who voted for it. I need to figure out how to add Dzone links to my blog like the Digg one I have a Windows Live Writer plug-in for. More project ideas are coming. In fact my goal for the summer is to develop a bunch of new programming project ideas.

    I had a number of useful things for people using Microsoft Office as well.  Here and here I talked about tools that make it easier to find things on the new Office 2007 ribbon interfaces. If you are teaching (or just using) Office 2007 those are tools you’ll want to check out.

    Other cool things that I talked about in May included:

    June is now off to a running start. Yesterday marked five years I have been working at Microsoft. The time has flown as I continue to have a good time working with great people – inside and outside of Microsoft. The best is yet to come I think.

Page 7 of 8 (22 items) «45678