Student Name: ___________________________ Student ID: ___________________________ Course: CS 460 – Algorithms | Spring 2026
This README is your project documentation. Write it the way a developer would document their design decisions , bullet points, brief justifications, and concrete examples where required. You are not writing an essay. You are explaining what you built and why you built it that way. Delete all blockquotes like this one before submitting.
Document why this problem is not just a shortest-path problem. Three bullet points, one per question. Each bullet should be 1-2 sentences max.
-
Why a single shortest-path run from S is not enough: It is not enough because it is not gaurenteed to provide the most optimal path 100% of the time because it can only procceed in one direction. Meaning it cannot backtrack.
-
What decision remains after all inter-location costs are known: The remaining decision is the choice of what order the relics get visited in so that less fuel is used.
-
Why this requires a search over orders (one sentence): It is not a single computation because from the start point it checks for the shortest path reachable from relic to relic, until it has visited all relics, which it then finds shortest path to the exit (T).
List the source node types as a bullet list. For each, one-line reason.
| Source Node Type | Why it is a source |
|---|---|
| node type | one-line reason |
| node type | one-line reason |
Fill in the table. No prose required.
| Property | Your answer |
|---|---|
| Data structure name | |
| What the keys represent | |
| What the values represent | |
| Lookup time complexity | |
| Why O(1) lookup is possible |
State the total complexity and show the arithmetic. Two to three lines max.
- Number of Dijkstra runs: your answer
- Cost per run: your answer
- Total complexity: your answer
- Justification (one line): your answer
Document your understanding of why Dijkstra produces correct distances. Bullet points and short sentences throughout. No paragraphs.
Two bullets: one for finalized nodes, one for non-finalized nodes. Do not copy the invariant text from the spec.
-
For nodes already finalized (in S): Your answer here.
-
For nodes not yet finalized (not in S): Your answer here.
One to two bullets per phase. Maintenance must mention nonnegative edge weights.
-
Initialization : why the invariant holds before iteration 1: Your answer here.
-
Maintenance : why finalizing the min-dist node is always correct: Your answer here.
-
Termination : what the invariant guarantees when the algorithm ends: Your answer here.
One sentence connecting correct distances to correct routing decisions.
Your answer here.
State the failure mode. Then give a concrete counter-example using specific node names or costs (you may use the illustration example from the spec). Three to five bullets.
- The failure mode: Your answer here.
- Counter-example setup: Your answer here.
- What greedy picks: Your answer here.
- What optimal picks: Your answer here.
- Why greedy loses: Your answer here.
One bullet. Must use the word "order."
- Your answer here.
Document the three components of your search state as a table. Variable names here must match exactly what you use in torchbearer.py.
| Component | Variable name in code | Data type | Description |
|---|---|---|---|
| Current location | |||
| Relics already collected | |||
| Fuel cost so far |
Fill in the table.
| Property | Your answer |
|---|---|
| Data structure chosen | |
| Operation: check if relic already collected | Time complexity: |
| Operation: mark a relic as collected | Time complexity: |
| Operation: unmark a relic (backtrack) | Time complexity: |
| Why this structure fits |
Two bullets.
- Worst-case number of orders considered: Your answer (in terms of k).
- Why: One-line justification.
Three bullets.
- What is tracked: Your answer here.
- When it is used: Your answer here.
- What it allows the algorithm to skip: Your answer here.
Three bullets.
- What information is available at the current state: Your answer here.
- What the lower bound accounts for: Your answer here.
- Why it never overestimates: Your answer here.
One to two bullets. Explain why pruning is safe.
- Your answer here.
Bullet list. If none beyond lecture notes, write that.
- Your references here.