Application of Discrete Mathematics principles in Algorithms.
I’ve recently been doing some refresher courses on discrete mathematics by studying online resources such as Dr. Trefor Bazett’s YouTube course, which includes very broad lectures on many principles, and reading Oscar Levin’s book on the subject. I realized that the improved knowledge of logic and approaching problems with “Discrete Math Mindset” has helped improve my algorithms. I have been able to tackle harder LeetCode problems because of that. At the moment, many new developers are getting into the industry, lacking in a lot of knowledge of mathematics and logic, which used to be instrumental to getting a job in Programming. While success can still be attained without knowledge of Mathematics, I would encourage people to understand the fundamentals of building algorithms, as it deepens their knowledge of programming concepts. In the AI age, where shallow work continues to lose its value as LLMs can perform those tasks faster and with more powerful Research tools at their disposal, in-depth domain and knowledge and deep understanding of concepts will be much more favored than the ability to perform “grunt work”. Essentially, knowing how to write code is becoming less important than knowing why certain code is written.
I got into the tech space by learning HTML and CSS, and honestly, I was fortunate enough to only need that to get reliable employment. That meant my journey into the Tech industry was unusual, so I did not get the proper fundamental knowledge to truly go far in the industry. This has been made increasingly clear to me, as deep domain knowledge is being a lot more favoured in the industry. This has encouraged me to undergo a Master’s program as well and deepen my knowledge of Computer Science and Mathematics concepts.
So, for a quick introduction to Discrete Mathematics. It is a branch of mathematics that deals with discrete and countable rather than continuous and flowing variables. I like to think of it as the Mathematics of Domains and Counting. If you go through any Discrete Mathematics course, you will learn about Set theory, Truth Tables, Mathematical Induction, Permutation & Combinations, Graph Theory, and other concepts. So, in what ways can knowledge of Discrete Mathematics improve our algorithms?
-
Visualizing the relationship of the input to the output: With Set theory, you develop an understanding of representing distinct figures in domains, and if you can visualize what domain the output of a function occupies and its relationship to the input, an optimized solution can be derived more easily.
-
Mathematical Induction: This enables you to envision every iteration of a loop or recursive function as a step in a progression of steps like rungs of a ladder. This concept theorizes that if you know the answer to some step of the iteration, you can derive the formula for the next step in relation to the former step.
-
Early return and detection of bad paths: An understanding of domains and clear boundaries of inputs and outputs can reduce unnecessary computation in your algorithms.
-
Time and space complexity: Representing your algorithm with Set notation and mathematical notation helps you to easily understand just how many iterations your algorithm is likely to go through. Counting operations like permutations and combinations can also help.
Solving the four-sum problem
Consider this problem https://leetcode.com/problems/4sum/.
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
-
0 ≤ a, b, c, d < n
-
a, b, c, and d are distinct.
-
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Here is a four-sum problem I got from LeetCode. I wish to demonstrate how my approach to solving this problem changed after I started refreshing my knowledge of Discrete Mathematics.
First, let’s represent this problem with some mathematical notation. Most solutions to this algorithm have a time complexity of O(n4), which is not bad considering the algorithm but that time complexity is high. A simpler form of this problem is the Two sum problem which could be solved using a two pointer solution and the most populer solution for the Four sum was to run this two pointer algorithm n2 times. This I believe can be improved upon. Remember mathematical induction enables us to represent the four sum problem in relation to the two sum problem using the number of elements in the sum as the step in the ladder N. For two sum N is 2 and for four sum N is 4.
Let’s say one array of elements that sum up to target is Y = [y0,y1,y2,y3 ], then the output result R is [Y0,…]. If x is an element in the input array, then Yt = [xi,xj,xk,xl] when xi + xj +xk + xl = T. This is the case when N = 4. When N = 3, Yt = [xi,xj,xk] when xi + xj +xk = T. When N = 2, Yt = [xi,xj] when xi + xj = T. N cannot be 1 as there is no such thing as a one sum. There has to be two elements in a sum. Therefore, N>=2.
Now if input array X is [x0,…,xn], lets consider a sorted array such that x0 < … xn. What would be the minimum possible n values of x that could sum up to target T. The minimum I could think of is an array of n values which were all x0. Then what would be the maximum values of x that could sum up to T. That would be an array of the largest value xn in a sorted array. Hence, the following can only be correct for output arrays, Ny0 >= T Nyn ≤ T These two conditions allow us to avoid bad paths in our algorithm.
Here is the best 2 sum algorithm I know in python:
def twoSum(nums, target):
nums.sort()
l = 0
r = len(nums) - 1
results = []
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append([nums[l],nums[r]])
l += 1
while l<r and nums[l-1] == nums[l]:
l+=1
elif s < target:
l += 1
while l<r and nums[l-1] == nums[l]:
l+=1
else:
r -= 1
while l<r and nums[r+1] == nums[r]:
r-=1
return resultsLet’s now use mathematical induction to represent the four sum or three sum in relation to the two sum. We can do that by looking at the three sum as the two sum algorithm F(n) running for all n values of the input array, so n*F(n). Then the four sum algorithm would be running the two sum algorithm against all the possible 2 combinations of the input array, so nC2.F(n).
But, how about we think about the path ways to the correct out array as pathways in a tree. Where leaf is a possible array that can be created from the parent. So finding the correct output array is a matter of finding the right path and ignoring bad paths. The best way to traverse a tree is using a recursion then. For algorithms where N>2, the F(n) would be run for a target - last value of the parent in the tree. So the two sum algorithm would be trying to find the two values that sum up to the target minus the values parents.
Now let us make our new function in relation to the two sum:
def findNSum(l, r, target, N, result, results):
if r-l+1<N or N < 2:
return
if N == 2:
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l],nums[r]])
l += 1
while l<r and nums[l-1] == nums[l]:
l+=1
elif s < target:
l += 1
else:
r -= 1
else:
for i in range(l, r+1):
findNSum(i+1,r,target-nums[i],N-1, [nums[i]]+result, results)We know that the base level of the algorithm is N==2, and remember our sights about the minimum and maximum possible values in the output array Y. We can use this construct our early return logic.
def findNSum(l, r, target, N, result, results):
if r-l+1<N or N < 2 or target > nums[r]*N or target < nums[l]*N:
return
if N == 2:
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l],nums[r]])
l += 1
while l<r and nums[l-1] == nums[l]:
l+=1
elif s < target:
l += 1
else:
r -= 1
else:
for i in range(l, r+1):
if i==l or (i>l and nums[i-1] != nums[i]):
findNSum(i+1,r,target-nums[i],N-1, [nums[i]]+result, results)I added if i==l or (i>l and nums[i-1] != nums[i]): to reduce duplicate checks if a value is the same at a certain level.