Great ideas in theoretical computer science
cs251.com
cs251.com
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.
1. understanding what product needs to be built
2. Having the technical expertise to build them
3. how much effort is needed to build it
And all three things can be hard in themselves. The product can technically be just straightforward (even if somewhat tedious) but you should know what to build because you should know what the customers need.
The product can be technically so challenging that without the theoretical background, you would not even know that such a product would be possible. (An example here would be something say that requires distributed and independent time clocks).
Finally the product can be something that is technically simple, obvious in its customer demand but requires quite a bit of effort and therefore requires you to be good at procuring resources and managing them.
You need to figure out which of these three things made you successfull with the product you call really hard and interesting and pursue that line of industry (even if it is not software!). And then slowly try to become good at other two things.
There's no need to struggle with them. You'll cover fully half of them simply with experience with trees. Build them. Traverse them top-down. Then bottom-up. Search it, Balance it, then rebalance on modification. Invert it, prune it, Roundtrip it to JSON, etc.
After mastering that, given a problem of "develop a flood-fill algorithm to this specification" should be a walk in the park.
1. To handle trees easily you have to understand recursion. Somebody with no CS experience (and no parser experience) might never ever used recursion in anger, even if they launched zillion commercial projects.
2. No Big-O notation. Interviewers usually ask questions about time/space complexity.
And the elephant in the room is that leetcodes are getting trickier and trickier, that's LLM era for you.
> 1. To handle trees easily you have to understand recursion.
Well that's the point of the exercises I suggest - to learn recursion :-/
> No Big-O notation. Interviewers usually ask questions about time/space complexity
Well, that's the other half of the interview, I only promised that my method will cover half the questions :-)
Then we must have been talking past each other. We are considering this problem here:
>> I never took affinity to computer science/math, but I love building real world products with software. [...] I am struggling with all the interviews that have these leetcode problems.
Then your advice to these interview problem is to learn some CS - the useful parts of it? E.g. recursion is CS.
> Then your advice to these interview problem is to learn some CS - the useful parts of it?
Theory was not my advice.
My advice was to do practical things with trees; I felt it would fit his love of building real things.
I mean, I didn't recommend doing problems out of a textbook, did I?
It sounds like leetcode problems require either memorization of a significant number of algorithm design patterns or seriously sharp algorithmic problem solving skills.
Unfortunately, I realized this a little late, and it wasn't until towards the end of my final year when I started appreciating these courses. I long for a day I can return to studying these topics.
Some universities offer Software Engineering as a BEng as well as CompSci as a BSc. At least in Canada.
So really there should be 3 fields of study: 1. The theory - computer science 2. How to apply the theory - software engineering 3. How to turn those designs into reality - programmers
It's like the mech engineering side. You have materials science and stuff, then mechanical engineers, then machinists.
I suppose in some schools computer science programmes might be fairly distinct from engineering ones. However, it seems that in lots of places a bachelor's in computer science is rather an generalist degree that covers lots of (mostly software) tech topics and some CS theory.
I'd still have trouble calling myself a software engineer, though, since I don't technically have an engineering degree, even though in lots of places my job might be described as such.
I also don't know a single programmer/developer whose job is distinct from field 2.
It makes me crazy that companies labels there entire programmer workforce as "software engineers" when there are no engineering concepts involved at all. Other fields (medical, mechanical, civil engineering) are a lot more mature in this area and have solved this issue long ago.
https://ia601605.us.archive.org/view_archive.php?archive=/23...
Neither are needed anymore if people will be able to tell a chatbot what to do.
Instead you’ll need a Problem Solution Verification minor.
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
For a proof of this, see https://github.com/tmoertel/practice/blob/master/dailycoding...
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.
March 15, 2024 Great ideas in theoretical computer science
https://news.ycombinator.com/item?id=39720388
93 comments
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.
> 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%9...
Unluckily,
> 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.
Usually attributed to Dijkstra.
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.
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".
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
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).