5 ms·

Great ideas in theoretical computer science

203 points by sebg 10mo ago

Ifkaluva 10mo ago
I seem to remember this specific class at the CMU School of Computer Science being described as a “weed-out class”.
- MangoToupe 10mo ago
  Theory is certainly a weed-out class. I think algorithms is certainly more difficult for a dedicated student tho.
- wrs 10mo ago
  When I took the theory of computation class at CMU in the mid-80s it was in the philosophy department. The professor knew almost nothing about actual computers. Which was pretty cool, honestly.
  - arethuza 10mo ago
    "Computer science is no more about computers than astronomy is about telescopes." Usually attributed to Dijkstra.
  - hearsathought 10mo ago
    > When I took the theory of computation class at CMU in the mid-80s it was in the philosophy department. To be fair, theory of computation is more logic/proofs/formalism than what is mistakenly associated with CS nowadays - programming. Besides isn't everything just philosophy at the end of that day? > The professor knew almost nothing about actual computers. The foundations of theory of computation were laid before actual computers. > Which was pretty cool, honestly. I can't imagine my philosophy professors teaching theory of computation as they too didn't know anything about computers. But I'm sure they would have made it interesting.
    - anthk 10mo ago
      >philosophy at the end of the day More like DIscrete Math
  - sota_pop 10mo ago
    I always thought it should be called “ComputING Science” as opposed to “ComputER Science”.
- awefpojoi 10mo ago
  It is indeed a weed-out class for the CS majors. It's fairly difficult the whole way through, and the difficulty jump afterwards for required classes is much more manageable. I never struggled with a required CS class after I managed to get an A in this one.
- jtbetz22 10mo ago
  I am old enough to remember when it was 15-199, taught by Steven Rudich, titled "How to think like a computer scientist". They had to run it for a few years before they realized CS kids who did poorly in the class dropped the major - the implicit signal being "you don't know how to think like a computer scientist".
MangoToupe 10mo ago
I notice "highlights" is essentially empty, which seems to be the referent of the title of this post
- Jtsummers 10mo ago
  The title of the submission is the title of the page, it's not referring to just the one section but the entire course.
  - MangoToupe 10mo ago
    I see. Where can we see these great ideas?
    - jll29 10mo ago
      The course's title set great expectations. The actual course has a narrower scope, usually this is just called "Formal Language, Automata and Complexity" or "Introduction to Theoretical Computer Science". There are many genius ideas in computer science, e.g. divide and conquer, the various forms of abstraction (see SICP), some astonishing algorithms like Dijstra's, Kalman filters, MCMC, Viterbi's or Integer-Bresenham, or data structures like the Bloom filter or Kohonen maps; for an intro, have a look at A. K. Dewdney's book "The Turing Omnibus" for a fairly non-technical exposition of a broad range beyond TCS (beginner level, does not include most from my list here).
      - MangoToupe 10mo ago
        I guess I was just confused by the structure of the course; I didn't intend to imply the stuff it covered wasn't crucial.
Neywiny 10mo ago
This is computer science. My uni's course number wasn't too different and I remember 3 things worth sharing here: 1. Somebody asked the lecturer what practical application something had. He pondered for a bit, and said "I don't really care." And then gave an explanation of how it's a science/theory class. 2. A classmate threw fits in the group chat about how he'd never have to do this kind of work after graduating because he could hire people like our lecturer to do it for him. 3. The rush when I figured out how to prove something during the last problem of an exam. As the time ticked away and I'm just staring at the words over and over, before I can sink an ice pick in and finally start grabbing a foothold. Other things not really worth mentioning were that we had some useless digital logic section at the start where we made a full adder and called it a computer. As a CompE, it was weird. The CS students thought they knew all there was to how a computer worked from that. Also, he was only a lecturer because our processor got sick right before the class and they found a grad student to do it. He was ok but took shortcuts and our TA would be like "oh, he did this fast and loose, so now I have to teach you the real way it's done". It was a great class in retrospect and certainly pushed my boundary on theoretical computing but you could feel the code monkeys regretting their decisions each homework and exam. It's what radicalized me to believing we needed programming and computer science to be different majors.
- AdityaSanthosh 10mo ago
  Hi, I am one of those code monkey you mentioned. I never took affinity to computer science/math, but I love building real world products with software. I built some really hard and interesting products. Basically, I love playing with tools and building tools from programming paradigms I know. Right now, I am struggling with all the interviews that have these leetcode problems. What sort of career in IT do you think would be best fit for me?
  - Neywiny 10mo ago
    Well what I'll say is this: my job never had leetcode. Embedded engineering, especially if you do FPGA work, is very different from what leetcode has. Honestly if recruiters are using it for jobs like mine, they really don't get it. But I don't know you nearly enough to know. There are so many different fields up and down the stack. Front end, backend, embedded, cloud, edge, consumer, IoT... The list goes on. I would cast a wider net, I guess.
skulk 10mo ago
Randomized algorithms are so damn cool. They really feel like cheating your way out of NP problems. I highly recommend that anyone interested in algorithms studies them.
- another_twist 10mo ago
  +1. My favourite bit is when pivots are chosen randomly in quicksort, we get linearithmic expected complexity. The CLRS proof using indicator random vars was a oh-shit moment.
  - gnull 10mo ago
    Btw, you can make quicksort deterministically O(n log n) if you pick the pivot point with linear median search algorithm. It's impressive how randomness lets you pick a balanced pivot, but even more impressive that you could do the same without randomness.
  - deleted 10mo ago
    [deleted]
  - tmoertel 10mo ago
    Similarly, quickselect with random pivots runs in expected linear time. For a proof of this, see https://github.com/tmoertel/practice/blob/master/dailycodingproblem_com/p661_find_elem_in_sorted_array_with_limited_ops.py#L51 https://github.com/tmoertel/practice/blob/master/dailycoding...
- gnull 10mo ago
  https://www.wisdom.weizmann.ac.il/~oded/PDF/rnd.pdf https://www.wisdom.weizmann.ac.il/~oded/PDF/rnd.pdf Then you reach derandomization and it hits you once again, it shows you that maybe you can "cheat" in the same way without randomness. Not for free, you usually trade randomness for a bit more running time, but your algorithms stay deterministic. Some believe all probabilistic algorithms can be derandomized (BPP = P), which would be a huge miracle if true.
senthil_rajasek 10mo ago
Earlier discussions: March 15, 2024 Great ideas in theoretical computer science https://news.ycombinator.com/item?id=39720388 https://news.ycombinator.com/item?id=39720388 93 comments
gorgoiler 10mo ago
Module 8 is worded in a way that surprised me: “if we could decide the languages in NP efficiently, this would lead to amazing applications.” My understanding of P=?NP is that all intuition points to the answer being “no”. The openness of the question doesn’t give us hope that a magical algorithm might one day arrive. It just means that despite a lot of suspicion that NP cannot be solved in polynomial time, we cannot yet prove this to be the case. I suspect the answer to BANKACCOUNT=?1_000_000 is “no”, but although my card stops working every month, it starts working again on the last Friday of the month! My research team and I hope to visit an ATM one day to prove my bank balance is meager but until then it remains an open question (albeit likely false) in Gorgoiler Science.
- IsTom 10mo ago
  There were surprising results in computational complexity before. We can't prove that P /= PSPACE which should be much easier to prove and yet people are stuck on trying to prove P /= NP. Personally I don't think that P = NP and if it were it would be very surprising, but "very surprising" in not "out of the question".
- aleph_minus_one 10mo ago
  > Module 8 is worded in a way that surprised me: “if we could decide the languages in NP efficiently, this would lead to amazing applications.” > My understanding of P=?NP is that all intuition points to the answer being “no”. The openness of the question doesn’t give us hope that a magical algorithm might one day arrive. It just means that despite a lot of suspicion that NP cannot be solved in polynomial time, we cannot yet prove this to be the case. I admit that I am slightly biased towards that P=NP does indeed hold. I know that this is a non-mainstream view; even though I could give arguments to actual experts in the field that (surprisingly) did convince them that it is much less "clear" than they thought all the time that P \neq NP "must" hold. On the other hand, I consider it to be plausible that the fastest algorithm that might exist for a "natural" NP-complete problem (e.g. 3-SAT) that exists could have a runtime of \Theta(n^(2^(2^(2^1000000)))). Or, it is also possible that the proof of P=NP might be highly non-constructive, and obtaining an actual algorithm from this non-constructive proof might be even harder than proving P=NP. Such a situation actually exists in the Robertson-Seymour theorem ("every family of graphs that is closed under taking minors can be defined by a finite set of forbidden minors"): > https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%93Seymour_theorem&oldid=1310513151 https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%9... Unluckily, > https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%93Seymour_theorem&oldid=1310513151#Polynomial_time_recognition https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%9... "The Robertson–Seymour theorem has an important consequence in computational complexity, due to the proof by Robertson and Seymour that, for each fixed graph H, there is a polynomial time algorithm for testing whether a graph has H as a minor. [...] As a result, for every minor-closed family F, there is polynomial time algorithm for testing whether a graph belongs to F: check whether the given graph contains H for each forbidden minor H in the obstruction set of F. However, this method requires a specific finite obstruction set to work, and the theorem does not provide one. The theorem proves that such a finite obstruction set exists, and therefore the problem is polynomial because of the above algorithm. However, the algorithm can be used in practice only if such a finite obstruction set is provided. As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it." So, it is in my opinion a very "religious" belief that even if we could prove P=NP, a practically relevant algorithm will arise from this proof.
