▲ 589 points
back
99 comments
Very neat. They write:
> In this course, we’ll be looking for the following trifecta: (i) ideas that are non-obvious, even to the well-trained computer scientist, so that we’re not wasting your time; (ii) conceptually simple — realistically, these are the only ideas that you might remember a year or more from now, when you’re a start-up founder, senior software engineer, PhD student, etc. (iii) fundamental, meaning that there is some chance that the idea will prove useful to you in the future.
In the first lesson, they discuss consistent hashing, and they seem to have achieved their goals.
ETA: Must include this anecdote on the history of the algorithm:
1. 1997: The implementation of consistent hashing given in this lecture first appeared in a research paper in STOC (“Symposium on the Theory of Computing”) [...] Ironically, the paper had previously been rejected from a theoretical computer science conference because at least one reviewer felt that “it had no hope of being practical.”
2. 1998: Akamai is founded.
3. March 31, 1999: A trailer for “Star Wars: The Phantom Menace” is released online, with Apple the exclusive official distributor. apple.com goes down almost immediately due to the overwhelming number of download requests. For a good part of the day, the only place to watch (an unauthorized copy?) of the trailer is via Akamai’s Web caches. This put Akamai on the map.
4. April 1, 1999: Steve Jobs, having noticed Akamai’s performance the day before, calls Akamai’s President Paul Sagan to talk. Sagan hangs up on Jobs, thinking it’s an April Fool’s prank by one of the co-founders, Danny Lewin or Tom Leighton.
Here’s one explanation of Consistent Hashing by a popular author that just started a systems design YouTube channel:
I love this channel, I've been watching their videos for a few weeks. The guy has a great ability to break things down and explain complex topics with ease.
I don’t understand the connection between 1 and 2.
What happened to the relationship between Apple and Akamai?
> (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 Search. (Dis)similarity metrics: Jaccard, Euclidean, Lp....
- Regularization. The polynomial embedding and random projection, L2 regularization, and L1 regularization as a computationally tractable surrogate for L0 regularization.
- Understanding Principal Component Analysis (PCA). ... The simple geometry of "diagonals in disguise." The power iteration algorithm.
- Low-rank matrix approximations. The singular value decomposition (SVD), applications to matrix compression, de-noising, and matrix completion (i.e. recovering missing entries).
- Graphs as matrices and the Laplacian of a graph. Interpretations of the largest and smallest eigenvectors/eigenvalues of the Laplacian. Spectral embeddings. Interpretations of the second eigenvalue
- Markov Chains, stationary distributions. Markov Chain Monte Carlo (MCMC)
- Fourier methods
- Compressive sensing
- Linear and convex programming. Matrix completion
- Differential privacy
I was thinking that the vast majority of those topics should be pretty much standard knowledge for a mathematically trained computer scientist (not being an expert in each of them, but knowing the basics of what they do, how they work and where they're applied). What level is this course at?
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
Another excellent paper on the similarities between all those linear models is “ A Unifying Review of Linear Gaussian Models”
> Factor analysis, principal component analysis, mixtures of gaussian clusters, vector quantization, Kalman filter models, and hidden Markov models can all be unified as variations of unsupervised learning under a single basic generative model.
This seems like a good thread to mention the YouTube channel 'Reducible', it's like 3Blue1Brown for algorithms:
Looks really good.
Interesting to me is that a lot of the material you could also find in a theoretical machine learning course or in an applied mathematics course. Before seeing the syllabus I was expecting more on streaming algorithms, randomized algoriths, etc. In my experience most Computer Science students get a bit freaked out when, e.g., concentration inequalities enter the scene.
"Nothing I learned in CS has an application to industry programming" is a regular complaint in discussion on education here and elsewhere. This is a good course to point to for people who have this very limited view on CS.
>"Nothing I learned in CS has an application to industry programming" is a regular complaint in discussion on education here and elsewhere. This is a good course to point to for people who have this very limited view on CS.
> Lecture 11 (Mon 5/2): Graphs as matrices and the Laplacian of a graph. Interpretations of the largest and smallest eigenvectors/eigenvalues of the Laplacian. Spectral embeddings, and an overview of applications (e.g. graph coloring, spectral clustering.)
What industry fields does this apply to? Machine Learning?
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 of clicks". This is the stationary distribution of a Markov chain.
The stationary distribution is the largest eigenvector of the matrix that represents the graph. This gives a way to compute the stationary distribution via well studied algorithms.
You can use this idea to
1) assign importance to pages based on the magnitude of the probability, to improve web search. You might call this algorithm PageRank.
2) found a company called Google that is currently worth USDtrillions.
Photogrammetry & image processing, anything to do with dimension reduction (basically every field with real-world sensor data), ontology/semantic data processing...
In the lecture note 6 about regularization, section 3.4:
the l1 norm of a vector is simply the sum of the absolute values of the coordinates, and hence it
is continuous (and linear). I don't think that the l1 norm is linear since |x+y| # |x| + |y|.
They probably meant that it is positively homogeneous (i.e. |ax|=|a||x|), I would assume, since it's definitely not a linear function.
True. Norms are never linear since they cannot be negative.
agreed.
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.
I have been able to do some algorithmic work in my 4 decades (mostly lately for generative art) but most of my career was How So I Ship This Complicated App With Too Few People In So Little Time. This usually requires creative thinking and experience, but rarely requires advanced knowledge of many of the topics mentioned. I never had a CS education so I had to learn things myself, but it still makes sense to me today to understand complex topics; even if you never use them, being able to understand such things is a benefit to the complex things you will have to do.
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 business idea and b) crazy hard to build (the time the show aired was before the Deep Learning proliferation iirc).
I think this is the reality for the majority of software developers, although it's not to be underestimated because it's not just a one-off button, it ends up being dozens, hundreds of "simple" things like that. Keeping all of them up to date and consistent is where the challenge is in that regard, and not many people manage - in my experience, a lot of systems as you describe them are rewritten every 5-10 years.
I'm not someone that graduated college, but do my best to study independently.
I'm somewhat familiar with all of the topics (except privacy preservation), but I'm a bit surprised to see these all lumped together. They're all certainly useful, but they seem some what sparsely related.
Can someone tie together
- Probabilistic data structures & hashing
- PCA/SVD/Sampling/Compressed Sensing
- Privacy preservation
for me? They seem like they should be three independent courses.
For anyone interested in the PCA/SVD/Compressed Sensing - Steve Brunton[0] (prof at UW) has a youtube channel full of various lectures from vector calculus, pca, svd, dynamical systems, and more
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.
You and me both! Especially the “without any distractions” part.
> tHE TRue vAlue Of cOlleGE Is THE NEtwork NOT ThE COurSeS
Well clearly people haven't been taking courses as cool as this.
To answer your strawman, nah for me I got zero network from "college" but I enjoyed the education. Financially the biggest benefit is not getting rejected from jobs that require it.
Wish the videos were public too!
My (heretical?) opinion is that videos are a waste of time compared to text for the majority of content and the majority of people. There are some ideas that can be very nicely visualized and some people (e.g. dyslexics, non-native speakers) who struggle with text. For the rest I think text is better.
This is "mostly" maths for "big data" (aka statistical efficiency over huge set of data or "qsort-ized" algos) but kind of taught the wrong way: first you learn maths, then you code algos based on current hardware architecture.
I had a doubt when I did realize I could not find one of the most important topics of computer science: proof of accuracy of floating point computations.
I see this more like an index of a library of various algorithms, and that, I think it's good.
It’s an “algorithmic toolbox” in the sense of a set of algorithms you can use as tools, not a set of tools for building new algorithms.
Any good resources on floating point accuracy proofs/literature?
As you say, it’s an often ignored topic while coming up again and again in software engineering
> Zero hits for "hardware".
Are there algorithm courses that take into account how hardware affects algorithms? For example with databases, you have implement theoretically inefficient algorithms which are faster in practice (mostly because they use sequential access).
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) and you can even design hardware to efficiently implement particular algorithms.
That said, there are areas within algorithms that do look at optimizing for typical hardware. E.g. cache oblivious algorithms are designed to take advantage of caches as found in modern CPUs.
This Advanced Data Structure course [1] which, while not accounting for any particular hardware, had some interesting "cache-oblivious" algorithms (i.e. designed to make the best use of your cache no matter the cache sizes.) Is that the type of work you are thinking about?
This area is less mature than traditional algorithms work. It is the case that cache-friendliness and minimization of data dependency chains is a huge deal for hyper efficient modern algorithms but this hasn't been the case for too long so there is a less rich history of ideas to pull from.
This course is also more about solving problems in the first place rather than implementation efficiency.
Usually that lives in more applied courses, I guess partially because there is less useful theoretical treatment of that and the usually-taught tools don't really fit it. "A cache miss is 1000x slower" is just a constant factor after all ;)
ooh this looks nice. although teaching a course with such an emphasis on decomposition in 2022 that doesn't include vae/nn/transformers methods seems... behind the times?
The lecture notes appear at a skim to be good enough to not need the lectures so anyone can dip in.
This seems like a great course. What level is it? Is this a first year course at Stanford?
Approx 4th year CS.
It presupposes the basics of CS (such as hashing) and mathematics (such as some linear algebra). The prerequisites are CS107 (Computer Organization & Systems) and CS161 (Design and Analysis of Algorithms), which have prerequisites in turn.
The lecturers write:
> We welcome all comers — there’s a zillion courses you could be taking, and we’ll be happy and flattered if you decide to take this one. That said, to prepare a coherent lecture, it’s helpful to have a target audience in mind. We view the canonical student in the class as a senior-year computer science major. As you can see in this lecture, we assume a certain degree of “computer science maturity,” taking for granted that you know and care about concepts like caching, hashing, balanced search trees, and so on. We also assume sufficient programming maturity to translate the high-level descriptions given in lecture to working implementations.
> Our ambition is for this to be the coolest computer science course you’ve ever taken. Seriously!
Are the assignments linked somewhere? I couldn't find them
this is Za. wish my school had stanford level classes, im caught at a t20 research focused university that isn’t a industry pillar of CS (Cal, MIT, stanford), and they don’t seem motivated to update the classes to be challenging and relevant, just dated and unnecessarily difficult niche topics
No videos? WHat's the point of sharing?
How can you cover such a huge and diverse amount of material with any level of rigor?
I view this type of courses as pointless. There's not enough time to cover any problems or pitfalls.
Its a class for undergrads. Nothing can ever be explored in its full depth. If people want to spend an entire semester on a single problem they should take a grad course.
Do you have any one particular topic in mind you think isn't covered rigorously enough? If so, what's missing from it? That way someone can use "is that covered" as a heuristic for evaluating other resources in the future.
Cool!
+10 to Griffindor for that last lune