Implement 10 Classic Algorithms with Written Complexity Analysis
6 weeks · 0 milestones
Implement 10 classic algorithms from scratch — spanning at least three of: sorting (merge, quick, heap), graph traversal (BFS, DFS, Dijkstra, A*), dynamic programming (LCS, knapsack, edit distance), and string algorithms (KMP, Rabin-Karp). Each implementation must include a written complexity analysis documenting the best, average, and worst-case time and space complexity with a brief explanation of the dominant operations, and documented trade-offs against at least one alternative algorithm. Proof: the implementations and analyses reviewed by a CS lecturer or senior engineer who provides a novel input case you haven't tested and asks you to predict your algorithm's behaviour before running it.
Milestone map
Milestone map
3 milestones
Implement from scratch without standard library implementations: merge sort, quicksort (median-of-three pivot), heap sort, binary search tree (insert, delete, in-order traversal), and a hash table with chaining. Write a test harness with at least ten test cases per data structure, including edge cases.
Proof required
Submit: a public GitHub repository containing all five implementations with a test harness showing correctness on at least ten cases per data structure (including empty input, single-element, sorted, and reverse-sorted); a performance benchmark comparing merge sort, quicksort, and heap sort on 1,000 / 10,000 / 100,000 random integers; and a 150-word explanation of the performance results. A CS lecturer or senior engineer must confirm the implementations are correct.
What gets checked
- All five implementations are from scratch — no standard library sort or hash map used for the core algorithm
- Test harness includes edge cases — empty input, single-element, sorted, and reverse-sorted
- A CS lecturer or senior engineer has confirmed the implementations are correct