data-structures-and-algorithms

ACSL prep + general competitive programming. I run the CS club I founded at school, so I keep adding to this whenever I learn something new or prep a lesson. The KMP and trie implementations are probably the most useful ones I've written — ended up using them way outside of contest prep.

Structure

data-structures-and-algorithms/
├── src/
│   ├── sorting/
│   │   ├── quicksort.py          # O(n log n) average, in-place
│   │   ├── mergesort.py          # O(n log n) stable sort
│   │   ├── heapsort.py           # O(n log n) heap-based
│   │   └── radix.py              # O(nk) non-comparative
│   ├── trees/
│   │   ├── bst.py                # Binary Search Tree
│   │   ├── avl.py                # Self-balancing AVL Tree
│   │   └── segment_tree.py       # Range query segment tree
│   ├── graphs/
│   │   ├── dijkstra.py           # Single-source shortest path
│   │   ├── bfs_dfs.py            # Breadth/depth-first search
│   │   ├── union_find.py         # Disjoint Set Union (DSU)
│   │   └── topological_sort.py   # Kahn's + DFS-based
│   ├── dp/
│   │   ├── knapsack.py           # 0/1 Knapsack
│   │   ├── lcs.py                # Longest Common Subsequence
│   │   ├── matrix_chain.py       # Matrix chain multiplication
│   │   └── coin_change.py        # Minimum coins / count ways
│   └── strings/
│       ├── kmp.py                # Knuth-Morris-Pratt
│       ├── trie.py               # Prefix trie
│       └── rabin_karp.py         # Rolling hash search
├── contests/
│   └── acsl_solutions.py         # ACSL-style problems with solutions
└── notebooks/
    └── complexity_analysis.ipynb # Big O analysis with timings

Categories

Category	What's covered
Sorting	QuickSort, MergeSort, HeapSort, Radix Sort
Trees	BST, AVL, Segment Tree, Fenwick Tree
Graphs	Dijkstra, BFS/DFS, Topological Sort, Union-Find
Dynamic Programming	Knapsack, LCS, Matrix Chain, Coin Change
String Algorithms	KMP, Trie, Rabin-Karp
ACSL Contests	LIFO/FIFO, prefix notation, recursion, boolean algebra

Quick start

git clone https://github.com/Bruh-Gang/data-structures-and-algorithms.git
cd data-structures-and-algorithms

from src.sorting.quicksort import quicksort
arr = [64, 34, 25, 12, 22, 11, 90]
print(quicksort(arr))  # [11, 12, 22, 25, 34, 64, 90]

from src.graphs.dijkstra import dijkstra
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}
print(dijkstra(graph, 'A'))  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

from src.dp.knapsack import knapsack_01
print(knapsack_01([2, 3, 4, 5], [3, 4, 5, 6], 8))  # 10

Complexity reference

Algorithm	Best	Average	Worst	Space
QuickSort	O(n log n)	O(n log n)	O(n²)	O(log n)
MergeSort	O(n log n)	O(n log n)	O(n log n)	O(n)
HeapSort	O(n log n)	O(n log n)	O(n log n)	O(1)
Dijkstra	—	O((V+E) log V)	O((V+E) log V)	O(V)
KMP	O(n+m)	O(n+m)	O(n+m)	O(m)
Segment Tree (query)	O(log n)	O(log n)	O(log n)	O(n)

ACSL focus areas

ACSL tests four main areas each contest:

1. LIFO / FIFO structures — stacks, queues, deques
2. Prefix / Postfix / Infix notation — expression evaluation and conversion
3. Recursive functions — trace execution, compute output
4. Boolean algebra — simplify expressions, truth tables
5. Computer number systems — base conversion, two's complement

All of these are covered in contests/acsl_solutions.py.

MIT © Vijith Velamuri