Algorithms, Part I: Kevin Wayne and Robert Sedgewick | Hacker News Reader

Algorithms, Part I: Kevin Wayne and Robert Sedgewick

coursera.org

109 pointscarlosgg33 comments

I'm glad to see more classes like this come online. I think its a bit of a shame that the material (of the book) focuses so much on Java, however. The algorithms classes I took in college focused a lot on math, logic and proofs. It took me a long time to understand exactly why; I thought we'd be learning L1 cache hacks and register tricks in Assembly or C. But the technology used to implement the algorithms changes a lot faster than the algorithms themselves, and the details of the best optimizations are different for just about every language. I now think it's far more important to have a solid grounding in problem decomposition and theory than it is to understand the intricacies of efficient algorithm designs for a specific language.

If you feel like I do, there are two books in particular that come to mind in that their content transcends the normal teaching curriculum and they both force you to think long and hard about how the authors came up with these fantastic little optimizations. I personally learned a lot from trying to reconstruct the thought process that must have led up to some of the algorithms implemented therein.

The first book is called Pearls of Functional Algorithm Design, and while it focuses on implementation in Haskell, you don't need to be a functional programming expert to get a lot out of the book.

The second book is called Foundations of Multidimensional and Metric Data Structures, and while the name might scare some away, it has a lot of interesting algorithms and accompanying research paper references so you can go off and explore. It took me several years to make my way through it completely, but I have gained a much better understanding of algorithms (and data structures!) that deal with more complex topics (such as computer vision).

There's one book I'd like to call out, as well. Introduction to Algorithms could be so much better than it is. It has all the right ingredients for a fantastic introduction to algorithms, but the way its written had most people in my algorithms class, myself included, bored beyond belief.

Just my 2 cents.

"the material (of the book) focuses so much on Java,"

This isn't really true. There is one section of the book (section 2 in Chapter 1 iirc) that details the minimalistic subset of java used, and there are a total of four interfaces used in the book (Comparable, Comparator, Iterable, Iterator) and each is explained very clearly. The code uses no inheritance, no fancy types, no design patterns. Input and Output are abstracted away by author provided classes with the minimal methods required to read in and write out strings, ints etc (vs struggling with BufferedOutputStreams or whatever in mainstream java).

