4.3 Fundamentals of Algorithims Flashcards
What are the 2 features of a breadth first graph traversal?
Shortest path for an unweighted graph
uses a queue
What are the 2 features of a depth first graph traversal?
Navigating a maze
uses a stack
pre order tree traversal order
Node, Left, Right -
post order tree traversal
Left, Right, Node -
in order tree traversal and when its used (1)
Left, Node, Right -
Used in binary search trees
What is Meant by O(N)
O represents the order of complexity
N represents the number of inputs
What are the factors of complexity used in big o notation
Memory used, time clompexity
Time complexity of linear search
O(n)
Time complexity of Binary/Binary tree search
O(log n).
Time complexity of Bubble sort
O(n^2).
Time complexity of Merge sort
O(n log n).
What is djikstras algorithim?
Finds the shortest path between one node and all other nodes on a weighted graph.
It is considered a type of breadth first algorithim
What does it mean when algorithims are tractable?
These are problems that have a polynomial (or less) time solution (x^2)
What is it when an algorithim is intractable?
These are problems that have solutions in greater than polynomial time
What methods are used when tackling intractable problems
Heuristic methods
How do we trace a graph depth first
Start at a root and follow one branch as far as it will go. (using stack)
How do we trace a graph breadth-first
start at root scan every node connected and then continue scanning from left to right (using queue)
What are heuristic methods
give 2 examples
practical approaches used when finding an optimal solution is impractical or impossible due to time constraints
For example trial and error, pattern recognition
Describe the traversing of a graph breadth first using a queue
Set the root node as current node
Add current node to list of visited nodes
For every edge connected to that node enqueue the linked node
Then dequeue the current node and move front pointer up by one and repeat steps with the new current node
output all visited nodes
Describe the traversing of a graph depth frist using a stack
Visited nodes are pushed onto the stack, when there are no nodes left to visit the nodes are popped off the stack.
what does a depth first graph traversal give us
Suitable solutions for game or puzzle problems
what does an inorder traversal tell us
what does an preorder traversal tell us
used to copy a binary tree
return prefix expressions in RPN
what does an postorder traversal tell us
used to delete a binary tree
outputting postfix expressions
What is meant by infix notation
Standard notation for where the operator is fixed between the operands : A + B
What is the problem with infix notation
It can be ambiguous without brackets.
What is reverse polish notation
An alternative to infix notation without ambiguity, where the operator comes after the two operands (postfix)
What are the three main reasons why RPN if so useful
Eliminates the need for brackets in sub-expressions
Expressions are suitable for evaluation using a stack
Can be used in interpreters based on a stack
How do we convert a infix expression into RPN
Store in a binary tree, take the first number and put it as a node when you come across a operator move up the tree and make it a central node, repeat
Then By using a post order traversal, left right node
How can we evaluate a RPN using a stack
When you hit an operand push it onto the stack, when you hit an operator pop the last two items off the stack perform the calculation and push the result back onto the stack
What is a linear search algorithm
Linear search finds an item in a sorted or unsorted list by checking each item one by one
What are the advantages and drawbacks of the linear search algorithm
Doesn’t require the data set to be in order
Can be efficient for smaller data sets
easy to implement
Is inefficient for large data sets
What is a application of the linear search
find and replace function in a word processor
What is the time complexity of linear search algorithim
O(n)
What is a binary search algorithim
An efficient algorithm for finding an item in a sorted data list
What does a binary search require from a list in order to work
The list must be sorted
Describe how a binary search works
Midpoint of list is found, by performing integer division on the first and last index values added together
Checks if midpoint is value we are looking for, if not then it checks if the value that it is looking for is larger or smaller
In either case it halves the size of the data set and move to the midpoint of the top or lower half of the data set.
Process is repeated until value is found or search range is empty
What is the time complexity of a binary search
O(log n)
What is a bubble sort algorithim
A bubble sort orders an unordered list of items by comparing each item with the next on and swapping the items if they are out of order
The algorithim is complete when there are no more swaps to be made
In effect it bubbles the largest value to the end of the list hence the name.
What is the time complexity of the bubble sort
O(n^2)
What is the space complexity of the bubble sort
O(1)
What is the space complexity of the binary search
O(1)
What is the merge sort algorithim
A sorting algorithm which is very fast that carries out the following operation:
Data set is repeatedly split in half until each item is in its own list
Adjacent list sare then merged back together with each item being compared and sorted in the new combined list
This process is repeated until new list is reconstructed
What are the applications of the merge sort
Works best with large data sets
Ideal for parallel processing environments which are computing systems that perform multiple calculations or processes simultaneously
What is the time complexity of a merge sort
O(n log n)
What is the space complexity of a merge sort
O(n)
What are the applications of Djikstras shortest path algorithim
chip design
finding routes from one place to another
web crawlers
Describe the operation of djikstras shortest path algorithm
Start with the source node and set its distance to 0, all others to ∞.
Pick the closest unvisited node and update its neighbors’ distances if a shorter path is found.
Mark the node as visited (processed).
Repeat until all nodes are processed.
At the end, you have the shortest path distances from the source to every node
What are some applications of djikstras algorithim
Geographical maps application, towns = nodes, distances = edge weights
What is an algorithim
A specific sequence of stems that can be followed to complete a task that always terminates.
What is pseudocode
A text based way of representing steps in an algorithm
