Solving Computer Science Algorithms

When I was a student, lots of my fellow students approached me and asked “Where do you start to solve a computer science problem?” A question could typically be something like “write an algorithm to calculate…” I hope the following will give a good starting point and building block to get you on the road to solving the problem.Let’s work through an example. You get the question to write an algorithm or program to solve “Pascal’s Triangle”. The question might be something like “The user will enter a row number, and then the program must calculate and display the elements of that row in the Pascal Triangle”Pascal’s triangle is a geometric arrangement of the binomial coefficients in a triangle. In plain English this can be explained as “every number in the triangle is the sum of the two numbers above”. The number Zero is always invisible to the left and right of the triangle’s edges. To read more about Pascal’s Triangle, search for “Pascal’s Triangle” in Wikipedia.Here are the first few rows of Pascal’s Triangle: (The triangle starts with Row 0 and each row starts with element 0 from left to right)11 11 2 11 3 3 11 4 6 4 1Now, to solve this in an algorithm / program, there are always 4 basic ways to approach the problem. The 4 approaches are here listed from generally easiest to advanced, and also generally from worst to best.1) Hard Coding2) Iterative3) Recursive4) FunctionLets look at all 4:Hard CodingThe hard-coded solution is a silly solution! Bad programming! To solve the problem with hard coding, we will store each row as a variable/memory structure and then when required, we return that specific row. Only use this method if you are writing an exam and you are seriously running out of time!IterativeThe iterative approach is in most cases the “model answer”. This is generally a good solid solution. The solution is easy to write, and also easy for someone to understand when reading the code.We will start with hard-coding only the first row. Then we will iterate calculating through the rows until we are at the required row. For Pascal’s triangle, our algorithm will loop until the required row. Each subsequent row is calculated by using the values from the previously calculated row.RecursiveThe recursive solution is normally the “higher grade” solution. It is something that is not always understood by students. I used to call this the “job security” solution. Computer Scientists enjoy this solution.With the recursive solution we will use a function to return each element of the required row. The function will call itself to calculate the answer by calling the same function (recursively). Each time the function is called, it will return “1” if it is the first element of the row, otherwise it will return the sum of the two elements above it.FunctionThe Function is normally the best and fasted approach. It could however be very difficult to work out a formula. With a formula we want to say:f(r,e) = some formulawhere r = row number and e = element number.For Pascal’s Triangle there is a formula! nCr or n! / (r! * (n-r)!)where n = row number and r = element number.So, our algorithm will call this function with the row- and element numbers as parameters and displayed the return value.That’s it! Problem solved.