Fog Creek Software
Discussion Board




Learning the basic algorithms


How long should I plan to learn basic algorithms for searching & sorting (basically what's typically teached in a BSs of CS) ?

Newbie (College Drop Out! And not proud of it!) :-(
Monday, August 16, 2004

Two years maybe, less than one if you're motivated.  Browse amazon for likely looking candidates to expand your library.

As for not being proud of your college career?  Why not?  Your education is not inextricably entwined with the established system.  You can learn quite well on your own, and with the help of the internet.  Yes, the classroom environment is invaluable, but if you haven't got it, you can make do.

I dropped out of High School.  That ought to get the hounds here at my heels right quick.

muppet
Monday, August 16, 2004

Don't.  Get a library.

Almost Anonymous
Monday, August 16, 2004

Even Bill Gates dropped out.... of Harvard.

You can spend a bunch of time reading about them, but I don't know how worthwhile that is for people, whether in school or out of school.

Teach yourself the algorithms by coding them.  Wikipedia (or by just googling) has a wealth of explanations of the algorithms.  Use them to do practice projects that you *don't* throw away.  Keep them around for reference.  It's not like you'll run out of disk space.

You mentioned searches and sorts, but I would add structures as well.

Walt
Monday, August 16, 2004

You must be going into web development work. I always love questions about sorting algorithims when I interview for web dev jobs.

me
Monday, August 16, 2004

I hope you are extremely self-motivated. There's nothing like mounting student loan debt and nagging parents to light a fire under your ass to understand recursion.
You can learn all the things that people learn in uni through books, it's just that finding themotivation to truly understand it can be a problem. It's just too easy to breeze over stuff and not really understand it when there is no direct consequence.

Natty
Monday, August 16, 2004

+++It's just too easy to breeze over stuff and not really understand it when there is no direct consequence.
+++

I've actually found this to be a blessing.  I usually burn through a book, absorbing all that I can from it, and then start putting what I can into practice.  If I come across a chapter that bogs me down, REALLY stumps me, I skip it.  It doesn't generally prevent me from comprehending the remainder of the material, and I don't get bogged down (or failed out of a class) for lacking the ability to absorb a concept RIGHT THEN AND THERE.

Usually after a few months of using a technology in practice, I'll go back to that really difficult chapter (usually because it'll come up in a project and I'll need it), and I'll blow right through it because the rest of the material has concreted in my mind.

Everybody learns differently.  Traditional curriculae (sp?) don't account for this well.

muppet
Monday, August 16, 2004

Agreed, muppet, everyone learns differently. For instance, I don't think I ever listened to an entire lecture in any of my comp sci classes. I don't learn well by listening, so I'd take my textbook to class and take notes from the recommended reading for that week.

In my case, I needed the whole 'forced learning' concept to motivate me to learn. For me, the key to comp sci and math related learning is doing a little bit every day. The university environment faciliated that for me, even if I didn't learn the 'traditional' way.

Natty
Monday, August 16, 2004

Obviously, everyone is different . . . must know thyself before knowing anything else.

But, just look at the good ol' law of averages:
"Most people with an education tend to make just a little bit more than those without."

But, we're in the good ol' USA ... if you work hard, it comes back to you. Usually, though, if you have an education; you don't have to work as hard.  :P

Anon
Monday, August 16, 2004

Muppet wrote:
>If I come across a chapter that bogs me down, REALLY
>stumps me, I skip it.

Interesting. I'm just the opposite: when I come across a chapter that stumps me, I know I'm onto something good. So I buckle down and really try to figure out what's going on.

This characteristic (personality flaw?) may be what led me into getting a degree in mathematics. :)

Michael Eisenberg
Monday, August 16, 2004

Well, I don't skip it for life, just for the moment  Like you, I've had times where I've simply beat my head against a concept until it sinks in, but I find that when I do that, I have trouble visualizing that concept from then on.  If I simply skip it, and come back later when perhaps my neurons are all in the correct alignment for that specific item, I usually absorb it easily on the second attempt and thereafter I'm able to use it fluently.

muppet
Monday, August 16, 2004

Sorry, I have to do this.  Bill Gates dropped out of Harvard... but that means he got in and was attending Harvard.  It's a little different if you drop out of High School (unless you're the Woz).

devinmoore.com
Monday, August 16, 2004

devin -

It's only different in that Bill Gates had an accredited institution acknowlege his ability to gain admittance.  In the grand scheme of things, that really isn't much.

