Computational Theory for Determining the Run Time
Game design is an exciting field as it offers a much more complicated programming environment than normal business applications. You need to write some form of AI normally, and it has to operate efficiently, so you need to take that into account.
Not all Computer Science course work is dealing with actual programming but instead involves Computational theory. This deals with abstract programming, so the big O of Algorithms, for example, determines how the run time varies according to the number of items. A sorting algorithm that runs with n2 time is fine if n is small, but as n increases, the time increases much more, so an algorithm that runs with n logn is much better as n increases.
OpenGL for 3D
OpenGL is the cross-platform 3D API. Windows supports DirectX and OpenGL, but Linux only supports OpenGL. It is a moderately low-level API, and there are engines built on top of it that provide a simplified API.
OpenCV for Image Processing
OpenCV stands for Open Computer Vision and deals with a series of algorithms for dealing with images and processing them. You can detect faces in images, outlines of shapes, adjustments to the contrast or color space of the image. It is cross-platform and has packages to enable it to be used in C++ and Python.
A UML diagram stands for the Uniform Markup Language diagram and is used to design (or document) data structures and functions. There are editors that allow you to generate UML using a GUI, and you can generate them from the text.
Arduino for Developing Hardware
The Arduino is often used if you want to develop small pieces of hardware that are designed to run automatically, so a simple alarm for example which uses sensors and indicates the status using LEDs. It is useful for prototyping as it is much cheaper than building hardware from scratch if you want to see if the device is feasible.
Raptor allows you to design a flowchart and then run it without having to convert it into a normal programming language. It is only designed for learning and has no real place outside of education.
Software engineering is the name for treating programming as a serious discipline and involves writing code that includes test suites, unit testing, etc.
Data structures - A complement to Algorithms
A Discussion on Program Design for Optimal Coding
Insertion of Data
Inserting data in an unsorted array is fast because we simply have to put the data at the end of the array and nothing more. Similarly, inserting data in an unsorted linked list is also fast because we simply put the data at the head of the node and we’re done. The only limitation of the array-based approach is it is limited in capacity.
On the other hand, inserting data in a sorted array is the slowest. That is because we need to maintain the sorted order thus when we have to find the index where to insert the data. Once an index has been found, we need to shift (or push) the affected values one step backwards and this tends to become really slow if there are too much data to shift. Inserting on a sorted linked list is also slow because we need to find the appropriate node in the list where to insert but at least no shifting of values is necessary once found, only fixing of links which is fast.
Heap-based priority queue’s insertion is not an as fast unsorted array or linked list but at least it’s not as slow as a sorted array and linked list. The heap basically re-arranges the elements in the array as a binary tree where the upper elements of the tree contain more prioritized items and lower elements of the tree are less prioritized. Re-arranging the tree is needed which takes time but not as a slow assorted array or linked list because we do not need to compare an element to all other elements to find an insertion point.
Returning the Head
Returning the next prioritized element in an unsorted array and linked list are the slowest. That is because the program has to go through all the items from the list to find the most prioritized item. Thus, if we’re talking about millions or billions of data, then it will take a very long time to complete.
In a heap and sorted priority queue, it is fast to return the next prioritized item. That is because the next prioritized item is already known and they simply have to return it when called.
Removing the Head
Removing the next prioritized element in an unsorted array and the linked list is the slowest. First of all, they have to find the next prioritized element to delete then delete it. In an unsorted array, once a delete is done, we need to make sure there are no gaps in-between the arrays thus we need to shift some elements and this is slow if there are too many of them. An unsorted linked list is more forgivable because it will simply remove the node and re-arrange the links but still it is slow to find the next prioritized element to delete.
Removing the next prioritized element in a sorted array and the linked list is slow too but at least it’s not as slow as the unsorted version. That is because we already know the next prioritized element to delete so what we have to do next is just remove them. In an array-based version, we still need to shift some elements after deletion to avoid gaps. For the linked list version, it is faster since we just have to arrange the links.
The heap-based version is the fastest because once the prioritized element is removed, no shifting is done but rather it will re-arrange the tree. It is faster because when we re-arrange the tree, we do not need to access and do checks to all other elements but only a part of them.
Testing Methodology Adopted
For this project, I used both black box and white box tests.
The white box test is making sure that the priority queues work as described and I utilized the Junit framework for automated testing. Each class’s functionality has been tested. Ideally, all the priority queues work the same so I made a general test that would accept any kind of priority queue and should return the expected result.
For the black-box test, I completed the partially-made Queue Manager program. Then I utilized it to manually test the behavior of all the queues and made sure the outputs are correct through observation.
I believe my code is correct because all the tests have passed and because I have implemented the classes accordingly based on how the “data structure” is theoretically defined.
Applications of Priority Queues
In real life, there are queues everywhere. I guess one of where I see priority queues are in retail stores and banks where customer representatives give more priority to the senior citizens, people with disabilities, and pregnant women.
I also see queues in my Windows OS because the computer has only a limited number of CPUs and there are processes that are more prioritized than others which I can set manually.
Analysis of Development
You do the write-up for this from a “student’s point of view”. I can’t write much about this because I haven’t really had problems working on this since I already know and implemented these data structures.