knitr::opts_chunk$set(echo = TRUE, warning = FALSE, message = FALSE)

1. Build and Inspect a priority queue

1.1 and 1.2

# Question 1: Build a min-heap by inserting values one at a time

insert_min_heap <- function(heap, value, label = NULL) {
  # Append new value at the end
  heap <- c(heap, value)
  
  # Bubble up while heap property is violated
  i <- length(heap)
  while (i > 1) {
    parent <- i %/% 2
    if (heap[parent] > heap[i]) {
      # Swap parent and child
      tmp <- heap[parent]
      heap[parent] <- heap[i]
      heap[i] <- tmp
      i <- parent
    } else {
      break
    }
  }
  
  if (!is.null(label)) {
    cat(label, ": ", paste(heap, collapse = " "), "\n", sep = "")
  }
  
  return(heap)
}

# Priority values in the given insertion order
values <- c(4, 2, 7, 1, 5, 3)

heap <- integer(0)

for (v in values) {
  heap <- insert_min_heap(heap, v, paste0("After inserting ", v))
}
## After inserting 4: 4
## After inserting 2: 2 4
## After inserting 7: 2 4 7
## After inserting 1: 1 2 7 4
## After inserting 5: 1 2 7 4 5
## After inserting 3: 1 2 3 4 5 7
cat("Final heap vector: ", paste(heap, collapse = " "), "\n", sep = "")
## Final heap vector: 1 2 3 4 5 7

1.3 Final Heap representation

  • Index: 1 2 3 4 5 6
  • Value: 1 2 3 4 5 7
  • The root is 1, which is the smallest priority value and therefore the most urgent

1.4 Heap Invariant

For every node \(i > 1\): \(heap[i] >= heap[parent(i)]\) - Every parent node’s value must be less than or equal to the values of its children \((Parent <= Child)\) and this ensures that the minimum element is always at the root

1.5 The complete heap is not necessarily a sorted vector

  • A min-heap only guarantees: For every node \(i > 1\): \(heap[i] >= heap[parent(i)]\) ie. \(Parent <= Child\)
  • A sorted vector requires: \(heap[1] <= heap[2] <= heap[3] <= ... <= heap[n]\)
  • The heap invariant does not order siblings or nodes in different subtrees. So a valid heap can have a vector that is not sorted.

2. Process alerts by priority

# Swap two elements in a vector
swap <- function(heap, i, j) {
  tmp <- heap[i]
  heap[i] <- heap[j]
  heap[j] <- tmp
  return(heap)
}

# Restore min-heap property upward
bubble_up <- function(heap, i) {
  while (i > 1) {
    parent <- i %/% 2
    if (heap[parent] > heap[i]) {
      heap <- swap(heap, parent, i)
      i <- parent
    } else {
      break
    }
  }
  return(heap)
}

# Restore min-heap property downward
bubble_down <- function(heap, i) {
  n <- length(heap)
  repeat {
    left <- 2 * i
    right <- 2 * i + 1
    smallest <- i
    
    if (left <= n && heap[left] < heap[smallest]) {
      smallest <- left
    }
    if (right <= n && heap[right] < heap[smallest]) {
      smallest <- right
    }
    
    if (smallest == i) break
    
    heap <- swap(heap, i, smallest)
    i <- smallest
  }
  return(heap)
}

2.1.1 Insert a new priority into the min-heap

# Define insertion function
insert_min_heap <- function(heap, value) {
  heap <- c(heap, value)
  heap <- bubble_up(heap, length(heap))
  return(heap)
}

# --- Demonstration & Validation ---
heap <- integer(0)
priorities <- c(4, 2, 7, 1, 5, 3)

for (p in priorities) {
  heap <- insert_min_heap(heap, p)
}

cat("Heap after insertions:", paste(heap, collapse = " "))
## Heap after insertions: 1 2 3 4 5 7

Explanation:

  • Appends the new priority value to the end of the heap vector and calls \(bubbleup()\) to swap it with its parent \((i %/% 2)\) until the parent is smaller or equal.
  • Time Complexity: \(O(log n)\)

2.1.2 Inspect the most urgent priority without removing it

