Rosalind — Algorithmic Heights — Every problem

FIBO — Fibonacci Numbers

BINS — Binary Search

DEG — Degree Array

INS — Insertion Sort

The swap count is the number of inversions, so the same loop answers INV as well. Sorts in place, which the index assignment added for these packs is what makes possible.

DDEG — Double-Degree Array

solved Problem statement

MAJ — Majority Element

solved Problem statement

Writing this found that `{}` parsed as an empty block and evaluated to nil, so a tally could not be opened the obvious way. Fixed in the parser; `{}` in value position is now an empty map.

MER — Merge Two Sorted Arrays

solved Problem statement

2SUM — 2SUM

solved Problem statement

Any valid pair is accepted, so the answers are checked against the definition rather than against the sample string: the scan reaches 8 and -8 first and reports 1 5 where the sample reports 2 4.

BFS — Breadth-First Search

solved Problem statement

CC — Connected Components

solved Problem statement

HEA — Building a Heap

solved Problem statement

Any permutation with the heap property is accepted, so the property is what is asserted. Floyd's construction reaches 7 3 5 1 2 where the sample shows 7 5 1 3 2.

MS — Merge Sort

solved Problem statement

PAR — 2-Way Partition

solved Problem statement

Any valid partition is accepted, so the three conditions are asserted rather than one arrangement.

3SUM — 3SUM

solved Problem statement

BIP — Testing Bipartiteness

solved Problem statement

DAG — Testing Acyclicity

solved Problem statement

DIJ — Dijkstra's Algorithm

solved Problem statement

HS — Heap Sort

solved Problem statement

INV — Counting Inversions

solved Problem statement

Counted during the merge rather than pairwise, so this is n log n where INS's swap count is quadratic. The two problems ask for the same number.

PAR3 — 3-Way Partition

solved Problem statement

Dutch national flag. Any valid arrangement is accepted, so the three regions are asserted rather than one output; this one happens to match the sample.

SQ — Square in a Graph

solved Problem statement

BF — Bellman-Ford Algorithm

solved Problem statement

CTE — Shortest Cycle Through a Given Edge

solved Problem statement

MED — Median

solved Problem statement

Quickselect: recurses into one side only, so it answers the question without sorting. Cross-checked against sorting in the assertion.

PS — Partial Sort

solved Problem statement

TS — Topological Sorting

solved Problem statement

Any order with every edge pointing forwards is accepted, so that property is asserted rather than the sample text.

HDAG — Hamiltonian Path in DAG

solved Problem statement

Hard in general, easy on a DAG: a Hamiltonian path exists exactly when consecutive vertices of the topological order are joined by an edge.

NWC — Negative Weight Cycle

solved Problem statement

Every distance starts at 0, not just vertex 1, so a cycle unreachable from vertex 1 is still found.

QS — Quick Sort

solved Problem statement

SCC — Strongly Connected Components

solved Problem statement

Kosaraju, both passes iterative: a recursive depth-first search reads better but its depth is the length of a path, and the track allows 10^3 vertices.

2SAT — 2-Satisfiability

solved Problem statement

The hardest problem in the track and the one that pays off the rest: the implication graph is solved with the same Kosaraju pass SCC uses. Answers are checked by substituting them back into the formula, since any satisfying assignment is accepted.

GS — General Sink

solved Problem statement

SC — Semi-Connected Graph

solved Problem statement

SDAG — Shortest Paths in DAG

solved Problem statement

Relaxing once in topological order is linear, where Bellman-Ford needs n-1 rounds; acyclicity is what buys that.