Practice - 5 Tasks
Answer the questions below
1fill in blank
easyComplete the code to sort edges by weight in Kruskal's algorithm.
DSA Rust
edges.sort_by_key(|edge| edge.[1]); Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Sorting by node1 or node2 instead of weight.
Not sorting edges at all.
✗ Incorrect
Edges must be sorted by their weight to pick the smallest edges first in Kruskal's algorithm.
2fill in blank
mediumComplete the code to find the parent of a node in the union-find structure.
DSA Rust
fn find_parent(parents: &mut Vec<usize>, node: usize) -> usize {
if parents[node] != node {
parents[node] = find_parent(parents, [1]);
}
parents[node]
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using node instead of parents[node] in recursion.
Using a fixed number like 0 or node+1.
✗ Incorrect
The function recursively finds the root parent by following the parent links.
3fill in blank
hardFix the error in the union function to correctly merge two sets.
DSA Rust
fn union(parents: &mut Vec<usize>, ranks: &mut Vec<usize>, a: usize, b: usize) {
let root_a = find_parent(parents, a);
let root_b = find_parent(parents, b);
if root_a != root_b {
if ranks[root_a] < ranks[root_b] {
parents[root_a] = [1];
} else if ranks[root_a] > ranks[root_b] {
parents[root_b] = root_a;
} else {
parents[root_b] = root_a;
ranks[root_a] += 1;
}
}
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Assigning parents[root_a] to root_a or a wrong node.
Mixing up root_a and root_b in assignment.
✗ Incorrect
When rank of root_a is less, root_a's parent should be root_b to merge sets correctly.
4fill in blank
hardFill both blanks to add edges to MST and update total weight.
DSA Rust
if find_parent(&mut parents, edge.node1) != find_parent(&mut parents, edge.node2) { union(&mut parents, &mut ranks, edge.node1, edge.node2); mst_edges.push([1]); total_weight [2] edge.weight; }
Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Pushing edge.weight instead of edge.
Using '-=' instead of '+=' for total_weight.
✗ Incorrect
Add the edge to MST edges and increase total weight by edge weight.
5fill in blank
hardFill all three blanks to create a vector of parents, ranks, and initialize MST edges.
DSA Rust
let mut parents = (0..[1]).collect::<Vec<usize>>(); let mut ranks = vec![[2]; [3]]; let mut mst_edges = Vec::new();
Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Initializing ranks with 1 instead of 0.
Using wrong size for vectors.
✗ Incorrect
Parents vector is from 0 to num_nodes-1, ranks initialized to 0 for each node, mst_edges starts empty.