~shahper.shahin
Back to Academic Showcase
Lab WorkData Structures & Algorithms • Semester 3 (2025)September 2025

Empirical Graph Algorithm Optimization & Complexity Analysis

Abstract

“Empirical performance profiling of shortest path, minimum spanning tree, and dynamic programming algorithms across sparse and dense graph topologies.”

C++Graph AlgorithmsValgrindTime Complexity Analysis

Research / Coursework Objective

Quantify constant-factor overheads and cache locality effects in theoretical asymptotic complexities.

Methodology & Experimental Procedure

  • 1.Implementation of Dijkstra with Binary Heap vs Fibonacci Heap
  • 2.Benchmarking Kruskal's algorithm with Disjoint Set Union (path compression + rank heuristic)
  • 3.Cache line profiling using Valgrind Callgrind

Technical Implementation

Compiled with g++ -O3 on Linux.

Key Findings & Analytical Results

  • Binary heap outperforms Fibonacci heap in practice for graph sizes up to 10^6 nodes due to cache locality
  • Path compression with union-by-rank achieves near-constant amortized time complexity
Academic References
  • [1] Introduction to Algorithms (CLRS, 4th Edition)
  • [2] LPU CSE Algorithms Laboratory Manual