Dijkstra-Backtrack-CSP-String-Analysis

Final compliant solution for two tasks:

• Task 1: Bus Allocation under distance and capacity constraints
• Task 2: Music Pattern Analysis (transposition-invariant contiguous patterns)

Key Constraints

• No dictionaries or sets used anywhere
• No external graph libraries (e.g., networkx)
• From-scratch algorithms and list-based data structures

Task 1: Bus Allocation

• Graph: adjacency list from (u, v, w) undirected roads
• Distances: Dijkstra implemented from scratch (manual binary heap)
• Allocation: Backtracking CSP to assign exactly T students
• Constraints: Each bus must carry between min and max; students only board buses within distance D

Complexity (worst-case)

• Distances: O(B * (R log L))
• Mapping students to buses: O(S * B)
• Backtracking guided by capacity checks (effective for given sizes)

Run Task 1

python3 assignment_solution.py
# choose Task 1 and follow prompts

Input formats:

• roads: (0,1,3), (0,2,5), ...
• students: 4,10,8,...
• buses: (0,3,5), (6,5,10), ...

Task 2: Music Pattern Analysis

• Normalization: interval differences (key-invariant)
• Preprocessing: substrings per sequence; manual duplicate removal (no sets)
• Query: getFrequentPattern(K) returns the most frequent normalized pattern of length K

Run Task 2

python3 assignment_solution.py
# choose Task 2 and follow prompts

Files

• assignment_solution.py — main solution (both tasks + CLI)
• test_both_tasks.py — optional test harness

License

MIT