Algorithm Design
Skills Gained
Graph Algorithms for the Red Scare Problem
Graph Algorithms (BFS, Dijkstra, DP on DAGs)
Algorithm Design & Complexity Analysis
NP-Completeness & Reductions
Python Programming
Experimental Evaluation & Benchmarking
Algorithm Design & Complexity Analysis
NP-Completeness & Reductions
Python Programming
Experimental Evaluation & Benchmarking
2025
This project focused on solving multiple graph problems involving constrained paths with “red” vertices. We implemented algorithms in Python to analyze s–t paths under different conditions, including alternating colors, shortest red-avoiding paths, and minimum/maximum red-vertex counts. Solutions combined BFS, Dijkstra’s algorithm, dynamic programming on DAGs, and reachability analysis. We also examined computational complexity, showing that the generalized maximum-red-vertex problem is NP-hard via reduction from Hamiltonian s–t Path.
This project focused on solving multiple graph problems involving constrained paths with “red” vertices. We implemented algorithms in Python to analyze s–t paths under different conditions, including alternating colors, shortest red-avoiding paths, and minimum/maximum red-vertex counts. Solutions combined BFS, Dijkstra’s algorithm, dynamic programming on DAGs, and reachability analysis. We also examined computational complexity, showing that the generalized maximum-red-vertex problem is NP-hard via reduction from Hamiltonian s–t Path.