10 ms·

CS 168: The Modern Algorithmic Toolbox

589 points by samuel246 4y ago

buttery101 4y ago
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|.
- political12345 4y ago
  agreed.
- the_svd_doctor 4y ago
  True. Norms are never linear since they cannot be negative.
- fjkdlsjflkds 4y ago
  They probably meant that it is positively homogeneous (i.e. |ax|=|a||x|), I would assume, since it's definitely not a linear function.
vrnmh 4y ago
Wish the videos were public too!
- noelwelsh 4y ago
  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.
  - dspillett 4y ago
    I find videos terrible for learning on their own. But combined with taking notes, reviewing them after, and using them to kick off a bit of reading or (better) experimentation, they can be an invaluable part of the learning process. Much like traditional lectures, in fact.
  - BazookaMusic 4y ago
    I disagree strongly with this opinion. Videos and text can play different roles in the comprehension of ideas. My experience is that if I'm comfortable with a topic, text is far more effective as a medium to absorb knowledge from. For learning programming languages, for example, I've found it much more effective to read books that to sit for lectures or online videos. However, for topics like complex mathematics or algorithms, especially with dense terminology, text often appears like an impenetrable wall of text for me. Good video lectures help me see through the professor's thought process and divide the problem in smaller, more comprehensible parts. In my opinion, the strongest advantage of video content is that they include an element of guided attention. A good video can forcefully mute the secondary details and highlight the essence of a concept or process. I can see how you can spend hours on videos and not learn a lot though. After getting an insight from a video, the concepts need to be practiced through exercises, which is active as compared to passive watching, else the advantages are lost because the information can be easily forgotten.
  - layer8 4y ago
    I generally agree, but the video linked upthread was quite nice and compact: https://youtube.com/watch?v=UF9Iqmg94tk https://youtube.com/watch?v=UF9Iqmg94tk
oxff 4y ago
> 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).
- noelwelsh 4y ago
  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.
  - anonymoushn 4y ago
    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.
    - noelwelsh 4y ago
      Thinking about it more, Daniel Lemire publishes very applied algorithmic stuff: https://lemire.me/en/#publications 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.
- detaro 4y ago
  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 ;)
xer0x 4y ago
This seems like a great course. What level is it? Is this a first year course at Stanford?
- FabHK 4y ago
  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!
FabHK 4y ago
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.
- wodenokoto 4y ago
  I don’t understand the connection between 1 and 2. What happened to the relationship between Apple and Akamai?
  - FabHK 4y ago
    Sorry, I left something out. The authors mention earlier in the lecture that > [The algorithm (Consistent Hashing)] has real applications [and] gave birth to Akamai, which to this day is a major player in the Internet. [...] (Quantitatively, Akamai serves 10-30% of all internet traffic, and has a market cap ≈ $19B.) This makes the rejection notice so funny.
    - 4y ago
noelwelsh 4y ago
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.
- grog454 4y ago
  >"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?
  - noelwelsh 4y ago
    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.
    - 4y ago
afroisalreadyin 4y ago
Crickey, what an exciting syllabus. What I would give to be a full-time student again and study stuff like this without any distractions.
- tasty_freeze 4y ago
  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.
  - afroisalreadyin 4y ago
    Still much better than the current situation of 8 hour day job and family.
- alex_suzuki 4y ago
  You and me both! Especially the “without any distractions” part.
  - dunefox 4y ago
    And the ability to focus.
quickthrower2 4y ago
The lecture notes appear at a skim to be good enough to not need the lectures so anyone can dip in.
curiousgal 4y ago
> tHE TRue vAlue Of cOlleGE Is THE NEtwork NOT ThE COurSeS Well clearly people haven't been taking courses as cool as this.
- quickthrower2 4y ago
  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.
  - bestest 4y ago
    I got zeroes from both network and education. Either of them was boring. But my counter-strike and virus-writing skills bloomed!
