462: Algorithm Analysis

Complexity analysis and design of advanced algorithmic strategies.

Topics

• Asymptotic notation: O, Ω, Θ

• Divide-and-conquer algorithms

• Dynamic programming

• Greedy algorithms

• Graph algorithms (shortest path, MST, topological sort)

• NP-completeness and reduction proofs

Projects

Travelling Salesman Problem (462/tsp/tsp.c)

Solves the Travelling Salesman Problem using branch-and-bound search. Reads city coordinates from stdin, computes pairwise distances, and finds the shortest tour with a bounding function to prune the search tree.

typedef struct s_node {
  int   level;
  int  *path;
  float bound;
} *t_node;

float best_length = FLT_MAX;
int  *best_path;

t_node give_birth(t_node parent);
t_node give_path(t_node parent, t_node kid);
float  get_bound(t_node n);

/* branch-and-bound: prune subtrees whose lower bound exceeds best known tour */
void search(t_node node) {
  if (node->bound >= best_length) return;
  if (node->level == d) {
    if (node->bound < best_length) {
      best_length = node->bound;
      memcpy(best_path, node->path, d * sizeof(int));
    }
    return;
  }
  for (int i = 0; i < d; i++) {
    t_node child = give_birth(node);
    give_path(node, child);
    search(child);
  }
}

Floyd-Warshall All-Pairs Shortest Path (462/floyd/)

Two implementations (floyd1.c, floyd2.c) of the Floyd-Warshall algorithm on a 5-node weighted graph, computing shortest paths between every pair of vertices in O(V³) time.

/* D[i][j] = shortest path i→j; P[i][j] = intermediate vertex */
for (k = 1; k <= N; k++)
    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
            if (D[i][k] + D[k][j] < D[i][j]) {
                D[i][j] = D[i][k] + D[k][j];
                P[i][j] = k;
            }

Quicksort (462/sorting/quicksort.c, 462/sorting/sort_main.c)

A partition-based quicksort implementation alongside a driver (sort_main.c) that reads integer arrays from stdin, sorts them, and outputs the result.

void quicksort(int lo, int hi) {
    if (lo < hi) {
        int pivot = partition(lo, hi);
        quicksort(lo, pivot - 1);
        quicksort(pivot + 1, hi);
    }
}

Priority Queue / Binary Heap (462/sorting/pq.cpp)

A C++ binary min-heap implementation with insert and extract-min operations, demonstrating the heap data structure underlying efficient priority queues and heap sort.

PQ_Entry Priority_Q::Extract_Min() {
    assert(Entry_Ct > 0);
    PQ_Entry result = Data[1];     /* root is the minimum */
    Data[1] = Data[Entry_Ct--];    /* move last element to root */
    Sift_Down(1);                  /* restore heap property */
    return result;
}

Pascal’s Triangle (462/pasc/pascals_triangle.c)

Generates Pascal’s triangle using dynamic programming, illustrating how combinatorial identities (binomial coefficients) can be computed iteratively in O(n²) time and space.

/* Each row reuses array b[], updating right-to-left */
for (i = 0; i <= n; i++) {
    for (j = i; j >= 0; j--) {
        b[j] = (j == 0 || j == i) ? 1 : b[j] + b[j - 1];
        printf("%d ", b[j]);
    }
    printf("\n");
}