Where’s the Math in Computer Science?
Today’s guest blogger is Kenrick Mock, Associate Professor of Computer Science from the University of Alaska Anchorage. Kenrick writes a blog called Teaching, Technology, and Learning.
As a computer science instructor sometimes a student will ask me why math is required for a CS degree. At the University if Alaska Anchorage we require Calc I, Calc II, and discrete math for all of our Bachelor of Science CS majors. I think one of the reasons for this question is that there really isn’t much direct math content in the introductory CS courses aside from the occasional algebraic equation and an understanding of exponents and logarithms for the data structures course. Nevertheless, I think one of the misconceptions that students have is they equate computer programming with computer science. It is possible to be an excellent programmer with only basic math skills (one example is the Information Systems degree) but computer science is more concerned with the science behind the construction of hardware and software systems. This scientific foundation is based on mathematics. With this in mind, I’ve outlined below several ways that math is important to a budding computer scientist as he or she works their way through a CS degree.
1. Mathematical Maturity and Problem Solving
College Algebra is prerequisite for our CS1 course although we only have a little bit of direct algebra content. However, college algebra is important to develop the maturity to solve programming problems. A big part of programming (and computer science) is not the construction of code but the process of problem solving. For example, one of the problems I give in my CS1 class is to write a program that can solve the problem below,where each letter can be a digit from 0-9 and no two letters can have the same value.
Solving this problem requires more than just understanding what a loop does and how to write if-then-else statements. The student must know how to break this problem up into appropriate algorithmic steps so that a program can be written to solve each step. This type of problem solving is similar to algebraic word problems given in math classes, and some CS education researchers have suggested that students that struggle with planning and problem solving in math also struggle in CS classes. More directly related to programming, many programming languages are based on functions, a concept similar to mathematical functions. Similarly, the concept of variables and variable manipulation is also closely related to mathematical variables.
2. Computer Hardware and Low-Level Software
An understanding of Boolean algebra and various number systems (base 2, 8, 16) is critical to represent and manipulate data. Computer instructions and data are represented in binary and it is common to map values between binary, decimal, and hexadecimal. Boolean logic is necessary to understand how basic circuits (e.g. AND, OR, NAND gates) operate. Such low-level detail is often hidden by software abstractions in today’s programming languages, so it is possible to be an excellent programmer with minimal knowledge of the underlying hardware and software. However, these topics are a part of the computer science curriculum.
3. Design and Analysis of Algorithms
A programmer quickly learns that there many ways to write a program that solve the same problem. The most obvious solution is not always the most efficient. For example, sorting a list of N items using the Selection Sort algorithm requires a number of steps proportional to N2 but if the Heapsort algorithm is used then the number of steps required is proportional to N*Log2(N). This is referred to as the runtime of the algorithm. With a large list of items the difference is significant; Heapsort will run much faster. While an understanding of exponents and logarithms is all that is necessary to get the big picture, determining the runtime requires an understanding of recursion and the ability to solve summations. Here’s a sample summation that describes the runtime of one algorithm:
Solving this summation indicates that the algorithm requires a runtime proportional to n steps.
4. Computer Theory
The computer science theory course describes what is possible to compute and is closely related to discrete mathematics. Topics include finite state automata (commonly used to model the “intelligence” behind computer players in games), grammars (used to describe programming languages), and Turing machines (analogous in power to a modern computer). These tools are all mathematical in nature and often rely on inductive proofs. For example, the concept of NP-Completeness allows computer scientists to determine how “hard” a problem may be which has implications on the efficiency of possible solutions. One of my favorite examples involving grammars is the Lindenmayer System which can be visualized as a plant-like structure:
5. Elective Specializations
Various upper-division elective courses also include mathematical content. For example, in an artificial intelligence course involving neural networks (used for a variety of machine learning tasks), the output of the network is typically computed using a sigmoidal activation function, which is loosely based upon the behavior of neurons in actual brains. The function to perform the actual learning in the network is derived from taking the derivate of the error function – hopefully you still remember your calculus! Other techniques in artificial intelligence also rely heavily upon statistics.
Another example is computer networking. Data across a network is split into packets and routed from the source to destination. The routing is based on graph theory, a sub-discipline of mathematics.
The subject of a program may also require some math. This scientific research project (http://www.math.uaa.alaska.edu/~orca/
) modeled the behavior of killer whales using models based on logistic curves, probability, and non-linear differential equations.
6. Computer Graphics
Lastly, perhaps one of the best examples of math in computer science is the generation of computer graphics. Computer games are a great example. Here is a screenshot from World of Warcraft:
How is the world drawn? How can a program tell if a projectile hits a player? How can a program determine what is visible and what is not? The solutions to all of these questions are based on math, in particular, principles of geometry and linear algebra. For example, objects in real-time 3D graphics games are typically decomposed into thousands of polygons, usually triangles. These triangles are positioned, rotated, and scaled on the screen to conform to the particular 3D scene. So if you want to become a 3D game programmer, you will need to learn some advanced mathematics.
Although math may not appear to be necessary for introductory computer science classes, it is still necessary for logical thinking and problem solving. As a student progresses to more advanced computer science classes the math prerequisite becomes more apparent, especially when covering topics involving the science behind computing as opposed to programming.
Possibly Related Posts: