macOS Need "awesome" programming problems

No awesome issue here, but a little tip: instead of jumping onto OOP focus on pointers and recursion first. For me understanding pointers was a milestone in learning programming as an amateur. Years later I was able to win a micro-contest in my class for a fastest solution to count distinct words in a file. My choice of pure C with binary tree was twice as fast as second program, that was using C++' STL.

Deitel and Deitel How to Program comes to mind. It had pretty awesome end of chapter question / quizes and some AMAZING programming exercises.

Elevator, Tower of Hanoi, ect.

I personally hated the tower of Hanoi and I'm pretty sure most students just look up the answer rather than figure it out.

Writing a sodoku solver is pretty challenging but rewarding.

I'd suggest looking through TopCoder's algorithm match archives. They often have interesting problems for a variety of skill levels.

Honestly, I fell in love with computers because I wanted to write games. I was probably 13 or 14 when I got my little Texas Instruments computer and it's extended basic cartridge. I would say within a year, I was animating sprites and had written a little star wars rip-off (remember the old atari star wars game?). They were simple and totally amateur, but I loved it and spent hours reading the reference guide to learn how to use new functions.

You could very easily find a language where the kids build a simple game step by step over the course of the year or semester. Maybe start off learning to position characters on a screen for one assignment (you could have them use for loops to repeat the character, use a 2 dimensioned array to determine positions, etc). Then load in information from a file which is used to position stuff on the screen, etc. All the way until you have a simple pursuer type game with obstacles and goodies to be collected. AI can be super simple, such as a pre-determined path for the "bad guys". You could even provide them the input files for these, leaving it strictly up to them to write the logic for both parts. Key stroke input is pretty easy to learn in any language.

Python and probably lots of other languages have some open source graphical interfaces which you might be able to use to allow them to manipulate simple graphics instead of ascii characters. There are lots of decent looking trees, dragons and stuff available online that you can freely use.

They'll probably make fun of the game they created, but I bet they'll have a lot of fun watching it take shape.

ArtOfWarfare said:

Writing a sodoku solver is pretty challenging but rewarding.

Click to expand...

Agree on that one; did it once in JS. Was really fun and something I always wanted to do.


Another one: Game of Life;with an interesting start screen like moving across the screen or some "violent battle"

Things that move

Things that move...

We did an elevator in Lego with three stops and buttons to summon th cage at each level.

What really got me hooked was programming a xy-plotter to write text.

Gunnar

jctj said:

So far, plans are:
(1) 2^64 question as in OP
(2) Towers of Hanoi ("just look up the answer" concern noted...)
(3) Soduku
(4) Bubble Sort (not going into all the sorting options, but great for linked lists)
(5) Game of Life

Click to expand...

Remove "Bubble Sort" and let the kids figure out how to sort an array by themselves. Bubble Sort is quite confusing and unintuitive. I'd think they would divide up 50% using direct insertion, and 50% using direct selection.

Then you can let them measure how long it takes to sort 10, 100, 1000, 10000, 100,000 and a million random numbers. That should be _very_ educational.

And then you can figure out together how you can sort a million random numbers thousand times quicker.

gnasher729 said:

Remove "Bubble Sort" and let the kids figure out how to sort an array by themselves.

Click to expand...

This.

Sort, and shuffle operations are both really interesting problems that have real world tangibility.

Shuffle can be applied to a simple blackjack or poker game.

B

I think it would be alot of fun coding up something and then interfacing it with say a raspberry pi, or a basic pic and circuit board and seeing how your code can actually mechanically interface with things!

Perhaps programming a chip to interface with an LCD screen outputting ambient air temp? or a sensor that detects if a cup is there where a pump will activate and fill?

Were I to teach OOP, I would make them work on something that is trivial in OOP BEFORE teaching OOP - let them fail at it completely before you come to the rescue with OOP.

Too many students don't understand why OOP is great until they've experienced first hand the pain of doing it wrong.

Also, don't touch #define, teach const.

You might use the same "do it wrong first" with goto when functions are what is needed. Goto has a single proper use that I know of in C: breaking out two loops in a row (IE, breaking all the way to the outside when control is in a loop in another loop.)

Arrays? No?

