15 ms·
Professor solves 240 computer science exam problems in 4 hours [video]
- kylebenzle 6y agoNot true, he skipped a few after giving up. Title should be, Professor TRIES to solve 240 computer science exam problems.
- ksj2114 6y agoThis is an awesome video and I'd love to see more content like this. I love watching experts explain how they think
- ComputerGuru 6y agoI 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.
- freyr 6y agoWhy 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.
- mv4 6y agoSeeing how the top 2 comments present completely opposing views, now I just HAVE to watch this.
- hawk_ 6y agowhat is GATE computer science?
- reubenmorais 6y agohttps://en.wikipedia.org/wiki/Graduate_Aptitude_Test_in_Engineering https://en.wikipedia.org/wiki/Graduate_Aptitude_Test_in_Engi...
- coderthrow 6y agoI 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.
- yters 6y agoI 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.
- jacb 6y agoIt 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.
- yters 6y agoWhat I said is compatible with what you say.
- jimhefferon 6y agoAnyone know if these questions are freely available?
- har33sh 6y agohttps://gateoverflow.in/categories https://gateoverflow.in/categories Questions are categorized based on the subjects, I used this while preparing for GATE in 2015/2016.
- jimhefferon 6y agoThank 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.
- aks_tldr 6y agoFrom link in video description https://pyq.ravindrababuravula.com/subject/ https://pyq.ravindrababuravula.com/subject/
- jimhefferon 6y agoThis page has a list of questions but not a license statement.
- kdtop 6y agoAs a non-computer science person, I feel very dumb right now. :-(
- racl101 6y agoAs a guy who graduated in comp sci I feel even dumber right now. :( edit: cause I don't remember much of this stuff.
- hinkley 6y agoThere 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.
- HashBasher 6y agoYou actually have sorted in your career?
- hinkley 6y agoQuite 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.
- juskrey 6y agoSkimming through the pages on the video, it shows vividly how far away academia is from real life problems.
- criddell 6y agoThe 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.
- dlubarov 6y agoMost programming languages support unlimited nesting (of parentheses, code blocks, etc.), so wouldn't they require at least a pushdown automaton?
- yters 6y agoProbably 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.
- juskrey 6y agoExcept they haven't, mostly internalized (sometimes stolen) and formalized achievements of free risk takers, who don't bother writing textbooks.
- yters 6y agoHow did we get the atom bomb and the internet?
- juskrey 6y agoInternet 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.
- atum47 6y agoI 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.
- gnusty_gnurc 6y agothis is my major complaint with interviewing "it's so easy, you just have to study it"
- kevmo314 6y agoBut 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.
- atum47 6y agoon 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
- forgotpwd16 6y agoThat kinda answers the question many students have whether the professors can solve the problems they put on exams in the allocated time.
- btilly 6y agoThe 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.
- euler_angles 6y agoSeems 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.
- 120bits 6y agoGATE: (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.
- LockAndLol 6y agoMy 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.
- crote 6y agoYeah, 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.
- TrackerFF 6y agoLikely 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.
- dazhbog 6y agoWatched 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?
- feanaro 6y agoYou'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.
- bo1024 6y agoI 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.
- bo1024 6y agoAnother 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, ....
- deleted 6y ago[deleted]
- bollu 6y agoI need to defend theory of computer science here, it seems. Please note that this computer science, not computer engineering. The idea of automata, regular languages, turing machines, and whatnot inform some of the most fundamental results of computer science. 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.
- dazhbog 6y agoSome 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?
- bachmeier 6y ago> 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.
- unixhero 6y agoGreat 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.
- sabujp 6y agoYou 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.
- czbond 6y agoAgree. 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.
- danielscrubs 6y agoI’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.
- cultofmetatron 6y agoI'd venture you'd see less bugs because there would be drastically less code out there.
- danielscrubs 6y agoYeah, that too.
- jacquesm 6y agoInteresting 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?
- Kalium 6y agoThat'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.
- jacquesm 6y agoBut do those fields have a similar split between the language used by the theoretical and the practical side of things?
- Kalium 6y agoGenerally 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.
- nickysielicki 6y agoI 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 6y ago[deleted]
- ianbooker 6y agoWe 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.
- tazedsoul 6y agoAcademia 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.
- waynecochran 6y agoAutomata 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.
- orange3xchicken 6y agoThis 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.
- hardwaregeek 6y agoThese...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.
- hoten 6y agoI 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.
- _wldu 6y agoAn 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.
- Syzygies 6y agoAs 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.
- hoten 6y agoA 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.
- areyousure 6y agoRegarding 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.
- pinacarlos90 6y agoLearning/building compilers was the most fun part of CS curriculum.
- beefcubebrush 6y agoThis 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 https://www.youtube.com/c/RyanDougherty/videos