When people hear the term competitive programming, they naturally think about programming contests and rankings. People who are encountering the term for the first time are just using the literal meaning, while those who are familiar with the topic think about the top competitors that they hear a lot about. But someone who is just starting to learn to solve the types of problems found in programming competitions may see things differently. In my experience, introductory problems often challenge mathematical thinking skills more than programming skills. Only a small subset of a programming language is required to solve these problems, and there’s plenty of time to look up syntax (since beginners are often not taking part in a timed competition). However, most problems (other than the very easiest ones) are structured to require mathematical thinking.
Mathematical Thinking
Stanford professor Keith Devlin teaches a Coursera course called Introduction to Mathematical Thinking. One of the principles of this course is that mathematical thinking is different from what is required to solve the math problems that students encounter in their pre-college schooling. In school math classes, students are often taught procedures, and then given problems that can be solved using those procedures. Students who are good at memorizing procedures can do well in pre-college math classes just by learning to recognize problem types and remembering the steps required to solve them.
For students in more advanced math classes, it isn’t enough just to apply procedures. Since these students often have to prove that mathematical statements are true, they need a more fundamental understanding of math topics. Mathematical thinking refers to a more advanced understanding. It is the type of thinking required of professional mathematicians and students who are pursuing a math degree. But it is also useful to students who aren’t in one of those categories, since it enables them to solve problems that don’t fit into pre-defined categories, or those which require procedures that they haven’t learned.
Learning the Procedures
The distinction between learning to thinking mathematically and learning to follow procedures is key to understanding the shortcomings of methods that are often used to teach mathematics. These methods include traditional school teaching techniques and new methods like those used by Khan Academy. In the short term, it may be easier to have students memorize the steps of a procedure than to teach them why the procedure works. In comparing these two approaches, Dr. Devlin makes the distinction between teaching and instruction. Instruction is primarily a one-way process of conveying information from an instructor to a student. Teaching is a two-way conversation between teacher and student, in which the student asks questions and the teacher responds based on the student’s specific needs in their current stage of understanding. Using this process, it’s possible for a teacher to ensure that the student knows why each step of a procedure is required.
Khan Academy
Inherent to the teaching vs. instruction distinction is the assumption that online learning platforms like Khan Academy can only provide instruction. Despite its growing interactivity, KA can’t evaluate a student’s understanding the way a human teacher can. And yet because many school classes focus on testing procedures rather than evaluating understanding, spending time on KA has a positive effect on students’ grades. Everything seems to be going well, at least until they encounter a math class that has a less test-focused emphasis.
It turns out that designing a computer system that can evaluate understanding is a hard problem. Students tend to want to outsmart the program without actually learning anything. This is an ongoing challenge for KA employees and other designers of computer-based learning programs. I’m trying to solve a slightly different (and hopefully easier) problem: how motivated autodidacts can learn the math that is required to successfully solve the programming puzzles found on competitive programming sites.
Dr. Devlin and math instructor Dan Meyer, who are both critical of some aspects of Khan Academy, both nevertheless point out that it can be useful for people who come to it with an interest in math, or the ability to learn math. That may sound like faint praise, but it’s actually good enough for my purposes. My goal is to design a learning process for people who voluntarily decide to practice programming, not students who are trapped in a classroom against their will.
It’s possible that KA offers even more than we need. Dr. Devlin believes that it’s possible for some people to use KA to achieve the “ultimate goal of mathematics education,” which he defines as follows: “faced with a real world problem whose solution requires the use of math, [some students] will, as a result of watching Khan’s videos, be able to use math to solve the problem.” Since programming puzzles generally don’t contain real-world problems, we don’t even need that much. But it’s good to hear an opinion that a KA-type learning experience can lead to this level of mastery.
When You Just Need More Math
Many students of competitive programming eventually come to a point where they could benefit from more math experience. If you don’t believe me, try working your way through Project Euler in problem order. You’ll get there eventually. In my case it only took 76 problems, but there should be enough there to challenge anyone. For contests like TopCoder and CodeForces that are less specifically focused on math, competitors may decide that there are more efficient ways to practice than getting better at math, even if it would help on some problems. But as with coding practice, there is a lot to be gained in the early stages of practicing math, before you reach the point of diminishing returns.
There are a lot of options for practicing the math that is used in programming contests. There’s something to be said for the comprehensiveness of an old-school textbook. Coursera has quite a few math courses (including Dr. Devlin’s), though no Discrete Math class yet. MIT has a discrete math class with video lectures and assignments. But for people who enjoy the interactivity of online judges and programming contests, there is something appealing about the Khan Academy experience.
Using Khan Academy
The key to using Khan Academy effectively, regardless of your age or math background, is remembering what you’re trying to learn. This can be difficult, since in many ways the site works against you. Gamification is everywhere, and the rewards are all connected to getting the right answer. So as you’re working through the procedure-oriented problems, you have to keep thinking about the underlying math that you’re trying to learn. One of many possible examples: Parabola Intuition 1.
When this question comes up, you can immediately start clicking on the + and – buttons. The first set moves the parabola up and down on the $y$-axis. The second set makes the parabola wider or narrower, and affects whether it opens up or down. The third set moves it left and right on the $x$-axis. (This is the “intuitive” explanation, of course). Mathematical intuition is an important skill to build if you want to solve problems quickly. But it’s easy to repeat numerous sets of parabola intuition problems without really thinking about what is going on in the equation, or why changing each number has the effect that it does on the graph. So as you’re solving KA problems, you have to keep reminding yourself to stop and think about what the problem is trying to teach, and not get caught up in button clicking or pattern recognition.
Back to Coding
Writing programs, especially for programming contests, inevitably involves some math. Whether it’s the basic math of calculating array positions or 2D grid movement, or the analytic geometry found in more advanced puzzles, it helps to be able to solve the math part of a problem independently of the programming problem. It’s possible to practice math and programming at the same time by doing many programming puzzles. But it’s more effective to isolate the math in order to reach the level of math ability that you’re interested in getting to, whether that level is “good enough for TopCoder,” or “good enough for Project Euler.”
(Image credits: Mathematical Association of America, Khan Academy)