Data Structures
Abstract Data Structures
Often a data structure is closely associated with a set of available operations. Data structure + operations = Abstract Data Type. From an OOP perspective, think about members (methods) of a class…etc.
- Example 1: Priority Queue
- Underlying implementation was a heap
- Operations were
InsertanddeleteMax
- Example 2: Stack
- push
- pop
- peek // Basically operations with a data type behind them. More on them below. Abstract Data Types
Common Data Types
The essentials:
Algorithm topics
Various algorithmic topics
Search Algorithms
Algorithms that are designed to find or retrieve a specific element from a data structure. The goal is to do this efficiently, both time and space, otherwise a linear search would be fine but it’s not cuz that’s very bad.
Common examples include.
Sorting Algorithms
The process of rearranging elements within a DataStructure such as Arrays or Lists according to a certain order, either ascending or descending or based on some complex criteria. Sorted data is easier to retrieve, read, use, analyse…etc. So there’s massive benefits to sorting data, including how it affects TimeComplextity. Choosing the right algorithm to sort your input data is paramount, especially in an interview. Read more here Sorting Algorithms.
Graph and Tree Traversal
Trees are incredibly useful for solving a myriad of problems. Deep dive here Graph and Tree Algorithms
COMP 3760
COMP3760 is the Algorithms course I took at BCIT during CST.
Abstract Data Types
AbstractDataType is a logical description of how to view data and operations concerned with said data and how they’re implemented. Simply concerned with how the data is represented and not how it will be constructed as that’s abstracted away.
This level of abstraction creates Encapsulation around the data and thus hides it from the user’s view, AKA Information Hiding.
DataStructure is the implementation of abstracted data.
Algorithm Analysis
Programs and algorithms can be compared by analyzing how long they take to execute and how many resources they consume. A common way for measuring algorithm performance is Big-O Notation The order of magnitude function describes the part of that increases the fastest as the value of n increases. Order of magnitude is often called Big-O notation (for “order”) and written as . It provides a useful approximation to the actual number of steps in the computation. The function provides a simple representation of the dominant part of the original . Performance is often considered using either the worst case and/or average case as it’s often best to consider those instead of the best case scenarios.
The order of Big-O magnitude (from fastest to slowest)
| f(n) | Name |
|---|---|
| Constant | |
| Logarithmic | |
| Linear | |
| Log Linear | |
| Quadratic | |
| Cubic | |
| Exponential |
Side note:
When writing an algorithm to solve a problem, it’s important to ask about the constraints that are imposed OR may be imposed. Everything from Array size to primitive type of a variable, number of factors to consider when designing a grid, how a robot moves… More examples Frankly, you’ve done this time and time again solving all sorts of problems in class, especially 1510 we had to actually think of constraints that Chris hasn’t…