Going Loopy with Loops
Reinventing the wheel can often give a deeper understanding of the problem and highlight some of the esoteric features of your chosen programming language — however, remember to go back to using the standard method and style in your production code!
I like loops, they are predictable, reliable and relatively easy to understand. For many common algorithms there are much more efficient ways of computing the solution, however loops often provide an easy to understand approach to getting to the right answer — eventually.
Recently, when demonstrating looping constructs to a beginner I provided the following three examples which spit out 1 to 10 on the terminal.
// Traditional
for(int i = 1; i <= 10; i++) {
System.out.println(i);
}
// Unorthodox
int i = 0;
while(i < 10) {
System.out.println(i+1);
i = i + 1;
}
// Too smart for own good
for(int i = 0; i < 10; System.out.println(++i));
Each sample was slightly more complex, conceptually, than the next. The final sample demonstrating how the for could be abused to show the desired output on only one correctly formatted line. In it we use my favourite pre-increment operator to push the the 0 up to 1 before we output the number to the display. Of course we could have used 1 and 11 as our bound with the post-increment operator, but any sane programmer would agree that numbering should start at zero.
Extending the code abuse further, while browsing over at Stack Overflow I discovered that while is largely redundant, if you are happy to abuse for some more. Turns out that for, as typically defined, assumes the test condition to be true when omitted and all three sections of the for statement are in fact optional. As one of the moderators put it:
This answer pretty much proves the awesomeness of the “No question is too simple” policy.
— Bill the Lizard
Likewise, while browsing an interesting article on The Daily WTF which highlights a simple method for square root calculation my muse overcame me. The article makes it quite clear that such iterative approximations are not highly regarded (unless you are John Carmack), however, it reminded me of a simple pi calculator that I wrote using JavaScript a number years ago when similarly inspired.
Armed with new knowledge about the abuse of for and an entirely redundant algorithm to code I set about developing a square root function.
double sqrt(double n) {
for(double r = 1; r != n; n = r == (r = 0.5 * (r + (n < 0 ? -n : n) / r)) ? r : n);
return n;
}
There are so many things wrong with this I’m not sure where to start. How about the blatant abuse of the parameter n as both the input and output, simply to avoid declaring another variable? This requires the break condition to determine whether the usually untouched n contains the currently calculated value of the result.
The final chunk of code actually does the calculation of the square root while deterministically assigning the value to n to terminate the loop and return the result. The calculation itself is relatively simple: is the average of our calculated root, r, and n / r equal to the previous value of r? If not, further refine r in the same way.
r == ( 0.5 * ( r + n / r ) )
The calculation, as implemented in my sqrt() function, is complicated somewhat by the embedded assignment of the new value to r, the poor-mans error handling of negative numbers (who wants to deal with imaginary numbers anyway?) and the inline if used to assign the final value to n.
Of course, we could always use the built in Java Math.sqrt() method which efficiently passes the calculation off to the hardware, but where’s the fun in that!?
Thoughts on Computer Science Education
While the old adage “Computer science is no more about computers than astronomy is about telescopes.” is often brought to bear, I often have to ask “But how else is one supposed to chart the heavens?”.
Throughout my time at school, college and university I have been passionate about the standard of the education provided to not only myself, but my fellow students as well. At many stages I’ve wondered, could I do a better job and teaching has always been something I would consider doing given the opportunity.
While I’m not an ‘activist’ student or even one who would voluntarily join the popularity contest which masquerades as a student parliament, or whatever the institution in question happens to call it (no, I’m not bitter, I’ve never run), I do try take an active role in shaping my learning experience.
Back in 2006 Jeff Atwood of Coding Horror wrote an interesting piece regarding the teaching of programming to computer science students. In the paper to which he refers the authors, for the most part, write off a large proportion of students and their ability to ever learn the skills required. However, the paper does have some interesting points, such as the following footnote.
Nowadays in the UK one has to say that they ought to fail, but because of misguided Quality Assurance procedures and the efforts of colleagues who doggedly believe in the normal curve, very many of them are mistakenly and cruelly ‘progressed’ into following courses. That process so far degrades the quality of their education and the reputation of computer science as an academic discipline as to be of burning commercial, professional and intellectual importance, but in this paper it must be by the by.
This somewhat struck a chord. Whenever big programming projects are due and I’ve got time to spare I make myself available to my peers and even in our second year I find students who are still unsure of the correct placement of semicolons in their Java code. Was it fair — to them — that they were progressed into the second year?
Testing What You Teach
In December 2008, the first year of my computer science course, the class was given a 1 hour, open-book programming test. The failure rate was astronomical and, if I recall the figures correctly, one of the lecturers informed us that of the first 50 projects he attempted to run from his test harness none of them compiled, let alone ran — at which point he gave up and began grading manually. The test was actually relatively simple, manipulating our numeric student ID in various ways and displaying the results on the terminal; the threshold for a pass was simpler still: anything that compiled, regardless of if you attempted to answer any questions. At this point it is probably prudent to note that IDE (if you can call it that) which we were using at the time was BlueJ and as you may imagine new projects compiled by default.
Regardless of the perceptual ease of this assignment I wrote a 2500 word essay on all the things wrong with the exam, including an alternative question set which I felt was more appropriate and focused on the objects first teaching style to which we had been exposed rather than the mathematically heavy string and integer manipulation. I felt that while students likely grasped Java to a reasonable standard, it was likely that the totally left-field questions and the untaught functional style required to answer the questions was the root of the problem, but the problems ran much deeper than that.
Syntactical Challenges
During the exam season in the following May we were given a written exam for the same class. While I don’t have a copy of the exam paper (the ethics of which are moot as first year students now take Python as part of a fully re-designed module instead) I have prepared an example question from the paper as it was presented:
5. Why does the following Java code fail to compile? (1 mark)
The astute among you may notice the error message at the bottom of the editor and the associated yellow highlight on the relevant line of code which in no uncertain terms explains why the code, does indeed, fail to compile. Yes, the answer to the exam question was in plain text in the question itself. When I asked students about this after the exam none of those I spoke to claimed to have noticed this and many professed that they did not answer the question at all. In light of this revelation my 6 page rant at the teaching staff regarding functional vs. object-oriented programming styles seemed rather redundant.
Despite this, which was said to have been an essential and doubly weighted module, it appears very few students were not progressed through to the second year.
Building a Team Environment
Our second year programming assignment was done as a group project and as such I expected there to be appropriate collaboration tools at our disposal, I was sorely disappointed. Each of my repeated request for collaboration tools to be made available were summarily turned down. Despite independent research into appropriate collaborative solutions being a requirement of the module, support from the teaching staff was noticeably lacking and no mention of the options available was made.
When I made both a Trac and Subversion (SVN) server available for my group to use they were clearly in awe and immediately saw the huge potential over passing .zip files of code back and fourth as most (if not all) of the other groups were forced to do. Of course, this configuration was neither sanctioned nor easy as I had to setup each of my group members with pre-compiled binaries of subversion and have them take up a fair percentage of the allocated storage on their mapped network drive.
In addition, despite being told we would have total control over the database schema for the project the entire class was given a single login to a single, poorly designed database on the provided database server. As you can imagine the database was quickly reduced to meaningless gibberish as around 150 students hammered away at it with different perceptions of what where appropriate values for each field with their buggy code. Here I was not alone in setting up my own database for the project for our software to use, insulating us from the chaos and allowing some subtle re-engineering to simplify development.
Solving Problems
The ability to work so closely with a group of inexperienced developers allowed me to note another interesting conundrum. Some students just don’t know how to tackle a problem programmatically. For example, I gave the following code snippet to a student in my group who was having trouble getting started.
public ArrayList<Donor> name(String name) {
ArrayList donors = new ArrayList();
// Get an iterable list of all Donors
Donors allDonors = new Donors();
// TODO: Search for [name] in each donors' name
// - Add matching donors to [donors] list
return donors;
}
Where Donors is a fully documented and conveniently packaged database access class representing all rows in the donor table (unless constructed otherwise) as simple data-bearing Donor objects, and inherits from the familiar and iterable ArrayList.
40 minutes later no progress had been made. Straight forward enough you may think, but still you have to give each student their due, this still doesn’t solve the problem — and maybe it is not obvious to everyone what to do now. Despite the clue in the return type, initially the student believed that the method should return the name of the user who was being searched for until we discussed the limited value in this response as we already knew the name of the person we were looking for. I prompted the student still further by asking
What would you do if I gave you the list on paper?
We discussed the repetitive task of going down the list, checking to see if the name matched and the proceeding to copy the donors’ details to another sheet of paper if the search term matched before drafting the following solution together.
public ArrayList<Donor> name(String name) {
ArrayList donors = new ArrayList();
// Get an iterable list of all Donors
Donors allDonors = new Donors();
for (Donor d : allDonors) {
if (d.getName().toLowerCase().contains(name.toLowerCase())) {
donors.add(d);
}
}
return donors;
}
A totally workable iterative solution. Gets a little hairy with those nested statements in the if as we do the search, but nothing ground breaking or ridiculously complex. Next I asked the student to fill out the following method body to search on the address.
public ArrayList<Donor> address(String address) {
ArrayList donors = new ArrayList();
// Get an iterable list of all Donors
Donors allDonors = new Donors();
// TODO: Search for [address] in each donors' address
// - Add matching donors to [donors] list
return donors;
}
The stark similarity should have been obvious, but they simply had no idea of where to start. After showing them some copy-’n'-paste coding we had a working solution in seconds. It wasn’t until I was explaining the most basic of algorithm designs and demonstrating the flexibility and, in many ways, the purpose of using an object oriented design methodology had I realised that problems that students were facing.
In reviewing the final and submitted code for this article, I noted the following comment had been added to the return statement of the address search method.
return donors; // returns the address of the donor
My heart sank. I thought we had this concept nailed down.
Timing, it’s of the Essence
Over the course of the class the teaching staff slowly dolled out the required materials, unnecessarily slowing the development of our projects and, as I noted before, when it came to version control and collaboration tools, none were provided. To add insult to injury the week before the project was due the class was finally given a lecture on design patterns — specifically MVC — and it was suggested that we use it in our project. It was a little late to ask for the class to re-engineer their projects.
The nature of group projects also allowed a number of students to avoid work, either by being uncooperative or simply ignoring emails and not turning up. A number of groups were half the specified size by the time the project was due. My own experience of this was one student who finally showed up the day before the project was due. It was a real shame as he understood the projects, just didn’t want to do any work. Together we rushed out some thing workable for his assigned part of the project and left it at that.
Setting the Standard
While results for the module have yet to be announce the class was informed that code that met the given criteria was not expected and projects which failed to work could still easily result in a pass for the module. While the nature of group projects does require some understanding from those who grade them to allow for students who are either well in advance or below that of their peers the idea that a group software engineering project which does not come close to working as an integrated whole garnering a pass mark shocked me somewhat.
Of course, I have myself benefitted from this arrangement. Our project is by no stretch of the imagination “complete”, however it does have some basic functionality. Had our group not had to fight the system to get collaborative tools maybe we would have been able to spend more time actually getting some work done — and maybe the other groups would have had the chance to get something working at all.
Conclusions
You might wonder why I would publicly criticise my university education? Well, for starters the university itself has already acknowledged the issues in my course by opting to re-engineer it from the ground up for the 2009-2010 intake of students. It also seems that my experience is not unique with supporting research from other institutions publicly available. I also believe in acting on issues and I made a point, maybe to the teaching staffs’ dismay, of raising my issues both with them and, as appropriate, our head of year.
I still truly believe that, despite the research mentioned in the paper, everyone can learn to program, at least to a basic level. I think for most students I have spoken to, they want to learn. It seems the issue is one of breaking down a problem into manageable chunks, finding where to look for solutions and maybe most importantly learning how to RTFM.
Dreams in Code Snippet
A quick overview of my development of the code snippet used in the blog byline.
Looking for a simple graphic to add to the site byline I elected to use some C-type code, being my most familiar dialect, and being a Mac user, the Monaco typeface in an appropriately anti-aliased size.
Now I’d set out some basic requirements, the question remained, what should it do? With the line “dreams in code” it certainly had to epitomise sleep and naturally I wanted to show some Zs. Thus the concept was born: sleep makes more Z! Latching onto the universally recognised ++ notation for incrementing a variable my first iteration looked like so:
int sleep(int z) {
return z++;
}
The first thing you might notice is that my use of braces is different. The above snippet being my preferred style of layout. The reason for the change? I had limited myself to a fixed sized graphic and the alternative code-block style allowed me to use a slightly larger font size. Lets clean that up so it’ll fit better in my Photoshop template:
int sleep(int z)
{
return z++;
}
However, that keen eyed among you are more likely to point out that my function, though perfectly legal in C, C++, Java, Objective-C and probably a number of other languages, does not in fact do as it appears. As ++ is a post-increment the increase in z would happen after the function or method returns — therefore the value of z is returned before it is changed.
Now, I debated whether to keep this as it, after all you might say that when sleeping the goal is to do nothing; however, my goal had been to increase the number of z, so the solution? Pre-increment.
int sleep(int z)
{
return ++z;
}
While this notation is not nearly as commonly seen in code, it does allow the function to return an increased value for z without using another line or a hard coded value. It was a shame to drop the original concept of z++, and you might consider the whole thing rather over-engineered, but as this tiny code-snippet sits proud atop every page on a blog about development I certainly believe this was an excellent occasion to favour a correct solution over a visually appealing one.