# Define peek function
peek_min <- function(heap) {
  if (length(heap) == 0) {
    return(NULL)
  }
  return(heap[1])
}

# --- Demonstration & Validation ---
cat("Most urgent priority (peek):", peek_min(heap))
## Most urgent priority (peek): 1

Explanation:

  • Returns \(heap[1]\) directly, as the root of a min-heap always holds the smallest number (highest urgency). it does not alter the vector
  • Time Complexity: \(O(1)\)

2.1.3 Remove and return the most urgent priority

# Define extraction function
extract_min <- function(heap) {
  if (length(heap) == 0) {
    stop("Heap is empty")
  }
  
  min_value <- heap[1]
  n <- length(heap)
  
  # Replace root with last element and remove last element
  heap[1] <- heap[n]
  heap <- heap[-n]
  
  # Re-order heap if not empty
  if (length(heap) > 0) {
    heap <- bubble_down(heap, 1)
  }
  
  return(list(min = min_value, heap = heap))
}

# --- Demonstration & Validation ---
# Extract 1st most urgent element
result1 <- extract_min(heap)
cat("Extracted priority:", result1$min, "\n")
## Extracted priority: 1
cat("Remaining heap:", paste(result1$heap, collapse = " "), "\n\n")
## Remaining heap: 2 4 3 7 5
# Extract 2nd most urgent element
result2 <- extract_min(result1$heap)
cat("Extracted next priority:", result2$min, "\n")
## Extracted next priority: 2
cat("Remaining heap:", paste(result2$heap, collapse = " "))
## Remaining heap: 3 4 5 7

Explanation:

  • Replaces the root \(heap[1]\) with the last element \(heap[n]\), drops the last element and runs \(bubbledown()\) to restore the min-heap order by swapping with the smaller child. Returns both the extracted value and the updated heap vector.
  • Time Complexity: \(O(log n)\)

2.2 Rebuild the heap from Question 1 using the insert function

heap <- integer(0)
for (p in c(4, 2, 7, 1, 5, 3)) {
  heap <- insert_min_heap(heap, p)
}
cat("Initial heap:", paste(heap, collapse = " "), "\n\n")
## Initial heap: 1 2 3 4 5 7
# Process and remove the first three priorities
for (k in 1:3) {
  res <- extract_min(heap)
  cat("Removal", k, "\n")
  cat(" (i) Value returned:", res$min, "\n")
  cat(" (ii) Heap after restoration:", paste(res$heap, collapse = " "), "\n\n")
  heap <- res$heap
}
## Removal 1 
##  (i) Value returned: 1 
##  (ii) Heap after restoration: 2 4 3 7 5 
## 
## Removal 2 
##  (i) Value returned: 2 
##  (ii) Heap after restoration: 3 4 5 7 
## 
## Removal 3 
##  (i) Value returned: 3 
##  (ii) Heap after restoration: 4 7 5

Explanation:

  • Each call to \(extractmin()\) removes the current root (the minimum priority number), moves the last element to the root position, and runs \(bubbledown()\) to restore the min-heap order.

Big-O Time Complexity Analysis

Heap Operations & Time Complexity
Operation Function BigO_Cost Concise_Explanation
Inspecting the root peek_min() O(1) Directly accesses the first element (heap[1]) without modifying the array
Inserting a value insert_min_heap() O(logn) Appends the element at the end and bubbles up along the height of the binary tree
Removing the root extract_min() O(logn) Replaces the root with the last leaf and bubbles down along the height of the binary tree.

\(Summary:\) - The height of a complete binary tree with n nodes is \([log_2n]\). Since both insertion and root extraction traverse at most the height of the tree during bubbling operations their worst-case time complexity is \(O(log n)\), while root inspection requires constant time \(O(1)\).

3. Represent the referral network as a graph

# install.packages("igraph")
library(igraph)

# Build the graph 
edges <- data.frame(
  from = c("Kabale",  "Kabale",  "Rubanda", "Rukiga",  "Rukiga",  "Kanungu"),
  to   = c("Rubanda", "Rukiga",  "Kisoro",  "Ntungamo","Kanungu", "Ntungamo"),
  stringsAsFactors = FALSE
)

## Create an UNDIRECTED graph directly from the edge list
g <- graph_from_data_frame(d = edges, directed = FALSE)

