Coding and Mathematics

Computer science has become one of the most sought-after courses in engineering. The promise of high-paying jobs attracts millions of students to pursue it. The demand for computer scientists has grown due to the rise of automation. A decade or two ago, most shopping, ticketing, and service-related transactions were done in person. Today, many of these tasks can be completed online without leaving home.

While many aspiring students are drawn to coding for automation, they often dislike or underestimate the importance of mathematics in computer science. One area where minimal mathematical knowledge is sufficient is website development. This is because much of web development relies on plug-and-play code or brute-force methods. A large number of software engineers, especially those working on ERP (Enterprise Resource Planning) software, are primarily involved in website development. Since these tasks are not heavily math-oriented, they tend to offer lower salaries. This often leads to disappointment among developers who expected high-paying computer science roles. In order to receive offer for well-paid jobs, one needs to have a solid mathematical foundation.

To highlight this distinction, we present example problems and multiple ways to solve them. We compare brute-force coding approaches with more efficient solutions based on mathematical analysis.

Sum of first \(N\) natural numbers

Suppose you are asked to write a code to compute the sum \(S\) of first \(N\) natural numbers. Mathematically,

\[S=1+2+3+\ldots+N\]

First approach

Consider someone without a mathematical background attempting to write a code for this problem. Their approach would be to run a loop from \(1\) to \(N\) and use a variable to calculate the sum of first \(N\) natural numbers. The solution works but the runtime of this code grows linearly with \(N\). Technically, one says that the complexity of this algorithm is \(\mathcal{O}(N)\).

Second approach

There's a mathematical result, derived by Euler which provides an expression for the sum of first \(N\) natural numbers. The result is as follows.

\[S=1+2+3+\ldots+N=\frac{N(N+1)}{2}\]

If someone knows this result, they can simply evaluate the expression on the right to compute the sum of first \(N\) natural numbers. The computation complexity of their code would be \(\mathcal{O}(1)\), which is a huge advantage when dealing with large \(N\).

Maximum number of safe knights on a chessboard

Here's another problem. Suppose someone wants to place maximum number of knights on a chessboard under the constraint that no two knights should attack one another.

First approach

The brute-force approach would involve running multiple nested loops or dynamic programming to iterate over all possible permutations. Remember that a chessboard has 64 places and each place can either have a knight or not. Therefore, total possible permutations is equal to \(2^{64}\). This would take a long time to iterate. So, brute-force approach fails for practical purpose.

Second approach

To observe a pattern in this problem, put a knight on any of the white square and check the possible squares that it can move to. You would notice that all the possible squares are black in color. This means if we keep 32 knights on 32 white squares, none of them would attack each other.

Pigeonhole principle

Consider an empty \(10\times 3\) matrix. You are asked to fill each of these cells using \(\{0,1,2,3,\ldots,9\}\) such that sum of each row is 45 and sum of each column is 15.

First approach

The brute-force approach would be to iterate over all possible values in each cell and identify the one that works. Unfortunately, this woud require you to go through \(10^{30}\) possible permutations in worst case. Therefore, brute-force is impractical for this problem.

Second approach

This is a problem that is impossible to solve. In this case, analysis prevents wastage of computational resource. The reasoning goes as follows. Sum of each row is 45. This implies that the sum of all elements in the matrix is equal to 135. Also, sum of each column is 15. This implies that the sum of all elements is equal to 150. This leads to a contradiction because the sum of all elements should be unique.

Additional resources

Read the article Mosquito gets Smashed by Two Trains: A Simple Puzzle to Demonstrate Overthinking for another example where analysis helps simplify the nature of the problem.

Author

Anurag Gupta is an M.S. graduate in Electrical and Computer Engineering from Cornell University. He also holds an M.Tech degree in Systems and Control Engineering and a B.Tech degree in Electrical Engineering from the Indian Institute of Technology, Bombay.

Comment

Past Comments

No comments yet. Be the first!