FRESH

Hacker News

Home

Great ideas in theoretical computer science

178 points by sebg

by Neywiny

5 subcomments

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.

by turingbook

0 subcomment

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

by skulk

2 subcomments

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.

by BrokenCogs

0 subcomment

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

by rivetfasten

0 subcomment

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

by gorgoiler

2 subcomments

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.

by senthil_rajasek

0 subcomment

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

by Ifkaluva

4 subcomments

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

by MangoToupe

1 subcomments

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