Fundamentals of Algorithms Flashcards
What is depth-first traversal of graphs?
Explores the graph as far a possible, then backtracking to visit unvisited nodes.
How is depth-first graph traversal implemented?
Using a recursive algorithm.
Using stacks , when a node is visited it is placed on the stack and if there are no more nodes attached to them they are popped off the stack.
What are the uses of depth-first graph traversals?
Finding a route between two nodes
Exploring a maze.
What is breadth-first graph traversal?
Visits to nodes closest to the starting point first.
How are breadth-first graph traversals implemented?
Queues keep track of the nodes to visit.
What are the uses of breadth-first graph traversals?
Social and peer-to-peer networks.
What is pre-order traversal of a binary tree?
Root
Left
Right
What is in-order traversal of a binary tree?
Left
Root
Right
What is post-order traversal of a binary tree?
Left
Right
Root
What does the in-order traversal of binary tree produce?
Alphabetical order
What does the post-order traversal of binary tree produce?
Reverse Polish Notation
What is recursion?
The process of calling a function from within itself.
What is the base/terminating case of recursion?
It defines the point at which the recursive function will stop calling itself.
What is Dijkstra’s shortest path algorithm?
An algorithm that calculates the shortest distance between two points.
What is Dijkstra’s shortest path algorithm used for in terms of graphs?
Used to calculate the shortest path between the starting node and all other nodes on weighted graphs.
What is Dijkstra’s shortest path algorithm used for?
Network routing
Packet switching
GPS
How can weighted graphs be represented?
With two dimensional arrays.
What is a linear search?
A search algorithm that looks through data one item at a time sequentially, until it finds the item being searched for or when it reaches the end of the list.
What are the advantages of linear searches?
Simple to implement
Works with unordered lists.
What are the disadvantages of linear searches?
Inefficient
Depends on the size of the dataset and where the item being searched for it located.
What are is a binary search?
It compares the item being searched for with the middle item and then splits the dataset in half, depending on if the item is less than or greater than. This repeats until the item it’s looking for is located.
What are the advantages of binary searches?
More efficient
Quicker
What are the disadvantages of binary searches?
Complex to implement
Only works for ordered lists.
What is infix notation?
An expression with the operators within the operands.
What is prefix notation?
An expression with the operators before the operands.
What is postfix notation?
An expression with the operators after the operands.
What is an operator?
A mathematical process within an expression.
What is an operand?
A value within an expression.
What is Reverse Polish Notation?
Postfix notation
Simplifying mathematical expressions, eliminating the need for brackets.
How is Reverse Polish Notation implemented?
Using a stack, operands are pushed onto the stack and when there is an operator the result is calculated, replacing the expression.
What notation is in-order binary tree traversal?
Infix notation
What notation is post-order binary tree traversal?
Postfix notation (RPN)
What notation is pre-order binary tree traversal?
Prefix notation (Polish notation).
What is bubble sort?
It compares the first two items, if the first item is bigger than the second they are swapped, this process is repeated (a pass) until the list is sorted, which is when no swaps are made.
What are the advantages and disadvantages of bubble sort?
Adv - easy to implement
Uses a small amount of memory.
Dis - inefficient with large lists
What is merge sort?
“Divide and conquer” algorithm which break the list down into sub-list, until each sub-list only contains one item, it then merges all the sub-lists together, ordering them as it goes, producing a sorted list.
What are the advantages and disadvantages of merge sort?
Adv- more efficient
Quicker for large datasets
Dis - uses more memory.
