Algorithms Flashcards
What type of data structure does a depth-first traversal use?
1) Stack
2) When a node is visited place it on the stack
3) Once every node connected to that node has been visited, pop that node from the stack
4) In theory, should reach the bottom of the graph before coming back up to the start (LIFO)
What type of data structure does a breadth-first traversal use?
1)Queue
2)Place the first node onto the queue and every node connected to that onto the queue
3)That node has then been fully discovered, so dequeue it
4) Repeat this process until the whole thing is traversed
What is a Pre-Order Traversal used for?
Copying trees - can be performed on any tree
How do you perform a pre-order traversal?
Place a marker on the left side of each leaf
(Root, Left, Right)
What is an In-Order Traversal used for?
To search the contents of a binary tree and output them in the correct order
(Only used on binary trees)
How do you perform an In-Order Traversal?
Place a marker on the bottom of each leaf
What is a Post-Order Traversal used for?
Useful for converting Infix to Reverse Polish Notation
(Can be used on any tree)
How do you perform a Post Order traversal?
Place a marker on the right of each leaf
What is an algorithm?
A set of instructions which completes a task in a finite time and always terminates
What is a linear search?
A search to find an item in an unordered list. You search each item until you find the one you are searching for
What are the Pros/Cons of Linear Search?
Pros -
Easy to program
Cons -
Very inefficient so rarely used in the real world
What is the time complexity of a linear search?
O(N)
What is a binary search?
A search to find an item in an ordered list. Works by looking at the midpoint of a list and determining if the target is higher or lower
What is the time complexity of a binary search?
O(logN)
What is a bubble sort?
An algorithm that sorts a list of data by swapping the position of adjacent items to order them
What is the time complexity of a bubble sort?
O(N^2) - Very Inefficient
What is a merge sort?
An algorithm that sorts arrays by splitting them into smaller lists and reforming them - Divide and Conquer Method
What is the time complexity of a merge sort?
O(nlogn)
What is Dijkstra’s shortest path algorithm?
An algorithm used to find the shortest path from a starting node to each other node in a network
What is meant by a recursive subroutine?
A subroutine which calls itself
What is Reverse Polish Notation?
A postfix way of writing expressions, eliminating any brackets and order of execution.
What are the uses of RPN?
They are used on a stack, meaning it is used in any interpreters based upon a stack
Describe how a stack is used to evaluate an RPN expression
1) Algorithm moves along the expression, pushing each operand onto the stack
2) When an operator is reached, two items are popped off the stack and applied to the operator
3) The result is then stored on the stack
4) This repeats until the end of the expression, in which the answer should be calculated - pop the answer off the stack
Explain why Reverse Polish Notation is used over infix
Brackets aren’t required, so its easier to write the program
Operators appear in the order required by computation, makes it easier for the computer to evaluate
Why does a bubble sort have the time complexity O(N^2)
Because in each pass through there are n items, and there will be at most n passes through the list
Why does a linear search have the time complexity O(N)
As the list gets bigger, the time taken to search the list increases at the same rate
It looks at each item in the list, so if there are n items in the list - at worst there are n comparisons
What is the usage of Dijkstra’s shortest path algorithm?
1) Routers deploy the algorithm when trying to route packets by using the shortest path
2) Also used in satelite systems that display the fastest route to a location
Pseudocode for Linear Search
Do Until Found == True or Count == Array[Count]
If Target == Array[Count]
Found = True
Else
Count = Count +1
END IF
If Found = True
OUTPUT Target
ELSE OUTPUT Target Not Found
Pseudocode for Binary Search
Do until Found = TRUE or TopPointer < BottomPointer
If Array(MidPoint) = Target
Found = True
If Array(MidPoint) > Target
THEN TopPointer = MidPoint - 1
If Array(MidPoint) < Target
BottomPointer = MidPoint + 1
