2: Fundamentals of Data Structures Flashcards
n-Dimensional Array
A set of elements with the same data type that are indexed by a tuple of n integers, where a tuple is an ordered list of elements
Abstract Data Structures (7)
- Queue
- Stack
- Graph
- Tree
- Hash table
- Dictionary
- Vector
Static Data Structures
They reserve memory for a set amount of data and cannot be resized
Dynamic Data Structures
They have no limit to the amount of data they can hold so can be resized
Static vs Dynamic Data Structures (6)
- Static data structures have storage size determined at compile-time
- Dynamic data structures can grow during execution
- Static data structures can waste memory if the number of data items stored is small relative to the size of the structure
- Dynamic data structures only take up the amount of storage space required for the
actual data - Dynamic data structures require pointers to the next item whereas static data structures do not
- Static data structures store data in consecutive memory locations whereas dynamic data structures do not
Queue (4)
- Items are added to the back of the queue
- Items are removed from the front of the queue
- Front and rear pointers are used
Linear Queue
Once the maximum number of items has been added to the queue, no more items can be added even if some are removed
Circular Queue
Once the maximum number of items has been added, if some are removed, items are added to the front of the queue
Priority Queue (5)
- Each item has a priority associated with it
- The queue has different points at which items can join the queue according to priority
- They join at the back of the section according to their priority
- If there are no items queued in the correct priority section then they join the queue at the front of the next
lower priority - Items are still taken one at a time from the front of the entire queue
Stack (3)
- Items are pushed to the back of the stack
- Items are popped from the back of the stack
- A top pointer is used for the item at the back
Graph
A data structure used to represent more complex relationships
Weighted Graph
A graph with a value associated with each edge
Vertex / Node
A point on a graph
Edge / Arc
A connection between two vertices
Undirected Graph
A graph where you can traverse an edge either way
Directed Graph
A graph where edged may have associated directions
Adjacency Matrices + (3)
- Appropriate when there are many edges between vertices or when graph is not sparse
- Appropriate when edges frequently changed
- Appropriate when presence of specific edges needs to be tested frequently
Tree
A connected, undirected graph with no cycles
Rooted Tree (3)
- A tree in which one vertex has been designated as the root
- A rooted tree has parent-child relationships between nodes
- The root is the only node with no parent and all other nodes are descendants of the root
Binary Tree
A rooted tree in which each node has at most two children
Rooted Tree Uses (4)
- Binary trees are used in compilers to build syntax trees
- Binary trees are used within routers to store routing tables
- Binary search trees can be built to speed up searching
- Expression trees can be used to represent algebraic and Boolean expressions in a way that simplifies the processing of the expression
Hash Table
A data structure that creates a mapping between keys and values
Collision
When two key values compute the same hash
Rehashing (4)
- When a collision occurs, the value is placed in the next free position in the hash table
- A pointer to the position of the value is stored in its hashed position
- When retrieving values, the key is checked against the key in the hashed position
- If they are different, the pointer position is checked
Dictionary
A collection of key-value pairs in which the value is accessed via the associated key
Dictionary Applications
Information retrieval
Vector
A vector can be represented as a list of numbers, as a function and as a way of representing a geometric point in space
Vector Notations (5)
- [2.0, 3.14159, -1.0, 2.718281828]
- 4-vector over ℝ written as ℝ⁴
- Function interpretation
0 ↦ 2.0
1 ↦ 3.14159
2 ↦ -1.0
3 ↦ 2.718281828 - ↦ means maps to
- All the entries must be drawn from the same field, e.g., ℝ
Vector Addition
Achieves translation
Scalar-Vector Multiplication
Achieves scaling
Convex Combination of Two Vectors
An expression of the form αu + βv where α, β ≥ 0 and α + β = 1
Dot / Scalar Product of Two Vectors
The dot product of u = [u₁, …., uₙ ] and v = [v₁, ….., vₙ ] is:
u ∙ v = u₁v₁ + u₂v₂ + …… + uₙvₙ
Dot Product Applications
Finding the angle between two vectors