Professor solves 240 computer science exam problems in 4 hours [video](youtube.com)
youtube.com
Professor solves 240 computer science exam problems in 4 hours [video]
https://www.youtube.com/watch?v=g_ZdcHSFGv0&t=10s
172 comments
A lot of people give theory a lot of crap. But that's normally because they are not comfortable with the material.
If you are comfortable with the material, you see applications for it all over the place, and use it all the time. Sure, you don't have to ground your system in some kind of formal model (you can just code-til-it-works), but when you do I've found it always ends up as a far simpler and more resilient product.
It's kind of like people who complain that math is useless in school and you'll never need it. Sure, if you never really master it, you'll never be able to use it, so you'll make things kinda work in ways that don't strictly require it, and then conclude it's useless. Meanwhile, if you are familiar with it, your prospects are broader, you may have to use it, and you'll see how it was absolutely relevant and important to know...
If you are comfortable with the material, you see applications for it all over the place, and use it all the time. Sure, you don't have to ground your system in some kind of formal model (you can just code-til-it-works), but when you do I've found it always ends up as a far simpler and more resilient product.
It's kind of like people who complain that math is useless in school and you'll never need it. Sure, if you never really master it, you'll never be able to use it, so you'll make things kinda work in ways that don't strictly require it, and then conclude it's useless. Meanwhile, if you are familiar with it, your prospects are broader, you may have to use it, and you'll see how it was absolutely relevant and important to know...
I think people are ready for things at certain times.
I think history class was wasted on me in high school because I was a kid and didn't have much life experience. But years later with a better grasp on human nature I think I would have had a better grasp.
Another example is a foreign language class. I took it in middle school, in high school and later in college. I learned lots and lots of theory for many years. But only when I went to another country did I learn I hadn't learned.
I think theory needs to be combined with: experience and practice.
I think history class was wasted on me in high school because I was a kid and didn't have much life experience. But years later with a better grasp on human nature I think I would have had a better grasp.
Another example is a foreign language class. I took it in middle school, in high school and later in college. I learned lots and lots of theory for many years. But only when I went to another country did I learn I hadn't learned.
I think theory needs to be combined with: experience and practice.
I've always sort of wished I could go back and get my CS degree after I had a few years experience in industry, instead of getting it before. I feel like I would have appreciated what I was learning a lot more.
I think there's two things that change in those years. One is practical experience. The other is life.
Perhaps it takes both. I've definitely seen people who have the one but not the other fail to appreciate the value of theory.
Perhaps it takes both. I've definitely seen people who have the one but not the other fail to appreciate the value of theory.
Agreed. The reason its not that way is that schools are mostly state-run daycare programs, setup so that parents can work, not a genuine implementation of skill building.
If you agree, the logical takeaway from
> I history class was wasted on me in high school because I was a kid and didn't have much life experience. But years later with a better grasp on human nature I think I would have had a better grasp.
would not be
> Schools are mostly state-run daycare programs, setup so that parents can work, not a genuine implementation of skill building.
This is due to the nature of the topic, not its pedagogy.
> I history class was wasted on me in high school because I was a kid and didn't have much life experience. But years later with a better grasp on human nature I think I would have had a better grasp.
would not be
> Schools are mostly state-run daycare programs, setup so that parents can work, not a genuine implementation of skill building.
This is due to the nature of the topic, not its pedagogy.
No, the reason is that the people who teach are naturally of greater experience and age. When you reach their age/experience they are starting to make sense.
I found it also helps with the hardest problem in software development: naming things.
Without knowledge of the theory it can be hard to come up with a descriptive name for some data structure/algorithm you created to solve your problem.
With some knowledge of the theory you can more easily put a name to what you have created, making it easier for other people to understand and giving them something to Google if they're unfamiliar.
Without knowledge of the theory it can be hard to come up with a descriptive name for some data structure/algorithm you created to solve your problem.
With some knowledge of the theory you can more easily put a name to what you have created, making it easier for other people to understand and giving them something to Google if they're unfamiliar.
> naming things
There are two hard problems in computer science: naming things, cache invalidation, and off-by-one errors.
There are two hard problems in computer science: naming things, cache invalidation, and off-by-one errors.
>> naming things
>There are two hard problems in computer science: naming
concurrency
>things, cache invalidation, and off-by-one errors.
>There are two hard problems in computer science: naming
concurrency
>things, cache invalidation, and off-by-one errors.
What’s wrong with FactoryProducerProxy? /jk
But loop variables are always i, j and k.
n for me for a long time but that’s BASIC showing through.
> It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.” - Edsger Dijkstra
> It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.” - Edsger Dijkstra
Except in EE.
There's often a gap in abstraction where you just don't see the point nor the value.. until you do. Follows the usual enlightened 'aah'
E.S.S Schumacher described this very well with his concept of adequatio
"What enables man to know anything at all about the world around him? … Nothing can be known without there being an appropriate “instrument” in the makeup of the knower. This is the Great Truth of “adaequatio” (adequateness), which defines knowledge as adaequatio rei et intellectus — the understanding of the knower must be adequate to the thing to be known.[...]
For every one of us only those facts and phenomena “exist” for which we posses adaequatio, and as we are not entitled to assume that we are necessarily adequate to everything, at all times, and in whatever condition we may find ourselves, so we are not entitled to insist that something inaccessible to us has no existence at all and is nothing but a phantom of other people’s imaginations.[...]
There is nothing more difficult than to become critically aware of the presuppositions of one’s thought. Everything can be seen directly except the eye through which we see. Every thought can be scrutinized directly except the thought by which we scrutinize. A special effort, an effort of self-awareness, is needed: that almost impossible feat of thought recoiling upon itself — almost impossible but not quite. In fact, that is the power that makes man human and also capable of transcending his humanity."
"What enables man to know anything at all about the world around him? … Nothing can be known without there being an appropriate “instrument” in the makeup of the knower. This is the Great Truth of “adaequatio” (adequateness), which defines knowledge as adaequatio rei et intellectus — the understanding of the knower must be adequate to the thing to be known.[...]
For every one of us only those facts and phenomena “exist” for which we posses adaequatio, and as we are not entitled to assume that we are necessarily adequate to everything, at all times, and in whatever condition we may find ourselves, so we are not entitled to insist that something inaccessible to us has no existence at all and is nothing but a phantom of other people’s imaginations.[...]
There is nothing more difficult than to become critically aware of the presuppositions of one’s thought. Everything can be seen directly except the eye through which we see. Every thought can be scrutinized directly except the thought by which we scrutinize. A special effort, an effort of self-awareness, is needed: that almost impossible feat of thought recoiling upon itself — almost impossible but not quite. In fact, that is the power that makes man human and also capable of transcending his humanity."
This is a much more pithy and compressed way of saying what I tried to say above, thanks
I empathise with people who go to college to study computer science, mainly with the intent of eventually landing a well-paid programming job, who are then frustrated when they have to learn actual computer science topics instead of just learning to program.
But their anger is usually directed at the wrong institution. The problem doesn't lie with academia teaching the wrong things, it lies with companies requiring CS degrees for simple programming jobs. They treat the theoretical computer science material as nothing more than a raw intelligence/perseverance filter.
But their anger is usually directed at the wrong institution. The problem doesn't lie with academia teaching the wrong things, it lies with companies requiring CS degrees for simple programming jobs. They treat the theoretical computer science material as nothing more than a raw intelligence/perseverance filter.
We spent entirely too much time on O(this) and O(that)
But that's the stuff that sort of stood up to the test of time.
Also really helpful was symbolic logic, which actually was not a computer science course.
The most interesting computer science topics to me in school were the different computer languages -- but very few of them survived the test of time.
But that's the stuff that sort of stood up to the test of time.
Also really helpful was symbolic logic, which actually was not a computer science course.
The most interesting computer science topics to me in school were the different computer languages -- but very few of them survived the test of time.
In my bachelor's degree, I spent two weeks of one course, tops on O(this) and O(that).
I suppose I spent two courses studying computational complexity, but reducing it to O(this) and O(that) does not quite do it justice.
I suppose I spent two courses studying computational complexity, but reducing it to O(this) and O(that) does not quite do it justice.
I use CS theory all the time in my professional career. Automata, was the most useful class I took (the 2nd most useful was Programming Language Concepts).
I don't dispute at all that theoretical CS is practically useful, I love it myself and think it offers amazing tools for thought. But my hunch is (and I'm emphasizing that I'm speculating here) that only people who like the material end up retaining enough to see the applications. I feel like some of my fellow students, including ones that I felt were smart (but who were application-oriented learners who have trouble focusing if they didn't see applications right away), had to drag themselves through the theoretical material to barely pass and then promptly forget about it. I imagine their perspective is:
1. They have to work through material that does not particularly interest them and is quite hard, but employers insist that they must master this stuff if they want a good position.
2. In their work environment, no one ever asks them to actually use theoretical CS concepts, and they don't spontaneously see applications themselves.
3. Therefore, they feel academia is out of touch and teaching irrelevant material that has no practical application. With my earlier comment I wanted to point out that I don't believe academia is to blame for their suffering.
1. They have to work through material that does not particularly interest them and is quite hard, but employers insist that they must master this stuff if they want a good position.
2. In their work environment, no one ever asks them to actually use theoretical CS concepts, and they don't spontaneously see applications themselves.
3. Therefore, they feel academia is out of touch and teaching irrelevant material that has no practical application. With my earlier comment I wanted to point out that I don't believe academia is to blame for their suffering.
That's the thing, it is useful, so I don't blame companies for wanting people who know CS theory.
And when I hire people, even though I hate doing adversarial whiteboard coding, I will probe to find out if people understand a bit of theory.
You can get a lot of work done without theoretical knowledge, (but the end result is often not as good, and it usually takes longer). Combine that with the fact that CS theory is hard, and you get a lot of people complaining about how theoretical CS is useless outside of academia.
It's basically an extension of "no one needs to know math beyond arithmetic in the real world".
And when I hire people, even though I hate doing adversarial whiteboard coding, I will probe to find out if people understand a bit of theory.
You can get a lot of work done without theoretical knowledge, (but the end result is often not as good, and it usually takes longer). Combine that with the fact that CS theory is hard, and you get a lot of people complaining about how theoretical CS is useless outside of academia.
It's basically an extension of "no one needs to know math beyond arithmetic in the real world".
What do you do professionally? How do you use automata there?
Web development, embedded systems, and game dev. I use FSMs, pushdown automata, and hierarchical state machines all the time.
What's amazing to me is how uncommon state machines are in software, comparatively. In ASIC and FPGA design, it's so fundamental and ubiquitous. At least with synchronous designs.
I pushed for using state machines and more formal methods in the rewrite of a system that I and a number of other devs were hired for. The idea was turned down in favor of lots of ad hoc state and string constants, even though the system has a limited and distinct set of states on the main domain objects. People don't do it because people don't do it, and they're afraid others aren't going to understand it.
The vast majority of companies essentially code and design to the lowest common denominator so that their devs are fungible cogs.
The vast majority of companies essentially code and design to the lowest common denominator so that their devs are fungible cogs.
The problem is that it's extremely easy to violate the boundaries of state machines. For example there's some small edge case, that would normally require you to completely re-create the state machine, but people bypass that by just escaping the state machine. In ASIC/FPGA, it's actually relatively hard to escape the state machine because escaping the state machine causes explosions in timing required and causes race conditions.
Code doesn't have fixed timing requirements, most of the time.
Code doesn't have fixed timing requirements, most of the time.
For embedded systems and game development I definitely understand automata applications (from experience) but web development has me curious. Are you writing transpilers or perhaps something else (I also try to avoid web dev, so there's that).
Mostly for user interfaces and modeling business processes. But I’ve also done some work on a super simple language for some of our non technical people to use for data transformation, and a templating system for form generation.
Not OP but there are more than a few domains that can be modeled with automata, a shipping pipeline with approval steps is an example.
Ecommerce order/payment/shipping status is a good example. Anything that has a well defined state that can be changed by events is well-modeled as a state machine of some kind. Also anything that has to progress through certain steps and might be interrupted or have exception cases, and you want to proceed/retry idempotently.
Personally I have also found basic graph theory to be immensely useful for representing and reasoning about things.
Personally I have also found basic graph theory to be immensely useful for representing and reasoning about things.
>Personally I have also found basic graph theory to be immensely useful for representing and reasoning about things.
I agree! The graph theory portion of my algorithms class (more than half of the class) was the third most useful thing I learned in my degree.
I agree! The graph theory portion of my algorithms class (more than half of the class) was the third most useful thing I learned in my degree.
You can say that about many fields. Employers outsource their testing to universities. It saves them a ton of effort and it has the side benefit of shielding them from some potential discrimination claims.
Without university, how is an employer to know you would've spent 4 years working on something reasonably challenging that took a moderate to large amount of effort over long periods of time? They can't discover any of this in an interview. The fact that high school is mandatory robs it of much of its signalling value.
Without university, how is an employer to know you would've spent 4 years working on something reasonably challenging that took a moderate to large amount of effort over long periods of time? They can't discover any of this in an interview. The fact that high school is mandatory robs it of much of its signalling value.
The fact that high school is mandatory robs it of much of its signalling value.
This will very clearly result in the same loss of signaling value for higher education.
This will very clearly result in the same loss of signaling value for higher education.
There's a bunch of commercial prep courses and coding bootcamps that focus on applied programming.
I wonder how long-term those skills are, reminds me of companies teaching MCSE certification a few decades ago.
I wonder how long-term those skills are, reminds me of companies teaching MCSE certification a few decades ago.
Think it depends entirely on the person. I know someone who went through one of those 6 years ago. He worked a grunt job for a while for experience, and has traded up to a very nice gig today. He also worked pretty hard on the side, teaching himself.
I can't speak for the longevity of the training, but he's doing fine.
For that matter, other than a terrible 101 class, I have no formal programming training and have been doing this professionally for over 20 years so far. But I'm a bit of a broken record when it comes to degrees-as-gatekeepers - the vast majority of programming jobs do not require a college diploma to competently perform. Very, very few people are writing blank-page Paxos implementations or researching "ai" - they're gluing APIs together and writing business logic. Moderate competence, the ability to do basic research and the patience to get past the WTF stage with a compiler are what you need, not a four year degree.
I can't speak for the longevity of the training, but he's doing fine.
For that matter, other than a terrible 101 class, I have no formal programming training and have been doing this professionally for over 20 years so far. But I'm a bit of a broken record when it comes to degrees-as-gatekeepers - the vast majority of programming jobs do not require a college diploma to competently perform. Very, very few people are writing blank-page Paxos implementations or researching "ai" - they're gluing APIs together and writing business logic. Moderate competence, the ability to do basic research and the patience to get past the WTF stage with a compiler are what you need, not a four year degree.
The way I've seen it distinguished in colleges is as a separate "Software Engineering" track within the compsci department.
There is a lack of a university (or above) level software engineering education that isn't aimed at computer science.
> The fact that one does not need this during their day job is, dare I say it, irrelevant.
I disagree for some of the fundamental things.
Binary arithmetic is fundamental. The number of times I have seen people using addition for logical-or and being confounded by bugs astounds me. I don't expect you to be able to do stupid bit tricks. However you must know how to use and,or,xor,not for masking and you must understand what integer overflow/underflow is.
State machines are fundamental. I'll go so far as to say that if you don't know how to do state machines, you don't really know how to program. You simply have no framework for understanding things like protocols, sequencing, concurrency, etc.
Data structures are fundamental. Sure, I can boil it down to "75% of the time use a hash table; 25% of the time use a vector; .001% of the time use something else". But you won't know when you shouldn't use something.
These are things I see all the time in programmers who I would expect to know better. These also seem to be things that "programming" course often slack on--they're hard to teach and hard to learn. It requires work from both sides to communicate the concepts.
I disagree for some of the fundamental things.
Binary arithmetic is fundamental. The number of times I have seen people using addition for logical-or and being confounded by bugs astounds me. I don't expect you to be able to do stupid bit tricks. However you must know how to use and,or,xor,not for masking and you must understand what integer overflow/underflow is.
State machines are fundamental. I'll go so far as to say that if you don't know how to do state machines, you don't really know how to program. You simply have no framework for understanding things like protocols, sequencing, concurrency, etc.
Data structures are fundamental. Sure, I can boil it down to "75% of the time use a hash table; 25% of the time use a vector; .001% of the time use something else". But you won't know when you shouldn't use something.
These are things I see all the time in programmers who I would expect to know better. These also seem to be things that "programming" course often slack on--they're hard to teach and hard to learn. It requires work from both sides to communicate the concepts.
I agree; My personal view is that it's fundamental to know these ideas, just as one can't be a physicist without knowing a decent chunk of mathematics.
On the other hand, it seems that biology majors seem to "get by" [as far as I can tell] without needing to learn much math. Perhaps one can argue that it's better if they learnt more math. But we can't argue that the profession of being a doctor seems to work without them knowing too much math.
It's unclear to me, where in the extremely broad spectrum of jobs known as "programmer" [writing code for the space shuttle v/s bringing up an android app] where the need for mathematics ends. So I hesitate to make blanket statements about this.
What I will never hesitate to defend is the utility of these ideas of theoretical CS/mathematics for all computer scientists and scientist-adjacent folks.
On the other hand, it seems that biology majors seem to "get by" [as far as I can tell] without needing to learn much math. Perhaps one can argue that it's better if they learnt more math. But we can't argue that the profession of being a doctor seems to work without them knowing too much math.
It's unclear to me, where in the extremely broad spectrum of jobs known as "programmer" [writing code for the space shuttle v/s bringing up an android app] where the need for mathematics ends. So I hesitate to make blanket statements about this.
What I will never hesitate to defend is the utility of these ideas of theoretical CS/mathematics for all computer scientists and scientist-adjacent folks.
Some people are more inclined to theoretical concepts, some people are more practical. Both have an understanding on how things work and/or an intuition, either by studying theoretical concepts or via practical, hands on experience.
My issue with this, and this is mostly my own personal opinion, is not whether or not this subject is important and that we need to defend it, but whether teaching it to students of that level is the 'right' thing.
Imagine a student that doesnt even know how to program yet, doesn't know any algorithms, or higher level paradigms, heck doesnt even know any computer architecture stuff yet, but has to go through this block of theory and get examined on it.. Is it the right move to motivate more people into this field?
My issue with this, and this is mostly my own personal opinion, is not whether or not this subject is important and that we need to defend it, but whether teaching it to students of that level is the 'right' thing.
Imagine a student that doesnt even know how to program yet, doesn't know any algorithms, or higher level paradigms, heck doesnt even know any computer architecture stuff yet, but has to go through this block of theory and get examined on it.. Is it the right move to motivate more people into this field?
> My issue with this, and this is mostly my own personal opinion, is not whether or not this subject is important and that we need to defend it, but whether teaching it to students of that level is the 'right' thing.
Teaching it to which students? If someone enrolls in a computer science class, it's reasonable to teach them computer science. If instead they want a mechanical introduction to programming, CS probably isn't the right material.
Teaching it to which students? If someone enrolls in a computer science class, it's reasonable to teach them computer science. If instead they want a mechanical introduction to programming, CS probably isn't the right material.
If you want people to write mostly CRUD apps, sure.
If you want people to develop programming languages, algorithms, models etc., not really. Computer Science is a subfield of math and trying to "lure" people into the field with flashy graphics and instant gratification will only frustrate them when it gets to the basics. In theory you can complete a Computer Science degree without ever programming a physical computer. To complete my Masters in CS I only had to take an introductionary course for Java, everything else programming related was optional.
If you want people to develop programming languages, algorithms, models etc., not really. Computer Science is a subfield of math and trying to "lure" people into the field with flashy graphics and instant gratification will only frustrate them when it gets to the basics. In theory you can complete a Computer Science degree without ever programming a physical computer. To complete my Masters in CS I only had to take an introductionary course for Java, everything else programming related was optional.
There are schools which just teach you programming and computer skills and do a good job at it. But companies will still prefer candidates with computer science degrees, or even outright require a CS degree, even for simple programming jobs that really don't need one. The degree is used as no more than an intelligence filter. This relegates anyone who has a practically oriented degree to being regarded as a second class programmer, the perception being that you would have studied CS instead if you had the ability.
This completely sucks for practically inclined people who are forced to trudge through a theoretical degree that doesn't interest them, and where 90% of the material they will never use, just to prove that they're smart enough.
They then tend to blame academia for being out of touch, ivory tower, etc. But academia is not at fault here, they are teaching what they claim to teach: computer science. There are good pratically minded degrees which prepare you just fine for the average programming job, it's employers who constantly signal that they value CS degrees more.
This completely sucks for practically inclined people who are forced to trudge through a theoretical degree that doesn't interest them, and where 90% of the material they will never use, just to prove that they're smart enough.
They then tend to blame academia for being out of touch, ivory tower, etc. But academia is not at fault here, they are teaching what they claim to teach: computer science. There are good pratically minded degrees which prepare you just fine for the average programming job, it's employers who constantly signal that they value CS degrees more.
But companies will still prefer candidates with computer science degrees, or even outright require a CS degree, even for simple programming jobs that really don't need one.
I haven’t seen any corporate dev jobs that care about formal computer science during an interview. I only see that from BigTech and BigTech wannabes that think they need “smart people” (tm).
I haven’t seen any corporate dev jobs that care about formal computer science during an interview. I only see that from BigTech and BigTech wannabes that think they need “smart people” (tm).
Agree. I loved the theoretical side of CompSci (automata, programming language at the meta level, algorithms). Practical was boring to me and I lost interest in the day to day (7 hours of typing in an IDE!? joy). The problems of the practical are a let down if you start theoretical.
Can you handle 1M concurrent in Go to replace a java load distributor? Sure! Crud apps..... oh brain hurts will never finish.
Can you handle 1M concurrent in Go to replace a java load distributor? Sure! Crud apps..... oh brain hurts will never finish.
> Both have an understanding on how things work and/or an intuition, either by studying theoretical concepts or via practical, hands on experience.
hands on experience with regular expressions manages to fail a lot of people with practical problems.
https://stackoverflow.com/questions/1732348/regex-match-open...
hands on experience with regular expressions manages to fail a lot of people with practical problems.
https://stackoverflow.com/questions/1732348/regex-match-open...
> whether teaching it to students of that level is the 'right' thing
I strongly doubt that any university or educator is teaching so much theory of computation to any level of computer science student who will not be focused on theory of computation. Notice that the OP's video seems targeted towards incoming CS theory Masters/PhD students who will explicitly be working on CS theory and doing research.
I strongly doubt that any university or educator is teaching so much theory of computation to any level of computer science student who will not be focused on theory of computation. Notice that the OP's video seems targeted towards incoming CS theory Masters/PhD students who will explicitly be working on CS theory and doing research.
Yeah! And why come we gots to teach kid how to plus and minus if theys just gonna be a plummer?
You aren't being serious, but that was once actually a fairly widespread sentiment. In colonial times in America, for instance, arithmetic was generally not taught in elementary school. It was something you would learn on the job if needed.
Amusingly, when it did start getting routinely taught at the end of the 18th century there were complaints from businessmen to the school boards that the methods taught in school were producing students totally unprepared for business.
For more on this, see the essay "What is Mathematics For?" by Underwood Dudley from the May 2010 Notices of the AMS [1]. (A more accurate title, he notes in the first paragraph, would be "What is mathematics education for?").
He makes some interesting points about the usual justifications that elementary and high school math are useful in your career are not really accurate.
[1] http://www.ams.org/notices/201005/rtx100500608p.pdf
Amusingly, when it did start getting routinely taught at the end of the 18th century there were complaints from businessmen to the school boards that the methods taught in school were producing students totally unprepared for business.
For more on this, see the essay "What is Mathematics For?" by Underwood Dudley from the May 2010 Notices of the AMS [1]. (A more accurate title, he notes in the first paragraph, would be "What is mathematics education for?").
He makes some interesting points about the usual justifications that elementary and high school math are useful in your career are not really accurate.
[1] http://www.ams.org/notices/201005/rtx100500608p.pdf
I think you are not addressing the point, which the GP tried to make. It's not about teaching or not teaching, but about the time when stuff is taught. Surely all these things have their time and place. Perhaps there are gentler introductions to some of these topics available?
If you can't teach theoretical computer science to undergraduate computer science students, you will have to shift it to the graduate level. Which means you won't really every have anyone earning a true masters in computer science because they'll need so much grounding to be able to complete the work they won't have time to do anything novel.
Eeh... automata, languages (of all kinds, not just regular), grammars, complexity, etc. are used in computer engineering all the time.
If a computer engineering degree does not have those, then it is a pretty bad one.
If a computer engineering degree does not have those, then it is a pretty bad one.
One of the best books I ever read was a book that implemented a large number of algorithms in Pascal. This served me well both when implementing things as well as when studying papers about algorithms. The gap between theory and practice in computer science is as small as it gets across many domains.
I'm seeing 'Computer Science knowledge is not necessary to be a better programmer' statements more often nowadays, even from those who have CS degree(Degree != Education).
Here's one example, who is in Kaggle 1% - https://twitter.com/bhutanisanyam1/status/120900088154848051....
Here's one example, who is in Kaggle 1% - https://twitter.com/bhutanisanyam1/status/120900088154848051....
[deleted]
Interesting how so many of these problems are probably hard for a fraction of the people that want to pass this exam simply because of the language in which they are expressed.
For example, and I've noticed this pattern with some regularity: large and complex expression in a paper or some other document. Actual implementation: one or more for loops with an add or a multiply in the body of the loop with some initialization. I get it that mathematical notation is nice and compact and a quick way to communicate an idea but pseudo code would quite often be more clear.
The same for a lot of the other terminology used in the questions. How much of studying in order to pass an exam like this is simply to cram the definition for a large number of terms?
For example, and I've noticed this pattern with some regularity: large and complex expression in a paper or some other document. Actual implementation: one or more for loops with an add or a multiply in the body of the loop with some initialization. I get it that mathematical notation is nice and compact and a quick way to communicate an idea but pseudo code would quite often be more clear.
The same for a lot of the other terminology used in the questions. How much of studying in order to pass an exam like this is simply to cram the definition for a large number of terms?
That's an excellent question!
It may be worth considering that the answer may not be as significant as some might guess. GATE is an exam that tests if you're ready for graduate school. Part of being ready for a specialized field is being fluent in the vocabulary and parlance used in that field, as this enables rapid learning and smooths communication. That you can understand the ideas if they are restated and re-expressed in a form more familiar to you is not as helpful as it sounds if you cannot engage with your peers without laborious translations. Have you ever tried to discuss imperative programming with someone who only knows functional programming, or the converse?
Medical, legal, chemical, and other fields have evolved conventions of specialized vocabulary for the same reasons. They make it possible to have very detailed communications in dense, rapid ways.
Agian, you raise an excellent and wise point. There is definitely a great deal of learning vocabulary in something like this.
It may be worth considering that the answer may not be as significant as some might guess. GATE is an exam that tests if you're ready for graduate school. Part of being ready for a specialized field is being fluent in the vocabulary and parlance used in that field, as this enables rapid learning and smooths communication. That you can understand the ideas if they are restated and re-expressed in a form more familiar to you is not as helpful as it sounds if you cannot engage with your peers without laborious translations. Have you ever tried to discuss imperative programming with someone who only knows functional programming, or the converse?
Medical, legal, chemical, and other fields have evolved conventions of specialized vocabulary for the same reasons. They make it possible to have very detailed communications in dense, rapid ways.
Agian, you raise an excellent and wise point. There is definitely a great deal of learning vocabulary in something like this.
But do those fields have a similar split between the language used by the theoretical and the practical side of things?
Generally no, because they do not have large populations of self-taught professional practitioners who never learned theory.
Least common denominator writing is very useful for a great many things. It is wonderful and ideally suited for items aimed at a popular audience. It just may not always be ideal for efficient and precise technical communication.
Least common denominator writing is very useful for a great many things. It is wonderful and ideally suited for items aimed at a popular audience. It just may not always be ideal for efficient and precise technical communication.
I don't really buy this. You're framing this as if people don't use this notation because they are self taught. But I've worked in companies full of fresh out of college people and we didn't use this notation when working on projects. And when working on group projects in college, we didn't use it either when discussing possible solutions. We used pseudocode.
Beyond that, I think you're selling an ideal here in these other professions that doesn't necessarily exist. There certainly is some vocabulary overlap but a huge problem in e.g. medicine is practicing doctors not being able to understand the science behind medicines and procedures that biased 3rd parties are recommending they offer to patients.
Beyond that, I think you're selling an ideal here in these other professions that doesn't necessarily exist. There certainly is some vocabulary overlap but a huge problem in e.g. medicine is practicing doctors not being able to understand the science behind medicines and procedures that biased 3rd parties are recommending they offer to patients.
Please accept my apologies. I can see I have been unclear.
It's been my experience that when attempting to communicate, people use the vocabulary they expect will do the job efficiently for the task at hand. As you say, for many things this is absolutely pseudocode! But I've also been in situations where mathematics, or the many Greek letter transformations of Haskell, or something else was the vocabulary of choice. As the projects I've worked on have grown more complex and occasionally abstract, pseudocode has increasingly not been the go-to answer.
Again, you're completely right. It's a major issue that medical professionals often lack a real understanding of how a given pharmaceutical works. It's one that is in dire need of addressing!
I also think medical professionals have this shared assumption that they can talk about anatomy and physical processes with one another to communicate effectively and precisely, rather than "the bone next to the other bone next to the chompy thing". Especially when on a chart and the other professional isn't nearby to ask. That's shared vocabulary at work. I've certainly struggled to have architectural discussions with people with whom I shared little vocabulary. I'm sure the failing was entirely mine.
You're completely right. There's a lot here and pseudocode is incredibly powerful! I find it worth considering that there might be value to be gained in shared vocabulary beyond that one tool. Your mileage may of course vary.
Thank you kindly for the opportunity to better explain my points.
It's been my experience that when attempting to communicate, people use the vocabulary they expect will do the job efficiently for the task at hand. As you say, for many things this is absolutely pseudocode! But I've also been in situations where mathematics, or the many Greek letter transformations of Haskell, or something else was the vocabulary of choice. As the projects I've worked on have grown more complex and occasionally abstract, pseudocode has increasingly not been the go-to answer.
Again, you're completely right. It's a major issue that medical professionals often lack a real understanding of how a given pharmaceutical works. It's one that is in dire need of addressing!
I also think medical professionals have this shared assumption that they can talk about anatomy and physical processes with one another to communicate effectively and precisely, rather than "the bone next to the other bone next to the chompy thing". Especially when on a chart and the other professional isn't nearby to ask. That's shared vocabulary at work. I've certainly struggled to have architectural discussions with people with whom I shared little vocabulary. I'm sure the failing was entirely mine.
You're completely right. There's a lot here and pseudocode is incredibly powerful! I find it worth considering that there might be value to be gained in shared vocabulary beyond that one tool. Your mileage may of course vary.
Thank you kindly for the opportunity to better explain my points.
But medicine once you get to application of drugs rather than anatomy (setting bones, surgery) crosses over into another domain: chemistry, and at it's lowest level chemistry in turn is physics. Doctors need to know how to diagnose an issue (which often involves other disciplines within medicine for instance radiology), and then what particular medication or procedure to prescribe to solve the problem. The implementation details of that medication are not that important until you get to side effects, akin to how a programmer might select a library to perform a certain function.
How can a self-taught individual such as myself begin to learn the theory presented in the academic computer science world without enrolling in a college or university?
If talking about physically going to university or college, take a class online.
If you don’t want classes in general, go to course sites for universities and check the textbooks they use/reference.
If you don’t want classes in general, go to course sites for universities and check the textbooks they use/reference.
to add a term...
they have professionalized.
With licensure, required training, standards, codes of ethics, legal recognition by government actors, etc.
they have professionalized.
With licensure, required training, standards, codes of ethics, legal recognition by government actors, etc.
[deleted]
> I get it that mathematical notation is nice and compact and a quick way to communicate an idea but pseudo code would quite often be more clear.
Isn't that only becuase you already know how to code, and don't know mathematical notation? I doubt looking at code for most non-programmers is that much easier than looking at mathematical symbols.
Isn't that only becuase you already know how to code, and don't know mathematical notation? I doubt looking at code for most non-programmers is that much easier than looking at mathematical symbols.
Easy things can look hard when typeset in LaTeX.
Hard things can look easy when typeset in monospace.
Hard things can look easy when typeset in monospace.
Having written some equations in LaTeX I can tell you that this can very much also be the other way around.
GATE: (Graduate Aptitude Test in Engineering. Its an entrance exam in India for Post-Graduate admissions. Considered to be one of the toughest exams)
This bring back memories. I was preparing for GATE in 2006 after getting my bachelors. Actually started preparing from 2004. I was so bad at Automata Theory and discreet maths. I never got admitted to the prestigious IITs, but that preparation and learning was helpful later in my career when I got admitted to MS program in a US university.
This bring back memories. I was preparing for GATE in 2006 after getting my bachelors. Actually started preparing from 2004. I was so bad at Automata Theory and discreet maths. I never got admitted to the prestigious IITs, but that preparation and learning was helpful later in my career when I got admitted to MS program in a US university.
I admit that I struggled with regular languages, I didn't fail the class or anything, but as soon as I was done with it, never looked back.
I thought about doing a Turing machine in JavaScript but I never actually did it.
I wonder if people that retains all that information use it everyday, that's why they retain it. Thing I don't use in real life, like propositional logic, regular languages, automatas... I can barely remember. It's kinda sad thought, but I fill I cannot dedicate time and resources to keep this things fresh in my head.
I thought about doing a Turing machine in JavaScript but I never actually did it.
I wonder if people that retains all that information use it everyday, that's why they retain it. Thing I don't use in real life, like propositional logic, regular languages, automatas... I can barely remember. It's kinda sad thought, but I fill I cannot dedicate time and resources to keep this things fresh in my head.
But despite not using it every day, you'd probably be able to refresh on it pretty quickly.
I've found that to be the real value for a lot of the courses I took. Sure, I don't actively remember the content or use it daily, but occasionally something reminds me of something I learned. Then, it's a quick wiki page away from me understanding and using it. Contrast that with some devs I've worked with who haven't seen such things before and end up reinventing a less elegant solution to the problem.
I've found that to be the real value for a lot of the courses I took. Sure, I don't actively remember the content or use it daily, but occasionally something reminds me of something I learned. Then, it's a quick wiki page away from me understanding and using it. Contrast that with some devs I've worked with who haven't seen such things before and end up reinventing a less elegant solution to the problem.
on the interview for the job I have right now, they asked me a lot about design patterns. I took a class on that and implemented a lot of them in Java. Factory, Facade, Visitor, Singleton... Never used them again after college, ask me about it, I think I would be able to explain Factory and Singleton from the top of my head, the rest... gone!!!
I guess what I'm trying to say is that I would love to be that guy with a lot of information in the head, that can casually drop statics formulas and math concepts in a conversation, but that's not the case for my. At least for a lot of topics.
Watching the videos made me think about that. Starting a live video and answering 240 questions on several topics likes it's no big deal. Haha
I guess what I'm trying to say is that I would love to be that guy with a lot of information in the head, that can casually drop statics formulas and math concepts in a conversation, but that's not the case for my. At least for a lot of topics.
Watching the videos made me think about that. Starting a live video and answering 240 questions on several topics likes it's no big deal. Haha
You never use a Factory or Singleton? That’s weird to me cause I use them daily. But certainly Singletons can also be problematic, especially if you do automated testing, which I do not.
The use case for a Singleton is that you want to use a global variable but don't want to admit that you are using a global variable.
Here's an embedded system. It has a hardware resource. There's only one such hardware resource. A singleton to manage it is a natural.
I suppose you could argue that it's still a global variable, but I think it's more fundamental than that. You use a singleton when there should be exactly one of something. Why is there exactly one? "Because there's only one in the hardware" is a fundamentally different answer than "because it's a global variable".
I suppose you could argue that it's still a global variable, but I think it's more fundamental than that. You use a singleton when there should be exactly one of something. Why is there exactly one? "Because there's only one in the hardware" is a fundamentally different answer than "because it's a global variable".
A singleton only seems natural to you because you are used to using them.
Other programmers might reach for a global variable or a static variable for the same purpose in the same situation. The tradeoffs are pretty subtle.
However, as I said, the main reason that I have seen singletons used is programmers who heard lectures about how bad global variables are, heard about global variables, and didn't understand that every argument against a global variable also applies to a singleton.
Other programmers might reach for a global variable or a static variable for the same purpose in the same situation. The tradeoffs are pretty subtle.
However, as I said, the main reason that I have seen singletons used is programmers who heard lectures about how bad global variables are, heard about global variables, and didn't understand that every argument against a global variable also applies to a singleton.
Not entirely true, because a singleton can implement defensive logic and maintain coordination state that is difficult with a global variable. For something like a unique hardware resource a singleton that administrates the resource can do things like enforce queueing on components that want to communicate with the hardware resource, and make decisions about which components to notify when the resource responds.
I said subtle, not non-existent.
For example you tout the advantages of enforced access rules. And indeed enforcement is good for avoiding bugs from accidental concurrent access. But said enforcement also means that bugs in releasing access at the proper time are harder to recover from. I've seen systems fail both ways, and it is unclear to me which one is better. (For example I've had more problems with Windows enforcing locking in its filesystem than with bugs in Unix's advisory only locking policy.)
For example you tout the advantages of enforced access rules. And indeed enforcement is good for avoiding bugs from accidental concurrent access. But said enforcement also means that bugs in releasing access at the proper time are harder to recover from. I've seen systems fail both ways, and it is unclear to me which one is better. (For example I've had more problems with Windows enforcing locking in its filesystem than with bugs in Unix's advisory only locking policy.)
That's probably because of the use of different paradigms.
If you write typical so called OOP code all the time, sure, you'll hit many instances of this or that pattern coming in handy. If you write FP and only occasionally strew in some OOP, well, many of the patterns fly out of the window, as you do not really need then any longer, because the building block is a function and you solve most of the stuff using closures and higher order functions. Also you usually do not mutate state, so that is another load of patterns out of the window.
Surely however, it is good to know the patterns approximately well, so that you can quickly understand the meaning of code, which makes use of them. If only all people used design patterns always in a correct way, instead of implementing them half-way correct and then using them in a weird way ... Never hurts too look up the details again, before introducing a pattern into the code!
If you write typical so called OOP code all the time, sure, you'll hit many instances of this or that pattern coming in handy. If you write FP and only occasionally strew in some OOP, well, many of the patterns fly out of the window, as you do not really need then any longer, because the building block is a function and you solve most of the stuff using closures and higher order functions. Also you usually do not mutate state, so that is another load of patterns out of the window.
Surely however, it is good to know the patterns approximately well, so that you can quickly understand the meaning of code, which makes use of them. If only all people used design patterns always in a correct way, instead of implementing them half-way correct and then using them in a weird way ... Never hurts too look up the details again, before introducing a pattern into the code!
If I can, I never use the classical singleton pattern because of testability. On the other hand I use one single instance of a class if I can make use of a dependency injection framework. I prefer that over static classes which have the bad habit of getting in the way of testing.
Facade, well, that’s obvious from the name. It’s not just an OO pattern.
Visitor is a hack. You need to traverse an opaque structure but you know the types of its nodes. A simple lambda in other languages, it’s needed in (older) C++ and Java because of the single dispatch method calls. Even so, it’s not common in languages that rely on runtime typing or algebraic data types.
Visitor is a hack. You need to traverse an opaque structure but you know the types of its nodes. A simple lambda in other languages, it’s needed in (older) C++ and Java because of the single dispatch method calls. Even so, it’s not common in languages that rely on runtime typing or algebraic data types.
I actually ended up spending some time thinking about Turing machines when trying to solve a LeetCode problem.
I like to have a handful of problems that (1) have known solutions, (2) that I should be able to figure out in a reasonable time, (3) and that I should be able to make significant progress on entirely in my head. I then work on these when lying in bed trying to fall asleep, or when exercising, and similar times, and LeetCode is a good source for such problems.
The problem was given an array of integers find the smallest positive integer that is not in the array, and do it in O(N) time and O(1) space.
The O(1) space part was killing me. I just could not do it in less than O(N).
I decided to spend a while trying to prove that it could not be done in O(1) space. Presumably that would fail, but maybe if I could figure out why it failed that would also suggest how to do it in O(1) space. And thus I ended up thinking about Turing machines and other models of computation.
Except my attempts to prove it cannot be done on O(1) space seemed to succeed, so I was stumped. I spent a couple months on this stupid problem, before finally giving in and peeking at a solution.
It turns out that on LeetCode you can modify input arrays. I'm not a barbarian so I had assumed that inputs were supposed to be immutable.
I like to have a handful of problems that (1) have known solutions, (2) that I should be able to figure out in a reasonable time, (3) and that I should be able to make significant progress on entirely in my head. I then work on these when lying in bed trying to fall asleep, or when exercising, and similar times, and LeetCode is a good source for such problems.
The problem was given an array of integers find the smallest positive integer that is not in the array, and do it in O(N) time and O(1) space.
The O(1) space part was killing me. I just could not do it in less than O(N).
I decided to spend a while trying to prove that it could not be done in O(1) space. Presumably that would fail, but maybe if I could figure out why it failed that would also suggest how to do it in O(1) space. And thus I ended up thinking about Turing machines and other models of computation.
Except my attempts to prove it cannot be done on O(1) space seemed to succeed, so I was stumped. I spent a couple months on this stupid problem, before finally giving in and peeking at a solution.
It turns out that on LeetCode you can modify input arrays. I'm not a barbarian so I had assumed that inputs were supposed to be immutable.
Teaching a course on it regularly would really help keep it fresh.
I guess. I took a look at a test we have to take here in Brazil, if I want to get a master's degree. no way I can score high enough without studying for a few weeks. Calculus, statics, propositional logic...
When looking at the test I thought "man, I learned this in college, I should know that" but my brain was like "forget that, let's watch something funny on youtube"
When looking at the test I thought "man, I learned this in college, I should know that" but my brain was like "forget that, let's watch something funny on youtube"
this is my major complaint with interviewing "it's so easy, you just have to study it"
My CS exams in Europe and Australia involved calculations, proving stuff and applying knowledge to find the solution without a list of possible answers. Multiple choice questions at this level have always confused me and seemed like a really inept way of testing understanding (if they test understanding at all).
I was fully expecting to see an implementation of a red-black tree, the use of software patterns, questions of why a certain solution was picked or what algorithm to pick and why, creating a circuit with logic gates that fulfill a certain function, etc.
This all seems more like a test of memory. "Do you remember exercise XXX on page YYY? Great, now pick the correct solution!". Him saying "I remember the solution to this from one of my earlier videos" even confirmed my bias against these things.
I was fully expecting to see an implementation of a red-black tree, the use of software patterns, questions of why a certain solution was picked or what algorithm to pick and why, creating a circuit with logic gates that fulfill a certain function, etc.
This all seems more like a test of memory. "Do you remember exercise XXX on page YYY? Great, now pick the correct solution!". Him saying "I remember the solution to this from one of my earlier videos" even confirmed my bias against these things.
Yeah, but that's much harder to grade.
The main benefit of multiple-choice is that grading is instant. There is no ambiguity, no half points.
I completely agree that tests like this should not exist, but sadly they do. Even in Europe bachelor's courses seem to be slowly shifting towards this.
The main benefit of multiple-choice is that grading is instant. There is no ambiguity, no half points.
I completely agree that tests like this should not exist, but sadly they do. Even in Europe bachelor's courses seem to be slowly shifting towards this.
Likely to do with the number of students taking the test. As N, number of students taking the test, grows - it just makes more sense to use a form which is easy to automatically grade.
I'm not how sure how many students are taking these test, but given that it's in India, we're probably talking about tens to hundreds of thousand students.
I'm not how sure how many students are taking these test, but given that it's in India, we're probably talking about tens to hundreds of thousand students.
This is an awesome video and I'd love to see more content like this. I love watching experts explain how they think
I don’t see how anyone can both solve and explain their solutions in such record time. I can’t imagine there is much explaining happening.
Why guess about the content here? It’s freely available to watch, so we don’t need to speculate.
He briefly explains his reasoning for each answer.
He briefly explains his reasoning for each answer.
We had a quite strong formal / theoretical community in our cs department, and besides really enjoying automaton theory in my later studies, it kind of formed an understanding of the practical side of researching algorithmic questions like "how to fit multiple circles into one bigger circle to maximize their combined diameter", as a reservoir of solutions you could later abstract your less abstract cs problems to.
That kinda answers the question many students have whether the professors can solve the problems they put on exams in the allocated time.
The usual rule of thumb is that if the professor can do the test in 20 minutes, it is probably appropriate for an hour for the kids.
As a graduate student I found that to be true.
As a graduate student I found that to be true.
Seems like a lot of people have converged around that.
I had a professor in my undergraduate mechanical engineering classes who used a 4x rule for his exams -- he had to be able to do it in 15 minutes, we had an hour.
I had a professor in my undergraduate mechanical engineering classes who used a 4x rule for his exams -- he had to be able to do it in 15 minutes, we had an hour.
Great effort by the professor and a very helpful thing that he published it all to YouTube. But to me all the content was garbled snafu.
This man was an INCREDIBLE BOON to me when I was studying Theoretical Computer Science just last semester. Awesome resource. Thank you Easy Theory!
He has another channel where he posts things that mainly pertain to Sipser's Computation. You can find it here: https://www.youtube.com/c/RyanDougherty/videos
He has another channel where he posts things that mainly pertain to Sipser's Computation. You can find it here: https://www.youtube.com/c/RyanDougherty/videos
You don't have to pass GATE in order to write a compiler, parser, etc. In fact I'd venture to guess that many of the most famous programmers of compilers and creators of new languages (e.g. Larry Wall) couldn't pass the GATE exam. So don't feel bad if you don't understand any of the math, I'd rather learn by programming and then learn the math to explain it as I go along.
I’d argue that if PhDs in CS where the only ones creating compilers you’d see less bugs and way more theoretical work being done before starting a project. Now it’s scrum galore and everything goes.
I'd venture you'd see less bugs because there would be drastically less code out there.
Yeah, that too.
Agree. Math isn't as important, but things one doesn't fully grasp 'just programming' are things like internal language management (eg: garbage collection, speed difference in different algos, pointer impacts [lang dependent], call outs to other libraries, etc)
"Just throw more EC2 units at it" (which is fine and I agree with) - until a Node Js API handles 100 req/s in prod.
"Just throw more EC2 units at it" (which is fine and I agree with) - until a Node Js API handles 100 req/s in prod.
As a math professor, I'm amazed that our students learn to answer exam questions about damped, driven systems without internalizing anything about the idea. Now, our pandemic is a damped, driven system and no one gets it.
I love multiple choice. I aced Regents exams in high school by borrowing old study guides to memorize the missing half of the corpus. I recently had a great time taking the Triplebyte quiz inebriated. So I was gearing up to trying to keep up with this guy.
Question 1, bam! B. Needs infinite memory, regularity is a finiteness condition. I read it first because it was shortest, didn't even look at the other choices. Show me question 2! What? He's still talking?
I understand the pumping lemma, but here it's a technical way to solve the problem under general anesthesia. I guess math isn't alone at failing to teach what things really mean.
I never got to question 2, I got bored.
I love multiple choice. I aced Regents exams in high school by borrowing old study guides to memorize the missing half of the corpus. I recently had a great time taking the Triplebyte quiz inebriated. So I was gearing up to trying to keep up with this guy.
Question 1, bam! B. Needs infinite memory, regularity is a finiteness condition. I read it first because it was shortest, didn't even look at the other choices. Show me question 2! What? He's still talking?
I understand the pumping lemma, but here it's a technical way to solve the problem under general anesthesia. I guess math isn't alone at failing to teach what things really mean.
I never got to question 2, I got bored.
A bit unfair to treat it as a race. He's talking through the problem for the benefit of the audience. If he was just thinking like you were (not speaking) I'm sure he'd go faster.
Regarding question 1: what if L is a very simple regular language? For example, if L is the empty language (which is regular), then option B is again the empty language (and thus regular).
While B is the best choice among those provided, the question is poorly written.
While B is the best choice among those provided, the question is poorly written.
Academia was not initially tasked with the purpose of preparing students for careers in industry. Academic interests are purely that: academic. They serve no intended purpose necessarily beyond their contribution to knowledge, understanding, and often the enjoyment of academics. In some cases, there is overlap between concepts of interest to academics and those in industry. However, to expect an undergraduate degree in an academic discipline, such as computer science, to prepare you for the needs of modern industry is to confuse the priorities and values of academia and industry. You can raise the question of, 'should this be the case?' and of course the answer will vary across fields, academics within fields, and students too. However, I would suggest that it may be an error to value the profit-driven needs of the industrial world to those of the academic world, which veer closer to having a value derived from the intrinsic nature of knowledge itself. If you want a school to teach you how to solve problems for Google or Facebook, I don't believe such a school should come at the cost of replacing the function and values of academia itself; perhaps some fields/departments in academia should extend study and degrees in the direction of industry-motivated study or new schools should open with such a focus. But don't be confused with your expectations that academic study should provide any tangible value in a capitalistic world.
This is a good comment, but I suggest you make some paragraphs! It's a bit hard to parse atm.
To add on to what you said, many academics pursue knowledge for its own sake. In many cases, especially in theory, the value of new knowledge may not be known at the time of its discovery.
For example, the multi armed bandit problem was formalized by Herbert Robbins in the 50s. It was almost universal declared a negative result. Now, bandit algorithms are classified as some of the most commercially succesful applications of machine learning algorithms (ad placement, recommendation, experimental design), and the corresponding techniques used in the formal analysis of bandit algorithms are widely used in 'non-bandit' settings (see ICML's test of time award this year).
It always saddens me to see negative comments about academics & ignorance about 'the point' of academia.
To add on to what you said, many academics pursue knowledge for its own sake. In many cases, especially in theory, the value of new knowledge may not be known at the time of its discovery.
For example, the multi armed bandit problem was formalized by Herbert Robbins in the 50s. It was almost universal declared a negative result. Now, bandit algorithms are classified as some of the most commercially succesful applications of machine learning algorithms (ad placement, recommendation, experimental design), and the corresponding techniques used in the formal analysis of bandit algorithms are widely used in 'non-bandit' settings (see ICML's test of time award this year).
It always saddens me to see negative comments about academics & ignorance about 'the point' of academia.
Automata allow us to rigorously argue about computation based on the simplest machines we can conceive of. If you can not make strong claims about automata, then you have no chance of making strong claims on "real world" (whatever that is) machines.
As a non-computer science person, I feel very dumb right now. :-(
As a guy who graduated in comp sci I feel even dumber right now. :(
edit: cause I don't remember much of this stuff.
edit: cause I don't remember much of this stuff.
There are two big reasons you have trouble recalling a piece of information about your craft:
You use it so much that it is down to intuition, or you never use it at all.
For example, my relationship to Orders of Complexity has been reduced to sorting options in my head, and picking the first one that is simple enough to keep working, and fast enough to satisfy the current and estimated future scope of the problem (which is also intuitive Capacity Planning).
If you make me explain the decision it might sound like I picked one at random.
You use it so much that it is down to intuition, or you never use it at all.
For example, my relationship to Orders of Complexity has been reduced to sorting options in my head, and picking the first one that is simple enough to keep working, and fast enough to satisfy the current and estimated future scope of the problem (which is also intuitive Capacity Planning).
If you make me explain the decision it might sound like I picked one at random.
You actually have sorted in your career?
Quite a bit. Lots of data has ranks/priorities, lots of UI has to be organized.
Are you asking if I have written (shipped) a sort implementation? Only once, ages ago. No built-in stable sort, and none of the dozen articles I found had examples that scaled past 20 elements (which I found quite upsetting). I did my own port of mergesort that was almost 2 orders of magnitude faster. Constant complexity kills.
It's good to build a few on your own to become an informed consumer. Just don't 1) ship it or 2) use it as an interview question. If you want NIH people, you get them by asking NIH questions during the interview process.
Are you asking if I have written (shipped) a sort implementation? Only once, ages ago. No built-in stable sort, and none of the dozen articles I found had examples that scaled past 20 elements (which I found quite upsetting). I did my own port of mergesort that was almost 2 orders of magnitude faster. Constant complexity kills.
It's good to build a few on your own to become an informed consumer. Just don't 1) ship it or 2) use it as an interview question. If you want NIH people, you get them by asking NIH questions during the interview process.
An exam was three problems, three hours, 33% of your final grade. That was my experience in CS algorithms. Lots of students switched majors because of that class.
These...don't seem that hard? I mean I just took a class on Theory of Computation but I did pretty poorly in it and stopped paying attention when we switched to online. Most of these seem to be CFG/RE questions with fairly simple answers. I'd expect some more challenging stuff with constructions from a graduate entrance exam.
I only went through the first ten or so questions so far (will do more later cuz it's neat stuff) but yeah, all if this was covered in a single semester of automata in my undergraduate. Although, maybe a graduate entrance exam isn't supposed to test much more than what you learn during the course of undergraduate classes.
Seeing how the top 2 comments present completely opposing views, now I just HAVE to watch this.
I don't mean to toot my own horn too much here but I'm ecstatic to see how much of my cramming and memorization in college seems to have actually crystallized. I'm doing better than I thought I would have on these as I follow along.
[deleted]
Anyone know if these questions are freely available?
https://gateoverflow.in/categories
Questions are categorized based on the subjects, I used this while preparing for GATE in 2015/2016.
Questions are categorized based on the subjects, I used this while preparing for GATE in 2015/2016.
Thank you. I was unclear. I meant licensed under some Free license. (I'm writing a Theory of Computation book that is Free and incorporating some of this material is attractive.)
The web site for IIT Delhi didn't say, that I could find.
The web site for IIT Delhi didn't say, that I could find.
From link in video description https://pyq.ravindrababuravula.com/subject/
This page has a list of questions but not a license statement.
Skimming through the pages on the video, it shows vividly how far away academia is from real life problems.
I'm biased, but this perspective hits a pet peeve for me. These are introductory theory of computation problems - of course they aren't real-life problems! Would we make the same complaint against a mathematics exam on group theory or real analysis? Does a question like "prove that the kernel of a homomorphism is a normal subgroup" show how far academia is from real-life problems? But probably the people responsible for inventing half the technology we use in daily life had to solve that problem at some point and R&D departments would be scared to hire them if they hadn't.
Knowledge, especially in mathematics, is not a buffet; it's a pyramid. Wecan't hope for society to build programming languages like Haskell or Rust without teaching people the knowledge base that rests on regular languages and pushdown automata and so on.
That said, this is definitely one of the most esoteric topics in an undergrad CS curriculum and many universities are making it optional, for theory-inclined students only.
Knowledge, especially in mathematics, is not a buffet; it's a pyramid. Wecan't hope for society to build programming languages like Haskell or Rust without teaching people the knowledge base that rests on regular languages and pushdown automata and so on.
That said, this is definitely one of the most esoteric topics in an undergrad CS curriculum and many universities are making it optional, for theory-inclined students only.
I guess this is a bit like the Someone Else's Problem phenomenon. Nobody needs to know about compilers, operating systems or analysis of algorithms because Somebody Else will deal with those things.
Are they really, though?
I've followed a few courses on this, and they all focus on the mathematical background of it. Sure, it's neat to be able to prove some stuff about a toy language, but what does it really teach you?
"Regular expressions" in most programming languages are not regular. A lot of programming languages aren't even context-free. Heck, C++ templates are Turing complete! Does anyone care? Not really. It works, and unless you intentionally abuse it, it's not even that painful to use.
Meanwhile in academia, the parser is automatically generated from its EBNF definition using an algorithm proven to be optimal, but when you try to compile anything containing syntax errors it's either crash, infinite loop, or dump a completely gibberish error message.
I really get the feeling that a large part of academia is busy inventing their own problems to solve. From my experience, they are extremely bad at teaching how to solve real problems.
I've followed a few courses on this, and they all focus on the mathematical background of it. Sure, it's neat to be able to prove some stuff about a toy language, but what does it really teach you?
"Regular expressions" in most programming languages are not regular. A lot of programming languages aren't even context-free. Heck, C++ templates are Turing complete! Does anyone care? Not really. It works, and unless you intentionally abuse it, it's not even that painful to use.
Meanwhile in academia, the parser is automatically generated from its EBNF definition using an algorithm proven to be optimal, but when you try to compile anything containing syntax errors it's either crash, infinite loop, or dump a completely gibberish error message.
I really get the feeling that a large part of academia is busy inventing their own problems to solve. From my experience, they are extremely bad at teaching how to solve real problems.
Academic research and education is normally focused on silo'd content and not holistic system design. To use your example, a parser that gracefully handles bad input is a completely different region of study than simple parsing/grammars. It's outside the context.
That does not mean that academia does not cover the topic, you just probably wouldn't get to it in an undergraduate course on (frankly trivial) compilers and parsers. If you read into research on things like semantic fuzzing, the slow death of batch compilers, and the various error propagation mechanisms out there from PL researchers you'd see those topics bring up lively academic discussions.
Academia lags in many ways behind practical designs because they aren't governed by deadlines and market realities, but they lead in many others precisely because ideas aren't constrained and they can focus on things that don't have immediate value to markets. It's not wise to discount an entire domain of expertise and culture of development just because it exists in a different context than professional engineering, particularly when we owe our entire industry to the efforts of academics in the first place.
That does not mean that academia does not cover the topic, you just probably wouldn't get to it in an undergraduate course on (frankly trivial) compilers and parsers. If you read into research on things like semantic fuzzing, the slow death of batch compilers, and the various error propagation mechanisms out there from PL researchers you'd see those topics bring up lively academic discussions.
Academia lags in many ways behind practical designs because they aren't governed by deadlines and market realities, but they lead in many others precisely because ideas aren't constrained and they can focus on things that don't have immediate value to markets. It's not wise to discount an entire domain of expertise and culture of development just because it exists in a different context than professional engineering, particularly when we owe our entire industry to the efforts of academics in the first place.
One obvious lesson is that you shouldn't try to parse arbitrary, non-trivial HTML with regular expressions.
[deleted]
The first few problems are about regular languages which are used when writing compilers and interpreters (among other things). It might not be something that very many people need in their daily work, but they are real life problems.
I'm not sure, but I think GATE is a graduate school entrance exam.
I'm not sure, but I think GATE is a graduate school entrance exam.
Most programming languages support unlimited nesting (of parentheses, code blocks, etc.), so wouldn't they require at least a pushdown automaton?
Probably a true statement for every theoretical academic field. Yet, very mysteriously the obscure academic problems have produced our great wealth of technology. I find this fascinating.
Except they haven't, mostly internalized (sometimes stolen) and formalized achievements of free risk takers, who don't bother writing textbooks.
The idea that academia is "risk-free" is frankly hilarious, given the state of the academic job market and the pay lines for most grants.
How did we get the atom bomb and the internet?
Internet story is mostly a fairytale, specifically modern stupidity of "fathers" shows this. They were just riding on the wave of something that everyone were experimenting with at that time.
A-bomb was about pulling some people away from academia, not building it by academia.
"Built by academia" result is something we can see with colliders.
A-bomb was about pulling some people away from academia, not building it by academia.
"Built by academia" result is something we can see with colliders.
Next time we need a project the size of A-bomb, we might also pull some people from academia and industry. Then they will take some obscure area of research on Prevalence of Memetics in Mating Habits of Extinct Species of Dung Beetles done 50 years ago by an old fart with tenure (and his 20 underpaid grad students) and build a psychodelic control system that can quickly and efficiently enslave and zombiefy large human populations.
TLDR: you never know what you'll need in the future. The only correct way is to research everything and we need a system for that.
TLDR: you never know what you'll need in the future. The only correct way is to research everything and we need a system for that.
The perception of people in academia is that innovation is the product of knowledge. That may have been true in the US. It has been true pretty much nowhere else (not for anything else, the real world is rarely so kind as to present solutions on a plate).
Korea, to name the best example, takes education extremely seriously...and they have had severe difficulty turning that into innovation (outside the chaebols, there is basically no R&D occurring).
I would also look at the exam being tested here. This is India, a system that is notoriously reliant on rote memorisation and turning out employees who crumble under pressure and cannot operate without very specific instructions. Again, this is not a coincidence.
The source of innovation isn't knowledge by the coincidence of knowledge, creativity, and opportunity. Knowing something is quite different from being able to understand and use it. Stuff like the atom bomb are entrepreneurial triumphs by people who happened to be academics.
(The university I attended pioneered AI in the 60s, they had the DoD battering down their door...they refused every opportunity, and doubled down in the ivory tower. Result? No serious innovation since the 60s, and most PHd students going elsewhere to do "real work". This kind of thing just doesn't happen in the US but is the most common result outside of the US.)
Korea, to name the best example, takes education extremely seriously...and they have had severe difficulty turning that into innovation (outside the chaebols, there is basically no R&D occurring).
I would also look at the exam being tested here. This is India, a system that is notoriously reliant on rote memorisation and turning out employees who crumble under pressure and cannot operate without very specific instructions. Again, this is not a coincidence.
The source of innovation isn't knowledge by the coincidence of knowledge, creativity, and opportunity. Knowing something is quite different from being able to understand and use it. Stuff like the atom bomb are entrepreneurial triumphs by people who happened to be academics.
(The university I attended pioneered AI in the 60s, they had the DoD battering down their door...they refused every opportunity, and doubled down in the ivory tower. Result? No serious innovation since the 60s, and most PHd students going elsewhere to do "real work". This kind of thing just doesn't happen in the US but is the most common result outside of the US.)
For what it's worth, I currently have the top comment in the thread defending the point of computer science. I'm an undergrad studying in India.
My exams in college have not been about rote memorization. I've written quite a bit of code, and taken down quite a bit of notes for them. It totally depends on where someone studies in India. I do concede that the vast majority of college in India outside the "top 20" or so do seem to rely heavily on rote memorization.
- My notes taken for university: https://github.com/bollu/notes
- Code I wrote for university: https://github.com/bollu/IIIT-H-Code
> Stuff like the atom bomb are entrepreneurial triumphs by people who happened to be academics.
This seems like an odd position to defend. The mathematics that was necessary to even begin this line of investigation was worked out in academia by pure mathematicians and theoretical physicists. The "steelman" version of your argument I would phrase as thus:
> Academia does not have the incentive and funding structure to pull of projects such as the Manhattan project, and thus had to occur as a government project with unlimited funding.
I will gladly accept this. Unfortunately, it's not just academia that suffers from this. I don't think a lot of startups do useful research either. Most of the "original research" that I am aware of occurs at extremely well funded government labs, or lately the large tech companies that are pouring billions into AI.
My exams in college have not been about rote memorization. I've written quite a bit of code, and taken down quite a bit of notes for them. It totally depends on where someone studies in India. I do concede that the vast majority of college in India outside the "top 20" or so do seem to rely heavily on rote memorization.
- My notes taken for university: https://github.com/bollu/notes
- Code I wrote for university: https://github.com/bollu/IIIT-H-Code
> Stuff like the atom bomb are entrepreneurial triumphs by people who happened to be academics.
This seems like an odd position to defend. The mathematics that was necessary to even begin this line of investigation was worked out in academia by pure mathematicians and theoretical physicists. The "steelman" version of your argument I would phrase as thus:
> Academia does not have the incentive and funding structure to pull of projects such as the Manhattan project, and thus had to occur as a government project with unlimited funding.
I will gladly accept this. Unfortunately, it's not just academia that suffers from this. I don't think a lot of startups do useful research either. Most of the "original research" that I am aware of occurs at extremely well funded government labs, or lately the large tech companies that are pouring billions into AI.
The problem in India may be more to do with the teaching style (i.e. rote memorization does not produce understanding) than the content being taught.
And the right answer might be a combination of academics and real world application, instead of an either/or dichotomy.
And the right answer might be a combination of academics and real world application, instead of an either/or dichotomy.
Try the same for theoretical physics and the practical version of it and compare how far away those are. CS has it easy in comparison. At least you won't need to wait half a lifetime or longer to see if your ideas pan out or not.
> At least you won't need to wait half a lifetime or longer to see if your ideas pan out or not.
Or in the case of physics, wait half a lifetime to get a non-postdoc job.
Or in the case of physics, wait half a lifetime to get a non-postdoc job.
If the real life problem is to develop a programming language or compiler then these aren't far at all.
[deleted]
Learning/building compilers was the most fun part of CS curriculum.
what is GATE computer science?
Watched a bit as I never came across these terms.. Staring at the wikipedia page of "Regular language" and I still dont get what is the purpose of this.
Anyone, not in academia preferably, using this for practical applications? What ARE the practical applications?
Anyone, not in academia preferably, using this for practical applications? What ARE the practical applications?
You've probably heard of regex, also known as regular expressions. Regex is at its core (before you add support for advanced stuff like backreferences) a generic way of defining an arbitrary regular language. Each regular expression corresponds to a deterministic finite automaton (DFA) which detects strings belonging to that language.
EDIT, to add a bit more:
The theory behind regular languages allows you to design a regex system, to know its limitations and to be able to determine whether a language can be matched by a regex or it requires a more powerful model.
It can definitely be useful to think in terms of such theoretical constructs when approaching new problems, but it takes some getting used to before it can become productive. For this reason, I think the cost/benefit ratio of learning this for someone completely new to it can vary. It's probably not always worth it in all settings, but it certainly has practical merit.
EDIT, to add a bit more:
The theory behind regular languages allows you to design a regex system, to know its limitations and to be able to determine whether a language can be matched by a regex or it requires a more powerful model.
It can definitely be useful to think in terms of such theoretical constructs when approaching new problems, but it takes some getting used to before it can become productive. For this reason, I think the cost/benefit ratio of learning this for someone completely new to it can vary. It's probably not always worth it in all settings, but it certainly has practical merit.
I don't think there are a lot of direct practical applications, outside of regular expressions for string search as others have mentioned. This is a building block to more advanced topics, some of which have practical applications. Theory of designing programming languages, and computational complexity theory. For instance, these are like baby steps toward P vs NP.
DFAs are used on all kind of things, including on protocol design and implementation.
Another reason this subject is taught, besides the topics themselves, is that it develops your logical reasoning, abstraction, and visualization muscles. For example the first problem, he has to argue that L concatenated with L-reversed is regular, and he uses general properties of regular languages to do it. Then to argue the prefix and suffix parts, he has to utilize the automaton for L by making copies of it and drawing transitions between them. A final example is the famous and dreaded "pumping lemma" that gives practice understanding alternating quantifiers: there exists a such that for all b, ....
I am impressed by this, however.. is this not a case of a Human training to act like a computer, and then doing it really well? There is something off about that part.
I haven't checked the questions carefully, but in general classifying the kind of language I believe is undecideable, so the video could be showing a human doing something computers in general cannot do.
It seems like a common misconception that humans have some secret power to solve undecidable problems that computers lack. But "this problem is undecidable in general" doesn't mean "computers cannot solve small instances of the problem", it means "there's no single algorithm that will correctly solve all instances of this problem". Typically undecidability results in language theory rely on embedding a Turing machine in the language and going "Turing machines halting is undecidable, therefore this is undecidable in general". But this only tells you that _some_ problem instances are undecidable (at least those that correspond to Turing machine embeddings, and probably many more). Smaller problems (that aren't big enough to be disguised Turing machines) can still be decidable, and I suspect that any problem simple enough to happen in an exam is decidable.
Another example of this: theorem-proving is undecidable, yet automated thoerem provers are definitely capable of solving simple problems. The undecidability result means that any given automated theorem provers isn't capable of proving the truth/falsity of all statements. But this isn't some crazy limitation - this is true of humans as well. You can solve some math problems, but if someone showed up with an exabyte-long statement about how a problem-solver-who-is-identical-to-you-in-every-capability solves problems and asked you to prove it, obviously you wouldn't be able to do that.
Another example of this: theorem-proving is undecidable, yet automated thoerem provers are definitely capable of solving simple problems. The undecidability result means that any given automated theorem provers isn't capable of proving the truth/falsity of all statements. But this isn't some crazy limitation - this is true of humans as well. You can solve some math problems, but if someone showed up with an exabyte-long statement about how a problem-solver-who-is-identical-to-you-in-every-capability solves problems and asked you to prove it, obviously you wouldn't be able to do that.
What I said is compatible with what you say.
Not true, he skipped a few after giving up. Title should be, Professor TRIES to solve 240 computer science exam problems.
At least in the fields where I work [compilers, formal verification], all of the above theory is common parlance. Everyone working on this stuff knows all of the above theory, since it forms the bedrock of a large part of what we do and how we think about the world. Knowing the complexity of the algorithms we use, the languages we parse, issues of decidability, etc. all crop up. That's because it's science, not engineering. GATE is meant as an entrance exam to pursue a graduate degree in computer science.
The fact that one does not need this during their day job is, dare I say it, irrelevant. This feels to me like people complaining that number theory is completely useless in the 19th century; Indeed it was... until it wasn't, and we needed cryptography.
This stuff is useful right now in a 'how to think about the world' kind of way. Knowing the power differences between automata, transducers, push down automata, and turing machines is critical in disparate applications involving formal verification. The difference in power of these different representations impacts what we can "do" with them. The knowledge of this hierarchy fundamentally shapes how I view the world.