cat("Graph summary:\n")
## Graph summary:
print(g)
## IGRAPH 8d29c00 UN-- 6 6 -- 
## + attr: name (v/c)
## + edges from 8d29c00 (vertex names):
## [1] Kabale --Rubanda  Kabale --Rukiga   Rubanda--Kisoro   Rukiga --Ntungamo
## [5] Rukiga --Kanungu  Kanungu--Ntungamo
cat("\nVertices:", vcount(g), "\n")
## 
## Vertices: 6
cat("Edges   :", ecount(g), "\n")
## Edges   : 6

3.1 Construct and display the Adjacency List

# Convert graph to adjacency list
adj_list <- as_adj_list(g, mode = "all")
cat("Adjacency list:\n")
## Adjacency list:
for(v in names(adj_list)) {
  cat(sprintf(" %-8s -> %s\n", v, paste(names(adj_list[[v]]), collapse = " ")))
}
##  Kabale   -> Rubanda Rukiga
##  Rubanda  -> Kabale Kisoro
##  Rukiga   -> Kabale Kanungu Ntungamo
##  Kanungu  -> Rukiga Ntungamo
##  Kisoro   -> Rubanda
##  Ntungamo -> Rukiga Kanungu

Explanation:

  • An adjacency list maps each vertex (health facility) to a vector containing all directly connected neighboring facilities. Since the network is undirected, connections are stored symmetrically in both directions.

3.2 List the neighbors of Rukiga

rukiga_neighbours <- names(adj_list[["Rukiga"]])
cat("Neighbours of Rukiga:", paste(rukiga_neighbours, collapse = ", "))
## Neighbours of Rukiga: Kabale, Kanungu, Ntungamo

Explanation:

  • Looks up the Rukiga element directly from the adjacency list to retrieve its connected nodes.
  • Rukiga has three direct referral links: Kabale, Ntungamo and Kanungu.

3.3 Count the total number of vertices and edges

# Calculate network metrics
n_vertices <- vcount(g)
n_edges <- ecount(g)
cat("Number of vertices (V):", n_vertices, "\n")
## Number of vertices (V): 6
cat("Number of edges (E)   :", n_edges, "\n\n")
## Number of edges (E)   : 6
cat("Degree of each facility:\n")
## Degree of each facility:
print(degree(g))
##   Kabale  Rubanda   Rukiga  Kanungu   Kisoro Ntungamo 
##        2        2        3        2        1        2

Explanation:

  • Vertices(V = 6): The six health facility nodes in the network
  • Edges(E = 6): The six direct referral road connections between facilities.
  • Degree: The count of direct links connected to each facility (Rukiga is highest at 3 and Kisoro is the lowest at 1).

3.4 Draw the graph visually

V(g)$color <- ifelse(V(g)$name == "Rukiga", "orange", "skyblue")
V(g)$frame.color <- "black"
V(g)$label.color <- "black"
V(g)$label.cex  <- 0.8
V(g)$size       <- 35

E(g)$color <- "grey40"
E(g)$width <- 3

## Fixed layout that mirrors the geography of the facilities
## (x, y) roughly matching their real positions in SW Uganda
layout_coords <- matrix(c(
  #  x   y    vertex name
   1.0, 10.0,   # Kisoro
   1.0, 7.0,   # Rubanda
   1.0, 4.0,   # Kabale
   2.5, 2.0,   # Rukiga
   1.5, 0.5,   # Kanungu
   3.5, 0.5    # Ntungamo
), ncol = 2, byrow = TRUE)
rownames(layout_coords) <- c("Kisoro","Rubanda","Kabale","Rukiga","Kanungu","Ntungamo")

## Match the layout row order to the graph's vertex order
layout_coords <- layout_coords[V(g)$name, , drop = FALSE]

plot(g,
     layout            = layout_coords,
     main              = "Referral Network (undirected graph)",
     vertex.label      = V(g)$name,
     vertex.label.dist = 0,
     edge.curved       = 0)

Explanation:

  • Renders the graph visually using node-link topology.
  • The plot confirms the layout, edge connections and highlights central hubs like Rukiga

3.5 Why an adjacency List is suitable for this network

