Intro Flashcards
What are data structures?
Data structures are systematic methods of storing and organising data so it can be used efficiently.
What is an algorithm?
An algorithm is a step by step procedure detailing a series of instructions to follow in order to accomplish a task.
What are the characteristics of algorithms?
- Unambiguous
- Must have well defined inputs
- Must have at least one output
- Must be language independent
- Must be easy to understand
- Must be generic; can be used for multiple input types
- Must have finite steps
- Must be feasible
What are the various operations on data structure?
- Sorting
- Traversing
- Deleting
- Updating/ Inserting
- Searching
What is an interface?
It is the set of operations that can be performed on a data structure.
What is implementation?
It is the internal representation of a data structure, which includes the algorithm of the data structure’s operations.
What are the execution time cases?
- Worst Case
- Average Case
- Best Case
What are Elementary items?
Data values that cannot be further simplified or broken down.
What is an entity?
An item that has a list of attributes.
Based on steps how can algorithms be classified?
- Sequential steps: steps that must be executed in the order they are defined/outlined.
- Selective steps: these steps include conditionals which allows for the selection of steps best suited for the problem.
- Iterative steps: have to be repeated a number of times to accomplish task
What are the characteristics of data structures?
- Correctness
- Time complexity
- Space complexity
Why do we need data structures?
- To search through large files with ease
- To improve processing speed
- To handle multiple requests
When is a function said to be a Big O notation?
When,
f(n) ≤ c • g(n) for all n ≥ no
What are the types of algorithm analysis?
- A priori or Asymptotic analysis (before implementation; theoretical analysis)
- A posteriori (after implementation; practical analysis)
What is pseudocode?
High level program representation of an algorithm.
What are the types of asymptotic analysis?
- Best case (uses Omega notation)
- Average Case (uses Theta notation)
- Worst case (uses Big O notation)
Relate Big O, Omega, and Theta notations with their bounds with respect to tim
Big O deals with upper bound
Omega deals with lower bound
Theta deals with the moment both upper and lower bounds are equal.
What is the formula for row-major order?
Address (A[I][j]) = Base address + storage size × (i × num of columns + j)
Remember BODMAS.
What is the formula for column-major order:
Address (A[i][j]) = base address + storage size × ( j × num of rows + i)
What are the components of a graph?
- data elements are called vertices
- Connections are called edges
- Vertices have more than one parents/relationship with other vertices
Dynamic Vs. Static Data Structures
Dynamic data structures do not have fixed memory spaces for elements but static data structures do.
Non-linear vs. Linear data structures
Non-linear data structures: data is not stored sequentially.
Linear data structures: data is stored sequentially/linearly
Characteristics of a tree
- Hierarchical and non-linear
- The beginning point is called the root.
- Data items are called nodes
- Has branches
Qualities of queues.
- First In First Out (FIFO) principle.
- Data files are added in one end called the rear and removed from another called the front.
Stacks properties.
- Operates on a Last In First Out (LIFO) principle.
What are linked lists?
Data structures where each data item holds both data and pointers to the next data item in the list.
Types of arrays
- One dimensional: has only one row.
- Two dimensional: has more than one row and column
- Multi-dimensional: array of arrays.
