Exam Flashcards
Negatives of adjacency lists
Enumerating over nodes directly is o(n) where n is number of vertices
if each node has k edges on average enumerating edges requires o(n*k) which equals o(m) where m is the total number of edges which scales badly
What is extendible hashing
A dynamic hashing technique where the hash code is treated as a bit string and the hash code splits when buckets overflow using more bits to differentiate keys
Advantages and disadvantages of quadratic probing
Advantages: reduces clustering in comparison to linear probing
better distribution of keys in tables
disadvantages: more complex than linear probing and can still fail to resolve collision if table size isn’t a prime number
suffer from secondary clustering where keys with the same initial hash code follow the same sequence
Psuedocode for bfs
BFS(Graph graph, startNode) {
currentLevel = [startNode] // Start with the list containing the start node
while currentLevel is not empty {
nextLevel = [] // Prepare a new list for the next level of nodes
for each node in currentLevel {
visit(node) // Process or visit the node
for each edge connected to node { // Explore all edges incident on the node
if edge is unexplored { // Check if the edge has been explored
neighborNode = graph.opposite(edge, node) // Find the other endpoint of the edge
if neighborNode is undiscovered { // If the neighbor node hasn’t been discovered yet
label(edge, “discovery”) // Label the edge as a discovery edge
add neighborNode to nextLevel // Add the undiscovered neighbor node to the next level
} else {
label(edge, “cross”) // If the neighbor node has already been discovered, label the edge as a cross edge
}
}
}
}
currentLevel = nextLevel // Move to the next level, update ‘currentLevel’ with the new list of nodes
}
Advantages of adjacency matrices and disadvantages
Fast edge lookup simple query A[i][j] which is o(1)
disadvantages: requires o(n^2) memory for n nodes even if a graph is sparse
finding all neighbours is an o(n) operation as it involves scanning entire row/column
What’s the length of a path
The number of edges it traverses
Why does dijkstras algorithm never work with negative weight
the algorithm assumes that adding an edge to a path will never shorten it. Negative weights violate this leading to incorrect results
Advantages and disadvantages of extendible hashing
Advantages: don’t need to resize entire table, dynamically adjusts to varying data sizes, handles collisions efficiently
disadvantages: more complex to implement and splitting buckets requires rehashing and reorganising data
Write an implementation of insertion sort (in place)
Public void insertionSort(array){
for (int i =1; I<array.length;I++){
temp = array[i]
j = i-1
while (j>=0 && array[j] > temp){
array[j+1] = array[j]
j–
}
array[j+1] = temp
Advantages of separate chaining
Handles collisions automatically
buckets can grow dynamically
performs well with a good hash function and low load factor
What’s a path
A path is a sequence of nodes and edges that link 2 nodes
How to remove a node in an edge list
Find the node object
remove from node list
traverse edge list and remove edges involving the node
Worst and average case for separate chaining
Worst case: hash function is poor and all keys map to the same bucket so it’s essentially a linked list
inserting is o(1) and searching/deleting becomes o(n)
average case: hash function distributes keys evenly.
search/delete is o(n/m)
if load factor is low it’s close to o(1)
Approach to BFS
Choose a node as first node, mark as visited
discover all neighbours that haven’t been discovered
visit each undiscovered node
once all neighbours are visited move to their discovered neighbours
Properties of a good hash function
Uniform distribution of keys
minimal collisions
fast computation
Worst and average case for separate chaining
Worst case: hash function is poor and all keys map to the same bucket so it’s essentially a linked list
inserting is o(1) and searching/deleting becomes o(n)
average case: hash function distributes keys evenly.
search/delete is o(n/m)
if load factor is low it’s close to o(1)
definition of a balanced binary search tree
In a balanced binary search tree the heights of the left and right sub trees differ by at most 1
What’s a strongly connected graph
A graph is strongly connected when the graph is connected and we respect the directions
What’s the recursive implementation of post order traversal
Public void traverse (BinaryTreeNode node){
if(node.left != null) traverse(node,left)
if(node.right!=null) traverse(node.right)
visit(node.element)
}
What’s the complexity of a rebalancing an AVL tree
A single rotation is an o(1) operation
propagating changes is an o(logn) operation as after a rotation the height of the subtree may change which requires updates to the balance factors of its patent, grandparent and so on. In the worst case the propagation may need to travel up the height of the tree which js proportional to o(logn)
Complexity of removal from an edge list
O(m) where m is the number of edges
What is a bucket overflow
A bucket overflows when it can’t store any more key value pairs due to collisions
How do we label nodes when updating a tree to deal with addition
W - the node added
Z - the first unbalanced node above w
X - the child of y with larger height
y- the child of z with larger height
how is minimal disruption value determined when deleting a node from a binary search tree
It’s the smallest value larger than the deleted node or the largest value smaller than it. So the leftmost node on the right subtree
What is a disadvantage of using heuristics
They don’t always return the correct or most optimal solution
Properties of a good hash function
Uniform distribution of keys
minimal collisions
fast computation
Psuedocode for dijkstras weighed algorithm
findShortestWeightedPaths(graph, sourceNode) {
unvisitedNodes = graph.getAllNodes() // Set of all unvisited nodes
for each node in unvisitedNodes {
shortestDistance[node] = infinity // Initialize all distances to infinity
}
shortestDistance[sourceNode] = 0 // Distance to the source node is 0
while unvisitedNodes is not empty {
currentNode = node in unvisitedNodes with smallest shortestDistance
remove currentNode from unvisitedNodes // Mark the current node as visited
for each edge connectedEdge incident on currentNode {
neighborNode = graph.getOppositeNode(connectedEdge, currentNode)
edgeWeight = graph.getEdgeWeight(connectedEdge) // Get the weight of the edge
newDistance = edgeWeight + shortestDistance[currentNode] // Tentative distance
if newDistance < shortestDistance[neighborNode] {
shortestDistance[neighborNode] = newDistance // Update to smaller distance
}
}
Psuedocode for bfs
BFS(Graph graph, startNode) {
currentLevel = [startNode] // Start with the list containing the start node
while currentLevel is not empty {
nextLevel = [] // Prepare a new list for the next level of nodes
for each node in currentLevel {
visit(node) // Process or visit the node
for each edge connected to node { // Explore all edges incident on the node
if edge is unexplored { // Check if the edge has been explored
neighborNode = graph.opposite(edge, node) // Find the other endpoint of the edge
if neighborNode is undiscovered { // If the neighbor node hasn’t been discovered yet
label(edge, “discovery”) // Label the edge as a discovery edge
add neighborNode to nextLevel // Add the undiscovered neighbor node to the next level
} else {
label(edge, “cross”) // If the neighbor node has already been discovered, label the edge as a cross edge
}
}
}
}
currentLevel = nextLevel // Move to the next level, update ‘currentLevel’ with the new list of nodes
}
}
Approach to BFS
Choose a node as first node, mark as visited
discover all neighbours that haven’t been discovered
visit each undiscovered node
once all neighbours are visited move to their discovered neighbours
Advantages of adjacency lists over edge list
No need to traverse over entire list
direct access to adjacency lists ensures o(1) removal time per edge
Complexity of node removal in an adjacency list
O(k) where k is the degree of the node
edge removal is o(1)/edge as we can directly access adjacency lists
How to remove a node in an adjacency list
Find the node object
remove from node list
remove incident edges:
access the nodes adjacent edge, for each adjacent edge remove the edge itself and update the adjacency list of the other endpoint to remove reference to this edge
Complexity of removal from an edge list
O(m) where m is the number of edges
What a weakly connected graph
A weakly connected graph is when the graph is connected if we ignore the direction of edges
Define a connected graph
A graph is connected if there’s a path between every pair of nodes
What’s a subgraph
A subset of the original nodes and edges
Definition of a tree in graphs
A tree is an undirected graph in which any 2 nodes are connected by 1 path
What’s path length
Path length is number of edges in a graph
What’s a path
A path is a sequence of nodes and edges that link 2 nodes
What is the degree of a node in a graph
The degree of a graph is the number of edges connected to it
undirected graph: total edges connected to the graph
directed graph: in degree - edges coming into the node
Out degree - edges going out of the node
