Huffman coding & activity selection — implemented and formally analyzed.
A study of greedy algorithms combining working C++ implementations with a 5-page IEEE-format research paper analyzing their correctness and complexity, co-authored with four classmates and advised by two faculty members at MIU.
Two classic problems were implemented from scratch with nothing but raw arrays and no vector, priority_queue or map. Huffman coding for optimal prefix-free text compression, and the activity selection problem for optimal interval scheduling.
A heap of indices, not a heap of values — The Huffman tree lives in a flat Node pool[] array addressed by integer index (-1 for "no child"), and the custom MinHeap doesn't store nodes directly, it stores indices into that pool and dereferences pool[data[i]].freq to compare. insert()/extractMin() drive the classic repeated-merge: pull the two lowest-frequency entries, combine them into a new pool slot, until one root remains.
Merge sort, hand-rolled, for the other greedy problem — Activity selection doesn't reach for std::sort either but a recursive merge sort (merge() + sortByFinishTime()) orders activities by finish time first, then a single linear pass keeps any activity whose start time is at or after the last selection's finish time.
Exchange-argument proofs, not just working code — "If an optimal solution does not contain the earliest finishing activity, it can be replaced with that activity without reducing the number of selected activities." The paper's stated proof outline for activity selection, alongside a worked ABRACADABRA example where Huffman coding compresses 88 bits (fixed-width) down to 23 bits, a 73.9% reduction.
Complexity analysis, not benchmark numbers — Both algorithms are proven O(n log n) time / O(n) space, heap operations for Huffman, sort-then-scan for activity selection with the paper explicitly noting that accuracy/F1/precision metrics "are not applicable" here since these are deterministic algorithms verified against worked test cases, not trained models.
- Huffman compression: build tree, encode, decode
- Activity selection with optimal scheduling output
- Custom pool-indexed min-heap and hand-rolled merge sort (no STL)
- Formal IEEE-format research paper with proofs and worked examples
C++ · Pool-Indexed Min-Heap · Merge Sort · Greedy Algorithms · Asymptotic Analysis · Academic Writing · Overleaf · LaTeX
- 465 lines of C++
- 73.9% compression on worked example
- O(n log n) proven complexity
huffman_coding_code.cpp— pool-indexed min-heap implementation of Huffman coding (build tree, encode, decode)activity_selection_code.cpp— hand-rolled merge sort + linear scan implementation of activity selectionFinal Research Paper - Algorithms and analysis Project.pdf— the 5-page IEEE-format paper: correctness proofs, complexity analysis, and worked examples for both algorithms
Part of Zeiad Abogebba's portfolio — see the full write-up and gallery in the portfolio site.