I think most CS degrees still do (and should) require the algorithms and data structures programming.
They are useful skills, and, I think the reason that the section seems "old-school" comes from the proliferation of Java in early CS courses.
Java has most of the algorithms and structures implemented already, and there's no point in anyone redoing it once they find those implementations, so the skills fall out of use.
Well, the point of binary trees and linked lists is also more of what gaius said.
Yes, it definitely helps to be able to visualize how things are structured, but I think the biggest thing you learn comes from understanding the asymptotic performance of various operations on those data structures.
Without understanding these structures, the fact that one provides much faster lookup, but slower deletes seems totally arbitrary and magical.
(Not sure I'm so much disagreeing with you as elaborating here.)
Thanks - I should have elaborated more. I was meaning more of the way memory is structured and accessed. Yes, it's all abstracted now - but it's still important to know and understand.
Just because you don't need to write your own sorting algorithms don't mean you don't have to know how to write one. First of all it is a good introduction to algorithms, analysis and construction and you still have to know the complexity of each to choose the correct one in some cases.
Some of these techniques are still very useful. For example when developing for embedded systems you don't have the luxury of infinite cpu cycles and ram, you need to understand the algorithms you are using, implement your own, and be able to optimize for performance.
Another way to look at it is this -- how can having more knowledge, more tools in your toolbox, hurt?
It's really jarring how this article switches between talking about linked lists and then explaining what multitasking is... is this for technical people or not? Reminds me of mainstream news coverage of any technology subject...
What the hell kinda crap is that article. You don't need to know sorting algorithms?
You may never write one to use in a production environment, but you better damn well understand them and then some.
And no need for memory management? I don't care if you're coding in a garbage collected language you STILL better understand how computer memory works.
This article is literally below coding horror standards.
This kinda misses the point of Hungarian. I don't care that two variables are both floats, the compiler will keep track of types for me. I do care very much that I'm not trying to add a width to a height, for example. Hungarian can help with that in languages like C and Python.
Indeed. That's also one of the biggest cases where static typing (especially inferred static typing) comes in handy. Mixing up those (or mistaking unit conversions!) can lead to particularly subtle bugs.
I'm haven't decided whether it's a net gain, but that's something it catches especially well.
In principle we ought to be able to treat width and height as two separate subtypes of some numeric type and have the compiler generate an error if we add them together. But unfortunately today's common languages like C and Java don't support that.
When I was forced to learn Ada for my current job, I was skeptical that it would be a good experience. But I must admit, I like being able to declare things in feet and meters and have the compiler complain when I try to add them.
But it's overbalanced by the sheer amount of effort necessary to make the compiler shut up when I do want to do that. Something like half my Ada code winds up as inane type conversions. I find myself very hesitant declare things in feet and square feet and milliwatts and meters because I know what a phenominal amount of work I am making for myself. Writing in Ada is a strange exercise in type engineering, trying to get exactly the amount of error-checking that I want out of the compiler without distracting myself too much from the actual problem I'm trying to solve. I'm rarely successful. I once recently spent four hours developing an algorithm in Perl, and then--with it understood and debugged--two days translating it into Ada. Most of that time was spent making reassuring gestures toward the compiler.
Then again, the extreme permissiveness of a language like Perl has its own drawbacks. I recently lost a whole day to a function I thought was expecting named parameters (but which wasn't). Ubiquitous default values and silent conversions are nice when you're expecting them and brutal when you aren't; to write efficiently, I must sprinkle die everywhere. And that's the catch: I'm not persuaded that truckloads of 'turn error-checking on' incantations are an improvement over truckloads of 'turn error-checking off'. It's inane code either way.
When you get right down to it, one size doesn't fit all, even within the same program. Ideally, I'd like a language that let me 'tag' variables and functions with types or units or associations, and let me decide when and what to check by default in what contexts. I'd love a language that stopped me from setting a variable in feet to one in meters, but also gave me a way to say "don't check units on this line--it's a formula--but please still check my pointer indirection". Alas, between building Perl up, quieting Ada down, templating C++, or simply building a baroque OO hierarchy in Java, nothing I've used seems really robust and flexible enough to serve this purpose well.
Ah yes, I remember one of my favorite assets being my mouse driver so that I could have mouse support in my applications...and then the happiness of porting it to Pascal from C and having it work in there too...nice big binary arrays to define what cursors look like...I'm glad I don't write mouse drivers or having to double buffer graphics anymore -- but on the other hand, figuring out everyone else's APIs, languages, frameworks, each with their own style, is a pain too.
Sometimes I find a really awesome javascript library that does exactly what I need it to do, but I find configuring it is a pain, or it is missing just one or two things that I need and I'm reading the source code and I really don't want to edit it...so I just write my own.
Oh while I'm ranting -- all you people that are making your ridiculous number of JQuery add-ons that do almost the same thing as tons of other add-ons, or your CSS+JQuery image slide that has been done a hundred times before just so that you can prove you have figured out how to write basic javascript and so you wrote something you've already seen a hundred times before to get some more traffic to your blog that hasn't said anything new for months now....please, stop it...stop it, stop it....your ruining the quality of my google searches. Really, you don't need to post all the time, we have readers now, we don't have to individually check back on your blog all the time, write when you have something to say, not to hit a quota. Ramble complete.
No, I don't miss them, but I'm sure glad I had to suffer through them. It has helped me to understand "what's happening under the hood" when I make a call with one line of code.
I used to screen programmers by having them code a bubble sort in 20 minutes. After about 1000 of these, I think the results were:
Pct Result
----- ---------------------------------------
50.0 Why would anyone ever want to to that?
25.0 Tried but couldn't do it
24.9 Did it in 2 loops
.1 Did it in 1 loop (Yes, I hired him.)
for (int ii = 0; ii < n-1; ++ii) {
// ii+1 largest elements end up in their correct position at the end of this loop.
for (int jj = ii; jj < n-1; ++jj) {
if (arr[jj] > arr[jj+1]) {
swap(arr[jj], arr[jj+1]);
}
}
}
One loop:
int ii, jj;
for (ii = 0, jj = 0; ii < n-1; ii = ((jj == (n-1)) ? (ii + 1) : ii), jj = ((jj == n-1) ? ii : (jj + 1))) {
// compare and swap as before
}
Unreadable, but it's one loop.
EDIT: use code formatting, oops.
EDIT 2: add proper conditional for jj update instead of jj = jj + 1.
Not really bubble-sort-specific; you can make any pair of loops into a single loop that way.
for (set up initial conditions for both loops;
check the outer loop termination condition;
if the inner loop is done reset the inner loop and advance the outer loop,
if the inner loop is not done advance the inner loop) {
// do the inside of the loop
}
OO languages have not eliminated the need for structured programming. It's still just as important as ever for code within class methods to be properly structured.
Of course that mainly only applies to OO languages which also follow the imperative and procedural paradigms. Structured programming is (mostly) irrelevant for functional languages since they don't have the same control flow constructs.
32 comments
[ 3.1 ms ] story [ 80.3 ms ] threadThey are useful skills, and, I think the reason that the section seems "old-school" comes from the proliferation of Java in early CS courses.
Java has most of the algorithms and structures implemented already, and there's no point in anyone redoing it once they find those implementations, so the skills fall out of use.
Yes, it definitely helps to be able to visualize how things are structured, but I think the biggest thing you learn comes from understanding the asymptotic performance of various operations on those data structures.
Without understanding these structures, the fact that one provides much faster lookup, but slower deletes seems totally arbitrary and magical.
(Not sure I'm so much disagreeing with you as elaborating here.)
Yes, that's why all general-purpose languages' standard libraries use the same implementation of the same sorting algorithm for the default sort().
Another way to look at it is this -- how can having more knowledge, more tools in your toolbox, hurt?
You may never write one to use in a production environment, but you better damn well understand them and then some.
And no need for memory management? I don't care if you're coding in a garbage collected language you STILL better understand how computer memory works.
This article is literally below coding horror standards.
I'm haven't decided whether it's a net gain, but that's something it catches especially well.
Here is the original Hungarian notation article by Charles Simonyi. http://msdn.microsoft.com/en-us/library/aa260976.aspx
But it's overbalanced by the sheer amount of effort necessary to make the compiler shut up when I do want to do that. Something like half my Ada code winds up as inane type conversions. I find myself very hesitant declare things in feet and square feet and milliwatts and meters because I know what a phenominal amount of work I am making for myself. Writing in Ada is a strange exercise in type engineering, trying to get exactly the amount of error-checking that I want out of the compiler without distracting myself too much from the actual problem I'm trying to solve. I'm rarely successful. I once recently spent four hours developing an algorithm in Perl, and then--with it understood and debugged--two days translating it into Ada. Most of that time was spent making reassuring gestures toward the compiler.
Then again, the extreme permissiveness of a language like Perl has its own drawbacks. I recently lost a whole day to a function I thought was expecting named parameters (but which wasn't). Ubiquitous default values and silent conversions are nice when you're expecting them and brutal when you aren't; to write efficiently, I must sprinkle die everywhere. And that's the catch: I'm not persuaded that truckloads of 'turn error-checking on' incantations are an improvement over truckloads of 'turn error-checking off'. It's inane code either way.
When you get right down to it, one size doesn't fit all, even within the same program. Ideally, I'd like a language that let me 'tag' variables and functions with types or units or associations, and let me decide when and what to check by default in what contexts. I'd love a language that stopped me from setting a variable in feet to one in meters, but also gave me a way to say "don't check units on this line--it's a formula--but please still check my pointer indirection". Alas, between building Perl up, quieting Ada down, templating C++, or simply building a baroque OO hierarchy in Java, nothing I've used seems really robust and flexible enough to serve this purpose well.
http://en.wikipedia.org/wiki/Hungarian_notation#Systems_vs._...
Sometimes I find a really awesome javascript library that does exactly what I need it to do, but I find configuring it is a pain, or it is missing just one or two things that I need and I'm reading the source code and I really don't want to edit it...so I just write my own.
Oh while I'm ranting -- all you people that are making your ridiculous number of JQuery add-ons that do almost the same thing as tons of other add-ons, or your CSS+JQuery image slide that has been done a hundred times before just so that you can prove you have figured out how to write basic javascript and so you wrote something you've already seen a hundred times before to get some more traffic to your blog that hasn't said anything new for months now....please, stop it...stop it, stop it....your ruining the quality of my google searches. Really, you don't need to post all the time, we have readers now, we don't have to individually check back on your blog all the time, write when you have something to say, not to hit a quota. Ramble complete.
Link { Link next; Object value; }
I used to screen programmers by having them code a bubble sort in 20 minutes. After about 1000 of these, I think the results were:
EDIT: use code formatting, oops. EDIT 2: add proper conditional for jj update instead of jj = jj + 1.
- One of my recent tasks was to implement a B-Tree and a Binary Tree. Also, I implemented merge-sort for another project.
- Our company does create it's GUI from scratch. No drag-and-drop magic there either.
- We use GOTO (sparingly). Mostly for error handling.
- We have our own memory managers and do malloc/free (+new/delete). So manual memory management as well.
- We have our own date conversion routines as well.
- We use NULL terminated C-strings everywhere!
- We do lots of things to make our code run faster. Some of these are probably strange!
I don't know if the article is poor or I am out of date! Anyone else out there feel the same?
In any case I would miss most of the above if I didn't have to do them.
Of course that mainly only applies to OO languages which also follow the imperative and procedural paradigms. Structured programming is (mostly) irrelevant for functional languages since they don't have the same control flow constructs.