Newbie to Newbie Blog Part Two

 

Today we will be looking at algorithmic design and data structure techniques, and we will explain how to use these concepts to develop the best tools for our needs. Note the distinction for our needs, as no single tool is best suited for all jobs. Similarly, no single algorithm or data structure will necessarily be the best for all programming applications. We will examine some common algorithms and data structures, point out their strengths, and identify some applications for which these algorithms and data structures may be well suited.

 

So, what would make an algorithm or data structure the best tool for the job? We can evaluate algorithms and data structures regarding how efficiently they use resources. Often, the resources in question are time and memory. Therefore, the best algorithm or data structure often produces the most work while consuming the least amount of time and memory.

 

One way to measure the efficiency of an algorithm is to count the rate at which the number of operations grows in proportion to the number of elements in a data structure. If the number of operations multiplies as elements are added, more resources will be needed to sustain operations. A steep growth curve like this would have high Big-O complexity.

 

Big-O complexity is a data structure analysis concept used to compare different algorithms' general resource consumption potential. Some common growth rates are O(1), O(logn), O(n), O(n^2), and O(n!). We can observe algorithms falling within the bounds of these growth rates based on the maximum limit of resources consumed. The graph below illustrates different growth rates in terms of Big-O complexity.

As you can see, each curve uses different amounts of resources (operations) depending on how many elements there are. You might notice how an algorithm with O(nlogn) complexity could perform better than an algorithm with O(n) complexity up to a point. Still, the O(n) algorithm maintains a linear growth rate which eventually proves more efficient for more considerable inputs while O(nlogn) curves exponentially toward greater complexity.

Another aspect to consider when deciding how to implement data structures is the program’s goal. For example, if you have data that you will need to sort or search, or if you will be inserting and removing elements from specific points in the data set, you might consider using a list structure. Linked lists and arrays are the most common list data structures, and either can perform these functions. Stacks are another data structure like lists, but their functionality is more limited. Stacks can add (push) or remove (pop) elements only from one end. Stacks are last-in, first-out, or LIFO because only the most recently added element can be popped off the stack. Since stacks are simpler than lists, it can be more efficient to use them where lists are excessive. A Queue is like a stack because elements can only be added to one end, but a queue is first-in, first-out, or FIFO instead of LIFO, as we see with stacks. 

Aside from our primary data structure, we must also consider how we will implement the functions we need to perform. Searching and sorting are some of the most common functions used in computing, and there are several different algorithms available for each of these tasks. One option for searching is to go straight through a list, end to end, until you find the element you are looking for, known as a linear search. On average, you will have to check half of the elements in a list before finding the target while using linear search. This is not the most efficient searching method, but it is often acceptable for smaller data sets and is simple to implement. A more advanced search algorithm that can dramatically outperform linear search for large data sets is a binary search. Binary search cuts the list in half repeatedly until it finds the target. However, binary search can only be performed on a sorted list. Sorting a list introduces more time and space costs to the overall implementation, so one must find a balance where the benefits outweigh the costs. Otherwise, more straightforward options like linear search might be more appropriate. 

Being a newbie to programming, my first concern in developing a structured program would be to get it to work. From there, I could turn to more sophisticated approaches to algorithmic design and data structure techniques. I have gained a solid foundation of knowledge through this course which will help me identify and understand the goals and methods of algorithm and data structure design, and I’m looking forward to applying that and building on it as I continue to learn.