BrokenCogs 10mo ago
There used to be a 'sophomore college' course at stanford called "Great Ideas in Computer Science" which I completed a while ago. I have great memories from that! https://stanforddaily.com/2015/11/02/classy-classes-cs-54n-great-ideas-in-computer-science/ https://stanforddaily.com/2015/11/02/classy-classes-cs-54n-g...
rivetfasten 10mo ago
Who reaches for a tool they forgot about? Few organizations invest in solutions only understood by one or two individuals on their team. This is actually what prevents undergraduate cs knowledge from having an impact. It makes me sad. Undergraduate CS isn't about the things you do most of the time. It's about enabling the occasions where the alternative is to give up and shrug, or perhaps speculate instead of evaluate. Undergrads, read this before taking a theory of computation class: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
turingbook 10mo ago
Discussion 2 years ago: https://news.ycombinator.com/item?id=39720388 https://news.ycombinator.com/item?id=39720388 The similiar course in - Stanford: https://web.stanford.edu/class/cs208e/cgi-bin/main.cgi/ https://web.stanford.edu/class/cs208e/cgi-bin/main.cgi/ - MIT https://ocw.mit.edu/courses/6-080-great-ideas-in-theoretical-computer-science-spring-2008/ https://ocw.mit.edu/courses/6-080-great-ideas-in-theoretical... - Harvard https://beta.my.harvard.edu/course/COMPSCI1/2026-Spring/001 https://beta.my.harvard.edu/course/COMPSCI1/2026-Spring/001

203 points by sebg 10mo ago

Ifkaluva 10mo ago

I seem to remember this specific class at the CMU School of Computer Science being described as a “weed-out class”.

MangoToupe 10mo ago
Theory is certainly a weed-out class. I think algorithms is certainly more difficult for a dedicated student tho.
wrs 10mo ago
When I took the theory of computation class at CMU in the mid-80s it was in the philosophy department. The professor knew almost nothing about actual computers. Which was pretty cool, honestly.
- arethuza 10mo ago
  "Computer science is no more about computers than astronomy is about telescopes." Usually attributed to Dijkstra.
- hearsathought 10mo ago
  > When I took the theory of computation class at CMU in the mid-80s it was in the philosophy department. To be fair, theory of computation is more logic/proofs/formalism than what is mistakenly associated with CS nowadays - programming. Besides isn't everything just philosophy at the end of that day? > The professor knew almost nothing about actual computers. The foundations of theory of computation were laid before actual computers. > Which was pretty cool, honestly. I can't imagine my philosophy professors teaching theory of computation as they too didn't know anything about computers. But I'm sure they would have made it interesting.
  - anthk 10mo ago
    >philosophy at the end of the day More like DIscrete Math
- sota_pop 10mo ago
  I always thought it should be called “ComputING Science” as opposed to “ComputER Science”.
awefpojoi 10mo ago
It is indeed a weed-out class for the CS majors. It's fairly difficult the whole way through, and the difficulty jump afterwards for required classes is much more manageable. I never struggled with a required CS class after I managed to get an A in this one.
jtbetz22 10mo ago
I am old enough to remember when it was 15-199, taught by Steven Rudich, titled "How to think like a computer scientist". They had to run it for a few years before they realized CS kids who did poorly in the class dropped the major - the implicit signal being "you don't know how to think like a computer scientist".

MangoToupe 10mo ago

I notice "highlights" is essentially empty, which seems to be the referent of the title of this post