adj_matrix <- as_adjacency_matrix(g, sparse = FALSE)
cat("Adjacency Matrix (6 x 6):\n")
## Adjacency Matrix (6 x 6):
print(adj_matrix)
##          Kabale Rubanda Rukiga Kanungu Kisoro Ntungamo
## Kabale        0       1      1       0      0        0
## Rubanda       1       0      0       0      1        0
## Rukiga        1       0      0       1      0        1
## Kanungu       0       0      1       0      0        1
## Kisoro        0       1      0       0      0        0
## Ntungamo      0       0      1       1      0        0

Explanation:

  • Space Efficiency: The network is sparse \((V = 6, E = 6)\). The matrix stores 36 values (mostly wasted 0 s), whereas the adjacency list only stores the 12 actual directional entries \((O(V + E) vs O(V^2))\).
  • Faster Operations: Querying neighboring facilities(like Rukiga in part b) or executing graph traversals (like BFS/DFS)only inspects connected neighbors directly instead of scanning full empty matrix rows

4. Traverse the referral network.

4.1 and 4.2 Implement BFS and Display Visit Order

# Define referral network adjacency list
referrals <- list(
  Kabale   = c("Rubanda", "Rukiga"),
  Rubanda  = c("Kabale", "Kisoro"),
  Rukiga   = c("Kabale", "Ntungamo", "Kanungu"),
  Kisoro   = c("Rubanda"),
  Kanungu  = c("Rukiga", "Ntungamo"),
  Ntungamo = c("Rukiga", "Kanungu")
)

# Breadth-First Search implementation (uses a FIFO Queue)
bfs <- function(graph, start) {
  visited <- character(0)
  seen <- c(start)
  queue <- c(start)
  
  while (length(queue) > 0) {
    # Dequeue front element
    v <- queue[1]
    queue <- queue[-1]
    visited <- c(visited, v)
    
    # Enqueue unvisited neighbours
    for (nbr in graph[[v]]) {
      if (!(nbr %in% seen)) {
        seen <- c(seen, nbr)
        queue <- c(queue, nbr)
      }
    }
  }
  return(visited)
}

# Run BFS starting from Kabale
bfs_order <- bfs(referrals, "Kabale")
cat("BFS Visit Order:", paste(bfs_order, collapse = " -> "))
## BFS Visit Order: Kabale -> Rubanda -> Rukiga -> Kisoro -> Ntungamo -> Kanungu

Explanation:

  • BFS explores the network level-by-level using a Queue (FIFO). Starting at Kabale, it visits immediate neighbors first (Rubanda, Rukiga) before moving to second-degree neighbors (Kisoro, Ntungamo, Kanungu).

4.3 and 4.4 Implement DFS and Display Visit Order

# Depth-First Search implementation (uses Call Stack / Recursion)
dfs <- function(graph, start) {
  visited <- character(0)
  seen <- character(0)
  
  explore <- function(v) {
    seen <<- c(seen, v)
    visited <<- c(visited, v)
    
    for (nbr in graph[[v]]) {
      if (!(nbr %in% seen)) {
        explore(nbr)
      }
    }
  }
  
  explore(start)
  return(visited)
}

# Run DFS starting from Kabale
dfs_order <- dfs(referrals, "Kabale")
cat("DFS Visit Order:", paste(dfs_order, collapse = " -> "))
## DFS Visit Order: Kabale -> Rubanda -> Kisoro -> Rukiga -> Ntungamo -> Kanungu

Explanation:

  • DFS explores as far as possible along each branch before backtracking using a Stack (LIFO / Recursion). Starting at Kabale, it dives deep through Rubanda to Kisoro before backtracking to discover Rukiga and its remaining path.

4.5 Why a Visited Record is necessary

# Demonstrate infinite loop prevention
cat("Without visited record: Kabale -> Rubanda -> Kabale -> Rubanda -> ... (Infinite Loop)\n")
## Without visited record: Kabale -> Rubanda -> Kabale -> Rubanda -> ... (Infinite Loop)
cat("With visited record   :", paste(bfs_order, collapse = " -> "))
## With visited record   : Kabale -> Rubanda -> Rukiga -> Kisoro -> Ntungamo -> Kanungu