Personally I think problems connected to real world applications are the most motivating. Perhaps a search problem, binary search is pretty simple in concept and also reveals the importance of algorithms when compared to linear search. Parallels could be drawn to something everyone is familiar with, like web search engines, although Google use map reduce which is a big ass hash table.

For languages I think Python or Ruby are better than basic, because both of them is actually used and they are simple. Eventhough both of them are larger than basic (especially including their libraries) you could restrict your use to a small subset to introduce concepts like, conditionals, loops and so on.

Another interesting language is Processing, which gives instant gratification by creating graphics, and at the same time still have the same basic constructs, loops, conditionals etc. When you get the Processing IDE everything is set up so that you can see the results immediately in the environment. There are lots of examples available at processing.org and since there is also a JS library available you can see it in the browser here.

http://processing.org/examples

subsonix said:

Personally I think problems connected to real world applications are the most motivating. Perhaps a search problem, binary search is pretty simple in concept and also reveals the importance of algorithms when compared to linear search. Parallels could be drawn to something everyone is familiar with, like web search engines, although Google use map reduce which is a big ass hash table.

Click to expand...

Oh yes, binary search is excellent.

It's also great to compare exhaustive on NP-Hard problems vs. greedy and various other things you can try to do to approximate an answer (although perhaps branch and bound would just go over their heads...)

At the same time though, it's important to teach the dangers of premature optimization. Always write the most legible code possible, first. Only reduce legibility in the event that you can definitively say that the particular spot is utilizing unacceptably large amounts of resources and that another method will do better, and in that case, comment it heavily.

Run Away! Run Away!

Stay far, far away from object oriented programming.

Stay far, far away from pointers.

Both of those require a level of abstraction that can kill dead any interest in programming before they experience the joy of creating new worlds. Both of my daughters took Java in high school and ran away screaming. One of them later graduated college with a math degree and the other is currently majoring in chemistry, so they're not science/math/complexity adverse.

Stay far, far away from anything that gets in the way of immediate gratification.

What they need to learn is variables, program flow, and simple input/output. This will give them a taste of creating new worlds and the excitement of programming.

----------

My suggestions:
- a guess the random number between 1 and 10 game. The user inputs a guess, the program returns High, Low, or Match! That will take a couple of days. Then have someone else write a program to do the guessing (have them run the programs on separate computers and manually type the guesses in). Someone will stumble on binary search!

- a program that computes the average speed in MPH given the time it takes Usain Bolt to run 100 meters (9.58 seconds) and 200 meters (19.19 seconds). This is a simple input a number, crunch it though a formula, and output it, but that's a building block skill that will be much needed later in their programming career.

- a program that adds up the integers between 1 and an input less than 1000. Then if you want you can casually mention Gauss's solution 250 years ago.

- a space attack game where you shoot either phasers or photon torpedoes, the enemy randomly picks shields or evasive manuvers (each of which have a different effectiveness against the two types of attacks). Or any game where there are two attacks and two defenses.

Another thumbs’ up for Robert Sedgewick’s "Algorithms in C" book. I'd focus on

1. sorting, because it’s thrilling to hunt down even better algorithms, and you can explain by creating simple yet instructive animations
   
2. trees, because they're elegant and magic

jctj said:

I am going to be teaching an Intro to Computer Programming class next year in High School. I am looking for examples of motivating problems to give the kids. It is easy to come up with something everyone hates, but there seems to be certain problems whose solutions are interesting enough to gain and keep attention, and whose solutions are hard enough (but not impossible) that there is real pride when the solution is found. I am looking for problems that require for their solution learning how to use various programming tools or ideas, from complete beginner (loops, if-then controls, variables, arrays) to beginning OOP.

Can you please tell me of computer problems you had to solve (lol - not bugs, not OS updates....) when learning to program that you really remember as being motivational? Please include which language (BASIC, Pascal, C, C++) or simply what type of language (Spaghetti, Procedural, Object-Oriented).

