Last semester in university we learnt Data Structures, and the obvious next step for the new semester is Algorithms, watch YouTube videos, visit stack overflow read some other forum and it will be pounded into you that Data Structure and Algorithms is the most important topic you will study as CSE student so what did i as a CSE student learn, lest go through perhaps the biggest topics in the first half of this semester “Divide and Conquer” and more importantly “Dynamic programming”
“math isn’t a problem solving technique” it is Despite the popular belief Computer Science Engineers aren’t coders who sit for hours in front of a black screen with green fonts making websites or hacking the internet, they are engineers. Problem solvers who essentially use mathematics and computers to solve different problems. our computer is at the end of the day just doing basic math adding 1’s and 0’s which sum up to the bigger pictures of AI, robotics and ML. everything we do stems from mathematics and it is important not to forget that as we move on to the next semester telling our friends “I hate math's” while choosing machine learning as your specialization Let’s first see what dynamic programming and divide and conquer algorithms actually are. Let’s start with the utmost basic, a function, because what is an algorithm without a function. A function is a piece of code that takes in some input runs some code and gives out some output based on the input and while writing a program u many times ``call” the function, where u write out its name and tell it to use these inputs to give out some sort of output. the main purpose of a algorithm is code reusability but it has other interesting features worth knowing about. Now a recursive function is a function that calls itself so if you were to look at the code you would see the same function name in there somewhere but with the inputs slightly changed normally some sort of increment or decrement. Now divide and conquer algorithms are algorithms that use recursion to take the original problem and then divide them into many smaller manageable problems sort of like how you slice up a pizza so that it can actually fit in your mouth you would normally call those problems “Sub problems” . Now in many situations this is a great technique. Look at this code for example. This function takes an integer n then prints numbers in ascending order up to the number n starting from zero here you can see how the function calls itself but reducing the input by 1 until it has reached zero and then starts printing the numbers. But this technique also falls flat in a number of scenarios, take the Fibonacci sequence for example, a Fibonacci sequence is where the next number in the sequence is the sum of the two numbers before it. So you would start with a 0 and 1 and then onwards add the two numbers just before it. If we use the recursion we see a process that is not optimal at all, take a look at this step to find the sequence at position 7 you need to find the sequence at position 6 and 5, but to find the sequence at position 6 you once again need to find the sequence at position 5 and so you end up calculating the same thing twice, this problem only multiplies as you go down the ladder with the Fibonacci sequence of 2 being calculated 8 times. This redundant step is extremely wasteful and just unacceptable to an engineer and so dynamic programming comes into play. in essence the problem with recursion was that it was calculating the same things over and over again well the simplest way to fix that is to simply “remember” your results. Dynamic programming basically takes this concept of dividing problems into subproblems and removes the need to calculate the same thing multiple times. lets look at one way this is implemented, let’s take the example of the Fibonacci sequence. Now we make an array whose index number corresponds to the Fibonacci position and the value of its result is stored at that index. An array is basically a list where we can store numbers and all those numbers have a corresponding index number in that array so that we can access it. We take in our input, we already know that fib(0) should be 0 and fib(1) should be 1 now we work our way up we say that fib(2) is the sum of the numbers before it that is fib(0) and fib(1) we take those values from the array add them up and then store back in the array at index 2 we keep doing this till we reach our desired value n at which point we look at our array and add the number at position n-1 and n-2. Let’s look at one more question. This question is called the Josephus problem. N people are sitting in a circle and they are numbered sequentially in a clockwise manner. Starting from number 1 each person kills the person to their left. In case that there are two people left the person opposite will be killed, given a number n you have to find out at which position you should sit to survive. you can simulate this problem at this site. Now a few of you have already started seeing the pattern. Let’s say there are 5 people. The killing process is going in a loop that is there are multiple iterations of it. And after 1 iteration a certain number of people are dead see where I am going with this? After each iteration the number of people reduces and so it becomes a sub problem here in case of 5 people after 1 iteration number 2 and number 4 are killed and this now becomes a problem with 3 people instead also here instead of the person at position 1 holding the sword the person at position 5 is holding the sword clearly you can use a recursive function and since there is no repetition of cases you don’t even have to use dynamic programming, but isn’t there a faster way to do this? If you see each iteration again you would see that in each iteration only even numbered people die that means in case when n is a power of 2 the person at position 1 always wins, in case that n is not a power of two you can still write n as a power of 2 plus some constant lets say (L) and after L people die it again becomes a power of two and the person holding the sword then will survive and so given a power n we can directly find the position as using this. This is where knowing a little math can save you a whole lot of trouble. take the log base 2 of n, with this you get the nearest power of 2 that's less than n. find the difference between the two, that is your L now since every other person is killed the final answer would be 2L+1. The time complexity with the first solution is O(log2(n)) the second solution was O(1). math is the root of algorithms and data structures and many times students don’t realize this, in fact the first computer scientists were mathematicians who wanted to automate processes to speed things up. that being said there are tricks for when those are necessary. i recently attended a codathon from my competetive coding course in it was this question : “Two students, Priya and Tony starts playing the game. The first turn is of Tony. In a two dimensional plane both players are at origin (0,0). A fixed step size is decided by the organizer i.e., S. Every player has to move in the 2d plane by adding S to either of its x or y coordinate. Players have to follow one constraint that after taking the step if their coordinates are (x,y) then, x^2+y^2<= q^2 must holds. Here, q is some distance from origin. The game will stop when one player is not able to make a move. If both Priya and Tony plays the game optimally, determine who will win.” my solution to this was the fact that they walk a very uniform path. if you were to draw this on the 2d plane you would see that all the points land on exactly two lines, lets assume that they first walk in x direction and then y and then repeat that the lines in that case would be y=x and y=x+s also the equation they have given us is the equation of the circle so y=x would intersect with the circle at q/root(2) and we would find the intersection for the other line and circle. however using this approach i was not able to finish the question in time an easier method would have been to take the square root of the equation to get root(x²+y²)=q. if students tried plugging in the values for x and y to simulate the game in the original equation they wouldn't succeed since for bigger values of q taking its square would be outside the limit of the 64 bit integer however by taking its square root you cheat this problem, and so even if this was slower this would have been the better answer to write as it would get the job done and sometimes that's all you need.