Slashdot Mirror
Memorable Programming Assignments?
Albert Schueller asks: "This fall I'll teach introductory programming for the third time. The class is generally populated by students from a wide range of backgrounds and interests-liberal arts and science types. While we use C++, the language isn't really the issue. Rather, the goal is to introduce basic programming ideas like loops, logic, modular programming etc. What are some of your favorite programming assignments that would be appropriate for students at this level?"
Conway's Game of Life perhaps?
One assignment I had gotten in my high school C++ course was a nice introduction to elementary image processing. The design required a simple program that would read a matrix of 1s and 0s from an ASCII text file to perform operations on. A 1 was considered white (on), while 0 was black (off); this part could be expanded to support the full spectrum, although it's good to keep it simple for beginners.
After loading the 'image', we were required to provide operations that the user could select and perform on the image, such as blob detection, scaling, blurring, etc. (This would be a nice way to introduce modular programming by defining an API for each operation to use and such.) Saving of the image was also supported.
An assignment such as this would be a great way to bring it all together; matrices, for loops, bounds checking, modular style and others would be covered, showing how all the little things contribute to a larger application.
The standard test I use whenever I learn a new programming language/system is to display the mandelbrot set. Drawing the set isn't that hard, but it doesn't stop there! You can set things up so that when you click on a part of the image it zooms in, you can select different colours, etc. I've done this (including zoom) using C++ in XWindows on a silicon graphics machine, using objective C on MacOS X, and even in perl/apache/internet explorer on a windows NT machine! The problem is simple enough to be possible, and complex enough to be challenging.
I am artificially intelligent.
Still, my most memorable freshman programming assignment (punch cards/line printer/mainframe no less) was to simulate a cocktail party.
The party was a two-dimensional array representing the room. At the edge was a door and in the center was the bar.
You fed the program a list of guests including name, arrival time, planned departure time and how interesting the person is.
Guests arrive and go first to the bar. From there they mingle by trying to move a square at a time if it will make the average "interestingness" of those surrounding that square more interesting that the average surrounding their current square.
If the guest cannot move to a square such that the surrounding guests are, on average, more interesting the guest is then he will go back to the bar.
One last provision...each trip to the bar causes a guest to become one point less interesting but to think he is one point more interesting and each drink also increments the planned departure time by one.
~~~~~~~
"You are not remembered for doing what is expected of you." - Atul Chitnis
First:
You'd better believe it's the issue. Language determines design is a Bell Labs aphorism. Another way of saying the same thing is that the (human) language in which you think and speak determines what you can think and speak about.
While I happen to be a big fan of C++, I will go on record as saying that it's not a good language to use for beginner programmers. (Neither is Java.) I'd say either Python, or Pascal (you know, that language whose major design goal was to teach introductory programming).
At least, if you are going to use C++, use a good text like Accelerated C++ by Koenig and Moo. Otherwise you'll spend too much time teaching "how to use C++" and not enough time teaching "how to write a good program."
Second:
My favorite prof in the intro sequence gave us a module that drew playing cards on the screen. (All ASCII-based with ANSI escape sequences for colors, no annoying graphics programming.) We had to write the logic to play Solitaire.
While there are a lot of problems that CS majors would find cool to solve, those aren't necessarily the same ones that will grab the interest of people "from a wide range of backgrounds," as you say your audience is.
You cannot apply a technological solution to a sociological problem. (Edwards' Law)
If you're one of the posters on this thread who thinks that a bunch of liberal arts losers are going to program pool table simulations and Mandelbrot sets, then you're living in a fantasy world.
The following is THE MOST DIFFICULT homework problem they were able to solve: Write a C function that takes an int, and returns one of the strings "st", "nd", "rd", or "th" to describe the ordinality of the associated number [e.g. 1 returns "st", for "1st", 2 returns "nd", for "2nd", 3 returns "rd", for "3rd", 4 returns "th", for "4th", etc.] The trick was that e.g. 11 returns "th", but 21 returns "st". A handful of them were able to get that right.
The final project was to write a program that would take large files and decompose them into smaller chunks, each small enough to fit onto a 1.44MB floppy. Not a single student in the class came close to finishing the project, and the class included at least three fellows who were already programming for a living.
In high school AP C++ class, when we were learning about sorting my teacher mentioned the different 'standard' sort algorithms, describing how they worked theoretically, and how some were n! and some were n log n, but we never actually compared the output of programs using the different methods. Out of boredom one day I went and made a program that generated a bunch of random arrays of various and then timed how long it took each of six or so algorithms to sort them all. I took the output and graphed it in Excel (being too lazy to make my own graphs ;) and sure enough the better sorts did much better. Coding several different algorithms to perform the exact same task may seem needlessly redundant (because it most certainly is) but it's a great way to get a grasp of loops & recursion &c.
Oh cruel fate, to be thusly boned! Ask not for whom the bone bones; it bones for thee. -Bender
Sometime in the fourth week, our lecturer announced the eagerly anticipated first Assignment. I couldn't wait, because I expected to ace it, after all, I had years of programming experience, a huge advantage over my peers. Not so: We had to write an Optical Character Recognition (OCR) program. I was stunned. I had never done anything that complex in my life, in any language, and now I was being asked to do it in a functional language! However, many people achieved recognition rates over 80%, and some people rates as high as 98%, even though most students were first-time programmers. It just goes to show what people are capable of when pushed.
The same lecturer (Andrew Taylor) later came up with a whole series of Evil assignments -- his students tell stories about them to this day. For example, our second assignment in Comp 1A was to write an AI for the card game Hearts. To mark the assignment, he wrote a system that ran submissions in randomly chosen four-player games automatically, and ranked them by total score after some number of games. Half the marks were based on the performance of your AI! He even made the ranking software available beforehand so that students could test their algorithms against each other in mini-tournaments.
Since Scheme is so simple, this is surprisingly easy to do, and it's a great learning tool. It helps students understand what's really going on when they run their program.
See Abelson and Sussman's classic computer science text, Structure and Interpretation of Computer Programs (aka The Wizard Book), for details. This book is also an excellent introduction to the basic concepts of computer science.
Give the model of a deck of cards where the first card is the 2 of spades, the second is the 3 of spades, the thirteenth is the ace of spades, the fourteenth is the two of hearts, etc. In other words, each card in the deck (minus jokers) is assigned a number.
/. can shut up now -- this is an introductory class).
When given a number from 1 to 52, spit out the name of the card to which it refers. If you want to make it interesting, tell them to solve it twice, using a different method each time. This has two probable solution types: 52 element lookup table or judicious use of the modulus operator. At the end of the assignment, there is usually a small amount of code (easier for beginners to debug -- easier to grade), but gets the gears turning for people not used to thinking in terms of algorithms.
Keep your eye on those folks who write out a series of 52 if-else-statements or a giant switch statement; they're going to need some tutoring soon.
---
Enter a number as input and spit out that number in hexadecimal and octal.
---
Enter a number under 100 and spit out that number in longhand (36 turns into "thirty six")
---
Read in a variety of data (user's name, age, favorite color, etc.) and spit it back out in a pleasant greeting: "Hello <name>! You are <age> years old and your favorite color is <color>."
---
These aren't horribly difficult -- so you won't drive many people away -- but you still have the opportunity to teach basic I/O, general style, adequate commenting, algorithm efficiency, and (most important) how to approach real-world questions in the step-by-step manner required in programming (multi-threaded/multi-process smart-ass programmers here on
Far too many people who program suffer from lifelong-geek syndrome: knowing how to program for so long that they've forgotten what it was like to learn how to program. As long as you demonstrate sufficient patience, anyone can be taught basic programming skills. I truly believe that most can grok pointers as well assuming they stick with programming long enough and have a good enough teacher.
Good luck with the class.
- I don't need to go outside, my CRT tan'll do me just fine.
Games are good because not only do they encompass a wide variety of possibilities, but they are acessable to everyone. None of my (non-programmer) friends cared that I could do the tower of Babel in x lines of code, but they liked my simple race car game I wrote in assembly (it was only single player). The coolest was the space invaders we did at the end of my 101 class; the TAs provided a mostly complete graphics library (so we could use images or shapes to make the baddies), and the really bored/advanced students modified the graphics library to change the players ship, weapons, ect. so there was something to challenge everyone.
Kurdt
I'm not anti-social. Just pro-technology.
Ideally you want to ease them into this slowly, give away the location of the first bug - bombing if you enter a string where numbers are expected for example, provide test data for the second and so on. Another important thing is to ensure that if the student chooses to re-write an entire function they don't side step another part of the exercise by obliterating another of your carefully crafted flaws.
The exercise tests the students understanding of the language, ability to prepare realistic test data, and ability to find common bugs like off-by ones, buffer underruns, overflows and so on. It's also pretty good preparation for the "real world" where you will need to read other code, fix other people's errors and improve their code, besides being damned interesting if done right.
UNIX? They're not even circumcised! Savages!
The first programming assignment I got at university was to convert between Roman and Arabic numbers. Mind you, this was for a "real" CS course (that is, my whole degree was computer science), and I was told to write it in Ada, so it wasn't exactly what you'd call fun ;-)
Something like this would help teach loops, and programming of simple logic and arithmetic. It would also teach the importance of input validation. A Roman number is all letters, so you have to read it into a string, but only certain letters have any meaning.
Also, the Romans had no representation for zero, nor (AFAIK) for negative numbers. They may have used fractions, but not decimals. The Arabic to Roman converter should (probably) therefore accept positive integers only. What, then, does the program do if the user inputs, say, "3.7"? The library function that reads an integer may read "3" and stop on the decimal point, or silently round it to 4. This would not be a good thing, so you'd need some validation there as well.
To simplify it, you could convert just one way. Roman-to-Arabic is probably easier than Arabic-to-Roman. You could also ignore the rule that says if a letter comes before one that has a larger value than it, you subtract the smaller from the larger. That is, 4 is normally written as IV (5 minus 1), but you can also write it as IIII. (I believe the Romans did this early on. You might also see clock faces that use IIII for 4. This is for the sake of symmetry with 8 (VIII) on the opposite side.)
Tell them that the program has to handle numbers up to 1,000, just so that they don't type in a big array or switch or if-then-else.
Just another wannabe fantasy novelist...
I've always wanted to teach a class just so I could give this assignement: Write a RPN calculator that does addition and subtraction, no more. A few rules that are different from every other project: other class mates will see your code; redit will be lost for implimenting functionality byond addition and subtraction; the due date is next week, but you get MANY extra points by getting the assignment to me sooner; class dissmissed, get to work.
Then the next week I would copy everyone's program, and randomly hand it out to other students, with a new assignment: add multiplication and division to this program, and fix any bugs in the code. Time counts again. Note that even though I say is the random, I will in truth pick out who gets what, those who did a good fast job get aweful programs to work with, while those who did a bad job get good ones, and there will be a comment as each studnet picks up his assignment that this is an example to learn from. After they turn in the completed assignment (remember time counts) they will get another assignment, write a short paper to the author of the program you graded on what you found good/bad. (english skills don't count so long as it is understandable, ideas do)
Finially, everyone see's how their program looked after the second guy got done with it, and the comments. Grades for the second half will take into account how the first half turned out, so someone who got a horrid, non-working assignment and took all week to make some stupid algorithm work will get as much points as someone who was able to get their assignment done in an hour. How long it took the second programer to modify the orginal code is a factor, but minor since bad programs should not take down easy to modify code.
Just make sure that this is done early in the year, if they are supposed to learn C++ in your class, this won't work, by the time they can do this all their other classes are in crunch time and a good student may notbe able to get this done quickly. I recomend giving this assignment the first day of class, if they can't hack it then, they need more expirence than your class can give.