muppet
Monday, August 16, 2004

"How long should I plan to learn basic algorithms for searching & sorting (basically what's typically teached in a BSs of CS) "

As I recall it was maybe one or two lectures, a very small part of the program of study.

Implementing a quicksort from scratch is probably worth the exercise. But I doubt you'll ever really need to implement a search or sort, because they're built into every library in every language.

Tom H
Monday, August 16, 2004

> As for not being proud of your college career?  Why not? 
> Your education is not inextricably entwined with the
> established system.

A diploma (from a decent univeristy) is much more than a list of books you studied (on your own).

Bill Gates is an exception. He had a vision, and he dropped out to focus all his energy on that vision. You don't see too many Bill Gateses running around, do you?

You do need lots of motivation and lots of experience. Can you work for free while you build up the experience (and the knowledge)?  Kinda like an unpaid internship (which really should be illegal but somehow fell through the cracks)

Yoda
Monday, August 16, 2004


Sedgewick has a really good intro to data structures book. Knuth is the bible of sorting and searching. You also need to learn OS internals -- not Windows internals, but OS internals such as paging strategies, virtual memory systems, how file systems work. The Aho compiler book (the Dragon Book) is the best compiler reference. Finite automata and discrete logic are also requisites to understanding CS to the level of a BS degree.

Depends on what you want, whether you want an education or a trade. Both are perfectly reasonable goals. But if you are not proud of dropping out, you probably want an education. Take night classes as you can afford them, or find an employer who offers tuition reimbursement. Don't cut your career short just because of money issues (if that's what your situation is)...

PS: Don't get me started on Gates. He got into Harvard because his parents got into Harvard. He dropped out because he lied to IBM and needed to deliver vaporware. Hardly a paragon of academic excellence. (And I don't care how much money he has.)

Jeff Kotula
Monday, August 16, 2004

"Delivering vapourware" is an oxymoron. Also, Bill Gates tried to point IBM in Intergalatic Digital Research's direction for their operating system requirement on more than one occasion.

John Topley (www.johntopley.com)
Monday, August 16, 2004

I remember learning to do bubble sort in BASIC. If nothing else, it demonstrates using the language to accomplish something useful.

On the surface that may not sound like much, but I've seen CS grads who simply cannot translate problems and solutions into code.

They knew the syntax, keywords, functions, MFC, or whatever, but they had no idea or clue of how to apply that knowledge to a real problem. How they got through labs, I can only guess.

?
Monday, August 16, 2004

Ok muppet, I'm going to call you on it. 

Explain tail recursion and why it is beneficial to write recursive functions using tail recursion.

Also explain the drawbacks of recursion.

You talk a big talk.  Let's see the goods.

christopher (baus.net)
Monday, August 16, 2004

Christopher -

I've no idea what you're talking about, firstly.  I have a basic understanding of recursion and the fact that poorly coded recursion can lead to infinite loop errors.  Aside from that, I really don't give a damn.  What has this to do with my ability to do my job?  Apparently, nothing, because I'm raking in good money programming professionally.  Burns, huh?

muppet
Monday, August 16, 2004

Jeff, you're a decade too late for the dig at Billlg on that one. He had written a BASIC interpreter for the Altair. The only thing missing was a loader which he and Allen wrote on the plane to ABQ.

BASIC in 4k. Was pretty amazing.

He may have got into Harvard because of his legacy, but he earned his first millions the hard way.

Miles Archer
Monday, August 16, 2004

> Burns
No it doesn't. 

You sit here claiming over and over that a strict CS education is useless which is utter bullshit.  A CS background ensures that you have a solid understanding the underpinnings of computing.  If you approach this in a less than systematic way you are going miss something.  If don't go through a program you are going to need a serious dose of discipline, which it is you obviously don't have.  I know people who have done this, but believe me they are a hell of a lot smarter than you.

If you don’t understand the drawbacks of recursion, you are going to use with out any consideration in how it might fail.  This is a bad thing.  If you don’t understand this you aren’t the kind of person I would want to work with.  In fact I would use this question to weed your ass out of an interview.  Then you would complain that us “educated” folks are a bunch of self righteous assholes.  Well take a hard look in the mirror.

Based on your post frequency you don't do shit, and you probably understand less.  You are convincing me to stop reading this board.  You post on every thread, and you rarely add anything useful.

