Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

CS 168: The Modern Algorithmic Toolbox

web.stanford.edu

Post reply on HN
Print view View original

61–70 of 101 posts

Re: CS 168: The Modern Algorithmic Toolbox

#61

Post by UmbertoNoEco »

melling wrote: post #45
t_mann wrote: post #25

Earlier quoted context omitted.

> (i) ideas that are non-obvious , even to the well-trained computer scientist > In the first lesson, they discuss consistent hashing, and they seem to have achieved their goals. I was really excited when I read your comment here before clicking the link, but having had a look at the rest of the curriculum, I'm slightly underwhelmed. - Generalization ... Empirical risk minimization. - lossy compression - Similarity S…

All those topics are unimpressive? I’ve spent quite a bit of time trying to teach myself them. I’ve seen several Stanford courses (e.g CS229) so the low course number of 168 would seem to indicate that it’s taken within the first couple years of college.

they are not; this is classic hn posturing

at the veryleast this would belong to a second or third class of algorithms for ug( after the usual meat and potatoes: big,small o notation, searching and sorting, dp, greedy algorithms and so on) depending on the difficulty of the assignments this could be easily a graduate course

remember that no matter how difficult, obscure or new a technical field is you will have people here claiming they took a class about it as a freshman 10 years ago and they wrote some papers about it. sometimes it may be true, but most of the time it isnt

Re: CS 168: The Modern Algorithmic Toolbox

#63

Post by tasty_freeze »

afroisalreadyin wrote: post #14

Crickey, what an exciting syllabus. What I would give to be a full-time student again and study stuff like this without any distractions.

Even when I was a student and loved a particular class, there was the constant distraction of having to attend and do homework for four or five other classes.

Re: CS 168: The Modern Algorithmic Toolbox

#64

Post by noelwelsh »

zamfi wrote: post #15
noelwelsh wrote: post #13

Earlier quoted context omitted.

Here's an example: The web is a graph. Each node in the graph is a web page. Each edge is a connection a hyperlink between pages. You can represent a graph as a matrix. If you random click on links you'll end up visiting some web pages (the more connected ones) more often than others. You can define a probability distribution over pages as "what is the probability I'll end up at this web page after an infinite number…

...or, you could just 1) use the raw count of inbound links, weighted by the count of inbound links of the linking pages, normalize by the total number of links on that page, and run it a few iterations to get a first approximation of the probability distribution. This is a pretty intuitive approach, would almost certainly have been good enough for Google, and avoids all the jargon, probability, and "well studied alg…

0. Why so anti-intellectual?

1. The algorithm you're attempting to describe in 1) above is either exactly PageRank or an approximation to it, so I don't get the point you're trying to make.

2. The point of jargon and well studied algorithms is that you can recognize when your problem is a problem someone else has already tackled. In the specific case of PageRank, if you recognise it's an eigenvalue problem you can

1) Find efficient algorithms to implement it. In the case of PageRank there is a matrix factorization that can make the algorithm much faster.

2) Find convergence bounds for appoximate solutions such as the power method, so you can appropriately tradeoff compute time versus accuracy.

3) Find numerical techniques to avoid calculating a matrix full of NaNs.

4) Benefit from the decades of work in optimizing numerical linear algebra.

3. When Google was first released it was clearly significantly better than the competition (mostly AltaVista). I assume that was due to PageRank. I wouldn't be surprised if PageRank is much less important to Google now, but to get this point it had to have that initial advantage.

Re: CS 168: The Modern Algorithmic Toolbox

#65

Post by sawyna »

t_mann wrote: post #38
giantg2 wrote: post #33

It would be cool to be an expert at algorithms, apply them to hard problems, and build cool things. I feel like, for me, there's no point in learning them since the work I get is always "put a button here, update the DB" type stuff.

try a side project? when I think of fun ideas, I always notice how easy it is to bump into computationally hard or complicated stats/ML/math problems left and right, even if it's just a simple game. I remember one time when I realized this: a TV show character suggested building an app that lets you take a picture of someone's shoes and then give you links where you could buy them. It sounded a) like a pretty good bu…

