For starters, data structures are essential building blocks in obtaining efficient algorithms. In other words, they are meant to be an organization or structuring for a collection of data items. Data Structures are meant to solve a problem and provide a solution that can be solved within the specified resource constraints: cost, time, technical capabilities, etc. It is important to remember that each data structure has an allocated amount of space for each data item it stores, a certain duration to perform a single basic operation, and a certain amount of programming knowledge. Hence, each problem is basically centered on two constraints: space and time.
Introduction to Data Structures
The fundamental role of most (if not all) computer programs is to store and retrieve information as quickly as possible. As beginner coders we usually focus on our programs performing calculations correctly, while neglecting speed and information retrieval or storage. In that regards, this unit will teach us how to structure information to support efficient processing. But before we get to that, we need to mentally prepare ourselves for three things (that we’ll get the hang of in the future):
- KNOW the commonly used data structures. That’s every programmers’ data structure “toolkit.”
- APPLY the concept of trade-offs and acknowledge that costs and benefits exist with every data structure.
- MEASURE the effectiveness of a data structure or algorithm.
**Those three things aka “KAM” which means “how much in Arabic” is what I’d like to know after finishing this course. (that acronym is mainly something to help me remember those 3 things, feel free to ignore it)
Data structures is about designing algorithms that make [efficient] use of a computer’s resources. Generally, a design pattern embodies vital design concepts for a recurring problem. In other words, a specific design pattern will appear from the discovery that a particular design problem occurs frequently in various contexts. One thing you should keep in mind is that a design pattern describes the structure for a design solution. It comes with both costs and benefits, where the concept of trade-offs kicks in.
Trade-offs is something like preferring or choosing one thing over another in order to gain optimum results within the set constraints. Given that, any design pattern might have variations upon its application to match the many trade-offs in a given situation. Hence, it is important to follow certain steps when selecting a data structure to solve a problem:
- Analyze your problem to know the basic operations that needs support.
- Quantify and utilize the resource constraints for every operation.
- Select the data structure that best suits the requirements in steps 1 and 2.
So, without further adieu, here are 4 example design patterns (that I won’t be elaborating on):
Flyweight Pattern: Mainly comes in handy when you have an application with many objects, where some of these objects are basically the same in terms of information and role. Yet, they have to be reachable from various places, while being conceptually distinct objects. On a side note, utilize the concept of reducing memory cost by sharing space since a lot of information is being shared.
Visitor Pattern: This pattern has to do with trees. Have you heard of tree traversal? Lets say, you got a tree of objects to describe a page layout and you want to perform some activity on each node in the tree. You will need to have some kind of order without changing associated elements. Visitor is basically the process of visiting every node in the tree in a [defined order]. In a nutshell, it represents the operation that will be performed on the elements of an object structure.
Composite Pattern: Is all about hierarchy of object types and a bunch of actions. It has to do with subclass hierarchy defining specific sub-types (I know, not the best definition, but you get the idea).
Strategy Pattern: In layman’s terms, this pattern is about encapsulating an activity that is part of a larger process.
Algorithms and Problem Solving
A problem, as we all may know from having attended math class, is something that needs to be solved. And an algorithm in this case, is the method or process followed to get the solution. Here are some facts, you need to know before I get to the point: any modern computer programming language can be used to implement a bunch of algorithms. An algorithm by default should provide enough detail that it can be converted into a program whenever necessary. Having said the facts, I will move onto the properties any algorithm should possess in order to solve a particular problem.
- It must be correct. In other words, it needs to implement the intended function, leading each input to the correct output.
- It is made up of a series of [concrete steps, which are finite] meaning that the action described by any step is 100% understandable and doable (no ambiguity allowed) by people or the machine within a specified duration & a number of steps.
- It must terminate and never go to infinite loop.
On a different note, this unit is definitely a brain whacker! Okay, now that we have established that the unit is hard, please checkout Jeliot, it is an important software for UoPeople students taking this course and maybe for other students too, you can download it here. I am pretty much done, below is a summary of the things covered. Please bear in mind, that this entire post serves as an introduction to the unit.
Checklist aka Things you should [kinda] know after reading this post:
- Philosophy of data structures
- Design patterns
- The role of algorithms in problem solving
Shaffer C.A (2011). A Practical Introduction to Data Structure and Algorithm analysis. Retrieved from http://courses.cs.vt.edu/cs3114/Spring09/book.pdf
Background Story: Hey, I’m Yasmin, a soon-to-be junior CS Major at UoPeople with 80 credit hours down. I will be using my blog as a platform to help me study and share what I learn on a weekly basis with my fellow classmates and readers. Follow the Studying CS at UoPeople section for weekly blog posts published every Friday. Please note, this series will not interfere with the weekly Monday posts. Thanks for reading. Cheers!