DS-Practice

Data structures, algorithms, and systems programs written while working through Computer Engineering coursework at TCET Mumbai — Data Structures and Java (Java), Design & Analysis of Algorithms, Operating Systems, and Computer Networks (Python).

Everything here is implemented from the algorithm rather than adapted from a library. Where a second version of something exists — a different partitioning scheme, an iterative form instead of a recursive one — both are kept rather than the earlier one being deleted.

---

Java — data structures

Structure	File
Singly linked list	singly_linked_list.java
Doubly linked list	doubly_linked_list.java
Stack	stack.java
Queue	queue.java
Circular queue	circular_queue.java
Collections framework — Stack, Queue, List, Map	collections_framework_demo.java
Multithreading — extends Thread and implements Runnable	multithreading_demo.java

Earliest exercises — control flow and operators — are kept under _early-practice/.

Python — algorithms

Sorting

Algorithm	Complexity	File
Selection sort	O(n²)	selection_sort.py
Insertion sort	O(n²), O(n) best	insertion_sort.py
Merge sort	O(n log n)	merge_sort.py
Quick sort	O(n log n) avg	quick_sort.py

Graphs

Algorithm	Complexity	File
Dijkstra (binary heap)	O((V + E) log V)	dijkstra.py
Kruskal MST (union–find, path compression)	O(E log E)	kruskal_mst.py
Floyd–Warshall (all-pairs, step trace)	O(V³)	floyd_warshall.py

Dynamic programming

Algorithm	Complexity	File
Longest common subsequence	O(mn)	longest_common_subsequence.py

Backtracking & branch-and-bound

Algorithm	Complexity	File
N-Queens	O(n!) worst	n_queens.py
15-Puzzle (A*, Manhattan heuristic)	branch-and-bound	fifteen_puzzle_astar.py

String matching

Algorithm	Complexity	File
Knuth–Morris–Pratt (LPS prefix table)	O(n + m)	kmp.py
Rabin–Karp (rolling hash)	O(n + m) avg	rabin_karp.py

Operating systems

Topic	File
Banker's algorithm — deadlock avoidance, safe-sequence simulation across scenarios	bankers_algorithm.py
Page replacement — FIFO / LRU / Optimal comparison	page_replacement.py
Memory segmentation — logical-to-physical address translation	memory_segmentation.py

Computer networks

Topic	File
Cyclic redundancy check — polynomial mod-2 division	crc.py
Hamming code — dynamic parity generation and single-bit error correction	hamming_code.py
TCP socket pair	tcp_server.py · tcp_client.py
UDP socket pair	udp_server.py · udp_client.py

Applications

Project	File
Railway reservation simulation — priority queue and deque scheduling across passenger categories	railway_reservation_sim.py

---

Still to add

Worked through on paper during coursework, not yet committed. The running list, with an approach and a test case for each, is in TO_TRANSCRIBE.md.

Binary search · Strassen's matrix multiplication · fractional knapsack · Prim's MST · job sequencing with deadlines · multistage graph · Bellman–Ford · 0/1 knapsack · Held–Karp TSP · sum of subsets · graph colouring · naive string matching · sliding window maximum · Boyer–Moore

---

Running

Python files are standalone and need nothing beyond the standard library:

python3 algorithms/graphs/dijkstra.py

Java files compile individually:

javac java-data-structures/stack.java && java stack

The socket programs run as a pair — server first, client in a second terminal.