CSC 482 — HW3: Language Comparison

HW3 Experiment Protocol (shared spec for every language implementation)

Source assignment: HW3.docx ("CSC 482 Homework 3 - Language Comparison", 15 pts). Unit reading tie-in: CLRS Chapter 5, "Probabilistic Analysis and Randomized Algorithms" (hiring problem, indicator random variables, randomized quicksort).

Algorithm

Randomized Quicksort, following CLRS's RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION: in-place quicksort where, at every partition step, the pivot is chosen uniformly at random from the current subarray range and swapped into the last position before running the standard Lomuto (or Hoare) partition. Expected running time O(n log n).

Cite this design as: Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 5, RANDOMIZED-QUICKSORT/RANDOMIZED-PARTITION pseudocode — implementation is original code in each language, not copied from any online source, unless a language's report says otherwise (any borrowed snippet must be cited with its URL/source).

Only language standard library / standard toolchain features may be used (e.g. Python's random module, C's rand()/<random> in C++, System.Random in C#, java.util.Random, Rust's rand crate from crates.io, Go's math/rand). No sorting-library shortcuts (don't call a built-in sort() — implement the algorithm by hand). No exotic/third-party frameworks.

Timing harness (same shape in every language)

  1. n starts at 1000.
  2. Each loop iteration:
    • Generate a fresh array of n random integers (range roughly [0, 1_000_000)). Data generation is NOT timed.
    • Start a high-resolution monotonic timer.
    • Run randomized quicksort on the array in place.
    • Stop the timer; record (n, elapsed_seconds).
  3. n *= 2 for the next iteration.
  4. Stop the loop when any of these is true:
    • the elapsed time for the iteration just run exceeds 4.0 seconds,
    • 25 iterations have run, or
    • n would exceed 200,000,000 on the next iteration (memory safety cap), whichever comes first. (Each language will naturally reach a different max n before hitting the 4s cutoff — that's expected and fine; faster/compiled languages should reach much larger n.)
  5. Append every (n, elapsed_seconds) pair, one per line, to a CSV file results/<lang>.csv with header n,time_seconds. Also print the same rows to stdout as the run happens (assignment: "Print or log the results").

Per-language deliverable layout

Each language gets its own subfolder under HW3/<lang>/ containing:

Each agent also writes HW3/reports/<lang>_report.md with:

Environment

Run inside WSL2 Ubuntu (distro name Ubuntu, 26.04 "Resolute Raccoon", default user granite with passwordless sudo) for a consistent Linux environment across all languages. Machine: AMD Ryzen 7 5800H (8 cores / 16 threads, ~3.2 GHz base), 32 GB RAM, Windows 11 Pro host, benchmarks executed inside WSL2 Ubuntu. Note the CPU in every report.

Toolchains already installed and confirmed working inside the distro:

Invocation convention — run every build/run command through WSL from the Windows side like this (works from both the Bash tool and the PowerShell tool):

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/<lang>' && <build/run command>"

Note the space in Algorithms 482 — always single-quote the cd path inside the outer double quotes exactly as shown. All Windows paths under this project are reachable at the equivalent /mnt/c/... path inside WSL, and files written from either side are immediately visible on the other (it's the same NTFS filesystem mounted into the Linux VM), so plain Write/Edit/Read tools on the Windows paths work fine for source files — only actually compiling/running needs to go through wsl.exe.

Round 2 languages (added after the initial 7)

Per the student's request to expand coverage, 8 more languages were added: JavaScript (Node.js), TypeScript, F#, Zig, Common Lisp (SBCL), Free Pascal, x86-64 Assembly (NASM), and PHP. Several genuinely non-existent or effectively-dead languages the student also asked about (R++, PEARL, Opal, Mercury, Lucid, Euler, Cobra) were skipped as infeasible — no working modern toolchain exists for them. R, Prolog, Erlang, Elixir, Swift, and COBOL were also skipped for this round: none have apt packages in this environment (a limited archive mirror missing many otherwise-common packages), each would require a substantial from-source bootstrap, and this environment's WSL Linux-side state proved unreliable during setup (an idle-timeout was silently discarding installed packages, and at least one file was found corrupted after being written — both worked around, see below), making further from-source builds a poor time/risk tradeoff for a 15-point assignment already covering 15 languages.

Toolchains for the round-2 languages, all confirmed working, none available via apt in this environment (installed via each project's official binary/source release instead) — all resolve directly by name in any WSL shell (symlinked into /usr/local/bin or wrapped there):

A note on this environment's reliability, relevant if anything needs reinstalling: this WSL instance's Linux-side state (installed packages, /etc/sudoers.d, even a script file's own contents) was observed to reset/corrupt itself at least twice during setup, correlated with the VM's default idle-auto-stop behavior — fixed by setting vmIdleTimeout=-1 in %USERPROFILE%\.wslconfig and NOT relying on sudo persisting (every root-requiring command in this project uses wsl -d Ubuntu -u root -- ... directly instead of sudo). If a toolchain that worked earlier suddenly isn't found, re-verify with a quick --version-style check before assuming the implementation is at fault.

Final synthesis (done by the coordinating agent, not per-language agents)