First project in my second year data structures intro

Question

I am currently teaching the pretty much normal second year Data Structures and Algorithms course. In this course there are four programming projects, with the first project completed the automated testing and grading yesterday. However, out of the 200+ students taking the course, only 72 managed to complete this project so that they passed my automated tester for the pseudorandom seed that I used. As my first question to this forum, I would like to get some second and third opinions about this issue before I decide how deep I dig my heels into the ground about it.

This project (full specification) asked them to create a Java class named IntervalUnion whose objects represent unions of integer intervals, such as [1-5,9-12] or [4-8,11-15], with an arbitrary number of individual intervals allowed inside each such object. This class should then have the public methods union and intersection to create new objects, with the union of these two objects being [1-15] and intersection being [4-5,11-12], along with toString, equals and hashCode as usual.

I simply cannot believe that this project would have been unreasonably difficult for second year computer science majors who have already taken the standard two first year courses of introduction to programming and computer science using Java. And yet for some reason it seemed to be, especially using my automated tester that, based on the given pseudorandom seed, generates random test cases and computes a checksum of the results returned by the implemented methods, this checksum then being expected to be equal to the checksum produced from my private model solution.

For a test run that generated one million objects, easily automated with a Bash shell script, the passing projects took between one and three seconds to finish, whereas some solutions had to be terminated after minutes of waiting and thus rejected. The project spec specified a thirty second time limit that I would have assumed to be more than enough for them even to dilly dally.

Of course I might be completely mistaken in my view about this, so I would like to hear some opinions of other teachers who have taught this same second year intro to algorithms, before I make any announcements to the students.

Since my course uses the three best projects out of four in determining the total course grade, I am currently of the opinion that I am going to just tell the students to wake the hell up, realize that this is serious, and do better in the three remaining projects. The second programming project consists of writing method to remove all nodes with given key from the given linked list, and to sort the given linked list, using the sorting algorithm of their choice. (As with all these projects, the grading is 5 points for passing the automated tester, and 5 points for comparative running time rankings among all submissions.) There is just no way that that task could be considered too hard for second year CS majors.

The last two programming projects ("Packing words in bins" and "Word filling") due at the end of the course should be easy to at least pass in that within the simple rules of both word search puzzles, there are really no wrong answers, but the difficulty of both projects is in quickly finding a good solution that scores well.

(As an aside, I am actually pretty proud of that Word filling problem, as its idea came to me last summer during a nice mellow walk, and the solution sketch the next day during a ride home followed by about an hour to implement after dinner, and I wonder if I could be the inventor of such a simple but tricksy puzzle that I simply can't recall ever seeing anywhere before this. Another more interesting variation might be to maximize the scrabble score of the words, since that doesn't actually change the solution algorithm.)

Answer 1

Sorry, but digging in your heels or telling the students to wake the hell up is going to get you exactly nowhere. When a small percentage of your students fail to successfully complete a project it is likely their own lack of background or application. But when only about a third are able to successfully complete it, it is a problem with the course, not with them.

Some possible reasons for the problem. Perhaps they started late on it and weren't able to do a good job as user Adam asked? If so, why was that? Are they overworked generally in your course and elsewhere? I doubt that so many are just late starters. Was it a problem of insufficient testing? Was it too many tried a brute force approach that doesn't scale? How much does the course stress that early on - both testing and scaling? It seems like they weren't able to ask questions (of the TAs at least) as the project progressed. If they get stuck, how do they get unstuck? Just on their own?

I think you have a problem and I can't diagnose it, but you can. You can, for example, have your TAs do a postmortem with small groups. I hope you have more than one or two for 200+ students. The first question I would want the failed students to answer was "Were you surprised by the failure?" That can lead to a lot of discussion about the nature of it. I would ask about how much testing they did, especially on large sets. Were they able to use the tester effectively, providing appropriate inputs, or were they misled by it. Another question I'd want an answer to is how many students now actually know why they failed. What was it in the code or its creation that led them to failure. If they don't know that you have a serious problem going forward. I think that for these and similar questions your TAs are better able to get you usable answers. The students are less likely to feel intimidated by the questions than if you ask them directly.

On another level, I'd ask how many independent runs did you do with each student's work? Just one? The data was random, remember. Maybe naive inputs to the tester gave them poor feedback while doing their own testing.

Maybe a five week project with little guidance or feedback is sub-optimal. Especially if you treat it as an exam. It seems like a lot of time, until it isn't. Why not shorter projects? Why not more feedback? Why not, to be honest, continuous feedback?

I wonder how many students who failed did so only for run time and how many weren't even able to put together an algorithm at all. Has anyone given them feedback on their code and approach other than "failed"?

Are your expectations about what they "should have learned" in the earlier courses realistic? Are you making assumptions not warranted by the facts?

Don't just stamp your feet. Find out why this happened and change your teaching structure accordingly. Treat it like a scientific problem with an engineering solution.

