CPT 307 Newbie to Newbie Part Two

 Hello Class,

 

·         Explain to another newbie how to apply algorithmic design and data structure techniques in developing structured programs.

Not all programs are created the same.  Some programs may take much longer to complete a given task than other programs.  If a program will be dealing with large amounts of data, how that data is organized or structured, and how it is accessed, can make a big difference.  The main considerations are time complexity and space complexity.

Time complexity is the biggest concern.  Time, here, does not refer to time as we’re used to.  Instead, it refers to the number of operations needed.  The operations are generally compare, swap, fetch from memory, and send to memory.  Each operation takes only a very small amount of time, however, the number of operations necessary grow exponentially (referred to as the big O).  As lists get larger, the number of operations, hence the amount of time taken, will grow.

The other complexity, space complexity usually isn’t a concern.  The space taken is close to the size of the list.  As the list grows, but size required does grow, but only to the size of the list.  It does not grow exponentially as the time does.  There are some other space requirements, but they are usually small and don’t grow even when the list grows. 

·         Are some algorithms and data structure designs better than others? If so, explain why one design would be used before another design would be used.

The algorithms and data structures do have an effect on performance.  This is described on a website aptly name Complexity Analysis.  “Some algorithms are more efficient than others” (Complexity Analysis, n.d., para. 2).  Size is a major consideration.  For very small lists, the operations will occur so quickly that structure won’t really matter.  However, as a list gets larger, efficiency will matter.

As mentioned above, the space complexity usually isn’t a very significant concern.  One exception may be the merge sort algorithm.  Merge sort requires a second list of equal size to the original list.  This means that the space complexity for a merge sort is double that of many other sort methods.

·         Discuss in the post how you would apply algorithmic design and data structure techniques in developing structured programs.

When a list gets large enough that search and sort times will be significant, the next major consideration is how often a list will be searched.  Searching a sorted list is much faster than searching an unsorted list, however, the search algorithm is costly.  If a list is infrequently searched—or changes significantly more often than it is searched—it doesn’t make sense to incur the overhead of sorting.  In this case, a sequential search would be best.

In cases where a list will be frequently searched, a binary search method could be the most efficient.  The algorithm checks the middle of the list to see if the sought value is higher or lower.  In this way, the list is cut in half and the algorithm then checks the new middle of the list.  The list continues to be cut in half until the value is found.

Binary search algorithms are far more efficient than sequential search algorithms, and the efficiency actually improves as the list gets longer.  However, a binary search requires a sorted list.  This means that when there will be many searches, it could be worth sorting the list first, then having the much more efficient binary search method available.

Thanks,

John

 

References

Complexity analysis. (n.d.). Retrieved from http://www.cs.utexas.edu/users/djimenez/utsa/cs1723/lecture2.html