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.
