Skip to content

Latest commit

 

History

History
181 lines (148 loc) · 6.5 KB

ALGORITHM_ADDITIONS.md

File metadata and controls

181 lines (148 loc) · 6.5 KB

High Priority Algorithm Additions to Pygorithm

This document summarizes the high priority algorithms that have been successfully added to the Pygorithm library.

Summary of Additions

1. Backtracking Algorithms (New Category)

Location: pygorithm/backtracking/

N-Queens Problem (n_queens.py)

  • Author: Adwaita Jadhav
  • Functions:
    • solve_n_queens(n) - Find all solutions
    • solve_n_queens_first_solution(n) - Find first solution
    • print_board(solution) - Display solution
    • count_solutions(n) - Count total solutions
  • Time Complexity: O(N!)
  • Features: Complete backtracking implementation with board visualization

Sudoku Solver (sudoku_solver.py)

  • Author: Adwaita Jadhav
  • Functions:
    • solve_sudoku(board) - Solve 9x9 Sudoku puzzle
    • is_valid_sudoku(board) - Validate Sudoku board
    • print_board(board) - Display board with formatting
    • create_empty_board() - Generate empty board
  • Time Complexity: O(9^(n*n))
  • Features: Full constraint satisfaction with validation

Maze Solver (maze_solver.py)

  • Author: Adwaita Jadhav
  • Functions:
    • solve_maze(maze, start, end) - Find path through maze
    • solve_maze_all_paths(maze, start, end) - Find all possible paths
    • print_maze_with_path(maze, path) - Visualize solution
    • create_sample_maze() - Generate test maze
  • Time Complexity: O(4^(n*m))
  • Features: Path finding with visualization and multiple path support

Permutations Generator (permutations.py)

  • Author: Adwaita Jadhav
  • Functions:
    • generate_permutations(arr) - All permutations
    • generate_unique_permutations(arr) - Handle duplicates
    • generate_k_permutations(arr, k) - K-length permutations
    • next_permutation(arr) - Lexicographic next permutation
  • Time Complexity: O(n! * n)
  • Features: Multiple permutation algorithms with duplicate handling

2. Advanced Graph Algorithms (Extended Pathfinding)

Location: pygorithm/pathfinding/

Bellman-Ford Algorithm (bellman_ford.py)

  • Author: Adwaita Jadhav
  • Functions:
    • bellman_ford(graph, source) - Single source shortest paths
    • bellman_ford_with_path(graph, source, target) - Path reconstruction
    • detect_negative_cycle(graph) - Negative cycle detection
  • Time Complexity: O(V * E)
  • Features: Handles negative weights, detects negative cycles

Floyd-Warshall Algorithm (floyd_warshall.py)

  • Author: Adwaita Jadhav
  • Functions:
    • floyd_warshall(graph) - All-pairs shortest paths
    • get_shortest_path(source, target, next_matrix) - Path reconstruction
    • print_distance_matrix(distance_matrix) - Formatted output
    • find_diameter(distance_matrix) - Graph diameter
  • Time Complexity: O(V^3)
  • Features: Complete all-pairs solution with path reconstruction

Prim's Algorithm (prims_algorithm.py)

  • Author: Adwaita Jadhav
  • Functions:
    • prims_mst(graph, start_vertex) - Minimum spanning tree
    • prims_mst_adjacency_matrix(adj_matrix) - Matrix-based version
    • validate_mst(graph, mst_edges) - MST validation
    • is_connected_graph(graph) - Connectivity check
  • Time Complexity: O(E log V)
  • Features: Priority queue implementation with validation

3. Advanced String Algorithms (Extended Strings)

Location: pygorithm/strings/

KMP String Search (kmp_search.py)

  • Author: Adwaita Jadhav
  • Functions:
    • kmp_search(text, pattern) - Find all occurrences
    • build_lps_array(pattern) - Failure function construction
    • kmp_search_overlapping(text, pattern) - Overlapping matches
    • kmp_replace(text, pattern, replacement) - Pattern replacement
  • Time Complexity: O(n + m)
  • Features: Optimal string matching with LPS array visualization

Edit Distance (edit_distance.py)

  • Author: Adwaita Jadhav
  • Functions:
    • edit_distance(str1, str2) - Levenshtein distance
    • edit_distance_with_operations(str1, str2) - Operation sequence
    • similarity_ratio(str1, str2) - Similarity percentage
    • is_one_edit_away(str1, str2) - Single edit check
  • Time Complexity: O(m * n)
  • Features: Complete edit distance with operation tracking

4. Advanced Sorting Algorithm (Extended Sorting)

Location: pygorithm/sorting/

Bingo Sort (bingo_sort.py)

  • Author: Adwaita Jadhav
  • Functions:
    • sort(_list) - Main bingo sort implementation
    • bingo_sort_optimized(_list) - Optimized version
    • is_suitable_for_bingo_sort(_list) - Suitability analysis
    • analyze_efficiency(_list) - Performance analysis
  • Time Complexity: O(n + k) best case, O(n^2) worst case
  • Features: Efficient for datasets with many duplicates

Testing

All algorithms include comprehensive test coverage in tests/test_backtracking.py:

  • ✅ 10/10 tests passing
  • Unit tests for all major functions
  • Edge case handling
  • Performance validation

Integration

All new algorithms are properly integrated:

  • Updated module __init__.py files
  • Added to main pygorithm/__init__.py
  • Consistent API patterns maintained
  • Documentation strings included
  • Time complexity information provided

Usage Examples

Backtracking

from pygorithm.backtracking import n_queens, sudoku_solver

# Solve 8-Queens
solutions = n_queens.solve_n_queens(8)
print(f"Found {len(solutions)} solutions")

# Solve Sudoku
board = [[5,3,0,0,7,0,0,0,0], ...]  # 9x9 puzzle
sudoku_solver.solve_sudoku(board)

Graph Algorithms

from pygorithm.pathfinding import bellman_ford, floyd_warshall

# Single source shortest paths
graph = {'A': [('B', -1), ('C', 4)], ...}
distances, predecessors = bellman_ford.bellman_ford(graph, 'A')

# All pairs shortest paths
distance_matrix, next_matrix = floyd_warshall.floyd_warshall(graph)

String Algorithms

from pygorithm.strings import kmp_search, edit_distance

# Pattern matching
matches = kmp_search.kmp_search("ABABCABABA", "ABAB")

# Edit distance
distance = edit_distance.edit_distance("kitten", "sitting")  # Returns 3

Educational Value

These additions significantly enhance Pygorithm's educational value by providing:

  • Constraint Satisfaction: Backtracking algorithms for complex problems
  • Advanced Graph Theory: Shortest paths and minimum spanning trees
  • String Processing: Efficient pattern matching and text analysis
  • Specialized Sorting: Algorithms optimized for specific data patterns

All implementations maintain the library's focus on education with clear documentation, time complexity analysis, and practical examples.