Fr0styMatt88 4y ago
This seems like a good thread to mention the YouTube channel 'Reducible', it's like 3Blue1Brown for algorithms: https://www.youtube.com/c/Reducible https://www.youtube.com/c/Reducible
giantg2 4y ago
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.
- t_mann 4y ago
  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).
  - sawyna 4y ago
    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.
    - t_mann 4y ago
      with anything involving AI/ML, like the shoes-app, you'll likely still have to create or train a model to achieve exactly what you want it to do.
  - nnoitra 4y ago
    Is this now a trivial problem because of Deep Learning?
- coldcode 4y ago
  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.
oldgradstudent 4y ago
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.
- Qualadore 4y ago
  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.
  - oldgradstudent 4y ago
    One week (two lectures, one discussion, one homework) for Fourier transforms? Seriously? Having been a TA for a course with similar pretentions. Students will be miserable because they aren't given the tools to deal with the homework, they will learn very little, and forget it all very quickly
    - utopcell 4y ago
      Stanford has a course dedicated to FFT, which is available online [1]. [1] https://see.stanford.edu/course/ee261 https://see.stanford.edu/course/ee261
- UncleMeat 4y ago
  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.
  - oldgradstudent 4y ago
    Undergrads deserve rigor too. The course description is especially ironic as it claims rigor. > This course will provide a rigorous and hands-on introduction to the central ideas and algorithms that constitute the core of the modern algorithms toolkit. The result, of course, will be a bunch of undergrads with a very hazy recollection, and zero real knowledge.
a-dub 4y ago
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?
BubbleRings 4y ago
+10 to Griffindor for that last lune
sylware 4y ago
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.
- maayank 4y ago
  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
  - layer8 4y ago
    The general topic is called numerical analysis.
- layer8 4y ago
  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.
xmonkee 4y ago
Are the assignments linked somewhere? I couldn't find them
dev_0 4y ago
No videos? WHat's the point of sharing?
jointpdf 4y ago
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 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 https://web.stanford.edu/~boyd/papers/pdf/glrm.pdf
- deleted 4y ago
  [deleted]
- nuclearnice1 4y ago
  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. https://authors.library.caltech.edu/13697/1/ROWnc99.pdf https://authors.library.caltech.edu/13697/1/ROWnc99.pdf
chrsig 4y ago
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 [0] https://www.youtube.com/c/Eigensteve https://www.youtube.com/c/Eigensteve
nothrowaways 4y ago
Cool!
grubby 4y ago
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

589 points by samuel246 4y ago

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|.

political12345 4y ago
agreed.
the_svd_doctor 4y ago
True. Norms are never linear since they cannot be negative.
fjkdlsjflkds 4y ago
They probably meant that it is positively homogeneous (i.e. |ax|=|a||x|), I would assume, since it's definitely not a linear function.

vrnmh 4y ago

Wish the videos were public too!

noelwelsh 4y ago
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.
- dspillett 4y ago
  I find videos terrible for learning on their own. But combined with taking notes, reviewing them after, and using them to kick off a bit of reading or (better) experimentation, they can be an invaluable part of the learning process. Much like traditional lectures, in fact.
- BazookaMusic 4y ago
  I disagree strongly with this opinion. Videos and text can play different roles in the comprehension of ideas. My experience is that if I'm comfortable with a topic, text is far more effective as a medium to absorb knowledge from. For learning programming languages, for example, I've found it much more effective to read books that to sit for lectures or online videos. However, for topics like complex mathematics or algorithms, especially with dense terminology, text often appears like an impenetrable wall of text for me. Good video lectures help me see through the professor's thought process and divide the problem in smaller, more comprehensible parts. In my opinion, the strongest advantage of video content is that they include an element of guided attention. A good video can forcefully mute the secondary details and highlight the essence of a concept or process. I can see how you can spend hours on videos and not learn a lot though. After getting an insight from a video, the concepts need to be practiced through exercises, which is active as compared to passive watching, else the advantages are lost because the information can be easily forgotten.
- layer8 4y ago
  I generally agree, but the video linked upthread was quite nice and compact: https://youtube.com/watch?v=UF9Iqmg94tk https://youtube.com/watch?v=UF9Iqmg94tk

oxff 4y ago

> 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).

noelwelsh 4y ago
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.
- anonymoushn 4y ago
  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.
  - noelwelsh 4y ago
    Thinking about it more, Daniel Lemire publishes very applied algorithmic stuff: https://lemire.me/en/#publications 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.
