Skip to content

README.md

Latest commit

 

History

History
258 lines (161 loc) · 7.29 KB

README.md

File metadata and controls

258 lines (161 loc) · 7.29 KB

Algorithm Challenges: Optimization & Algorithm Analysis

Python Algorithms License Tests

��� Project Overview

A comprehensive implementation and analysis of fundamental algorithms covering:

  • Sorting Algorithms: Bubble Sort, Quick Sort, Merge Sort, Python sorted()
  • Searching Algorithms: Linear Search, Binary Search, Interpolation Search, Python bisect
  • Recursion: Factorial, Fibonacci, Tower of Hanoi
  • Dynamic Programming: Memoization, Knapsack Problem, Fibonacci with DP

This project provides empirical verification of time complexity theories, performance benchmarking across multiple dataset sizes, and practical recommendations for algorithm selection.

��� Learning Objectives

  1. Implement and compare algorithmic efficiencies
  2. Analyze time and space complexity empirically
  3. Apply algorithms to real-world datasets
  4. Visualize algorithm performance
  5. Understand recursion and dynamic programming trade-offs
  6. Make data-driven decisions for algorithm selection

��� Project Structure

algorithm-challenges/ ├── data/ # 19+ benchmark datasets │ ├── sorting_benchmarks.csv │ ├── search_benchmarks_optimized.csv │ ├── recursion_benchmarks.csv │ ├── dp_benchmarks.csv │ └── [15+ more datasets...] ├── notebooks/ # 6 comprehensive analysis scripts │ ├── 01_sorting_algorithms.py │ ├── 02_searching_algorithms.py │ ├── 03_recursion_algorithms.py │ ├── 04_dynamic_programming.py │ ├── 05_algorithm_comparison.py │ └── 06_executive_summary.py ├── reports/ # 7 detailed analysis reports │ ├── sorting_algorithm_report.txt │ ├── search_algorithm_report.txt │ ├── recursion_algorithm_report.txt │ ├── dp_algorithm_report.txt │ ├── algorithm_comparison_report.txt │ ├── final_project_report.txt │ └── final_project_summary.json ├── visualizations/ # 18+ performance visualizations │ ├── 01_sorting_time_comparison.png │ ├── 02_time_complexity_growth.png │ ├── 08_factorial_performance.png │ ├── 12_fibonacci_dp_performance.png │ ├── 16_cross_algorithm_comparison.png │ ├── 17_algorithm_performance_heatmap.png │ ├── 18_executive_dashboard.png │ └── [11+ more visualizations...] ├── tests/ # Unit tests for algorithms ├── requirements.txt # Python dependencies ├── LICENSE # MIT License └── README.md

��� Getting Started

# Clone repository
git clone https://github.com/Awande07/algorithm-challenges.git
cd algorithm-challenges

# Install dependencies
pip install -r requirements.txt

# Run analysis (in order)
python notebooks/01_sorting_algorithms.py
python notebooks/02_searching_algorithms.py
python notebooks/03_recursion_algorithms.py
python notebooks/04_dynamic_programming.py
python notebooks/05_algorithm_comparison.py
python notebooks/06_executive_summary.py
��� Key Results
Sorting Algorithms

    Fastest: Python sorted() - 0.026 seconds for 50,000 elements

    Slowest: Bubble Sort - 1,005 seconds for 50,000 elements

    Speed Difference: 37,478x faster

    Recommendation: Use Python sorted() for production code

Searching Algorithms

    Binary vs Linear: 564x faster on 50,000 elements

    Best Overall: Python bisect module

    Special Case: Interpolation search for uniformly distributed data

Recursion vs Dynamic Programming

    Fibonacci DP vs Recursive: 176,456x faster for n=30

    Memory Trade-off: DP uses O(n) space vs O(n) recursion stack

    Best Practice: Use memoization for overlapping subproblems

Dynamic Programming

    Knapsack DP vs Brute Force: 5,000x faster for n=10 items

    Space Optimization: Iterative DP reduces space complexity

    Real-world Application: Resource allocation optimization

��� Performance Highlights

    37,478x speedup - Python sorted() vs Bubble Sort (n=50,000)

    176,456x speedup - Fibonacci DP vs Recursive (n=30)

    5,000x speedup - Knapsack DP vs Brute Force (n=10)

    564x speedup - Binary Search vs Linear Search (n=50,000)

��� Methodology
1. Data Generation

    Created synthetic datasets of varying sizes (100 to 50,000 elements)

    Generated edge cases (sorted, reverse sorted, duplicates)

    Created real-world scenarios (student grades, knapsack items)

2. Benchmarking Framework

    Consistent timing using Python's time.perf_counter()

    Comparison counting for algorithm operations

    Memory usage tracking with sys.getsizeof()

    Multiple test runs for statistical significance

3. Analysis Techniques

    Empirical time complexity verification

    Space complexity measurement

    Best/worst case scenario analysis

    Cross-algorithm performance comparison

��� Visualizations Created

The project includes 18 comprehensive visualizations:

    Sorting Algorithms: Time comparison, complexity growth, edge cases

    Searching Algorithms: Performance by dataset size, comparison counts

    Recursion Algorithms: Factorial performance, Fibonacci comparisons, Hanoi growth

    Dynamic Programming: Fibonacci DP performance, Knapsack comparisons

    Cross-Algorithm: Performance heatmap, executive dashboard

���️ Technical Stack

    Python 3.9+ - Core programming language

    NumPy/Pandas - Data manipulation and analysis

    Matplotlib/Seaborn - Visualization and plotting

    Pytest - Testing and benchmarking

    Memory Profiler - Space complexity analysis

��� Files Generated
Data Files (19+ files)

    Benchmark results for all algorithms

    Test datasets for various scenarios

    Performance metrics and comparisons

Reports (7 files)

    Individual algorithm analysis reports

    Cross-algorithm comparison

    Final project executive summary

    JSON summary for programmatic access

Visualizations (18+ images)

    Performance comparison charts

    Time complexity growth plots

    Algorithm operation heatmaps

    Executive dashboard

��� Business Applications

    Performance Optimization: Choose optimal algorithms for specific problems

    Resource Planning: Understand time/space trade-offs for system design

    Code Review: Identify inefficient algorithm usage in existing code

    Education: Learn algorithm complexities through empirical evidence

    Decision Making: Data-driven algorithm selection for projects

��� Contributing

Contributions are welcome! Please follow these steps:

    Fork the repository

    Create feature branch: git checkout -b feature/algorithm-improvement

    Commit changes: git commit -am 'Add new algorithm or improvement'

    Push to branch: git push origin feature/algorithm-improvement

    Create Pull Request

��� License

This project is licensed under the MIT License - see the LICENSE file for details.
��� Author

Awande Gcabashe

    GitHub: Awande07

    Project: Algorithm Challenges: Optimization & Analysis

    Date: January 5, 2026

��� Acknowledgments

    Computer Science fundamentals and algorithm theory

    Python community for excellent data science libraries

    Real-world optimization challenges that inspired this project

    Educational resources on algorithm analysis and complexity theory
    EOF