Explanation:

  • In an undirected graph, connections exist symmetrically in both directions (e.g., Kabale \(\leftrightarrow\) Rubanda). Without a visited or seen record, the traversal algorithm would get trapped bouncing back and forth infinitely. The record ensures every facility is processed exactly once and the execution terminates.

Supplementary Theory: Data Structures and Complexity

Structures Used

Data Structures & Complexity
Traversal DataStructure ProcessingLogic
BFS Queue First-In, First-Out (FIFO) — processes nodes in order of discovery level.
DFS Stack/Recursion Last-In, First-Out (LIFO) — processes deepest nodes first before backtracking.

Time Complexity For an adjacency-list representation, time complexity is \(O(\vert{}V\vert{} + \vert{}E\vert{})\): - \(\vert{}V\vert{}\) (Vertices = 6): Each vertex is added to the queue/stack and visited at most once. - \(\vert{}E\vert{}\) (Edges = 6): Every edge is inspected twice (once from each endpoint in an undirected graph). - Total Operations: \(O(6 + 6) = O(12)\) operations, making both traversals linear relative to the network size.

5. Compare searching methods

5.1 and 5.2 Linear Search for “HC12” and Comparison Count

# Define original unsorted health facility codes
codes <- c("HC17", "HC03", "HC21", "HC08", "HC12", "HC05", "HC30", "HC01")

# Implement Linear Search function
linear_search <- function(vec, target) {
  comparisons <- 0
  for (i in seq_along(vec)) {
    comparisons <- comparisons + 1
    if (vec[i] == target) {
      return(list(index = i, comparisons = comparisons, found = TRUE))
    }
  }
  return(list(index = NA, comparisons = comparisons, found = FALSE))
}

# Run linear search for "HC12"
res_lin <- linear_search(codes, "HC12")

cat("Target 'HC12' found at index:", res_lin$index, "\n")
## Target 'HC12' found at index: 5
cat("Number of comparisons made :", res_lin$comparisons)
## Number of comparisons made : 5

Explanation:

  • Linear search iterates through the vector sequentially from left to right. It checks \("HC17", "HC03", "HC21", "HC08"\) and finds \("HC12"\) on the 5th comparison at index 5

5.3 Sort the Facility Codes

# Sort codes in ascending alphabetical order
sorted_codes <- sort(codes)

cat("Sorted codes:", paste(sorted_codes, collapse = " "))
## Sorted codes: HC01 HC03 HC05 HC08 HC12 HC17 HC21 HC30

Explanation:

  • Binary search requires the dataset to be sorted beforehand. \(sort()\) arranges the facility codes alphabetically so that index values correlate directly with element magnitude

5.4 and 5.5 Implement Binary Search and Search for “HC12”

# Implement Binary Search function
binary_search <- function(sorted_vec, target) {
  low <- 1
  high <- length(sorted_vec)
  comparisons <- 0
  
  while (low <= high) {
    mid <- floor((low + high) / 2)
    comparisons <- comparisons + 1
    
    if (sorted_vec[mid] == target) {
      return(list(index = mid, comparisons = comparisons, found = TRUE))
    } else if (sorted_vec[mid] < target) {
      low <- mid + 1
    } else {
      high <- mid - 1
    }
  }
  return(list(index = NA, comparisons = comparisons, found = FALSE))
}

# Run binary search for "HC12" on sorted list
res_bin <- binary_search(sorted_codes, "HC12")

cat("Target 'HC12' found at index:", res_bin$index, "\n")
## Target 'HC12' found at index: 5
cat("Number of comparisons made :", res_bin$comparisons)
## Number of comparisons made : 3

Explanation:

Binary search divides the search space in half repeatedly: - 1. 1st check \((mid = 4)\): \("HC08" < "HC12"\) \(\rightarrow\) search right half \((low = 5)\). - 2. 2nd check \((mid = 6)\): \("HC17" > "HC12"\) \(\rightarrow\) search left half \((high = 5)\). - 3. 3rd check \((mid = 5)\): \("HC12" == "HC12"\) \(\rightarrow\) Match found in 3 comparisons.

5.6 Search for Absent Code “HC19”

# Run binary search for an absent item
res_absent <- binary_search(sorted_codes, "HC19")

