Topic 2 – Algorithms and Programming
What is an Algorithm?
This is a much more complex question than you might imagine. Just take a look at the Wikipedia article on algorithms – http://en.wikipedia.org/wiki/Algorithm . As a computer programmer you will be creating and documenting algorithms.
Before we get into specific data structures we must first understand algorithms. It is a good practice to break larger tasks into smaller tasks, and each of these tasks in the programming world would be called a method or a function. We will use the term functions. A function can implement an algorithm, it can also implement multiple algorithms – meaning that it could be broken into multiple smaller functions.
Let’s look at some simple algorithms. The table below represents an array – we will call it array A. Array A has a length of 8 and it is a fixed length. Also notice that A incorrectly represents the first 8 prime numbers.
| 1 | 3 | 5 | 7 | 11 | 13 | 17 | 19 |
If the array is zero indexed then we can say A at index 0 = 1. Please note that different languages use different notation – but for many languages this is expressed as A[0] = 1.
Now – let’s say we notice that it is missing the second prime number which is 2 and we want to add it to the array. We could always just set A[1] = 2. But of course if we did that we would now be missing the prime number 3. So we need an algorithm that Inserts the new number and pushes everything to the right. So we would define the function Insert. The insert function needs three things, the array, the number to insert, and the location of where to insert it.
Now you must decide what the function needs. In Object oriented programming you might reference the Insert function as a method of the object. The programming call would look something like this (using dot object notation)
A.Insert(index =>1, value=>2)
If we are not using object oriented programming we would also need to pass the array – or the call would look like
Insert(A, 1, 2)
Of course now we need the algorithm to actually insert the value. So here is a simple algorithm to do this;
– 1. Go to the last element in the array n = (length-1)
– 2. If it is not the passed index (n > index), set it’s value to the value of the previous element A(n) = A(n-1)
– 3. If it is the passed index (n = index), set the value to the passed value A(n) = value and exit
– 4. Move left one element n = n-1
– 5 Repeat steps 2, 3, and 4
This is now an algorithm. It can be represented in code, by description, or using a flow diagram.
The Black Box (information hiding)
Once you have written the algorithm, and are sure it works – you can use principles of encapsulation and information hiding. In other words, once the algorithm is written and tested, the details of how it works are not important. However there is information about the algorithm that is still important – it’s Interface, Time Complexity, and Space Complexity. And of course these are important because you want the best algorithm possible for your purposes – and there is normally more than one way to achieve the same results – or
There’s more than one algorithm to complete a task.
As a programmer – you will be expected to be able to use lots of different common algorithms. I highly recommend you lay back and watch a few video segments on common algorithmic solutions – or at least have them in your bag of tricks. Here are a few video’s from Khan Academy on different common algorithms. Yes – you should know each of these, though luckily if you are a good programmer you will know most of them already.
https://www.khanacademy.org/computing/computer-science/algorithms
If you really want to get more in depth into algorithmics, the GeeksForGeeks – has a complete in depth of many different algorithms (know your C) – http://www.geeksforgeeks.org/fundamentals-of-algorithms/
Common Algorithms
Inserting a value into an Array
Big O and Complexity of Algorithms
If you write algorithms you will need to be able to measure the performance of the algorithm. The most common measure is Big O notation.
First it is important – https://www.quora.com/What-is-the-importance-of-big-O-notation-in-programming
Here is a handy cheat sheet to see the difference of the Big-O notations – http://bigocheatsheet.com/
And finally – you WILL need to be able to determine the Big-O of algorithms. This is getting into algorithmic analysis, but simply means you need to be able to follow the code and determine the Big-O. You will be learning this in the homeworks and quizzes over the first few weeks of this class.
Coolest Algorithm
If you can think of an algorithm as cool – this one has it. It simply calculates x^-1/2 (the inverse square root). Why would anyone care if you can calculate this quickly well it turns out that in 3D graphics the inverse square root is part of the equation that calculates the angle of incidence off a planed surface. So in 3D simulation – anything that bounces off a plane (like light for lighting effects) needs this calculation. This is calculated a lot – so an efficient algorithm is really important.