Semester 2 Project: Algorithms Library and Benchmarked Tradeoffs

Required Output Classification

Required output	Classification	Public/private guidance
Runnable project implementation and repository structure	Portfolio candidate	Polish the public repo only after tests pass, secrets are removed, and setup steps work from a clean checkout.
README with setup, inspection, verification instructions, and known limitations	Portfolio candidate	Make this public-facing if the project is safe to share; keep internal coursework notes in a private evidence folder.
Tests, traces, proofs, diagrams, benchmark outputs, or review notes required by the brief	Checkpoint evidence	Keep raw logs, benchmark runs, and reviewer comments private by default; publish summarized or reproducible versions when useful.
ADRs, design memos, runbooks, benchmark reports, and other high-effort engineering writeups	Portfolio candidate	These are worth polishing publicly when they tell a clear tradeoff story; otherwise keep them as private coursework evidence.
Final reflection, retrospective, or carry-forward notes	Checkpoint evidence	Keep candid self-assessment private unless rewritten as a concise public learning note.

tip

Build a small but disciplined algorithms repository that demonstrates three things at once: correctness, analysis, and engineering judgment. This is not just an implementation dump.

---

Project goal

Create an algorithms library in your primary language that covers all five Semester 2 modules and includes tests, benchmark evidence, and short design notes explaining why each structure or algorithm belongs in the repository.

The finished project should prove that you can:

• implement core algorithms and data structures correctly
• analyze their complexity and practical tradeoffs
• compare competing approaches with measured evidence
• organize technical work in a reviewable engineering style

---

Required scope

Your repository must include work from every module.

Module	Required project coverage
Module 1: Algorithm analysis and design	Complexity notes, recurrence examples, and at least one divide-and-conquer implementation with a proof sketch or invariant note
Module 2: Sorting, searching, and structures	Binary search plus at least three sorting algorithms, with tests that check correctness and edge cases
Module 3: Graph algorithms	Graph representation utilities plus BFS, DFS, and one weighted-graph algorithm or spanning-tree algorithm
Module 4: Dynamic programming	At least two DP problems solved in brute-force and optimized form, plus one greedy comparison
Module 5: Advanced structures	Union-find and one ordered structure or heap-heavy component, with operation-cost notes

---

Deliverables

• Repository with clear folders for src, tests, benchmarks, and docs
• README explaining how to run implementations, tests, and benchmarks
• Tests for all public algorithms and data structures
• Benchmark harness comparing at least three pairs of alternatives
• Per-module notes describing complexity, correctness idea, and tradeoff summary
• Short retrospective describing what benchmark results matched or contradicted theory

---

Benchmark requirements

Your benchmark section must include at least three comparisons such as:

• merge sort vs quicksort on different input shapes
• binary search vs linear search across changing input sizes
• adjacency list vs adjacency matrix for selected graph operations
• memoized vs tabulated DP for the same problem
• heap-backed vs tree-backed approaches for ordered retrieval workloads

For each comparison, record:

• the input shape and size
• the measured result
• the expected theoretical behavior
• the explanation for any mismatch

---

Engineering quality bar

This project also advances the cross-cutting tracks.

• Testing: include edge cases, empty inputs, duplicate values, disconnected graphs, and small counterexamples that often break naive implementations
• Git discipline: make incremental commits by feature or algorithm family, not one large final commit
• Documentation: every major algorithm should have a short note on when to use it and when not to use it
• Review readiness: another engineer should be able to clone the repo, run the tests, and understand the benchmark conclusions

---

Suggested structure

algorithms-library/
  src/
  tests/
  benchmarks/
  library/raw/
  README.md

Inside library/raw/, keep one short note per module rather than one giant write-up.

---

Self-grading rubric

Criterion	Weight	What good looks like
Correctness	30%	Implementations pass tests and handle edge cases
Analysis quality	20%	Complexity and correctness notes are accurate and concise
Breadth across modules	20%	Every module is represented with meaningful work
Benchmarks	20%	Comparisons are fair, explained, and tied back to theory
Code quality	10%	Naming, organization, and commit history support review

---

Submission checklist

• Tests pass
• Benchmarks run and results are recorded
• Every module has at least one corresponding artifact in the repo
• README explains setup and evidence
• Reflection note explains what changed in your algorithm-selection judgment during the semester

---

Production-Style Project Brief

Use this project as a reviewable engineering brief, not only a completion exercise.

Problem statement

Write a one-paragraph statement covering the user, the problem, the constraint, and the outcome this project is meant to produce.

Required evidence

• working artifact or reproducible deliverable
• README with setup, inspection, and verification instructions
• tests, traces, proofs, diagrams, benchmark output, or review notes appropriate to the semester
• decision log with at least three meaningful tradeoffs
• known limitations section with explicit scope cuts

Review questions

1. What is the smallest vertical slice that proves the project works?
2. Which requirement is most likely to be misunderstood by a reviewer?
3. What did you deliberately not build, and why?
4. What evidence would convince someone else that the result is correct?

Done means

The project is done only when another technical reader can inspect the artifact, run or review the verification evidence, and understand the tradeoffs without a live explanation.

---

Weekly Project Milestones

Use these milestones to keep the project from becoming a last-week scramble.

Milestone	Focus	Evidence
Start	Scope the smallest useful slice	problem statement, non-goals, first task list
Early build	Produce a walking version	runnable skeleton, first test, first committed artifact
Middle	Add the hard part	implementation note, trace/proof/benchmark/design decision
Review	Stress the weak point	failure case, debugging note, peer/self review, correction commit
Finish	Package for inspection	README, verification instructions, known limitations, reflection

Answer-Quality Examples

Quality	What it sounds like
Weak	"I built it because the module asked for it."
Acceptable	"It works for the required examples and I can explain the main idea."
Strong	"Here is the tradeoff I chose, the evidence that supports it, and the case where it would fail."
Portfolio-ready	"A reviewer can inspect the artifact, rerun the checks, and understand why this solution fits this semester's goals."

Future Capstone Connection

Before closing this project, write two sentences on how it could help the final capstone: one reusable technical skill and one artifact habit to preserve.

Calibration Materials

Use these learner-visible calibration materials before self-grading or requesting review:

• Answer key and solution outlines
• Rubric, passing standard, strong traits, and weak patterns