CST370.1 Module One

 

CST311.8 Module One

Review of Data Structures and Algorithms

What I learned this week:

This week was a brief overview of what we plan to cover throughout the course, along with some review of the primary data structures we will be using in formulating and analyzing of algorithms. We covered the different categories of problems we'll be facing, such as sorting, searching, string processing, graph, combinatorial, geometric, and numerical-based problems. In the review, we also covered the fundamental data structures, in which the two most important data structures are Arrays and Linked Lists. All other data structures can be structured out of these two. For example, even graphs are represented as either an adjacency matrix(array-based) or an adjacency list(linked-list-based). We also briefly covered the analysis of algorithms and how by deducing the algorithm down to its basic operation, we can find the algorithm's time complexity.

Notes on the types of problems we'll be covering:

• Sorting:
• good sorting algorithms at best have an O(n*log n) time complexity
• stability is based on whether the sorting algorithm preserves the relative order of any two equal elements of its input
• a sorting algo is considered in-place if it doesn't require extra or relatively little memory.
• Searching:
• issues that could arise when it comes to searching pertain to whether the underlying data may change frequently. This is consistent with what we've learned in previous classes in the likes of operating systems and our database course.
• Graph:
• graphs are one of the most widely used for modeling a myriad of systems, especially in regard to:
• transportation
• communication(like in Computer Networks course)
• social and economic networks
• project scheduling
• games
• Combinatorial Problems:
• Combinatorial problems are some of the most difficult problems in computing, this is due to the fact that as the problem size increases so do the combinatorial objects needed within the algorithm.