For example: my "become a geek" moment was in 7th grade when my math teacher challenged the class to figure out 2^64 - EXACTLY. Yes, we all grabbed our calculators (as he knew we would) and got an answer, but we then had a discussion on rounding errors, digits of accuracy, etc. This was back in 1980, so clearly what he was expecting was for us to do the multiplying by hand. Being stubborn and having just learned BASIC on an Apple I or Apple IIe (can't remember which one we had at that time), I was determined to figure it out with a program. It took over 4 hours - multiples of what it would have taken to do it by hand... - but I finally got it perfect so that it showed commas and leading zero's where it needed to. The very first thing I did when I downloaded Chipmunk Basic (Old-style BASIC compiler for Mac - in preparation for my class) was to replicate this program (this time in just 30 minutes, lol). It was amazing to me that, some 33 years later, I could still remember the approach, the problems encountered, and the solutions to those problems. As a teacher, I would call that problem a "significant learning moment" but just because it was significant for me doesn't mean it would be significant for anyone else. So.... I need to know what sort of problems created significant learning moments for all of you, so I can present multiple problems to my class.

Thank you in advance for your help!

James

Click to expand...

I agree with some of the others that getting to hairy too soon would be a mistake.


My first "Real" program was a simple game for the Apple 2 called Blockade, written in Integer Basic. It was like snake for 2 people, where you tried to box in the other person with your snake, who's tail got ever longer. That would be too much first first program however.

Games are good though.

How about a hangman game, developed as a team?

Simon (memory game, remembering increasing sequences of random notes/colored lights flashing)

A recursive routine for calculating factorials? Easy to write, fairly simple to understand once you get the idea of recursion.

I've also written a prime number generator that used a fixed-sized C array of integers to save the primes it found. It tested each candidate number against all previous primes. It seeded the array with 2 and then only looked at odd numbers.

I then fine-tuned it to try dividing each candidate against all previous primes up to an arbitrary value, and then beyond that value, calculate the square root of the prime and stop checking for prime divisors once I reached the square root.

You can calculate a million primes pretty fast with this algorithm. You could then talk about faster algorithms, and how large primes are useful in cryptography.

You could walk the class through the steps of creating a very naive generator, then talk about possible enhancements (first dividing by all numbers less than the candidate, then only checking against the previous primes, stopping at the square root, only calculating the square root once/candidate, etc.) Measure performance all along the way to illustrate optimizing code.

I've also used a large word list to pick 2 random words as a password generator. With a word list of 100,000 words you get very random passwords that are easy to remember. This has the advantage of being dirt-simple to do and real-world useful. The passwords are often funny.

I also wrote a polar equation graphing program in my trig class in high school and demonstrated it to the class. You had to modify the code to add a new equation, which was fine for teaching (an equation parser is way beyond an intro class.) Requires an understanding of trig.

The motivation for the original question reminded me of this:

http://worrydream.com/LearnableProgramming/

Fascinating concepts

I just picked up a Romo from romotive.com. I have no idea how practical it will be for the app programming club, but I thought it was cute and would look into the API and see what it could do.

I highly recommend greenfoot.org as a way to teach programming to students. It helps students visualize OOP and they will be publishing 'scenarios' within days.

I imagine it could be used as a step off to bluejay and then eclipse their senior year.

the problem with today's programming pedagogy... is today's programming pedagogy

Motivation is easy: every kid wants to make their own games. Those games might be shooters, they might be world builders, they might be social; that'll vary according to individual tastes. Lots of interesting CS-y problems there, like graphics, physics, path finding/AI, network comms, etc. that are considered 'hard' in themselves but these days have extensive library support.

The real challenge isn't teaching students mechanistic details like loops, conditionals, values and variables, nor even how to assemble larger programs using prebuilt libraries, it's teaching them structured thinking, independent learning and analytical problem-solving skills. The most important concept in all of computer science is abstraction (to quote Guy Steele), so anything else you have to introduce before abstraction that is just diverting them from that, filling their minds with distractions and trivia instead of instituting a clear framework for thinking.

Unfortunately, popular languages today (C, Java, Python, Ruby, JavaScript, etc) with their love of special forms draw far too much attention to mechanistic trivia like variables and flow control, encouraging novices to believe that these hardcoded, low-level features are central and unique concepts in programming. That in turn draws their attention away from what's really important, which is the tools and techniques for extending the basic language by adding your own more specific features on top of the general ones already there. (Or, to put it another way: sorry Algolers, but the Lispers were right after all.)

Basically, if you really want to understand the problems with CS pedagogy today, you need to go right back to Papert's work on LOGO and look at how he approached it. Bear in mind that Papert was successfully teaching abstraction to 8 year olds. Of course, he wasn't teaching programming specifically; he was teaching structured thinking and problem solving, and the LOGO language and environment was just a good platform for that.

The original turtle system gets a lot of snark now for being so 'primitive' and 'limited' in features, but that was the point. When the only predefined drawing operations are 'forward', 'left turn', 'pen down' and 'pen up', they are quick and easy to learn and are a direct representation of atomic physical operations so contain no abstract mysteries of their own. Naturally, once users master these commands they want to perform more sophisticated operations, like drawing complex shapes such as a 'house', a 'person' and so on. The obvious way to construct complex shapes, of course, is to arrange the existing forward/turn/up/down words into longer and longer sequences until they produce the required shapes - and in a language like BASIC this is all you would learn to do; thus BASIC creates the impression of empowering users, but really all it does is create unthinking menial drones, like Charlie Bucket's dad screwing the caps on toothpaste tubes eight hours a day.

With LOGO, a student will easily fall into this behavior too as part of their independent learning process, but this is where the educator would step in, introducing the student to the mind-blowing concept that they can in fact expand the existing, limited vocabulary with much more powerful and expressive words of their own. Thus the student is introduced to LOGO's 'procedure' feature, and shown how they can define new words like 'rectangle', 'triangle', and 'circle' as compositions of existing words, so that instead of writing 'fd 100 lt 120 fd 100 lt 120 fd 100' every time they want to draw a triangle they can just say 'triangle' and a triangle is drawn for them. And then they can be shown how to parameterize their own words, so that they can write 'triangle 50', 'triangle 100', etc. to create any size of triangle using the same word. And once they've got the basic principles of word composition then they can create even more powerful task-specific words that do exactly what they want. For example, a 'house' word is simply a composite of 'rectangle' (the front wall) and 'triangle' (the roof above it), and since that's a bit more complicated to get right they can be shown how how to learn by making mistakes, then troubleshooting and correcting them (i.e. debugging).

Along the way, of course, students can be introduced to other useful words like 'if' and 'repeat' which they might find useful. While they are certainly useful, they are not initially essential so can be completely ignored while teaching the far more important concept of word composition, And because the are just ordinary words, not special forms with their own unique and important-looking syntax and behavior rules, once they are introduced to them the user is not deceived into thinking that these built-in words are more important than, or any different to, their own words. Which is exactly as their mental priorities should be: after all, what's of most importance to the student themselves: 'if' and 'repeat', or 'house' and 'tree'?

By the time these learners are drawing elaborate landscapes full of highly detailed buildings of various shapes and sizes, their thinking is much more sophisticated than that of the modern BASIC/JavaScript/Processing/whatever student, who is simply handed a much more powerful 'helpful' language pre-packed with special keywords and syntaxes and libraries full of complex black-box abstractions like 'rectangle(x0, y0, x1, y1)' and taught to plug in numbers.

Basically, it's the difference between teaching a student how to use an existing tool, and teaching them how to make their own tools; and it's a priceless educational insight that's unfortunately been swamped by great waves of cheap but shiny trinkets that offer superficial rewards and the illusion of control while mostly just taking it away.

I posted some comments to similar discussions on a couple months back if you want to read more:

http://www.osnews.com/thread?559172

http://arstechnica.com/civis/viewtopic.php?f=20&t=1202483

You should also get yourself a copy of Papert's Mindstorms and read it cover to cover until these concepts 'click' in your own head:

http://www.amazon.com/Mindstorms-Children-Computers-Powerful-Ideas/dp/0465046746

As to how you fuse those lofty principles with the ugly realities of today's popular toolsets, I wish I could offer some solid advice. But having previously educated myself and others on a 'mainstream' end-user language my eventual conclusion was to go away and design my own end-user language from scratch - which is a project I'm still working on.

Games. Having students do things like bubble sort and all the typical boring programming problems is a great way to bore them.

My high school programming class was BASIC and we did all sorts of graphical and gaming related things. It was a lot of fun.