mgreen@cs.toronto.edu (Marc Green) (08/22/90)
A few weeks ago, I posted a request for suggestions on teaching a languages course. Thanks to all who responded. I've decided to center the course of the view that computer languages are a way to formally specify algorithms. I'd like the students to program the same 3-4 algorithms in several languages, to get a feel for the differences. I am now asking for suggestions on good algorithms/problems to have them implement. I have in mind algorithms like bubble-sort, merge-sort, tree-search and problems like the Tower of Hanoi. Any others? (My students are not computer jocks and can't handle anything too esoteric.) Marc Green Trent University
Chris.Holt@newcastle.ac.uk (Chris Holt) (08/23/90)
In article <90Aug22.090345edt.9450@neat.cs.toronto.edu> mgreen@cs.toronto.edu (Marc Green) writes: > >I've decided to center the course of the view that computer languages >are a way to formally specify algorithms. I'd like the students to >program the same 3-4 algorithms in several languages, to get a feel >for the differences. > >I am now asking for suggestions on good algorithms/problems to have >them implement. I have in mind algorithms like bubble-sort, >merge-sort, tree-search and problems like the Tower of Hanoi. Any >others? (My students are not computer jocks and can't handle anything >too esoteric.) DON'T use bubble sort; once people learn it, they use it for the rest of their lives, it seems like, and it takes ages to unteach. You might try a pattern matching (string search) algorithm (it's got a simple specification); and the old matrix multiplication is a good one to start arrays with. ----------------------------------------------------------------------------- Chris.Holt@newcastle.ac.uk Computing Lab, U of Newcastle upon Tyne, UK ----------------------------------------------------------------------------- "Extreme bounds are most appropriate for extreme kangaroos..."
pattis@cs.washington.edu (Richard Pattis) (08/23/90)
In article <1990Aug22.182415.27036@newcastle.ac.uk>, Chris.Holt@newcastle.ac.uk (Chris Holt) writes: > DON'T use bubble sort; once people learn it, they use it for the > rest of their lives, it seems like, and it takes ages to unteach. > > You might try a pattern matching (string search) algorithm (it's got a > simple specification); and the old matrix multiplication is a > good one to start arrays with. > What exactly is wrong with bubble sort? It is the smallest sorting algorithm to state (in most imperative programming languages), and is the easiest one to prove correct (assuming a Swap procedure). For small array sizes, its performance is just fine. If a student ever has to reconstruct a sorting method from scratch, he/she will have the highest probability of getting bubble sort right (higher than any other algorithm I can think of). There are even sets of data (almost sorted) where bubble sort can do better than many "asymptotically faster" sorting algorithms. So, do I teach bubble sort in my CS-1 class? Yes. How do I ensure they won't use it in subsequent programs? By the end of the class my students have learned about generic subprograms (I teach Ada) and they are presented with various N**2 and NLogN generic sorting procedures; all are instantiated in exactly the same way (element type, array type, comparison function). In all their CS-2 programs, wherever sorting is required, they instantiate whatever sorting subprogram they want (and can easily change their mind about the decision later). In this course we have them compute approximate values for the constants of all these subprograms, and predict running times on large data (so they understand bubble sort's weakness). We also teach them how to use program profilers, to try to understand where the majority of time is spent in a system. If they ever go to a new language/system that doesn't have such built-in sorting procedures, and they really need to write their own from scratch (no books) I'd be happy if they wrote bubble sort. If the problems they had to solve had a large amount of data, and sorting was the bottleneck, they would know about other algorithms, and I hope be able to transcribe them from some source to the particular language/system. I guess the bottom line is that I don't think it takes more than 2 quarters to give students a good perspective on sorting algorithms in software systems. Back to the main topic: Sedgewick's book, "Algorithms" is a great place to get string algorithms. The most recent CACM had a few variants on these. Boolean matrix multiplication for path problems or solving stochastic systems can be presented in a realistic manner. Rich Pattis
draughn@iitmax.IIT.EDU (Mark Draughn) (08/23/90)
In article <90Aug22.090345edt.9450@neat.cs.toronto.edu> mgreen@cs.toronto.edu (Marc Green) writes: [...] >I've decided to center the course of the view that computer languages >are a way to formally specify algorithms. I'd like the students to >program the same 3-4 algorithms in several languages, to get a feel >for the differences. [...] >I have in mind algorithms like bubble-sort, merge-sort, tree-search >and problems like the Tower of Hanoi. Any others? I always start learning a language by writing a program that prints "Hello world." It's short and simple in most languages. Seriously, maybe I'm misunderstanding you, but this plan of yours sounds a bit boring. These algorithms look about the same in almost all languages. Sure, LISP recursions and FORTRAN loops look different, but what do you do after that? Let me suggest a test. Before assigning the "do bubble sort in three different languages" problem, do it yourself. Be sure to do everything you would expect the students to do: Input/output, comments, documentation, and maybe input verification. Be sure to test your programs, since the students would test theirs before turning them in. If your students would have to prepare floppies or hardcopy, you should do the same. If this seems like a lot of work for no purpose or if you are tempted to quit once you have proved to yourself that you can do the first one, it is likely that your students will feel the same way. This is just My Humble Opinion, but I find some fault with the usual thinking about large v.s. small programming assignments. Many people think that a group of several small assignments is more interesting than one big assignment because the big assignment probably has a lot more non-concept-related code than the small one. I often find, however, that if the concepts are too closely related, the overhead of preparing the resulting code (testing, printing copies, making floppies, checking documentation) seems too wasteful. (If you want to tell a friend 5 different things, would you rather send one long letter discussing all five things, or five short letters?) Although excitement is not the primary criterion for judging the value of homework assignments, it seems to me that by requiring several programs that do exactly the same thing, you are making the process more boring than it has to be. -- Mark Draughn | <draughn@iitmax.iit.edu> or <SYSMARK@IITVAX> on BITNET ----------------+ Academic Computing Center, Illinois Institute of Technology +1 312 567 5962 | 10 W. 31st Street, Chicago, Illinois 60616
mjl@cs.rit.edu (08/23/90)
When I took a language concepts course all those many years ago (1970? when dionsaurs roamed the earth?) the concepts themselves were clearly separated from the particular languages we used in our labs. In fact, I remember clearly a lecture on binding time with the following exchange: Professor; "And in Snobol you can do this <some esoteric construct>" Student: "You can't do that in Snobol!" Professor: "Well, you should be able to!" The point was that the concepts were the key, and languages were chosen on the basis of how they demonstrated different approaches to solving various problems. As for labs, we did two in each of the languages we studied. Typically the first lab showed the strength of the language, while the second emphasized the language's weaknesses (typically we solved a problem for which the language was at best a marginal choice). I thought this worked marvelously, as it reinforced the class lectures while providing object lessons in how to choose an appropriate (or inappropriate) language. By the way, I'd be concerned with a course that emphasized algorithms alone. As Wirth's book title said many years ago, Algorithms + Data Structures = Programs. Without any emphasis on the data structuring approaches embodied in each language, students will get a warped view of the languages. For instance, most algorithms in Smalltalk are boring, and stressing them would miss the whole point of the language. -------- Mike Lutz Rochester Institute of Technology Rochester, NY 14623-0887 mjl@cs.rit.edu
kanamori@Neon.Stanford.EDU (Atsushi Kanamori) (08/23/90)
In article <12868@june.cs.washington.edu> pattis@cs.washington.edu (Richard Pattis) writes: > >What exactly is wrong with bubble sort? Because there are two other N**2 algorithms that are just as intuitive (more, imho) and are more efficient. If I were teaching sorting algorithms, I would much prefer that the students adopt insertion or selection sort as their quick & dirty standby. Bubblesort is basically a selection sort where the "find smallest element" part is written incredibly inefficiently and performs a lot of extra swaps that don't need to be there. Whereas selection sort moves the smallest element to the top in one swift leap, bubblesort does it the hard way by bubbling it up using multiple swaps. Seems like an unnecessary burden, both on the cpu & human brain.
kanamori@Neon.Stanford.EDU (Atsushi Kanamori) (08/23/90)
In article <4147@iitmax.IIT.EDU> draughn@iitmax.iit.edu (Mark Draughn) writes: >In article <90Aug22.090345edt.9450@neat.cs.toronto.edu> mgreen@cs.toronto.edu (Marc Green) writes: >[...] >>I've decided to center the course of the view that computer languages >>are a way to formally specify algorithms. I'd like the students to >>program the same 3-4 algorithms in several languages, to get a feel >>for the differences. >[...] >>I have in mind algorithms like bubble-sort, merge-sort, tree-search >>and problems like the Tower of Hanoi. Any others? > > >Seriously, maybe I'm misunderstanding you, but this plan of yours >sounds a bit boring. These algorithms look about the same in almost >all languages. Sure, LISP recursions and FORTRAN loops look >different, but what do you do after that? > I think the intended approach was to disallow side-effects in Lisp; then the difference between Lisp sorters and Fortran sorters are a lot more than just syntactic. In general, the fun part of this approach is choosing problems that require a nontrivial amount of head-scratching to implement in each language. It might help if we try to think in terms of problems rather than algorithms; fixing the algorithm tends to fix the programming paradigm (i.e. some algorithms are naturally Fortran-ish and others are naturally Lisp-ish) and I believe the intent is to force the student to think in the different paradigms of each language. BTW: Don't use Towers of Hanoi; it may be a classical example of recursion but there is an obscure iterative solution: if a student happens to know this, you'll have a horny policy problem on your hands. Tree-search is pretty good as a method of comparing the dynamic-data-structure abilities of different languages. You might also consider a companion problem in which data structures shrink as well as grow (i.e. show how garbage collectors make one's life easier.)
pattis@cs.washington.edu (Richard Pattis) (08/24/90)
In article <1990Aug23.153652.23949@Neon.Stanford.EDU>, kanamori@Neon.Stanford.EDU (Atsushi Kanamori) writes: > In article <12868@june.cs.washington.edu> pattis@cs.washington.edu (Richard Pattis) writes: > > > >What exactly is wrong with bubble sort? > > Because there are two other N**2 algorithms that are just as intuitive > (more, imho) and are more efficient. If I were teaching sorting algorithms, > I would much prefer that the students adopt insertion or selection sort > as their quick & dirty standby. > > Bubblesort is basically a selection sort where the "find smallest element" > part is written incredibly inefficiently and performs a lot of extra > swaps that don't need to be there. Whereas selection sort moves the > smallest element to the top in one swift leap, bubblesort does it the hard > way by bubbling it up using multiple swaps. Seems like an unnecessary burden, > both on the cpu & human brain. OK; choose your language and write either of those sorting procedures; I'll write bubble sort. Then, write a one paragraph justification of why your sorting procedure works; I'll do the same. The justification should include a demonstration that the array is sorted, and a permutation of the input array. Rich
smithc@motcid.UUCP (Chris Smith) (08/24/90)
In article <12868@june.cs.washington.edu>, pattis@cs.washington.edu (Richard Pattis) writes: > In article <1990Aug22.182415.27036@newcastle.ac.uk>, Chris.Holt@newcastle.ac.uk (Chris Holt) writes: > > DON'T use bubble sort; once people learn it, they use it for the > > rest of their lives, it seems like, and it takes ages to unteach. > > ... > > What exactly is wrong with bubble sort? It is the smallest sorting algorithm > ... I agree with Chris, once bubble sort is learned, it is invariably used. A professor of mine in grad school claimed this was because it had a nifty name :-). Simply put, insertion or selection sorts are as simple to write, once learned, as is bubble sort. Their performance is better with near random data due to the far fewer number of data swaps occuring. While working for a defense contractor, I found a bubble sort executing on random data with repetition where the boolean function was less-than or equal. The software was a realtime EW suite. Granted, the original engineer had a foolish boolean operation, however the sort itself was terribly inefficient. The engineer's reaction when question was 'I know that. I took data structures too!'. I would prefer bubble sort was left as an example for an algorithms course when comparing complexities of common sorts, not introduced in early language classes. -- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^ Chris Smith @ Motorola Inc. "I know life is unfair, but why can't it be ^ ^ ..!uunet!motcid!smithc "unfair in my direction sometime" <--LEVITY ^ ^-------------------My thoughts, not my employer's------------------------^
tpmg0848@uxa.cso.uiuc.edu (Tom Magliery) (08/25/90)
Since this has evolved into a discussion of sorting-for-beginners, I'll add a couple of my cents on an idea that nobody's mentioned yet... I find it useful to teach insertion and selection sort together, rather than to emphasize one or the other. The similarity between them makes a nice generality that helps the students to remember what's going on. In particular, with both methods, the idea is that you select an item from an unsorted pile, and insert it into a sorted pile; the difference is where you "get smart". With insertion sort, you pick up any element you want, and then you "get smart" about where you put it down. With selection sort you "get smart" about which element you pick up, and then you don't have to think much about where you put it down. I thought of this all by myself as a way to keep the two straight. Of the 5 or 6 professors with whom I've been involved who've taught these methods, only one drew the analogy. I think it helped the students. As for teaching bubble sort, I do think it's nifty-looking if you can do a neat demonstration, preferably with a program running so the students can see why it's so named. To me, it's no more intuitive than insertion or selection, though, and those can be neato-ly demonstrated, too. But (I don't think anybody has mentioned this either) bubble takes *less code*. This may not seem very important to us (I'm not sure how important I consider it), but it is often important to the students, so it's something to keep in mind. Enough. mag -- ____._._...___.....__.__.._..__ Tom Magliery mag@cs.uiuc.edu OR mag@uiuc.edu
gillies@m.cs.uiuc.edu (08/26/90)
Why not teach them about hash tables and then have the implement LZW data compression? See IEEE Computer June 1984 for more information. This is a very good use of hash tables, and one of the fastest and most powerful compression algorithms known (LZ compression is, theoretically, asymptotically optimal for many types of redundancy). I can't stand these idiotic algorithms books that concentrate on huffman coding which is a dead algorithm. If the students have access to bitmapped displays, why not teach them about "floyd's" algorithm for converting grey-scale images into binary images. Actually, I don't really know the precise details of floyd's algorithm, but it is one of the most widely used heuristic algorithms for producing pictures (just about every binary image you ever saw was probably produced by a variant of floyd's algorithm).
Chris.Holt@newcastle.ac.uk (Chris Holt) (08/27/90)
In article <1990Aug24.183639.15361@ux1.cso.uiuc.edu> tpmg0848@uxa.cso.uiuc.edu (Tom Magliery) writes: > >I find it useful to teach insertion and selection sort together, rather than >to emphasize one or the other. I do this too, in my formal methods course; and then optimize one up to merge sort, and the other up to quick sort. It fools the students into thinking we've got a complete taxonomy for sorting algorithms :-). > ... But (I don't think >anybody has mentioned this either) bubble takes *less code*. This may not >seem very important to us (I'm not sure how important I consider it), but it >is often important to the students, so it's something to keep in mind. It's important if it means someone can understand it all at once, as opposed to understanding parts of it. However, when I'm concerned with proofs of correctness, bubble sort doesn't win at all, since you have to go operational, and functional proofs are so much easier. >Enough. Yea, verily. ----------------------------------------------------------------------------- Chris.Holt@newcastle.ac.uk Computing Lab, U of Newcastle upon Tyne, UK ----------------------------------------------------------------------------- "The meanest flower..can give thoughts that do often lie too deep for words."
dlm@sjfc.UUCP (Don Muench) (08/29/90)
Try doing Dijkstra's single-source shortest-path algorithm in FORTRAN, Pascal, BASIC, Modula-2, ISETL.