Data structures and algorithsm Flashcards
What is a linked list
A dynamic data structure where each node consists of data and a pointer. The pointer gives the location of the next node.
What is a tree
A data structure that consists of nodes and sub nodes. The first node is called the root and lines that join nodes are called branches.
What is a binary tree
A type of tree where each node has a maximum of two sub nodes. If a child node is less than the parent node, to goes to the left of the parent and if a child node is greater than the parent node is goes to the right of the parent.
What is depth-first traversal?
Dept-first traversal is an algorithm for searching a graph/tree. It goes to the left child node when it can and if there is no left child it goes to the right child. When there are no child nodes, the algorithm backtracks to the parent node. It uses a stack.
What is breadth-first traversal?
Breadth-first traversal is an alghorithm for searching a graph/tree. It visits all nodes connected directly to the start node, then visits all nodes directly connected to each of those nodes directly connected to each of those nodes and so on. it uses a queue.
What are the advantages of depth-first traversal in comparison to breath-fiorst traversal
Depth-first traversal require less memory than breath-first tranversal. It is also quicker if you are looking at deep parts of the tree.
What are the disadvantages of depth-first traversal in comparison to breadth-first traversal.
Depth-first isn’t guarateed to find the quickest solution and possibly many never find the solution if we don’t take precautions not to revisit previously visited state.s
What is a Stack.
A data structure that operates on a first in last out basis.
What is a queue.
A data structure that oerates on a first in first out basis,.
What is a hash table?
A data structure that maps keys to values. It uses a hash function to generate the key.
What is the difference between an Array and a linked list.
An array is static yet a linked list is dynamic
Elements in arrays can be accessed directly but has to be traversed ina linked list.
Contents of array are stored contiguously in memory nit a linked list might not be.
What is meant by a graph structure?
A collection of data (nodes) and connections (edges) are made between nodes. Edges can directional, bi-directional directed or undirected.
Define Big O notiation
The Big O notation describes the complexity of an algorithm, It evalutates the worst-case scenario for an algorithm and shows how time/ memory increase as data size increases.
What is meant by logarithmic growth in terms the complexity of an algorithm
As the size of an array increases, the rate at which the algorithm runs increases more slowly. This is the inverse of exponential growth, the rate of increase is a logarithmic function of the size of an array.
When might a linear search perform better than a binary search?
If the data set is small or if the item being search for is close to the start of the array.
What’s the best case for binary search?
If the element you are search for is the first element to be compared to (the midpoint).
What’s the best case for linear search?
If the element you are searching or is the first element to be compared to ( the first element in the list).
Whats’ the best case for bubble sor?
O(n)
What’s the best case for insertion sort?
O(n)
What’s the best case for merge sort?
O(n log n)
Whats the best case for quick sort?
O( n log n)
name an algorithm that has a big O notation of O(1)
Hash function
Name an algorithm that has a Big O notation of O(n)
e.g Linear search
Name an algoriuthm that has a big O notation of O(n^2)
e.g Bubble sort.
Name an algorithm that has a Big O notaƟon
of O(2n)
E.g. Fibonacci sequence
Name an algorithm that has a Big O notaƟon
of O(log2n)
E.g. Binary search
Name an algorithm that has a Big O notaƟon
of O(n log2n)
E.g. Merge sort
How does the linear search algorithm work?
Linear search works by:
Going through each element in the list.
Comparing each element to the target value.
Returning the index of the target value once
found.
How does the binary search algorithm work?
Binary search works by: Finding the midpoint of a list.
Comparing the midpoint to the target value.
Returning the midpoint if it is equal to the target
value. Creating a sub‐list from the left if the midpoint
is greater than the target value. Creating a sub‐list
from the right if the midpoint is less than the target
value. Repeating this process until the midpoint is
equal to the target value.
How does the bubble sort algorithm work?
Bubble sort works by:
Looking at the first two elements of the list.
Comparing their values. Swapping them if the
second element is smaller than the first
element. Repeating this until no further
changes need to be made.
How does the insertion sort algorithm work?
Intersion sort works by:
going through each element of the list.
Comparing its value to each element on the left of the element. Inserting the item in the correct position in the list.
how does the merge sort algorithm work?
Merge sort works by:
splitting the list of size n into n number of lists. Comparing values in these lists merging them into temporaty lists.
How does the qucik sort algorithm work?
Quick sort works by:
choosing an item as a pivot. Creating two sub-lists, one bigger than the pivot, one smaller.
Comparing each item to the pivot and sorting them accordingly.
Name the two path finding algorithms?
Dijkstr’s algorithm and A* algorithm
What are the differences between dikstra’s and the A* algorithm
The A* algorithm uses a heuristic value, so finds a path in a faster time. Does not consider all possible paths. Dijkstra’s uses a weightinh value and considers all paths before finding a solution, so may take longer but may find shorter route.