Jtsummers 10mo ago
The title of the submission is the title of the page, it's not referring to just the one section but the entire course.
- MangoToupe 10mo ago
  I see. Where can we see these great ideas?
  - jll29 10mo ago
    The course's title set great expectations. The actual course has a narrower scope, usually this is just called "Formal Language, Automata and Complexity" or "Introduction to Theoretical Computer Science". There are many genius ideas in computer science, e.g. divide and conquer, the various forms of abstraction (see SICP), some astonishing algorithms like Dijstra's, Kalman filters, MCMC, Viterbi's or Integer-Bresenham, or data structures like the Bloom filter or Kohonen maps; for an intro, have a look at A. K. Dewdney's book "The Turing Omnibus" for a fairly non-technical exposition of a broad range beyond TCS (beginner level, does not include most from my list here).
    - MangoToupe 10mo ago
      I guess I was just confused by the structure of the course; I didn't intend to imply the stuff it covered wasn't crucial.

Neywiny 10mo ago

This is computer science. My uni's course number wasn't too different and I remember 3 things worth sharing here: 1. Somebody asked the lecturer what practical application something had. He pondered for a bit, and said "I don't really care." And then gave an explanation of how it's a science/theory class. 2. A classmate threw fits in the group chat about how he'd never have to do this kind of work after graduating because he could hire people like our lecturer to do it for him. 3. The rush when I figured out how to prove something during the last problem of an exam. As the time ticked away and I'm just staring at the words over and over, before I can sink an ice pick in and finally start grabbing a foothold. Other things not really worth mentioning were that we had some useless digital logic section at the start where we made a full adder and called it a computer. As a CompE, it was weird. The CS students thought they knew all there was to how a computer worked from that. Also, he was only a lecturer because our processor got sick right before the class and they found a grad student to do it. He was ok but took shortcuts and our TA would be like "oh, he did this fast and loose, so now I have to teach you the real way it's done". It was a great class in retrospect and certainly pushed my boundary on theoretical computing but you could feel the code monkeys regretting their decisions each homework and exam. It's what radicalized me to believing we needed programming and computer science to be different majors.

AdityaSanthosh 10mo ago
Hi, I am one of those code monkey you mentioned. I never took affinity to computer science/math, but I love building real world products with software. I built some really hard and interesting products. Basically, I love playing with tools and building tools from programming paradigms I know. Right now, I am struggling with all the interviews that have these leetcode problems. What sort of career in IT do you think would be best fit for me?
- Neywiny 10mo ago
  Well what I'll say is this: my job never had leetcode. Embedded engineering, especially if you do FPGA work, is very different from what leetcode has. Honestly if recruiters are using it for jobs like mine, they really don't get it. But I don't know you nearly enough to know. There are so many different fields up and down the stack. Front end, backend, embedded, cloud, edge, consumer, IoT... The list goes on. I would cast a wider net, I guess.

skulk 10mo ago

Randomized algorithms are so damn cool. They really feel like cheating your way out of NP problems. I highly recommend that anyone interested in algorithms studies them.

another_twist 10mo ago
+1. My favourite bit is when pivots are chosen randomly in quicksort, we get linearithmic expected complexity. The CLRS proof using indicator random vars was a oh-shit moment.
- gnull 10mo ago
  Btw, you can make quicksort deterministically O(n log n) if you pick the pivot point with linear median search algorithm. It's impressive how randomness lets you pick a balanced pivot, but even more impressive that you could do the same without randomness.
- deleted 10mo ago
  [deleted]
- tmoertel 10mo ago
  Similarly, quickselect with random pivots runs in expected linear time. For a proof of this, see https://github.com/tmoertel/practice/blob/master/dailycodingproblem_com/p661_find_elem_in_sorted_array_with_limited_ops.py#L51 https://github.com/tmoertel/practice/blob/master/dailycoding...
gnull 10mo ago
https://www.wisdom.weizmann.ac.il/~oded/PDF/rnd.pdf https://www.wisdom.weizmann.ac.il/~oded/PDF/rnd.pdf Then you reach derandomization and it hits you once again, it shows you that maybe you can "cheat" in the same way without randomness. Not for free, you usually trade randomness for a bit more running time, but your algorithms stay deterministic. Some believe all probabilistic algorithms can be derandomized (BPP = P), which would be a huge miracle if true.

senthil_rajasek 10mo ago

Earlier discussions: March 15, 2024 Great ideas in theoretical computer science https://news.ycombinator.com/item?id=39720388 https://news.ycombinator.com/item?id=39720388 93 comments

gorgoiler 10mo ago

