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.
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?
> Right now, I am struggling with all the interviews that have these leetcode problems.
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.
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.
There are three parts of building products in software just like everywhere else:
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.
I was one of those students initially but then came to appreciate the beauty in the science and nature of computation. I always tell people that computer science is not about programming -- its about studying the dynamics of problems in nature.
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.
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.
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.
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.
+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.
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.
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.
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.
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.
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. 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.
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.
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.
March 15, 2024 Great ideas in theoretical computer science
https://news.ycombinator.com/item?id=39720388
93 comments
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.
Usually attributed to Dijkstra.