In other words, Java is used as a very minimalistic pseudocode. (e.g http://algs4.cs.princeton.edu/11model/Shuffle.java.html). It is almost python like.

A simple imperative language is best to learn the basics of algorithms in. You can't appreciate functional datastructures before you thoroughly understand imperative ones..

Something like SML may have been better, but the minimal 'loops + classes-as-structs-and-no-java-heavy-machinery' approach in the book works fine. There are certainly valid criticisms of the book to be made, but an 'excessive focus on Java' is not one of them imo (and I don't even like Java fwiw).

PS: Thank You for your book reccommendations. The "Metric Data Structures" book looks really interesting. Ordered.

Seeing some comments about Java...

I'm taking this course right now (just finished the first "percolator" assignment this afternoon!). I've never used Java before this, but getting Eclipse up and running with "Hello World" was easy. Eclipse took a little exploring to get used to, but the C-like syntax of Java makes the language very easy to pick up.

If interested in this material, but turned off because you can't use your favorite language: take this as an opportunity to step outside of your comfort zone. That's what I'm doing. It's character building.

Sedgewick's tone/approach is very natural. He says things in terms of "this is what we know," sometimes implying that the subject is not as settled as it appears. This in contrast to professors that just go through the motions of "this is X, this is Y, quiz on Friday."

I found the video lectures for this course extraordinarily boring compared to the Stanford algorithms courses taught by Roughgarden. Sedgewick is a brilliant computer scientist, but those videos really put me to sleep.

Both classes are still solid offerings from Coursera, but having gone through both levels of both, I'd recommend the Stanford ones first.

Also, I don't know if this has changed, but the programming assignments required a custom Java installation provided by Princeton with a bunch of extra packages specifically for the course. I found that a little weird compared to the Stanford class's approach of just giving you an input file and verifying the output provide (ala a coding competition).

There is no "custom Java installation" required, although they do offer one (called "DrJava") to get people up and running quickly and presumably to make support easier. I used IDEA and it worked just fine.

They do require one JAR file, stdlib.jar, to handle things like file I/O that are boring and take away from the algorithms themselves.

There is a second JAR, algs4.jar that contains all of the completed classes, which is useful if you want to implement one particular algorithm yourself, without going back and implementing the others that it relies on.

> I found the video lectures for this course extraordinarily boring compared to the Stanford algorithms courses taught by Roughgarden. Sedgewick is a brilliant computer scientist, but those videos really put me to sleep.

At the risk of sounding overly negative when it's not intended: they're both very boring lecturers. I actually wonder if that might change a bit when they're interacting with a real audience.

Having actually been in Sedgewick's lectures, I can confirm that his soothing slow monotone is more effective than Nyquil for lulling students to sleep. That said, his course is damn excellent, and I know of no other teachers that have done better at making a course that actually teaches comp sci fundamentals in an approachable way. He's very understandable and clear even when played at 1.5x speed, which I recommend to anyone who isn't having trouble thinking through the concepts faster than he can lecture through them.

it's the grandfatherly tone...

for me it was the other way around :) I felt Roughgarden was skimming through the lessons..Sedgewick ,in my opnion is the better teacher

On the contrary, I found Sedgewick's lectures very interesting. The animations of algorithms using cards, trees, nodes etc. is an excellent way to get a good grasp. It is a solid representation of what you would imagine in your mind while learning algorithms.

Another particularly interesting thing about his lectures is when he shares some stories from his vast experience over the years. For eg. When they named a red-black BST after the best contrasting colours you could get on the first ever color printer built in Xerox PARC. Or his excitement to build an animation for Prim's MST on a personal computer.

Came here to say the same thing, I thought he explained things well and in different ways then I had learned them in the past.

I believe Java is chosen for its popularity and its static typing, which helps the learner gain a better understanding of the algorithm at play than a duck-typed language would. It is even better to learn algorithms in C, where one has to work directly with the memory trade-offs. But learning these algorithms in Java is certainly more effective than learning them in Python, Ruby, etc.

I know some (most?) of you reading HN saw this last week, but remember that you can use Coursera-dl[1] to download the material for offline reference.

[1]: https://github.com/dgorissen/coursera-dl

I just tried it, did not work :(. Says failed to authenticate as username. I tried it on Saturday and it worked ok. Maybe they are blocking it?

It's working for me ... this was a godsend! Thanks a lot!

When was the last time you tried it?

Not working for me too with the same error.

Noticed the issue raised ( probably by you? ) - https://github.com/dgorissen/coursera-dl/issues/81

Edit: Tried this one ( https://github.com/jplehmann/coursera ) and it too failed for login.

Yes that was me. I hope Coursera has not blocked it somehow...I think the dgorissen implementation is based on the other one, so not surprising the other one doesn't work either.

Are you running Firefox at the same time as the script? :)

https://github.com/dgorissen/coursera-dl/issues/81

I took this class in Princeton - COS226 http://www.cs.princeton.edu/courses/archive/spring13/cos226/...

It was easily one of my favorite classes. It's very straightforward and the lecture slides are great. I highly recommend flipping through them.

Signed up. I've been developing online education software for a few years now, and never actually used any. And like many self-taught, working programmers, I'm very weak on algorithms. So I'm excited.

Side note, am I the only person on earth who whitelists cookies? With cookies blocked, every page on coursera.org, including the home page shows nothing but the word "loading" and a spinning gif. Blogger was like that for a while, except they had gears. Sure, you need cookies to log in, and sure, they're used for analytics, and sure, you can do some progressive enhancements if I come back. I guess I'm old fashioned, but I'm at a loss to understand how the failure to get cookies back from a first-time visitor can stop all content from "loading," including the template. Must be a framework thing.

Great, but I hope it doesn't follow the book...

"Algorithms in C" by Sedgewick is a great book, which uses C to implement the algorithms talked about in the book. "Algorithms" also by Sedgewick, which looks like this course is based on, spends a hell of a lot of time teaching you Java!

I've just done the first week's lectures and exercises. They assume you know Java, but if you don't you're pointed in the right direction for suitable resources.

It look substantially similar to COS 226 at Princeton, also taught by Kevin Wayne, which uses this textbook: http://algs4.cs.princeton.edu/home/

Yes, that's the textbook for this course.

If that's the case, there's an unhealthy amount of basic Java in the text, but it's still a very good course.

I took one of the previous offerings of the course, and they assume that you know Java. The programming assignments start on week 1 with "real algorithm" work, there's no time wasted introducing you to Java or anything like that.

I watched the video (but didn't take part in the class assignments) last spring, and I want to paraphrase an important remark by prof Sedgewick that really struck a chord in my mind:

> Though we have faster computers, algorithms remain absolutely essential in our field, because the amount of data that we process is greater than ever before.

It was nice to hear someone in a position of authority clearly explain why this field of research is important. It also helps understand why he prefers tilde notation to big-theta notation; the former takes into account the constant factor of the fastest growing term, thus allowing us to compare different implementations that are all O(n^2) in theory.

This looks great, but I'm not so keen on getting into Java at this point. Has anyone taken this, and if so would it be feasible for someone from a Ruby/Python background to grok what they're getting at?

I took this last time (for the first few weeks). It is a very applied course. The autograder for the exercises is terrific, it will pinpoint the space time complexity of individual parts of your program so you can fine tune your data structures and algorithms. The whole setup is java based. IMHO, the course is far less valuable if you don't do the exercises. If you want theory oriented courses the Stanford ones (Tim Roughgarden) are more to your liking. The exercises for that course are in any language of your choice.

Excellent reply, exactly what I was looking for. Thanks very much!

"If I have not programmed before, can I still take the course?"

"Probably not."

much appreciated (I can code, but I was hunting around for some coding courseras for a friend who has expressed interest in learning)

Reply on news.ycombinator.com