Answer 2

This answer is a complement to Buffy's and is more oriented towards future applications of autograding.

The description of the assignment gave me the impression that your autograder is rather lazy. Instead of checking whether the functions the students have written are correct it executes a bunch of operations and compare a checksum of the result. Although this does check if the code is correct, it only produces right or wrong diagnostics. A small error like using < instead of <= is undetectable by this method. In other words, the autograder helps you (the instructor) to detect problems in the code, but it does not help students to understand their mistakes.

I prefer using autograders that behave more like unit testing. They go through all functions of the class students defined and test inputs and outputs. If there is something wrong it prints a nice message stating where it fails, for which input and lists current output and expected output. You can still grade only for correct solutions if you want to, but students get much more feedback on their progress. You also get more information about their performance and can see where the failing students made mistakes they could not figure out how to correct. You can even publish a set of "simple" tests and require students to write tests for tricky cases. IMHO this is a much more "modern" approach to grading and it has the added benefit of getting students used to software testing.

If you are not convinced by the argument above, let's explore a more technical perspective. A class is, essentially, a contract that says that a certain number of methods will behave in a certain way. How these methods are implemented should not be of concern to the caller (at least in term of correctness). In this situation, checking each method for correction is a very reasonable approach. It also allows for partial credit: a student that implemented some methods correctly deserves a better (but maybe still failing) grade than a student that did not implement a single method correctly.

Answer 3

Late answer: I agree greatly with @igordsm's response above (emphasize unit testing with more detailed feedback, not just a "pass/fail" output), so this should be considered in support of that.

I agree with the comment by @pojo-guy that the specification seems "unnecessarily convoluted and artificial". Having read the specifications for the 1st and 4th projects, the tone also seems a bit snarky in a way that I would not recommend. Have the specification run 5 or 6 pages seems pretty long to me.

But the main thing is that I would recommend you consider changing your grading policies, as several of the terms seem poorly considered. E.g.:

• First, the whole idea of a binary auto-grader with a checksum output seems to have a bad "code smell", as we say. Anecdotally I hear lots of stories of CS professors trying to be clever in this way, with them and their students being perpetually frustrated that the auto-grader isn't working exactly as desired. And what's the point of checksum output anyway, versus a yes/no correct output test? Recommendation: Consider grading in ways other than auto-grader alone. Simplify the auto-grader to use a yes/no test suite (example). Increase visibility.

• Second, giving zero credit in any case when the output is not exactly correct. Do you not wish to consider any aspect of a solution being partly correct, or issues of code formatting, readability, documentation, reusability, etc? I think all of those things are important items for which to provide feedback (and hence partial credit). Recommendation: Expand the grading criteria to cover other important issues than just correctness (and secondarily give opportunities for partial credit).

• Third, having half of the grade component judged by competitive ranking of the speed of the programs can have deleterious effects. (a) Pedagogically, it turns the students against each other, and prevents them from sharing knowledge on even the theoretical level (even potentially sabotaging each other). (b) Students will be judged and graded on different criteria across semesters, depending on the strength of their cohort. (c) The focus on speed can take all the oxygen away from students being able to focus on correctness, which should come first (as I've seen back when I taught assembly). Recommendation: Not generally grading on speed, except maybe one special assignment. Failing that, compare to fixed time benchmarks, not relative to other students.

• Fourth, the prize of writing a recommendation letter to only the top-performing student strikes me as somewhere between distasteful and immoral. You should be writing letters for any student who is qualified, in my opinion -- which should be more than 4 per semester. This element gives the signal of a professor who is just lazy and a barrier against student success in principle. Recommendation: Delete this unique "prize" and offer letters openly to more students.

• Fifth, the final assignment takes a little bit too much glee in how unique, "clever" it is, and does a humble-brag about how little time it took the instructor to come up with it and solve it. Again, this smells bad. In my experience, any test question that I consider "clever" or fun/interesting is a recipe for disaster for my students -- regardless of how elegant or short I can personally make the solution. Recommendation: Assuming you have some quality textbook that you're teaching from, stick to projects from, or similar to those in the book, which have presumably been developed and tested by book authors and reviews over several years and classrooms.

Answer 4

Your students do not know how to engineer software. They have not been taught. Teach them. (Suggest you find out what their syllabus has been & what they actually learned.) You do not know how to acquire software. You have been burned. The solution is the same: software engineering. You must be the engineer of your desired software. A software client must be a software manager. You just didn't realize that you assigned yourself a software engineering project.

The Emperor's Old Clothes:

At last, there breezed into my office the most senior manager of all, a general manager of our parent company, Andrew St. Johnston. I was surprised that he had even heard of me. "You know what went wrong?" he shouted--he always shouted--"You let your programmers do things which you yourself do not understand."

The core of the solution is the same: milestones. (Which, taking a module to be a unit of work, is just information hiding yet again as the foundation of software engineering.)