I haven't posted anything for a few weeks now. I was very busy during midterms and therefore neglected to make any posts for some time. Today we had our second term test. We had three proofs and about 50 minutes to complete them. On the first question we had to prove a statement, the second we had to disprove by first negating the statement and finally we had to prove another statement.
I understood and completed all three proofs with time to spare. I found them to be very straight forward and also very similar to the proofs we had done previously in the course. At this point in the course, that is now that we are moving away from proofs and towards algorithm complexity, I can now say that I am not having any significant difficulties with any proofs that we have done so far. This is something worth noting because as I've said in previous posts, when I was first introduced to proofs a few years ago, I never came anywhere near as close to understanding what I was doing as I have now.
Last term I watched several online MIT lecture videos regarding complexity, purely out of curiosity. They were very informative and I believe have helped me understand the material we are currently covering in this course more easily. Complexity is very interesting because it allows a programmer to determine the most (or least) number of steps that a program will go through as it is moving through an algorithm. This allows a programmer to compare for example the efficiency of one algorithm to another, where each may use a different approach to solve the same problem.
I've been working on a game for a few months now, programming in Visual Basic 6.0. In this 2D game the player can control persons on a map. This is map contains walls, chairs and doors, all of which the persons must collide with. Recently I've been working on an algorithm that takes lines and squares and creates a polygon mesh that the persons use to navigate around the map. At first I was using an algorithm that created points that the persons would use to move around an obstacle, however the problem was that I was creating at most 6 points per line. At first this algorithm worked very well and was quite accurate, however as the map grew in size, the number of points increased to such a number that the program would take several seconds just to calculate the movement path of a person.
As a result I began working on a polygon navigation mesh, which will reduce the number of points the program will have to search through when calculating the person's path. In terms of complexity, the path finding algorithm I used before was operating in O(n^2) time. With my new algorithm, the program is now operating in O(n) time making it much faster. Now simply running the two different algorithms would clearly show me what algorithm is more efficient. I would just have to keep track of how long it took for the algorithm to find the shortest path using the points or the navigation mesh. However, if before ever even writing the code for these two algorithms, I instead calculated the worst case scenario using complexity, I could have easily determined which algorithm would be more efficient without ever having to test them. From what I understand this is one of the main uses of complexity, that is to determine beforehand the efficiency of an algorithm.
As I continue to create my 2D game, I will now use complexity to determine which algorithms I should or should not implement before I ever write a single line of code.
