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?"
and after that.... beat any student that thinks main can return anything other than an int. Beat them well.
Moneyed corporations, non-working 'poor' and criminal prisoners are turning productive citizens into tax-slaves.
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)
..making students prove NP=P is a good assignment for 1st year students.
DrLunch.com The site that tells you what's for lunch!
It's easy to maintain interest if the end result is something fun that you can actually show people.
Now let's see - what's easy to write? Maybe a card game(solitaire?) or a tetris-type thing or other puzzly-thingy, or very simple 2D action games (hey, they fit in 4KB back in the day).
The wrong thing to do is to assign something where the result of their work is a bunch of printed text.
a ry / -robocode/
Something along the lines of RoboCode would be ideal:
http://www-106.ibm.com/developerworks/java/libr
But since you're doing this in C++, you'll have to roll your own.
Basically, whatever it is that they're doing, make it something that can take input from some external source, and have its output be read by something that can transform the output into something fun. This means a *lot* of work for the teaching staff, since they'll be writing lots of libraries and/or server/client code.
For example:
output for their code are integers ranging from 0 to 2^16. These integers are fed into a digital to analog converter and the students get hear the result. Student will go from producing a single tone (they'll have to create a sine wave, or even a triangle wave is fine) to chords and melodies in no time! lots of good programming and SIMPLE programming meat to chew on.
students could write a black jack player. the input will be integers representing the value of their card, and they'll output if they want to hit or stay. then the staff (you) could write a nice gui and driver around the thing and the students can play black jack (or any other card game...) against a program that they wrote. you could also make the programs play against each other.
etc., etc.
Best,
andrew
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
(Oh, to be a freshman again. To take a "programming" class. To never have heard things like "this implementation is O of log n" or "NP complete" or "software cost estimation" or "preemptive fixed priority scheduling"...)
The only assignment I remember from my first programming class was one in which we read in stuff from a file into a linked list, printed it forwards and then printed it backwards. The abstraction of the linked list was so cool, and when it actually worked I felt like king of the nerds (little did I know the horrors to come).
When I was at CMU, there was one intro to programming class, and it was no fun for anyone. Now they've broken it up into people-who-might-take-another-CS-class, and people-who-don't-like-smelling-like-the-cluster, hence a class that is very light on fun and heavy on syntax and object oriented garbage, and one light on programming and heavy on pointy clicky fill in the blanks and make a game happiness.
stepping onto my soapbox:
While we're talking about intro classes, I think everyone who is going to take any additional classes in computer science, especially in the systems area, should take their first class in C, and it should be no fun. Every now and then you can toss them something fun, but learning the discipline of malloc/free, strncmp, etc., will serve you so well when you get to do object-y type computer science stuff. Writing good code, in a scientific or engineering sense, is just like learning to use UNIX - if you didn't suffer, you didn't learn. And if you get to new/delete or just new and then forget about it, you never learn the discipline that writing good code demands.
-- steps off soapbox.
Outside of a dog, a book is a man's best friend. Inside a dog, its too dark to read.
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.
Dare I say was to generate the Fibonacci sequence!
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.
While we use C++, the language isn't really the issue.
You'd better believe it's the issue. "Language determines design" is a Bell Labs aphorism.
It's not the issue in a computer science class. Yes, language definitely affects design -- but this is not a real-world engineering problem. If the assignments illustrate theory, and it's theory that drives the curriculum, then the language is only an issue to the extent that it illuminates the theory.
Please note that Bell Labs is not a teaching facility.
In real-world engineering, however, your point totally holds. The end result of an undergraduate CS education should be adability, and the facility to think in whatever language the situation demands.
One of my most memorable programming assignments was implementing Conway's Game of Life. With all of the bruhaha surrounding complexity and Wolfram's new book, this would seem particularly germane.
'He who has to break a thing to find out what it is, has left the path of wisdom.' -- Gandalf to Saruman
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.
As many othe rpeople have said, GAMES!!!
For example start with somethign simple like Hangman, then move to somethign a little more difficult like the towers of hannoi (spelling?) I also had a lot of fun programming the game of monopoly in my introductory programming class. So many diffrent objects to create!
-Windchill2001 The One, The Only, The Cold...
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...
From the early days of programming, I recall that everyone that is just starting out programming will automatically strew various bugs and imperfections around their programs.
Hence, the big thing you learned outside of the classroom was how to debug and to interpret error diagnostics.
Funny, but years later I'm still doing the same thing.
"Provided by the management for your protection."
My favourite is to have them implement a simple recursive-descent parser for a minimalist computer language. This is not hard at all, and given that you can limit the scope sufficiently (e.g: a command-line calculator), it should be possible to have as a four-week assignment (assuming you have already teached them about ifs, while-loops, and recursion).
Another great example is a small computer game. You could either choose the silly variant (paper-rock-scissor), or a more advanced variant (tetris, snake, asteroids, space invaders, pacman) using simple graphics. Write the graphics-routines yourself, and have them put in the game-code.
A simple trick for making your students do larger projects, but limit the work, is to write everything yourself first, and then delete the lines you think they should be able to do, and replace them with a comment about what they should insert there. It's very efficient for learning.
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.
Read the /. article. Find resources at the Google Web Directory.
It sucks that you have to consider this, but...
Be sure to give assignments that lend themselves to lots of creative solutions. This is especially true these days, with academic dishonesty so commonplace. If the assignment is open enough to allow people to solve it in many different ways, you will get a lot of different answers - this will make your life much easier when it comes time to detect the cheaters.
Have the students write simple graphics assignments.
You, the instructor, can supply the bootstrap code needed to get a drawing surface up in whatever platyform you choose. Supply a function like GraphicsMain() and ask the students to fill it in.
You can do all kinds of neat things like reading in points from a file and displaying them (you supply the files initially). Then have the students write a program to generate their own point files. Have them make a simple 2D visualization program.
This would be a great way to demonstrate modularity too, since you can emphasize that if carefully written, the code can be used later on the next phase.
In addition, these types of assignments are a lot of fun (since there is instant visual feedback) and they really lend themselves to creativity. Encourage everyone to explore for themselves beyond the boundaries of the assignment and you will get the brightest, most talented students submitting really interesting things.
I think a fractal engine which displays L-systems would be very appropriate, for example. Instructor supplies the bootstrap code, and a handout describing what L-Systems are, and asks the students to draw it. Not too difficult, a good example of file-io (to read the L-system) some basic maths (geometry, etc to get angles right - you can even supply this on the handout if you think the students might be lost), and string manipulation. There are a few ways to do it also, and the good students can come up with their own L-systems to demonstrate.
Those are some of my most enjoyable ideas.
I recall a particularly cool assignment where the professor gave us a long-ish (~1-2KB) chunk of text that had been run through a rotation filter. He gave us the background info on what rotation filters were, how to defeat them (look for most frequent character, that's 'e', determine the shift, then reverse that and print out), etc. all the theory to solve the problem. It taught us simple file I/O (open old, read data, do computation, print out into new), really simple data structures (making us think about the best way to store the frequency information), as well as a little baby-step taste of how cool encryption/decryption was. There was just something magical about running the program and having it work right, producing the cleartext. It's great to feel like James Bond cracking the Secret Evil Message ;-)!
The kicker was that he chose a very cool poem as the cleartext, so when you reached the finish line you got rewarded with a result that was actually interesting to read. This part might well appeal to liberal arts people, as well history types will be aware of how critical a role codes haved played throughout time.
This is just my very humble opinion, but are you sure c++ is the way to go for beginning programmers? I fully realize you may not have a choice due to departmental constraints. It's just my experience that most intro-level programmers being taught C++ have such a hard time with the language itself that they can't see past that to the applications of it. Otoh, a language with a C-like syntax is probably a good move because so many things use that (I've always said that if you learned C well you were half-way or more to learning any of a dozen other languages). So, have you considered something like Java or Perl? (Or, god forbid, python ;-)) Both of those languages are easier to grasp, enabling you to focus more on what you can do with them than how to write a virtual destructor... Heck, with perl you could give them a very easy taste of web applications development using cgi and databases, for example, a collaborative story writing system (user A writes chunk 1, B writes 2, and so on)...
News for Geeks in Austin, TX
And isn't it a game? Ok, it the computer solves it then it isn't much of a game, but if you play it then it is a game.
Lasers Controlled Games!
Towers of Hanoi
Boggle
Tic-Tac-Toe
Bunny World -ok, Bunny World wasn't that simple
Lode Runner
Simple Fractals
Driving directions
Mad libs
Slot Machine
Simple Drawing Program
C interpreter - seriously, they gave this to second quarter students
If anyone wants details on any of these please ask.
Lasers Controlled Games!
You might also look at The New Turing Omnibus: 66 Excursions in Computer Science by A. K. Dewdney from W. H. Freeman & Co. (ISBN 0-8050-7166-0) which is a good source for important and interesting CS topics, though it may be more work to construct concrete projects.
In my experience, the problem most beginning CS students have is understanding "computer think", or how to solve a problem.
Very early in my first CS class (like the second or third class after we got the obligatory lesson in history and basic terminology) our instructor brought in a loaf of bread, a knife, peanut butter, and jelly. She asked people to write instructions on how to make a peanut butter and jelly sandwich on a piece of paper.
After about 20 minutes she called on one person and followed their instructions, smashing bread into the jar and using the knife to stab the bread. It took a visual exercise like this to make people understand how each instruction is very important, and to be attentive to details.
Later when we did Towers of Hanoi she brought in three of those Fisher Price ring-stack toys. She showed us with those how to get the disks from peg one to peg two in a way we could understand.
One other thing that was helpful was being shown that we weren't just "learning C++" or "learning Java", that we were learning skills that are portible to other languages. After our first looping program we got a small booklet from our teacher that showed the same problem solved in several different languages.
As for actual problems we had to solve, I hated most of them, but I'm thankful for having done them. Most were intentionally difficult (reading and writing data in bizarre file formats) that made me a much better programmer.
"All I ever wanted was to see Larry Wall give Bill Gates a Perl necklace."
http://www.eisenschmidt.org/jweisen
The best way to make people (moderate geeks at least) excited about the programs they write is when they are excited about the output they produce. There are a few ways to get those results:
In essence what you are trying to avoid is the "I'm embarrassed to be proud of this" factor. The first time you pick up a musical instrument and haltingly jam out "mary had a little lamb" it's a huge moment. But you can't stroll into class the next day and say "dude, check it out. Last night I was playing Mary Had a Little Lamb. Oh yeah, I'm serious." If you can avoid the analagous situation, make programming fun while teaching fundamental skills, then even for non-geeks the 'ugh I don't want to do -that-' inerta factor is easier to overcome, hence making teaching fundamentals (and grading, no doubt) easier and more fun as well.
But what do I know . . . I took all my intro courses with hardcore CS majors. We were excited about spewing out ASCII UI's
The best "beginner" programming assignment that I ever heard of was about sorting. Very fundamental stuff. But the items to sort were graphically displayed, with a simple API to swap two items. The goal was to let folks see their software in action.
In an improved version of this approach, each student was told to sort the numbers, and given the initialize(), value(i), and swap(i,j) functions. But they were not told how to perform the sorting. Afterwards, each different sorting algorithm that was implemented was described by the students, and the professor covered any techniques that had been missed. This leads to a discussion of O(N^2) vs O(NlogN). And a future assignment to implement and compare (graph) the efficiencies (number of swaps) of different sorting algorithms.
Ultimately, if you can foster a attitude of "here's a little bit, lets see how far you can take this", and then shape their results further, they will learn far more.
The most instructive assignment I ever had was based on this. It involved writing a simple 3D perspective drawing program from scratch. The instructor said we could use any language, on any computer, and write the code any way we wanted to. Grades were entirely based on how well it ran. Some time after we turned it in, he announced the next assignment: Extend the previous assignment to handle shading from multiple light sources. That assignment, whether intentionally or not, taught me more about commenting and documenting my code than anything else ever did.
Yeah, all of the above I agree with wholeheartedly. I'm of the opinion that CS education should de-emphasize individual languages -- and to that end, an intro course should use a language which facilitates de-emphasizing.
C++ is certainly not such a language!
Pascal is a decent choice. I'm personally a fan of Schemefor the first semester (worked marvelously at Macalester), but not religious about that. Java could work OK, if students use a very limited subset -- it's not a shoot-yourself-in-the-foot language -- but it's very hard with Java not to get into high-level structure questions inappropriate for the first semester. It's probably better for the second semester, when you start talking ADTs.
Perhaps you'd quibble with some of the previous paragraph, but I think we've basically found consensus. On Slashdot!! And without any Microsoft-bashing, even....