CPT304: Week 5 Final Project: Blog Post

  

Greetings Everyone

Regarding writing applications, algorithms are used to create the structure and steps the program must take to perform the task asked of it.  When developing programs, which algorithms are used should be considered as some are more efficient than others.   We can use the Rubik's Cube as an analogy.  Competitive Rubik's cube solvers use algorithms as a matter of course to create solutions for scrambled cubes.  Programmers use algorithms to solve other problems.  Some algorithms are better suited for specific scenarios.  With the Rubik’s cube analogy, the Layer-by-Layer method is easy to learn.  “Compared to other methods, there are only a few algorithms to memorize, and they are relatively intuitive.  This technique is perfect for beginners since it is the most accessible.  On the other hand, this method is not efficient for speedcubing (GoCube. 2020).  Layer-by-Layer is a great way to learn to solve a cube if you do not have the time or resources to spend a lot of time memorizing routines.  On the other hand, another method called Advanced CFOP uses over a hundred algorithms to come to a solution.  Still, the time to solve is reduced, and some competitors can achieve solve times that are less than 10 seconds.  (GoCube. 2020).  The amount of effort put into memorizing the algorithms is much more involved than the Layer-by-Layer approach; however, the solve times are significantly improved. 

Algorithms in the world of programming are similar to the example above.  Some programs are more efficient than others, while others are easier to program and design.  If program maintenance and speed to launch are priorities, a simpler yet less efficient algorithm may be the way to go.  However, if datasets are large or there are complex computations, we should select a more complex yet efficient algorithm.

There is an algorithmic efficiency calculation called Big-O notation.  This calculation can be used to calculate the complexity of an algorithm by measuring the number of steps and determining the amount of time and space complexity a set of instructions takes.  Big-O notation looks at the algorithm to calculate the worst-case scenario for how much runtime an algorithm can take.  (Sambol.  2017).  Take Figure 1 below.  If we look at sorting algorithms, we will notice three major algorithms.  If we compare the time and space calculations for the bubble, merge, and quick sort algorithms against the figure 2.  complexity chart, we find that the bubble sort has the worst time complexity but the best space complexity.  We would choose this algorithm in scenarios where processor and memory speed are good, but storage space is at a premium.  The merge and quick sort, in comparison, have a slightly better time complexity requirement, so if speed was a consideration, we should choose these sort methods over bubble.  Comparing merge and quick sort, we would want to opt for the quick sort as it takes up less space.   

Figure 1.  Big-O CheatSheet (La Vivien Post. 2021). 

Figure 2.  Big-O Complexity Chart

We don't have to sort our data; however, if we do not sort, we will need to use a linear search to find what we are looking for.  A linear search can be time-consuming as we must step through each item in the list until we reach our goal.  We may get lucky and need to look up Aardvark and if we are sorted alphabetically.  However, on average, this is an inefficient method.  Once we have sorted our data, we can look at other algorithms to search through our data to find the information that we are looking for.  With sorted data, we now can use a binary search that works by splitting the search field in half and again until it finds the requested value.   "Binary search is incredibly efficient in finding an element within a sorted list.  During each iteration or step of the algorithm, binary search reduces the search space (i.e., the remaining elements to search within) by half."  With larger datasets, we are able to use a more efficient search algorithm so that the sum of the steps to complete the search is fewer despite the extra actions taken to sort first.

In Conclusion, different algorithms have different efficiencies, which should be considered to best utilize the resources available to accomplish the tasks at hand.  I hope this post finds you well and illustrates how algorithmic efficiency and analysis are vital in developing applications and code to best suit requirements with available resources. 

References

 

GoCube (2020).  Comparing Different Methods for Solving the Rubik's Cube.  Comparing Different Methods for Solving the Rubik's Cube - GoCube (getgocube.com)

La Vivien Post.  (2021).  Big-O CheatSheet.  Big O notation cheat sheet | Download cheat sheet | La Vivien Post

Lysecky, R., Vahid, F., Lysecky, S., & Givargis, T. (2015).  Data structures essentials.  https://zybooks.zyante.com/#/zybook/DataStructuresEssentialsR25/chapter/1/section/3

Rowell, Eric. (n.d)  Big-O Cheat Sheet.  Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell (bigocheatsheet.com)

Sambol, Michael, (2017).  Introduction to big-O notation.  (185) Big-O notation in 5 minutes - YouTube