christopher (baus.net)
Monday, August 16, 2004

Well in that case, let's just compare dicks.

muppet
Monday, August 16, 2004

> What has this to do with my ability to do my job? 
> Apparently, nothing, because I'm raking in good money
> programming professionally

As an aside from the university education issue, I'd just like to point out that how much you make has absolutely nothing to do with how good you are at your job.  We all know plenty of overpaid morons...

Personally, I'm also a college drop out.  At the time, I felt that the system wasn't teaching me anything of real value -- I was learning lots of concepts, but very little application (and looking down the road, it wasn't going to get any better).  Perhaps it was just the particular school I was at, but it just wasn't doing it for me.

Now that I've had a couple of years in the "real world," I do want to go back and learn all those concepts.  I feel I've picked up the knowledge I required to be able to appreciate what real CS is about (the study of computing theory, not just shoving database records into UI forms to pay the rent/mortgage).  That's the difference between a Computer Programmer, and a Computer Scientist...

Joe
Monday, August 16, 2004

If the study of computing theory isn't paying my bills, why do I need it?  That said, a smart developer will figure out much of what you learn in CS (if not all of it) on his own over time.  CS is for people who don't take natively to programming.  Anyway  I'm fairly certain I said that already so I suppose I'm done.

muppet
Monday, August 16, 2004

Jeff Kotula speaks sooth: Aho, HopCroft+Ullman and Knuth Vol 3 are rightly very well respected and authoritive works -A/H/U is particularly heavy going, Knuth is just genius.

If you want to take up Tom H's suggestion to Quicksort, grab a copy of  Kernighan+Plaugher "Software Tools"  (Addison-Wesley, 1976) or "Software Tools in Pascal" (Addison-Wesley, 1981) handling sorting, text patterns, editing, macros etc at a practical level and is easily the most-thumbed text I have.

There are later texts (all this work was done in the '70s) but you did ask about basic algorithms.

I think it's essential that coders know the basics so they:
don't assume a slow algorithm can always be cured by bigger, faster equipment, 
don't use crappy libraries,
don't try to replicate a remote database by serializing XML table images through a WAN
don't assume everything is done in VBA.

Best way to learn is to complete a small project incorporating a database and a remote client. The real trick is to know what to build and what to buy, but you have to know the basics to do either with any degree of confidence.

trollop
Monday, August 16, 2004

Newbie,

You can learn some good stuff about basic algorithms pretty quickly (a few days) assuming you have sound programming skills.

Try this:
1.
Implement a basic sort function in your favourite programming language.  It doesn't have to be too generic, but it should be able to sort an arbitrarily sized list/array of integers.
For this first sort implemenation try making the algorithm up yourself - don't reference any textbooks.  Forget about efficiency and concentrate on correctness and simplicity.

2. Do some timings of your sort function for short and longish sets of random numbers.

3. Look at a textbook or website.  Figure out the name of your sort and its performance characteristics.

4. Understand and implement one of the following: quicksort/mergesort/heapsort.  Compare timings to your original sort.

If you have a passion for programming the above will be fun and you will learn a lot from it.

cheers,
Peter

Peter M
Monday, August 16, 2004

Since the standard libraries include searching and sorting, it's more important to know how to use them. For example, make sure you understand order-N notation, and why searching for an element in a linked list takes O(N) time.

I'm surprised how many people I interview who don't know that stuff. It's not essential, but it helps you write efficient code.

Julian
Monday, August 16, 2004

Christopher, in fairness he's probably not using a compiler that does tail-call optimization.  He's probably used to consuming the same amount of stack space either way.

Kalani
Monday, August 16, 2004

Here's some books I think are nice. As usual, I don't want people to think they must part with any needed cash for these things, just I would've liked someone to tell me about them.

Imperative searching+sorting:
- Bentley, Programming Pearls.
- Aho/etc, Design and Analysis of Computer Algorithms.
Aho's book is much slimmer than CLR and Knuth. I think it's a clearer intro. Bentley's book is entertainingly written, and IIRC it tries to get one into the right mindset.

Computation:
- Minsky, Computation: Finite and Infinite Machines.
Context-free grammars aren't covered too much here; it's an old book and he just said something to the effect of, "Hey, this Chomsky guy's doing interesting work here..." But it's covered everywhere else, including in AIMA which I mention below. I think in comparison, Sipser and Hopcroft/Ullman aren't too fun. Then again, they're in print. ;)

Search:
- Russell/Norvig, AIMA.
I'm not going to spend a long time arguing that AI isn't the kiss of death. ;) There's such a huge bias against AI. I think this book is worth eyeballing for a sec to see whether it speaks to you.

Tayssir John Gabbour
Tuesday, August 17, 2004

Bruno R. Preiss has made an excellent (and very comprehensive) book on the subject available online.

It is available in Java, C++, C# and Python flavours:

http://www.brpreiss.com/books/opus4/

Ged Byrne
Tuesday, August 17, 2004

+CS is for people who don't take natively to programming.+

That's just plain wrong. People come to this career from many different walks of life. Just like it's wrong to assume that people without a formal CS education aren't competent.
I was programming in BASICA when I was 8 years old and have a CS degree.

Natty
Tuesday, August 17, 2004

> If the study of computing theory isn't paying my bills,
> why do I need it?  That said, a smart developer will
> figure out much of what you learn in CS (if not all of it) on
> his own over time.  CS is for people who don't take
> natively to programming. 

That actually wasn't intended as a dig on you muppet, but since this thread doesn't seem to have died yet...

You don't need computing theory.  If you want to be a programmer, then be a programmer.  But don't whine to me when all the database font-end coding jobs at small to medium size firms have been outsourced to foreign countries.

There are many people in the BSCS program who don't really "get it."  But these aren't the people the program is intended for, and I know just as many programmers without CS degrees who don't get it either.  Bottom line is, even a smart developer isn't going to just "figure out" how to write an OS kernel, compiler, RDBMS, or 3D rendering engine on their own (not one worth using, anyway).  I'm sure there are exceptions to that for extreme geniuses and people who have years to tinker with building such things, but in 99.99% of cases...

Whether you teach yourself from the book, or someone else teaches you from the book, you still need to pick up the book (or the open source code, or whatever) and learn it.  If I'm going to go to the trouble, then I'd at least like the nod of approval from the accredited institution...

Personally, my motivation is that I'm getting bored with writing those bread'n'butter DB apps and web sites.  Yes, you can get plenty of work without a degree.  If that's your goal, great, go for it.  But don't expect to be writing anything particularly cutting edge or revolutionary, unless you happen to be one of those incredibly motivated geniuses who falls into the afore mentioned 0.01%.

So I argue that CS isn't for people who don't get it, but rather for people who actually have interest in CS topics that go beyond typical day to day line-of-business applications.

Joe
Tuesday, August 17, 2004

+++That's just plain wrong. People come to this career from many different walks of life. Just like it's wrong to assume that people without a formal CS education aren't competent.
I was programming in BASICA when I was 8 years old and have a CS degree.+++

So what's your point?  I still say those who can't, get trained.  I was programming in BASIC 2.0 on my Commodore 64 when I was 8 years old, and I don't have a CS degree.

muppet
Tuesday, August 17, 2004

If you can't see the point in my post, which was stated plainly, then there's no point in arguing with you. It's obviously not going to cure your little-man syndrome.

Natty
Wednesday, August 18, 2004

I think you're projecting, Natty.  I saw the sophmoric point in your post "I'm a native programmer but I did a CS program".  Good for you!  Kudos!  You probably didn't need it.  Others do because they're not programmers deep down in their marrow.  Your point is accessory to the discussion and really has nothing to do with it.  "Republicans can be black men."  Absolutely!  So?

muppet
Wednesday, August 18, 2004

Really? Thought you had to have a penis to be a little man. Guess I've learned something new today.

Nice backpedal though, as IF you weren't implying that ALL CS degree holders don't 'get it' naturally. Obviously you didn't catch the 'little man' implication in my 'sophmoric' post.

Natty
Wednesday, August 18, 2004

How did I imply that, again?  I said CS degrees are for people who don't 'get it'.  I did not say that people with CS degrees must necessarily not 'get it'.  One is a subset of the other, but it doesn't work backwards.  With your logic skills, it's a wonder if you're a programmer at all.

And no, you don't need a penis to suffer from "little man" syndrome.  You just need an acute self esteem problem, like you seem to have with your petty insults in lieu of actual argument.

muppet
Wednesday, August 18, 2004

And another thread dies of muppetitis... inflammation of the muppet.

Programming a C-64 at eight years old hey? How old does that make you?

Aussie Bloke
Thursday, August 19, 2004

*  Recent Topics

*  Fog Creek Home