I got the following question in an email.
My nephew is currently in high school in China and has developed a strong interest in computer science and mathematics. Recently, we've been talking about how computers can solve incredibly complex problems, yet there are still some problems that even the most powerful computers struggle to handle efficiently. I work in backend data maintenance myself, so I often think about how much a system's performance depends on the way a problem is approached, rather than simply how powerful the technology is.
From your experience, what do you think is the most important thing a young student should understand about the limits of what computers can do? Would you encourage someone like my nephew to begin exploring these questions through mathematics and logical reasoning, or to start by writing programs and discovering the challenges through practice?
A great question with no perfect answer. For me, I did considerable programming in high school and college in the early days of personal computers. Computers were slow so you really had to optimize. I learned new algorithmic techniques mostly from talking to other programmers and there were some problems that the computers just didn't have enough time to solve. Those experiences definitely helped me have a good understanding of the power of good algorithms and the limitations of computing when I later went into theoretical computer science.
But many of my colleagues successfully went into the field from the mathematical side without much programming experience and did fine.
My experience comes from a different time. Now computers are much faster and AI can just give you the best known algorithms. We have much better algorithms for NP-complete problems like Satisfiability. Unless you go looking for hard problems, you'll rarely hit one you can't solve.
Reminds me of when I took my daughter driving during a snow storm to teach her how to handle a skid. In an empty parking lot I told her to move fast and hit hard on the brakes. The car just stopped. She failed to learn because of anti-lock brakes.
Ultimately, to learn why some problems are hard, you need to understand some theoretical computer science, particularly why the halting problem is impossible to solve and why NP-complete problems are likely hard. How you get there depends on the person.
If your nephew likes to program, you can give him the challenge of trying to solve some SAT competition problems or solving some of the hard LeetCode problems. If he is more into mathematics, ask him to try to come up with a SAT algorithm mathematically so he understands how hard the problem is. The difference today is that you have to search out hard problems as it's just less likely to run into them naturally.
When I was in high school, one of our Pascal programming assignments was a version of Travelling Salesman, with like 5 cities, set in the Star Wars universe.
ReplyDeleteI thought I'd found a fast way to do this! and excitedly told my teacher. He sort of looked at me, and said something like, "Why don't you write the program, and try running it?"
I did so (on an Apple II), and eventually realized that I had rediscovered... nested for loops.
Which was an efficient way of implementing the naive solution (for a limited number of cities). But obviously not super-fast in general...
I think this was good teaching, as it did make clear what the naive solution was.
I thought no one understands complexity which is why P vs NP, several people getting internet access etc.
ReplyDelete"you have to search out hard problems"
ReplyDeleteReally.
The other day I saw a number theory problem that wasn't immediately obvious (to me), and coded it up in Python. My estimate of how fast it'd be was several orders of magnitude low. (And it took an age to figure out when to output values to see how they were changing without zillions of lines of numbers scrolling by ridiculously fast.)
Sheesh. And people keep saying Python is slow. ROFL.
I coded up an Othello program (in C) back in the mid-1990s (or so) as peecees were getting faster, mostly to see how to code the Alpha-Beta algorithm. Also a Conway's life program (using one bit per cell and adding up neighbors in parallel (i.e. 3 32-bit words encoded 32 3-bit adders). Said Life program lived in a DOS emulator and spat bits to the video controller. Windows NT put the kibosh on that, and every time I look at "graphics" things nowadays, it doesn't tell my how to do something like that.
But what would modern people find interesting? We dinosaurs would like to know...
The impression I got through cs faculty is generally students in theory are bad at programming.
ReplyDelete