Computer Science

Algorithms, complexity, automata, number representation and digital logic.

• How to Get a Simplified Sum of Products from a Truth Table
  Write the canonical SOP from the rows where the output is 1, then simplify with Boolean algebra or a Karnaugh map. Fully worked 3-variable example.
• Insertion Sort Average Case – Comparisons, Shifts and Θ(n²)
  Derivation of insertion sort's average case on a random permutation, about n²/4 comparisons and shifts, with the exact formula (n² + 3n)/4 − Hₙ.