A Project for 2019

Discrete

Petr Mitrichev, legendary competitive programmer and current Google employee, didn’t major in computer science. He got a degree from Moscow State University in mathematics. In a Topcoder Spotlight Session in 2008, he answered a few questions about how math relates to competitive programming practice:

Mathematical Thinking

CONDOR_316: How important is math in solving problems and practicing?

Petr: I don’t know because I don’t know how it is not to know math. :)

leadhyena_inran: So your math talent also contributes to your coding skill?

Petr: I think my ‘mathy’ thinking contributes a lot, because logical puzzles are often an important part of algorithmic problems.

sam14871: Do you think the problems nowadays require more than just learning algorithms and their tweaks? If so, what other fields (e.g., math maybe) do you suggest for learning to do better these days?

Petr: Logical thinking (you can name it math, but it’s really only the basis of math).

jbernadas: My brain has a hole in the math section, and I want to fill it. Is Concrete Mathematics a good book?

Petr: I think it is, but I’m not sure it’s a cure-all.

jbernadas: But it is a good start, right?

Petr: One thing that is absolutely crucial is to be able to think ‘mathematically’.

Petr: I’m not sure how you develop that.

Despite the first comment above, it’s clear that Petr believes mathematical thinking skills are important for competitive programming success. However, he provides no advice on how to develop those skills. As he suggests, that may be because mathematical thinking is so intuitive for him that he can’t imagine what it would be like not to “know math.”

Since we’re talking about math for competitive programming, I don’t think it’s controversial to say that the way to develop mathematical thinking skill is to solve math problems. After all, solving competitive programming problems is the universally agreed-upon method for getting better at competitive programming.

But just as there are more and less effective ways to practice competitive programming problems, not all practice routines are equally valuable when solving math problems. Here are three guidelines for effective math practice:

  • Pick the right topic area. You can’t study everything at once, so focus on the broad area that aligns with your goals.
  • Focus on questions at the right difficulty level. It’s inefficient to practice with questions that are too easy or too hard, the former because you already know the material and the latter because math builds on itself. Each problem type has a prerequisite that you need to master first, so struggling with an area you’re not prepared for just leads to frustration.
  • Learn both the why and the how. When studying math through problem-solving, there’s a risk of relying too much on a cookbook approach to solving each problem type. This can lead to difficulties when you encounter problems that require a creative approach.

A New Project

In recent years, I’ve been working on year-long projects: a time tracking app in 2017, and a competitive programming FAQ in 2018. My project this year is learning math for competitive programming.

With the previous three guidelines in mind, here are more details about this year’s project:

Topic area

When people talk about math for competitive programming or computer science, they’re referring to discrete mathematics. A college class in discrete math (I have taken a few of them) might last 2-4 months. Here’s what will make this a year-long project:

  • I’ll be publishing blog posts about the project while I work on the project. In my experience, every hour of project work also requires an hour of writing, so that doubles the time requirement.
  • University classes never cover every section of a textbook, and don’t assign every problem in the sections they do cover. So there’s an opportunity to cover more breadth than a standard class.
  • Finishing a college class, even with a good grade, doesn’t require mastering a subject. You just need to know it well enough to complete problem sets and pass exams. So with more time available, there’s also an opportunity to increase depth of knowledge by learning the subject to a higher level of mastery.

Difficulty level

For K-12 math, the practice system on Khan Academy provides an effective way to manage problem difficulty level: It knows which skills are prerequisites for which other skills, so it can present problems in the right order. Within a skill, there are often multiple exercise types arranged according to difficulty. And the system keeps track of multiple levels of mastery in an exercise type, culminating in a mastery challenge.

Unfortunately, the Khan Academy curriculum doesn’t include many discrete math topics. And although there are other online resources for learning discrete math, none of them — even Brilliant, which has a discrete math section — work the same as Khan Academy. So my plan is to use textbook problems to simulate the Khan Academy system, without being able to practice discrete math problems directly on the Khan Academy site.

Learn the why

This is the hardest part of learning math by solving textbook-style problems. Textbook authors write example problems that introduce a problem-solving process, and then ask students to solve problems using that process. The more problems you solve from a textbook, the better you learn how to apply the process for each problem type. This is an effective way to succeed on problem sets and pass exams, but it can inhibit understanding.

Nevertheless, solving problems is the best way to learn math, and solving textbook problems is a prerequisite to solving more creative problems in the same area. So bypassing textbook problems isn’t an option. Instead, the key is to observe one’s thought process (practice metacognition) while solving problems. Resist the temptation to blindly follow predefined steps. Solve problems by thinking through them, not just by applying a procedure.

The Plan for 2019

Here’s the high-level plan for my discrete math project in 2019:

  • Solve a lot of discrete math problems, mainly from the textbook Discrete Mathematics and Its Applications by Kenneth Rosen. Find problems of appropriate difficulty (don’t just solve all the problems in a section). Understand the steps used to solve problems. Since I have already taken classes in this topic, I plan to use problems to find areas to focus on, rather than giving equal time to each area.
  • On the blog, I plan to write about techniques for learning math, applications of discrete math to competitive programming, interesting math problems I come across, and anything else I learn along the way.

For someone interested in algorithmic problem solving, one appeal of math is that it’s fundamental. Math problems, unlike competitive programming problems, don’t tempt the problem-solver to rush into implementing a solution, because there is no code implementation. Once you solve a math problem on paper, you’re done. In theory, you can interpret any competitive programming problem as a math problem and solve in that domain before you do any coding. No doubt there are competitive programmers with strong math skills who approach problems that way. Studying math is a way to target one aspect of the algorithmic problem-solving process in isolation, thereby building a valuable skill that many programmers don’t have.

(Image credit: Groume)