Module 8 is worded in a way that surprised me: “if we could decide the languages in NP efficiently, this would lead to amazing applications.” My understanding of P=?NP is that all intuition points to the answer being “no”. The openness of the question doesn’t give us hope that a magical algorithm might one day arrive. It just means that despite a lot of suspicion that NP cannot be solved in polynomial time, we cannot yet prove this to be the case. I suspect the answer to BANKACCOUNT=?1_000_000 is “no”, but although my card stops working every month, it starts working again on the last Friday of the month! My research team and I hope to visit an ATM one day to prove my bank balance is meager but until then it remains an open question (albeit likely false) in Gorgoiler Science.

IsTom 10mo ago
There were surprising results in computational complexity before. We can't prove that P /= PSPACE which should be much easier to prove and yet people are stuck on trying to prove P /= NP. Personally I don't think that P = NP and if it were it would be very surprising, but "very surprising" in not "out of the question".
aleph_minus_one 10mo ago
> Module 8 is worded in a way that surprised me: “if we could decide the languages in NP efficiently, this would lead to amazing applications.” > My understanding of P=?NP is that all intuition points to the answer being “no”. The openness of the question doesn’t give us hope that a magical algorithm might one day arrive. It just means that despite a lot of suspicion that NP cannot be solved in polynomial time, we cannot yet prove this to be the case. I admit that I am slightly biased towards that P=NP does indeed hold. I know that this is a non-mainstream view; even though I could give arguments to actual experts in the field that (surprisingly) did convince them that it is much less "clear" than they thought all the time that P \neq NP "must" hold. On the other hand, I consider it to be plausible that the fastest algorithm that might exist for a "natural" NP-complete problem (e.g. 3-SAT) that exists could have a runtime of \Theta(n^(2^(2^(2^1000000)))). Or, it is also possible that the proof of P=NP might be highly non-constructive, and obtaining an actual algorithm from this non-constructive proof might be even harder than proving P=NP. Such a situation actually exists in the Robertson-Seymour theorem ("every family of graphs that is closed under taking minors can be defined by a finite set of forbidden minors"): > https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%93Seymour_theorem&oldid=1310513151 https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%9... Unluckily, > https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%93Seymour_theorem&oldid=1310513151#Polynomial_time_recognition https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%9... "The Robertson–Seymour theorem has an important consequence in computational complexity, due to the proof by Robertson and Seymour that, for each fixed graph H, there is a polynomial time algorithm for testing whether a graph has H as a minor. [...] As a result, for every minor-closed family F, there is polynomial time algorithm for testing whether a graph belongs to F: check whether the given graph contains H for each forbidden minor H in the obstruction set of F. However, this method requires a specific finite obstruction set to work, and the theorem does not provide one. The theorem proves that such a finite obstruction set exists, and therefore the problem is polynomial because of the above algorithm. However, the algorithm can be used in practice only if such a finite obstruction set is provided. As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it." So, it is in my opinion a very "religious" belief that even if we could prove P=NP, a practically relevant algorithm will arise from this proof.

BrokenCogs 10mo ago

There used to be a 'sophomore college' course at stanford called "Great Ideas in Computer Science" which I completed a while ago. I have great memories from that! https://stanforddaily.com/2015/11/02/classy-classes-cs-54n-great-ideas-in-computer-science/ https://stanforddaily.com/2015/11/02/classy-classes-cs-54n-g...

rivetfasten 10mo ago

Who reaches for a tool they forgot about? Few organizations invest in solutions only understood by one or two individuals on their team. This is actually what prevents undergraduate cs knowledge from having an impact. It makes me sad. Undergraduate CS isn't about the things you do most of the time. It's about enabling the occasions where the alternative is to give up and shrug, or perhaps speculate instead of evaluate. Undergrads, read this before taking a theory of computation class: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html

turingbook 10mo ago

Discussion 2 years ago: https://news.ycombinator.com/item?id=39720388 https://news.ycombinator.com/item?id=39720388 The similiar course in - Stanford: https://web.stanford.edu/class/cs208e/cgi-bin/main.cgi/ https://web.stanford.edu/class/cs208e/cgi-bin/main.cgi/ - MIT https://ocw.mit.edu/courses/6-080-great-ideas-in-theoretical-computer-science-spring-2008/ https://ocw.mit.edu/courses/6-080-great-ideas-in-theoretical... - Harvard https://beta.my.harvard.edu/course/COMPSCI1/2026-Spring/001 https://beta.my.harvard.edu/course/COMPSCI1/2026-Spring/001