Professor solves 240 computer science exam problems in 4 hours [video]

https://www.youtube.com/watch?v=g_ZdcHSFGv0&t=10s

by ryandougherty • 6 years ago

307 166 6 years ago

kylebenzle• 6 years ago

Not true, he skipped a few after giving up. Title should be, Professor TRIES to solve 240 computer science exam problems.

mrspeaker• 6 years ago

It goes up to Question 247.

elygre• 6 years ago

Didn’t watch far, but got to the point where he said there were 247 questions. So maybe he skipped seven?

ksj2114• 6 years ago

This is an awesome video and I'd love to see more content like this. I love watching experts explain how they think

ComputerGuru• 6 years ago

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.

freyr• 6 years ago

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.

mv4• 6 years ago

Seeing how the top 2 comments present completely opposing views, now I just HAVE to watch this.

hawk_• 6 years ago

what is GATE computer science?

reubenmorais• 6 years ago

https://en.wikipedia.org/wiki/Graduate_Aptitude_Test_in_Engi...

coderthrow• 6 years ago

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.

yters5• 6 years ago

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.

jacb• 6 years ago

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.

jimhefferon3• 6 years ago

Anyone know if these questions are freely available?

har33sh• 6 years ago

https://gateoverflow.in/categories

Questions are categorized based on the subjects, I used this while preparing for GATE in 2015/2016.

jimhefferon3• 6 years ago

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.

aks_tldr• 6 years ago

From link in video description https://pyq.ravindrababuravula.com/subject/

jimhefferon3• 6 years ago

This page has a list of questions but not a license statement.

kdtop• 6 years ago

As a non-computer science person, I feel very dumb right now. :-(

racl101• 6 years ago

As a guy who graduated in comp sci I feel even dumber right now. :(

edit: cause I don't remember much of this stuff.

hinkley2• 6 years ago

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.

juskrey4• 6 years ago

Skimming through the pages on the video, it shows vividly how far away academia is from real life problems.

criddell• 6 years ago

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.

dlubarov• 6 years ago

Most programming languages support unlimited nesting (of parentheses, code blocks, etc.), so wouldn't they require at least a pushdown automaton?

yters5• 6 years ago

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.

juskrey4• 6 years ago

Except they haven't, mostly internalized (sometimes stolen) and formalized achievements of free risk takers, who don't bother writing textbooks.

globular-toast• 6 years ago

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.

juskrey4• 6 years ago

The fact that writing compilers is an academic fetish does not imply that compilers are written by academics.

crote2• 6 years ago

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.

bo10244• 6 years ago

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.

jacquesm5• 6 years ago

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.

jackcosgrove• 6 years ago

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.

DavidVoid• 6 years ago

That's not necessarily a bad thing. This is Computer Science and not Computer Engineering after all.

zerr• 6 years ago

I bet you haven't watched the first lecture video of SICP :)

paxys• 6 years ago

If the real life problem is to develop a programming language or compiler then these aren't far at all.

atum473• 6 years ago

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.

gnusty_gnurc• 6 years ago

this is my major complaint with interviewing "it's so easy, you just have to study it"

kevmo314• 6 years ago

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.

atum473• 6 years ago

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

bo10244• 6 years ago

Teaching a course on it regularly would really help keep it fresh.

atum473• 6 years ago

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"

tzs2• 6 years ago

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.

forgotpwd16• 6 years ago

That kinda answers the question many students have whether the professors can solve the problems they put on exams in the allocated time.

btilly4• 6 years ago

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.

euler_angles• 6 years ago

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.

120bits• 6 years ago

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.

LockAndLol• 6 years ago

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.

crote2• 6 years ago

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.

TrackerFF• 6 years ago

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.

dazhbog2• 6 years ago

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?

feanaro• 6 years ago

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.

bo10244• 6 years ago

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.

bo10244• 6 years ago

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

dependenttypes• 6 years ago

DFAs are used on all kind of things, including on protocol design and implementation.

bollu3• 6 years ago

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

dazhbog2• 6 years ago

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?

bachmeier• 6 years 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.

cycrutchfield• 6 years ago

Yeah! And why come we gots to teach kid how to plus and minus if theys just gonna be a plummer?

foepys• 6 years ago

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.

czbond2• 6 years ago

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.

sigstoat• 6 years ago

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

ookdatnog3• 6 years ago

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.

Vervious• 6 years ago

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.

vbtemp2• 6 years ago

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

chmod775• 6 years ago

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.

m4634• 6 years ago

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.

agumonkey• 6 years ago

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'

jfkebwjsbx• 6 years ago

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.

jacquesm5• 6 years ago

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.

ookdatnog3• 6 years ago

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.

m4634• 6 years ago

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.

learc835• 6 years ago

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

prostoalex• 6 years ago

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.

chongli• 6 years ago

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.

bartwe• 6 years ago

There is a lack of a university (or above) level software engineering education that isn't aimed at computer science.

bsder• 6 years ago

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.

bollu3• 6 years ago

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.

Abishek_Muthian• 6 years ago

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

unixhero• 6 years ago

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.

sabujp• 6 years ago

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.

czbond2• 6 years ago

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.

danielscrubs3• 6 years ago

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.

cultofmetatron• 6 years ago

I'd venture you'd see less bugs because there would be drastically less code out there.

jacquesm5• 6 years ago

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?

Kalium4• 6 years ago

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.

jacquesm5• 6 years ago

But do those fields have a similar split between the language used by the theoretical and the practical side of things?

layoutIfNeeded• 6 years ago

Easy things can look hard when typeset in LaTeX.

Hard things can look easy when typeset in monospace.

contravariant• 6 years ago

Having written some equations in LaTeX I can tell you that this can very much also be the other way around.

edanm• 6 years ago

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.

nickysielicki• 6 years ago

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.

ianbooker• 6 years ago

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.

tazedsoul• 6 years ago

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.

waynecochran• 6 years ago

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.

orange3xchicken• 6 years ago

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.

hardwaregeek• 6 years ago

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.

hoten2• 6 years ago

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.

_wldu• 6 years ago

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.

Syzygies• 6 years ago

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.

hoten2• 6 years ago

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.

areyousure• 6 years ago

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.

pinacarlos90• 6 years ago

Learning/building compilers was the most fun part of CS curriculum.

beefcubebrush• 6 years ago

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

Professor solves 240 computer science exam problems in 4 hours [video]

Related Stories