detaro 4y ago
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 ;)

xer0x 4y ago

This seems like a great course. What level is it? Is this a first year course at Stanford?

FabHK 4y ago
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!

FabHK 4y ago

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.

wodenokoto 4y ago
I don’t understand the connection between 1 and 2. What happened to the relationship between Apple and Akamai?
- FabHK 4y ago
  Sorry, I left something out. The authors mention earlier in the lecture that > [The algorithm (Consistent Hashing)] has real applications [and] gave birth to Akamai, which to this day is a major player in the Internet. [...] (Quantitatively, Akamai serves 10-30% of all internet traffic, and has a market cap ≈ $19B.) This makes the rejection notice so funny.
  - 4y ago

noelwelsh 4y ago

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.

grog454 4y ago
>"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?
- noelwelsh 4y ago
  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.
  - 4y ago

afroisalreadyin 4y ago

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

tasty_freeze 4y ago
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.
- afroisalreadyin 4y ago
  Still much better than the current situation of 8 hour day job and family.
alex_suzuki 4y ago
You and me both! Especially the “without any distractions” part.
- dunefox 4y ago
  And the ability to focus.

quickthrower2 4y ago

The lecture notes appear at a skim to be good enough to not need the lectures so anyone can dip in.

curiousgal 4y ago

> tHE TRue vAlue Of cOlleGE Is THE NEtwork NOT ThE COurSeS Well clearly people haven't been taking courses as cool as this.

quickthrower2 4y ago
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.
- bestest 4y ago
  I got zeroes from both network and education. Either of them was boring. But my counter-strike and virus-writing skills bloomed!

Fr0styMatt88 4y ago

This seems like a good thread to mention the YouTube channel 'Reducible', it's like 3Blue1Brown for algorithms: https://www.youtube.com/c/Reducible https://www.youtube.com/c/Reducible

giantg2 4y ago

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.

t_mann 4y ago
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).
- sawyna 4y ago
  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.
  - t_mann 4y ago
    with anything involving AI/ML, like the shoes-app, you'll likely still have to create or train a model to achieve exactly what you want it to do.
- nnoitra 4y ago
  Is this now a trivial problem because of Deep Learning?
coldcode 4y ago
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.

oldgradstudent 4y ago

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.

Qualadore 4y ago
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.
- oldgradstudent 4y ago
  One week (two lectures, one discussion, one homework) for Fourier transforms? Seriously? Having been a TA for a course with similar pretentions. Students will be miserable because they aren't given the tools to deal with the homework, they will learn very little, and forget it all very quickly
  - utopcell 4y ago
    Stanford has a course dedicated to FFT, which is available online [1]. [1] https://see.stanford.edu/course/ee261 https://see.stanford.edu/course/ee261
UncleMeat 4y ago
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.
- oldgradstudent 4y ago
  Undergrads deserve rigor too. The course description is especially ironic as it claims rigor. > This course will provide a rigorous and hands-on introduction to the central ideas and algorithms that constitute the core of the modern algorithms toolkit. The result, of course, will be a bunch of undergrads with a very hazy recollection, and zero real knowledge.

a-dub 4y ago

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?

BubbleRings 4y ago

+10 to Griffindor for that last lune

sylware 4y ago

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.

maayank 4y ago
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
- layer8 4y ago
  The general topic is called numerical analysis.
layer8 4y ago
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.

xmonkee 4y ago

Are the assignments linked somewhere? I couldn't find them

dev_0 4y ago

No videos? WHat's the point of sharing?

jointpdf 4y ago

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 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 https://web.stanford.edu/~boyd/papers/pdf/glrm.pdf

deleted 4y ago
[deleted]
nuclearnice1 4y ago
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. https://authors.library.caltech.edu/13697/1/ROWnc99.pdf https://authors.library.caltech.edu/13697/1/ROWnc99.pdf

chrsig 4y ago

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 [0] https://www.youtube.com/c/Eigensteve https://www.youtube.com/c/Eigensteve

nothrowaways 4y ago

Cool!

grubby 4y ago

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