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?

> we needed programming and computer science to be different majors.

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.

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.

> radicalized me to believing we needed programming and computer science to be different majors.

Some universities offer Software Engineering as a BEng as well as CompSci as a BSc. At least in Canada.

Is code monkey derogatory here?

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

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

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.

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

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

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.

Theory is certainly a weed-out class. I think algorithms is certainly more difficult for a dedicated student tho.

The title of the submission is the title of the page, it's not referring to just the one section but the entire course.