Week 1 Flashcards
What is a Data Structure?
The study of Data Structures is about how the data is stored in memory to ensure efficient processing of data
Definition of a Data Structure
*Collection of elements each of which is either a data type or another data structure
*A set of associations or relationships (the structure) involving the collection of elements
Classification of Data Structures
- Linear structure (e.g. stack, queue)
- Hierarchical structure (e.g. management structure, family tree)
- Network or Graph structure (e.g. railway map, computer network)
- Set Structure (e.g. students)
How to choose a right data structure
*Analysing the problem
*Determining basic operations needed
*Selecting the data structure
Brute Force Algorithm
Algorithm that considers all the possibilities and selects the best solution
*Advantages: Simple
*Disadvantages: Infeasible
Divide and Conquer Algorithm
Algorithm that works by recursively breaking down a problem into two or more sub-problems of the same or related type. The solutions to the sub-problems are then combined to give a solution to the original problem
Backtracking Algorithm
Algorithm that attempts to complete a search for a solution to a problem by constructing partial solutions, always ensuring that the partial solutions remain consistent with the requirements of the problem. Then, it attmepts to extend a partial solution towards completion, but when an inconsistency with the requirements of the problems occurs, the algorithm backtracks by removing the most recently constructed part of the solution and trying another possibility
Greedy Algorithms
In a Greedy Algorithm a decision is made at each stage that appears to be good but no consideration is given to future consequences of this decision
Abstract Data Type (ADT)
A collection of data associated subprograms/ methods stored as a single module
Datas in Abstract Data Type (ADT)
*Cannot be accessed directly
*Can only be accessed indirectly via one of the methods associated with the data
What is in Abstract Data Type (ADT)
*The data structure
*Statements to access the data structure
*Statements to modify the data structure
Difference between ADT and Data structure
ADT | Data Structure
High level description | Concrete description
Concerned with what it can do | Concerned with how a task is done
Implementation independent | Implementation dependent
What is a stack ?
A stack is a collection of objects organised such that only the most recently inserted object can be removed at any time | is a linear data structure with the property that only the top element of the stack is accessible
Methods that Stack ADT must support
*Push (Add an element to the top of the stack)
*Pop(Remove an element from the top of the stack)
*Peek(Examine element at the top of the stack)
*Length(Give the size of the stack)
Implementation of a Stack - Using an Array
The stack of elements will be stored in an array S of size N
An additional integer variable TOP will be required to give the index of the last element in the array S
Operations for Using an Array
- Push: The element is added to the top of the stack. TOP is incremented by one. If the stack was full an error occurs
- Pop: The required element is at the top of the stack. The element is removed. TOP is decremented by one. If the stack was empty an error occurs
- Peek: The required element is at the top of the stack. TOP is unchanged. If the stack was empty an error occurs
Application - Queue Abstract Data type (What is a queue?)
A queue is a collection of objects organised such that the object that has been stored in the queue the longest is the next one removed | is a linear data structure with the property that elements are inserted at one end of the linear data structure (called TAIL) and removed from the other end of the linear data structure (called HEAD) of the queue
Methods that Queue ADT must support
*Enqueue (Add an element to the tail of the queue)
*Dequeue(Remove element from the head of the queue)
The objective of using Big-O Notation
Represent the general efficiency of an algorithm
O(1)
The running time of the program is CONSTANT irrespective of the value of N |
The running time is NOT DEPENDENT on the value of N
O(N)
The running of the program is LINEAR
|
The running time is DEPENDENT on the value of N
O(N^2)
The running time of the program is QUADRATIC
O(N^3)
The running time of the program is cubic
O(log N)
The running time of the program is LOGARITHMIC
O(N log N)
The running time of the program is N log N
O(2^N)
The running time of the program is EXPONENTIAL
