295: Discrete Structures

Foundations of mathematical reasoning for computer science.

Topics

• Boolean algebra and logic gates

• Combinatorics and counting principles

• Graph theory

• Inductive and deductive proofs

• Recurrence relations

• Finite state machines (FSMs)

Projects

Finite-State Automaton (295/fsa.c)

Implements a three-state FSA that accepts a stream of binary integers and transitions between states according to a fixed transition table, demonstrating the connection between formal automata theory and executable code.

int state = 0;
int input = 0;

while (input != -1) {
  scanf("%d", &input);
  if (state == 0) {
    state = (input == 0) ? 1 : 0;
  } else if (state == 1) {
    state = (input == 0) ? 2 : 0;
  } else if (state == 2) {
    state = (input == 0) ? 2 : 0;
  }
  printf("state = %d\n", state);
}

Tower of Hanoi (295/hanoi.c)

Generates the move sequence for the Tower of Hanoi problem, illustrating recursive problem decomposition and exponential time complexity.

/* M(k) = 2·M(k-1) + 1 minimum moves for k discs */
int m[64];
for (k = 1; k < 64; k++)
    m[k] = 2 * m[k - 1] + 1;

for (i = 0; i < 64; i++)
    printf("m[%d]=%d\n", i, m[i]);

Factorial (295/factorial.c)

Recursive implementation of the factorial function — a canonical example of inductive definition and base-case reasoning.

int Factorial(int n) {
    if (n <= 1)
        return 1;
    return n * Factorial(n - 1);
}

Compound Interest (295/compound.c)

Recursively computes compound interest at 5.5% annual growth, demonstrating recurrence relations applied to a real-world financial formula.

float amount(int t) {
    if (t == 0)
        return 1000.0;            /* principal */
    return amount(t - 1) * 1.055; /* 5.5% annual growth */
}

Sorting Algorithm Comparison (295/improved_bubble.c, 295/sort.c, 295/time.c)

Three programs exploring optimized bubble sort: improved_bubble.c implements early-termination bubble sort, sort.c compares it against the naive version on large arrays, and time.c measures wall-clock execution time using ftime.

void improvedbubble(int a[], int n) {
    int pass = 1, sorted = 0, temp;
    while (!sorted) {
        sorted = 1;
        for (int i = 0; i < n - pass; i++)
            if (a[i] > a[i + 1]) {
                temp = a[i]; a[i] = a[i+1]; a[i+1] = temp;
                sorted = 0;
            }
        pass++;
    }
}