Activity 38: Confidence quiz

Instructions: For each question below, rate your confidence level on answering it:

  • ✅ Confident - "I can do this!"
  • ⚠️ Uncertain - "I'd need to think about it"
  • ❌ Need Review - "I should study this more"

Or the happy face scale or whatever scale you want :-)

You don't need to actually answer the questions - just assess your confidence. Use this to identify areas to focus on before the exam

Fill-ins

1.1 To use both == and < comparisons on a custom struct, implement the _____ and _____ traits.

1.2 The ? operator propagates errors and can only be used in functions that return _____ or _____.

1.3 An array of i32 is stored in _____, while a String allocates memory on the _____.

1.4 To process tasks in the order they arrive, use a _____.

1.5 Data structures: BFS uses a _____ while DFS uses a _____ or recursion.

1.6 To maintain a collection where you frequently need the maximum element, use a _____.

1.7 The key property of a min-heap is that each parent node is _____ than its children.

1.8 A graph with V vertices and E edges represented as an adjacency list uses _____ space.

1.9 Quick sort's worst-case time complexity is _____, which occurs when _____.

1.10 To check if a graph contains a cycle, you can use _____ with a visited set.

1.11 Command to see the commit history: _____

1.12 Command to create a new branch called feature-x: _____

1.13 Command to see what changes you've made but haven't staged: _____

1.14 To iterate over both indices and values of a vector, use the _____ method.

1.15 A Vec<T> owns its data, while a _____ is a borrowed view of a sequence.

1.16 When a function parameter is &mut self, it can _____ the struct, but when it's &self, it can only _____.

1.17 An adjacency matrix uses O(___) space, which is wasteful for _____ graphs.

1.18 To find if there's a path between two nodes in a graph, use _____ or _____.

Code Tracing

2.1 What does this print?

#![allow(unused)]
fn main() {
use std::collections::BTreeMap;
let mut map = BTreeMap::new();
map.insert(3, "three");
map.insert(1, "one");
map.insert(2, "two");
for (k, v) in &map {
    println!("{}", k);
}
}

2.2 What is the time complexity?

#![allow(unused)]
fn main() {
fn find_pair_sum(arr: &[i32], target: i32) -> bool {
    for &num in arr {
        for &other in arr {
            if num + other == target {
                return true;
            }
        }
    }
    false
}
}

2.3 What kind of error does this produce?

fn main() {
    let data = vec![1, 2, 3];
    let first = &data[0];
    let more = data;
    println!("{}", first);
}

2.4 What does this print?

#![allow(unused)]
fn main() {
let mut v = vec![5, 3, 8, 1];
v.sort();
v.pop();
println!("{}", v.len());
}

Hand-Coding Problems

4.1 Write a function count_occurrences(vec: &Vec<i32>, target: i32) -> usize that counts how many times target appears in the vector.

4.2 Write a function using .filter() and .collect() that takes Vec<String> and returns a new Vec<String> containing only strings with length > 5.

4.3 Write two tests for a function fn median(nums: Vec<i32>) -> f64 that tests a normal case and an edge case (eg an empty vector).

Algorithm Tracing

DFS Traversal

Given this graph:

0: [1, 3]
1: [0, 2]
2: [1, 3, 4]
3: [0, 2]
4: [2]

a) Draw the graph

b) Starting from node 0, what is the DFS traversal order (assuming you visit neighbors in numerical order)?

c) After processing node 2, what is the stack contents?

Topological Sort

Given this DAG:

A: [B, C]
B: [D]
C: [D]
D: []

What is a valid topological ordering of these vertices?









Shortest Path

Given this weighted graph:

     3         2
 A ----- B ----- D
 |       |
4|      1|
 |       |
 C ----- E
     2

Edge weights: A-B: 3, B-D: 2, A-C: 4, B-E: 1, C-E: 2

Starting from A, what is the shortest path to D using Dijkstra's algorithm? Do any values get updated twice?

Max Heap

Start with an empty max-heap. Insert: 8, 3, 10, 1, 6

After all insertions, what is the array representation of the heap?

Stack-Heap Diagram

Draw a stack-heap diagram at the labeled point

fn process_data(data: &mut Vec<i32>) -> i32 {
    data.push(5);
    let s = &data[1..3];
    let x = s[0];
    // DRAW STACK-HEAP HERE
    return s.len();
}

fn main() {
    let mut nums = vec![1, 2, 3, 4];
    let result = process_data(&mut nums);
}