if (res_absent$found) {
  cat("Found at index:", res_absent$index, "\n")
} else {
  cat("Result: 'HC19' not found in the list.\n")
}
## Result: 'HC19' not found in the list.
cat("Number of comparisons made:", res_absent$comparisons)
## Number of comparisons made: 3

Explanation:

    1. 1st check \((mid = 4)\): \("HC08" < "HC19"\) \(\rightarrow\) go right \((low = 5)\).
    1. 2nd check \((mid = 6)\): \("HC17" < "HC19"\) \(\rightarrow\) go right \((low = 7)\).
    1. 3rd check \((mid = 7)\): \("HC21" > "HC19"\) \(\rightarrow\) go left \((high = 6)\).
    1. Since \(low (7) >high (6)\), the loop terminates and safely returns found = FALSE after 3 comparisons.
Data Structures & Complexity
Traversal DataStructure ProcessingLogic
BFS Queue First-In, First-Out (FIFO) — processes nodes in order of discovery level.
DFS Stack/Recursion Last-In, First-Out (LIFO) — processes deepest nodes first before backtracking.

6. Decide when sorting is worthwhile.

Given:

  • One linear search = \(O(n)\)

  • One sort = \(O(n log n)\)

  • One binary search (sorted) = \(O(log n)\)

  • One linear search: \(O(n)\)

  • Sort + One binary search: \(O(nlogn) + O(logn) = O(nlogn)\)

  • Sort once + k binary searches: \(O(nlogn) + k * O(logn) = O(nlogn + k logn)\)

For ONE search, sorting first costs \(O(n log n)\) but a single linear search only costs \(O(n)\). Since \(O(n) < O(n log n)\), sorting is wasted work when \(k = 1\).

For MANY searches on the same dataset:

  • k linear searches = \(O(kn)\)
  • sort once + k binary = \(O(n log n + k log n)\)
  • for large k, \(k log n << k n\), so the second strategy wins.
  • The sort cost \(O(n log n)\) is paid once and amortized.

7. Empirical demonstration (real timing, not estimates) for 6

set.seed(1)

## Build a dataset of n unsorted facility codes
n    <- 5000
pool <- sprintf("HC%04d", 1:n)
unsorted <- sample(pool)          # shuffled
sorted   <- sort(unsorted)

## Pick k targets that exist in the data
k_targets <- sample(pool, 100)

## ---- Strategy A: k linear searches on the UNSORTED vector ----
time_linear <- function(vec, targets) {
  t0 <- proc.time()["elapsed"]
  for (t in targets) {
    for (i in seq_along(vec)) if (vec[i] == t) break
  }
  proc.time()["elapsed"] - t0
}

## ---- Strategy B: sort once, then k binary searches ----
time_sorted <- function(vec, targets) {
  t0 <- proc.time()["elapsed"]
  s  <- sort(vec)                     # sort cost
  for (t in targets) {
    lo <- 1; hi <- length(s)
    while (lo <= hi) {
      mid <- (lo + hi) %/% 2
      if (s[mid] == t) break
      else if (s[mid] < t) lo <- mid + 1
      else hi <- mid - 1
    }
  }
  proc.time()["elapsed"] - t0
}

cat(sprintf("n = %d, using up to k = 100 searches\n\n", n))
## n = 5000, using up to k = 100 searches
cat(sprintf("%-6s | %-18s | %-22s\n", "k", "linear (sec)", "sort once + binary (sec)"))
## k      | linear (sec)       | sort once + binary (sec)
cat(paste(rep("-", 55), collapse = ""), "\n")
## -------------------------------------------------------
for (k in c(1, 5, 10, 20, 50, 100)) {
  tgts <- k_targets[1:k]
  ta <- time_linear(unsorted, tgts)
  tb <- time_sorted(unsorted, tgts)
  cat(sprintf("%-6d | %-18.4f | %-22.4f\n", k, ta, tb))
}
## 1      | 0.0100             | 0.0500                
## 5      | 0.0000             | 0.0400                
## 10     | 0.0200             | 0.0300                
## 20     | 0.0300             | 0.0500                
## 50     | 0.0600             | 0.0500                
## 100    | 0.1700             | 0.0600