Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

youtube.com

Post reply on HN
Print view View original

121–130 of 173 posts

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

#121

Post by nitrogen »

Grimm1 wrote: post #119
Frost1x wrote: post #110

Earlier quoted context omitted.

For embedded systems and game development I definitely understand automata applications (from experience) but web development has me curious. Are you writing transpilers or perhaps something else (I also try to avoid web dev, so there's that).

Not OP but there are more than a few domains that can be modeled with automata, a shipping pipeline with approval steps is an example.

Ecommerce order/payment/shipping status is a good example. Anything that has a well defined state that can be changed by events is well-modeled as a state machine of some kind. Also anything that has to progress through certain steps and might be interrupted or have exception cases, and you want to proceed/retry idempotently.

Personally I have also found basic graph theory to be immensely useful for representing and reasoning about things.

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

#122

Post by nitrogen »

chongli wrote: post #108
ookdatnog wrote: post #77

Earlier quoted context omitted.

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 C…

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 an…

The fact that high school is mandatory robs it of much of its signalling value.

This will very clearly result in the same loss of signaling value for higher education.

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

#123

Post by btilly »

AnimalMuppet wrote: post #104
btilly wrote: post #71

Earlier quoted context omitted.

The use case for a Singleton is that you want to use a global variable but don't want to admit that you are using a global variable.

Here's an embedded system. It has a hardware resource. There's only one such hardware resource. A singleton to manage it is a natural. I suppose you could argue that it's still a global variable, but I think it's more fundamental than that. You use a singleton when there should be exactly one of something. Why is there exactly one? "Because there's only one in the hardware" is a fundamentally different answer than "b…

A singleton only seems natural to you because you are used to using them.

Other programmers might reach for a global variable or a static variable for the same purpose in the same situation. The tradeoffs are pretty subtle.

However, as I said, the main reason that I have seen singletons used is programmers who heard lectures about how bad global variables are, heard about global variables, and didn't understand that every argument against a global variable also applies to a singleton.

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

#124

Post by nanomonkey »

commandlinefan wrote: post #116
chmod775 wrote: post #70

Earlier quoted context omitted.

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…

> naming things There are two hard problems in computer science: naming things, cache invalidation, and off-by-one errors.

>> naming things

>There are two hard problems in computer science: naming

concurrency

>things, cache invalidation, and off-by-one errors.

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

#125

Post by Vervious »

dazhbog wrote: post #46
bollu wrote: post #43

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 o…

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…

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

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

#126

Post by tzs »

cycrutchfield wrote: post #58
dazhbog wrote: post #46

Earlier quoted context omitted.

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…

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

You aren't being serious, but that was once actually a fairly widespread sentiment. In colonial times in America, for instance, arithmetic was generally not taught in elementary school. It was something you would learn on the job if needed.

Amusingly, when it did start getting routinely taught at the end of the 18th century there were complaints from businessmen to the school boards that the methods taught in school were producing students totally unprepared for business.

For more on this, see the essay "What is Mathematics For?" by Underwood Dudley from the May 2010 Notices of the AMS [1]. (A more accurate title, he notes in the first paragraph, would be "What is mathematics education for?").

He makes some interesting points about the usual justifications that elementary and high school math are useful in your career are not really accurate.

[1] http://www.ams.org/notices/201005/rtx100500608p.pdf

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

#127

Post by projektfu »

atum47 wrote: post #34
kevmo314 wrote: post #20

Earlier quoted context omitted.

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 su…

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…

Facade, well, that’s obvious from the name. It’s not just an OO pattern.

Visitor is a hack. You need to traverse an opaque structure but you know the types of its nodes. A simple lambda in other languages, it’s needed in (older) C++ and Java because of the single dispatch method calls. Even so, it’s not common in languages that rely on runtime typing or algebraic data types.

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

#128

Post by Syzygies »

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.

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

#129

Post by yters »

jacb wrote: post #79
yters wrote: post #17

Earlier quoted context omitted.

I haven't checked the questions carefully, but in general classifying the kind of language I believe is undecideable, so the video could be showing a human doing something computers in general cannot do.

It seems like a common misconception that humans have some secret power to solve undecidable problems that computers lack. But "this problem is undecidable in general" doesn't mean "computers cannot solve small instances of the problem", it means "there's no single algorithm that will correctly solve all instances of this problem". Typically undecidability results in language theory rely on embedding a Turing machine…

What I said is compatible with what you say.

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

#130

Post by tzs »

atum47 wrote: post #14

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 barel…

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.

Post reply on HN