B
Ben Pfaff
SM Ryan said:
Apparently it is okay to quote 100 lines to top-post a snarky comment?
Apparently it is okay to quote 100 lines to top-post a snarky comment?
D
David Lightstone
SM Ryan said:
What topic? You read the subject line, you read the content and decide for
yourself if there is a correlation.
Perhaps I should have retitled the subject when I made my post. Perhaps the
author of the post to which I responded should have retitled it.
Either way it did not occur.
What to title the subject of this post. Can't decide. Perhaps - "a decision
criteria for determining when it might be wise to consider changing the
subject of the newsgroup posting" no that is just to long
B
blmblm
(e-mail address removed) said:
Well, for starters, either teach them how to program or tell them not to
apply for programming jobs.
You know, my initial reaction to this was "excellent advice!" --
but one of the advantages (?) of putting off a reply is that there's
time for second thoughts ....
We do get some students who just plain don't like programming
(difficult though that may be for some of us to imagine
).These students are apt to get discouraged and drop out of CS early
on, because the introductory courses are almost 100% programming.
The ones that stick around, though .... They almost certainly
should be encouraged to find some career path that doesn't involve
programming, even as an entry-level job.
But for the ones who do enjoy programming enough to do it for a
living, at least for a few years, I don't know. I'm not sure we
*can* teach them to program -- we can teach them some rudimentary
skills, but the only way they can become good programmers is to
actually program, and our ability to make them do that is limited
given that we also want to teach them "basic principles" (i.e.,
given them a framework of basic knowledge on which they can hang the
technical details they'll learn in later years). I don't think we
should skimp on the "basic principles" stuff, because that's what
I think we do well, better than the workplace. But the result is
that only the ones who enjoy programming enough to do side projects
really graduate with more than rudimentary programming skills. I'm
not sure we can fix that.
Oh, no need to be so diplomatic -- I asked, right? though if you
want to say it's not your *responsibility* to teach me/us how to
teach, well, yeah ....
However. You may or may not know that how to teach beginning
programming is a topic of perennial debate among people who do it for
a living. In the most recent ACM report on undergraduate curricula
(2001, linked from http://www.acm.org/education/curricula.html),
six, count 'em six, approaches are listed. Something rather like
what you describe is one of them ("hardware first").
[ snip ]
I like your thinking here. I'm a little biased, maybe -- the first
CS course I took was introductory programming using Fortran, and
though I did well I didn't feel like I understood much, and it wasn't
until I took another course in assembly-language programming (IBM
360 ALC -- that probably dates me, right?) that I started to think
"oh, I get it now ...."
Then, once they know all that, teach them programming from the clean end.
easily, because they understand what's going on underneath.
Yeah .... And if you don't teach this kind of thing at some point,
I'm inclined to think that on some level the students will never
really understand what they're doing. Then again, one of my
colleagues, a fairly bright guy, claims that by doing this you're
locking them into how things are done now and making it less likely
that they can come up with fresh perspectives, and the right way
to start is with something much more abstract. (He likes J, which
is more or less a descendant of APL.) I don't know. More in responses
to other posts in this thread.
Anyway, a "thank you!" to you and everyone who replied to my question.
It's all being filed for reference next time we argue about curriculum
revisions.
B
blmblm
[ snip ]
Cool idea. And you say this works well in practice? Hm ....
Cool idea. And you say this works well in practice? Hm ....
B
blmblm
[ snip ]
Exactly.
Too much focus on details, too early, carries the risk of creating
the impression that whatever detailed system you teach is the only
possible one. I'm not thinking of a really great example of what I
have in mind here -- something along the lines of "if all you know
is Windows, the idea of a powerful command line is unimaginable",
or equivalently, "if all you know is CLIs, the idea of a system with
menus and icons is unimaginable". Starting out with a more abstract
view supposedly avoids this "lock the students into a too-limited
mental model". Can MIT really be totally wrong to start 'em out
in Scheme? (If they're still doing that.)
Then again, too much focus on abstractions carries the risk that they
never really understand .... I think this is especially a risk for
the less-bright students, who aren't very good at abstractions and
when forced to deal with them are apt to just get confused and ....
I wonder if this is the origin of that (bad) approach to writing
code that seems to consist of trying things at random until something
seems to work.
Exactly.
Too much focus on details, too early, carries the risk of creating
the impression that whatever detailed system you teach is the only
possible one. I'm not thinking of a really great example of what I
have in mind here -- something along the lines of "if all you know
is Windows, the idea of a powerful command line is unimaginable",
or equivalently, "if all you know is CLIs, the idea of a system with
menus and icons is unimaginable". Starting out with a more abstract
view supposedly avoids this "lock the students into a too-limited
mental model". Can MIT really be totally wrong to start 'em out
in Scheme? (If they're still doing that.)
Then again, too much focus on abstractions carries the risk that they
never really understand .... I think this is especially a risk for
the less-bright students, who aren't very good at abstractions and
when forced to deal with them are apt to just get confused and ....
I wonder if this is the origin of that (bad) approach to writing
code that seems to consist of trying things at random until something
seems to work.
D
David Lightstone
I would say that it will work quite well.
When I learned programming (cerca 1967), the technique was called "desk
checking". The difference being that we did it at the level of the FORTRAN
instruction, rather than the machine instruction.
For those not familiar with the era, batch processing was the norm.
Turnaround time was measured in days, not seconds. It has to compile
correctly the first time. It has to execute correctly the first time.
otherwise you loose several days
..
?
=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=
Ben Pfaff said:
Mathematicians are nearly always good programmers -- if you can
structure a proof of a complex mathematical statement, you can program
also. They might find C++ obstruse and complicated (who doesn't?),
but give them a good functional programming language, and they will
out-program most so-called "programmers".
Indeed. I would rather criticise someone who calls himself a
programmer and who isn't able to program a sub-quadratic sorting
algorithm without having to consult a textbook (or use a library
routine).
Torben
J
Jonathan Bartlett
I had an adult Walmart stocking clerk who had attended my class by
mistake (she was supposed to be in the "how to use MS Word class" decide
to stay and learn to program... and did every bit as good a job as the
kid who played around with Linux in the offtime.
Because of the game/simulation, she felt she could actually understand
how it all worked together.
Jon
A
Andrew Poelstra
In general, if she herself decided to stay and learn how to code, she'd
be motivated enough to do a good job. Just a thought.
That would likely be the main reason that she was motivated. I think I
will steal your idea and use it to teach my class. Thanks!
K
Keith Thompson
I would criticize any programmer who *bothers* to implement a
sub-quadratic sorting algorithm without consulting a textbook or using
a library routine.
I can write a Quicksort function if I have to -- but I don't have to.
And if I tried it without consulting any references, it's likely the
resulting function would have some (probably subtle) bugs.
I don't remember where I read this, but I seem to recall that there
was a gap of a decade or so between the first implementation of a
binary search algorithm, and the first *correct* implementation of a
binary search algorithm.
R
Richard Heathfield
Keith Thompson said:
I think that's unlikely - in the sense that I am quite confident your
function would sort correctly (after a few muffled curses and a bit more
typing, obviously).
I think it's far /more/ likely that it would in fact be a SlowSort, and that
you could easily write a Shell sort to out-perform it.
Implementing Quicksort is pretty easy. Implementing it *efficiently* is a
fair bit harder.
I think that's unlikely - in the sense that I am quite confident your
function would sort correctly (after a few muffled curses and a bit more
typing, obviously).
I think it's far /more/ likely that it would in fact be a SlowSort, and that
you could easily write a Shell sort to out-perform it.
Implementing Quicksort is pretty easy. Implementing it *efficiently* is a
fair bit harder.
D
David Lightstone
Richard Heathfield said:
I guess you basic argument is something like - Efficiently is why academics
study such things. Programmers often only need concern themselves with
evaluating whether the algorithm is or is not in conflict with NP
completeness
When you define success that way, I doubt if anyone could possible disagree.
When I first started out (auto industry) success was often being able to
reduce the cost of a part by 1 cent (US). Efficency counted
R
Richard Heathfield
David Lightstone said:
No, that's not what I'm saying at all. In fact, I was agreeing with the idea
that it's far better to write a call to qsort (possibly two minutes to bash
out a comparison function, and another twenty seconds to check the order of
the args in K&R) than to spend two hours getting Quicksort /wrong/. We all
know that Quicksort is faster than Shell sort, so it isn't a question of
choosing which algorithm to use. But having coded up a Shell sort just for
the hell of it, and then a Quick sort because I'm-so-smart-I-can, I was
astounded to discover that my Shell sort consistently outperformed my Quick
sort over a large range of data set sizes - tiny, through mid, and right
the way up to huge. Obviously I got my Quick sort wrong. It sorted just
fine, but it took way too long to do it.
Yeah, but if saving a cent is success, then saving a dollar is a triumph.
The best way to make your sort Quick is to use the standard library's
sorting routine. That cuts down on writing time, debugging time, and run
time.
No, that's not what I'm saying at all. In fact, I was agreeing with the idea
that it's far better to write a call to qsort (possibly two minutes to bash
out a comparison function, and another twenty seconds to check the order of
the args in K&R) than to spend two hours getting Quicksort /wrong/. We all
know that Quicksort is faster than Shell sort, so it isn't a question of
choosing which algorithm to use. But having coded up a Shell sort just for
the hell of it, and then a Quick sort because I'm-so-smart-I-can, I was
astounded to discover that my Shell sort consistently outperformed my Quick
sort over a large range of data set sizes - tiny, through mid, and right
the way up to huge. Obviously I got my Quick sort wrong. It sorted just
fine, but it took way too long to do it.
Yeah, but if saving a cent is success, then saving a dollar is a triumph.
The best way to make your sort Quick is to use the standard library's
sorting routine. That cuts down on writing time, debugging time, and run
time.
F
Flash Gordon
Richard said:
I agree completely. In addition, if after doing it you find your
libraries quicksort implementation isn't fast enough the best thing to
do is see if you can find a better one that someone else has implemented
and use that.
I'll never write code myself if I can find and legally use some written
by an expert in the field.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc
Inviato da X-Privat.Org - Registrazione gratuita http://www.x-privat.org/join.php
P
pete
Richard said:
The truth of that is entirely implementation dependant.
qsort on my implementation,
goes quadratic on worst cases,
and it has more than one kind of worst case,
and it is easy to beat hand coded, for all cases.
Using
http://www.mindspring.com/~pfilandr/C/e_driver/
/* BEGIN e_driver.c program output */
Timing 4 different sorting functions.
Sorting arrays of N number of elements,
in 2 different distributions.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.
Distribution #1: Shuffled
N qisort qrsort m_sort qsort
199998 0.110000 0.109000 0.140000 0.156000
199999 0.110000 0.125000 0.140000 0.157000
Total times:
qisort: 0.220000 qsort interface, center pivot introspective
qrsort: 0.234000 qsort interface, random pivot introspective
m_sort: 0.280000 qsort interface, stable merge, TOO_SMALL is 10
qsort: 0.313000 standard library qsort
Distribution #2: Ramp, Drives center pivot qsorts, quadratic
N qisort qrsort m_sort qsort
199998 0.250000 0.094000 0.078000 0.922000
199999 0.266000 0.094000 0.078000 1.250000
Total times:
qisort: 0.516000 qsort interface, center pivot introspective
qrsort: 0.188000 qsort interface, random pivot introspective
m_sort: 0.156000 qsort interface, stable merge, TOO_SMALL is 10
qsort: 2.172000 standard library qsort
/* END e_driver.c program output */
/* BEGIN e_driver.c program output */
Timing 4 different sorting functions.
Sorting arrays of N number of elements.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.
Distribution #1: Two values, Badly written qsorts choke on this
N qisort qrsort m_sort qsort
19998 0.000000 0.000000 0.000000 1.594000
19999 0.000000 0.000000 0.000000 1.593000
Total times:
qisort: 0.000000 qsort interface, center pivot introspective
qrsort: 0.000000 qsort interface, random pivot introspective
m_sort: 0.000000 qsort interface, stable merge, TOO_SMALL is 10
qsort: 3.187000 standard library qsort
/* END e_driver.c program output */
R
Richard Heathfield
pete said:
Naturally, but:
(a) mostly it's true anyway;
(b) in cases where the implementation gives you a lousy qsort, get a better
implementation!
(a) takes care of maybe 90% of the cases. (b) takes care of maybe 90% of
what remains. And even if you're in the unlucky 1%, nevertheless you can
probably still find something on Usenet, written by some guy who calls
himself Lower Case Pete, which does the job for you. So there's no real
need to write it yourself.
Naturally, but:
(a) mostly it's true anyway;
(b) in cases where the implementation gives you a lousy qsort, get a better
implementation!
(a) takes care of maybe 90% of the cases. (b) takes care of maybe 90% of
what remains. And even if you're in the unlucky 1%, nevertheless you can
probably still find something on Usenet, written by some guy who calls
himself Lower Case Pete, which does the job for you. So there's no real
need to write it yourself.
C
CBFalconer
pete said:
It is always possible to make quicksort go quadratic solely by the
appropriate input data. See:
SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 29(0), 1–4 (0 1999)
A Killer Adversary for Quicksort
M. D. MCILROY
Dartmouth College, Hanover, NH 03755, USA
I have this as a file mdmspe.pdf on my system. Not sure where I
found it.
You can use sorts with guaranteed worst case performance, such as
heapsort and mergesort. There is no guarantee that the C system
qsort is actually quicksort.
--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
G
Googmeister
CBFalconer said:
No, that's not true. If you partition on the median element,
you can guarantee O(n log n) - admittedly finding the median
in linear time is not so practical. Alternatively, if you
partition on a random element (using a good source of
randomness), no fixed input will make it go quadratic.
This is a great paper, but the technique only apply to a
certain (but broad) class of partitioning schemes.
K
Keith Thompson
Richard Heathfield said:
Some things to keep in mind:
The basic Quicksort algorithm is quadratic (O(N**2)) for some inputs.
There are various ways to tweak it to avoid this problem, such as
being smarter about picking a pivot value.
The best possible performance for a sorting algorithm (using only a
certain set of operations) is O(n log n). Quicksort isn't the only
O(n log n) sorting algorithm.
Despite the name, there is no requirement for C's qsort() function to
be implemented using the Quicksort algorithm. No sane implementer
would use a quadratic algorithm for qsort(), but it would be legal.
(Perhaps the DS9K does this.)
The qsort() function does impose a significant performance overhead
compared to a hand-written sorting routine. It has to perform an
indirect function call for each comparison. If you re-implement the
exact same algorithm used by your implementation, but using inline
comparisons, you'll probably get a constant factor speedup. There are
undoubtedly cases where this would be worth doing -- *if* you've
measured the actual performance and determined that it's significant.
For sufficiently small arrays, the complexity of Quicksort and other
O(n log n) algorithms can make them slower than quadratic algorithms
like insertion sort. One common approach is to use Quicksort, but
fall back to something like insertion sort for small subarrays.
K
Keith Thompson
Googmeister said:
One approach I've seen is to take the median of the first, middle, and
last elements, and use that as the pivot.