I suppose even then you'd use a library which solves the problem rather than figure out and build the entire thing yourself.

I do agree that algorithms are fun and the basic ones are probably useful in everyday work, but for anything complicated you'd rather use a proper library. It's also definitely good to have knowledge of their internal workings though.

Re: CS 168: The Modern Algorithmic Toolbox

#66

Post by noelwelsh »

anonymoushn wrote: post #36
noelwelsh wrote: post #10

Earlier quoted context omitted.

The problem with accounting for hardware, is which hardware do you account for? If you really want to get into the performance optimization weeds you end up relying on e.g. specific characteristics of a vendor's CPU. The Mechanical Sympathy blog had posts that do this, and the problem with this is it doesn't generalize. Hardware changes (e.g. SSDs have different performance characteristics compared to spinning disks)…

Rather than insisting on things that generalize with no additional work, it may be useful to use a certain modern architecture as a target for learning techniques and then rely on the wetware to generalize.

Thinking about it more, Daniel Lemire publishes very applied algorithmic stuff: https://lemire.me/en/#publications

A lot of his work is in the journal "Experimental Algorithmics", so I guess there are a substantial number of people working in this way. I don't know this field very well, and I don't know if there are general principles that have been extracted from their work.

Re: CS 168: The Modern Algorithmic Toolbox

#67

Post by dunefox »

alex_suzuki wrote: post #42
afroisalreadyin wrote: post #14

Crickey, what an exciting syllabus. What I would give to be a full-time student again and study stuff like this without any distractions.

You and me both! Especially the “without any distractions” part.

And the ability to focus.

Re: CS 168: The Modern Algorithmic Toolbox

#68

Post by jointpdf »

VMLS by Stephen Boyd (also of Stanford) would be great background reading for the vector/matrix stuff (i.e. most of this course): https://news.ycombinator.com/item?id=18678314

I love this book. As opposed to the way that linear algebra is typically introduced, this book focuses on concrete applications (like text analysis, image/signal processing, finance, ML, etc.) and eschews more arcane concepts (like eigen). To me, building practical intuition is the best way to learn* the subject.

A more advanced but still accessible manuscript by Boyd et al: Generalized Low Rank Models (establishes connections between PCA/SVD and many other matrix factorization methods, and shows you how to roll your own): https://web.stanford.edu/~boyd/papers/pdf/glrm.pdf

Re: CS 168: The Modern Algorithmic Toolbox

#69

Post by shuckles »

v3gas wrote: post #27
t_mann wrote: post #25

Earlier quoted context omitted.

> (i) ideas that are non-obvious , even to the well-trained computer scientist > In the first lesson, they discuss consistent hashing, and they seem to have achieved their goals. I was really excited when I read your comment here before clicking the link, but having had a look at the rest of the curriculum, I'm slightly underwhelmed. - Generalization ... Empirical risk minimization. - lossy compression - Similarity S…

Guessing from the number (168), probably second year? So not too basic if that's what you're implying

The Stanford CS curriculum only distinguishes on the first digit: 1XX for undergrads and 2XX and above for graduate students. (Undergrads often take one or more graduate courses as they progress.)

Most taking this course are advanced 2nd year or 3rd or 4th year students who have taken the introduction to algorithms course. Most/many CS majors never take this class at all.

Re: CS 168: The Modern Algorithmic Toolbox

#70

Post by [deleted] »

jointpdf wrote: post #68

VMLS by Stephen Boyd (also of Stanford) would be great background reading for the vector/matrix stuff (i.e. most of this course): https://news.ycombinator.com/item?id=18678314 I love this book. As opposed to the way that linear algebra is typically introduced, this book focuses on concrete applications (like text analysis, image/signal processing, finance, ML, etc.) and eschews more arcane concepts (like eigen ). To…

[deleted]
Post reply on HN