[HN Gopher] Professor solves 240 computer science exam problems ...
___________________________________________________________________
Professor solves 240 computer science exam problems in 4 hours
[video]
Author : ryandougherty
Score : 175 points
Date : 2020-07-07 14:34 UTC (8 hours ago)
(HTM) web link (www.youtube.com)
(TXT) w3m dump (www.youtube.com)
| [deleted]
| kylebenzle wrote:
| Not true, he skipped a few after giving up. Title should be,
| Professor TRIES to solve 240 computer science exam problems.
| mrspeaker wrote:
| It goes up to Question 247.
| elygre wrote:
| Didn't watch far, but got to the point where he said there were
| 247 questions. So maybe he skipped seven?
| ianbooker wrote:
| 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.
| hawk_ wrote:
| what is GATE computer science?
| reubenmorais wrote:
| https://en.wikipedia.org/wiki/Graduate_Aptitude_Test_in_Engi...
| unixhero wrote:
| 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.
| coderthrow wrote:
| 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.
| yters wrote:
| 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 wrote:
| 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.
| sabujp wrote:
| 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.
| czbond wrote:
| 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.
| ksj2114 wrote:
| This is an awesome video and I'd love to see more content like
| this. I love watching experts explain how they think
| ComputerGuru wrote:
| 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 wrote:
| 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.
| LockAndLol wrote:
| 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.
| crote wrote:
| 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.
| juskrey wrote:
| Skimming through the pages on the video, it shows vividly how far
| away academia is from real life problems.
| bo1024 wrote:
| 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.
| yters wrote:
| 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.
| juskrey wrote:
| Except they haven't, mostly internalized (sometimes stolen)
| and formalized achievements of free risk takers, who don't
| bother writing textbooks.
| yters wrote:
| How did we get the atom bomb and the internet?
| juskrey wrote:
| 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.
| UnFleshedOne wrote:
| 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.
| hogFeast wrote:
| 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.)
| yters wrote:
| 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.
| mattkrause wrote:
| 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.
| DavidVoid wrote:
| That's not necessarily a bad thing. This is Computer _Science_
| and not Computer _Engineering_ after all.
| zerr wrote:
| I bet you haven't watched the first lecture video of SICP :)
| jacquesm wrote:
| 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.
| globular-toast wrote:
| 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.
| crote wrote:
| 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.
| mattkrause wrote:
| One obvious lesson is that you shouldn't try to parse
| arbitrary, non-trivial HTML with regular expressions.
| qppo wrote:
| 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.
| juskrey wrote:
| The fact that writing compilers is an academic fetish does
| not imply that compilers are written by academics.
| saagarjha wrote:
| Some are, some are not ;)
| [deleted]
| criddell wrote:
| 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.
| nickysielicki wrote:
| 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.
| atum47 wrote:
| 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.
| bo1024 wrote:
| Teaching a course on it regularly would really help keep it
| fresh.
| atum47 wrote:
| 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"
| gnusty_gnurc wrote:
| this is my major complaint with interviewing "it's so easy, you
| just have to study it"
| kevmo314 wrote:
| 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.
| atum47 wrote:
| 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
| valuearb wrote:
| 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.
| btilly wrote:
| 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.
| zelphirkalt wrote:
| 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!
| chopin wrote:
| 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.
| jimhefferon wrote:
| Anyone know if these questions are freely available?
| har33sh wrote:
| https://gateoverflow.in/categories
|
| Questions are categorized based on the subjects, I used this
| while preparing for GATE in 2015/2016.
| jimhefferon wrote:
| 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 wrote:
| From link in video description
| https://pyq.ravindrababuravula.com/subject/
| jimhefferon wrote:
| This page has a list of questions but not a license
| statement.
| mv4 wrote:
| Seeing how the top 2 comments present completely opposing views,
| now I just HAVE to watch this.
| forgotpwd16 wrote:
| That kinda answers the question many students have whether the
| professors can solve the problems they put on exams in the
| allocated time.
| btilly wrote:
| 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 wrote:
| 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.
| kdtop wrote:
| As a non-computer science person, I feel very dumb right now. :-(
| racl101 wrote:
| As a guy who graduated in comp sci I feel even dumber right
| now. :(
|
| edit: cause I don't remember much of this stuff.
| hinkley wrote:
| 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.
| jacquesm wrote:
| 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?
| Kalium wrote:
| 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.
| jacquesm wrote:
| But do those fields have a similar split between the language
| used by the theoretical and the practical side of things?
| Kalium wrote:
| 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.
| bollu wrote:
| 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.
| jfkebwjsbx wrote:
| 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.
| dazhbog wrote:
| 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?
| foepys wrote:
| 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.
| cycrutchfield wrote:
| Yeah! And why come we gots to teach kid how to plus and minus
| if theys just gonna be a plummer?
| zelphirkalt wrote:
| 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?
| Jtsummers wrote:
| 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.
| sigstoat wrote:
| > 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...
| ookdatnog wrote:
| 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.
| czbond wrote:
| 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.
| bachmeier wrote:
| > 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.
| jacquesm wrote:
| 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.
| bsder wrote:
| > 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.
| bollu wrote:
| 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.
| vbtemp wrote:
| 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...
| m463 wrote:
| 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.
| chmod775 wrote:
| 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.
| m463 wrote:
| But loop variables are always i, j and k.
| ookdatnog wrote:
| 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.
| learc83 wrote:
| 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).
| walty wrote:
| What do you do professionally? How do you use automata
| there?
| m463 wrote:
| 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.
| vkou wrote:
| 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.
| prostoalex wrote:
| 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.
| dazhbog wrote:
| 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 wrote:
| 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.
| bo1024 wrote:
| 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.
| dependenttypes wrote:
| DFAs are used on all kind of things, including on protocol
| design and implementation.
| bo1024 wrote:
| 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, ....
| 120bits wrote:
| 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.
___________________________________________________________________
(page generated 2020-07-07 23:00 UTC)