# DSA Full Evidence Summary ## Best Time to Buy and Sell Stock - Question: Given daily prices, find the maximum profit from one buy followed by one sell. - `naive` at largest completed size `64.0MiB`: `10.3663` ns/element-query. - `cache-aware` at largest completed size `64.0MiB`: `5.1578` ns/element-query. - `SIMD` at largest completed size `64.0MiB`: `9.8042` ns/element-query. - `cache-aware + SIMD` at largest completed size `64.0MiB`: `0.6901` ns/element-query. - Evidence verdict: timing evidence favors `cache-aware + SIMD` at the largest completed size. - Perf evidence: generic counters were captured; use the perf chart and CSV for IPC/cache-miss-rate support. ## Product of Array Except Self - Question: For every index, return the product of all other elements without division. - `naive` at largest completed size `64.0MiB`: `20.2096` ns/element-query. - `cache-aware` at largest completed size `64.0MiB`: `8.7122` ns/element-query. - `SIMD` at largest completed size `64.0MiB`: `21.1712` ns/element-query. - `cache-aware + SIMD` at largest completed size `64.0MiB`: `3.5731` ns/element-query. - Evidence verdict: timing evidence favors `cache-aware + SIMD` at the largest completed size. - Perf evidence: generic counters were captured; use the perf chart and CSV for IPC/cache-miss-rate support. ## Maximum Subarray - Question: Find the contiguous subarray with the largest sum. - `naive` at largest completed size `64.0MiB`: `10.7273` ns/element-query. - `cache-aware` at largest completed size `64.0MiB`: `8.9412` ns/element-query. - `SIMD` at largest completed size `64.0MiB`: `9.8056` ns/element-query. - `cache-aware + SIMD` at largest completed size `64.0MiB`: `1.1407` ns/element-query. - Evidence verdict: timing evidence favors `cache-aware + SIMD` at the largest completed size. - Perf evidence: generic counters were captured; use the perf chart and CSV for IPC/cache-miss-rate support. ## Trapping Rain Water - Question: Given bar heights, compute how much water is trapped. - `naive` at largest completed size `64.0MiB`: `21.4591` ns/element-query. - `cache-aware` at largest completed size `64.0MiB`: `10.4751` ns/element-query. - `SIMD` at largest completed size `64.0MiB`: `27.2468` ns/element-query. - `cache-aware + SIMD` at largest completed size `64.0MiB`: `2.4624` ns/element-query. - Evidence verdict: timing evidence favors `cache-aware + SIMD` at the largest completed size. - Perf evidence: generic counters were captured; use the perf chart and CSV for IPC/cache-miss-rate support. ## K-Sized Subarray Maximum - Question: For every fixed-width window, report the maximum value. - `naive` at largest completed size `64.0MiB`: `64.3484` ns/element-query. - `cache-aware` at largest completed size `64.0MiB`: `20.6639` ns/element-query. - `SIMD` at largest completed size `64.0MiB`: `112.4712` ns/element-query. - `cache-aware + SIMD` at largest completed size `64.0MiB`: `3.9415` ns/element-query. - Evidence verdict: timing evidence favors `cache-aware + SIMD` at the largest completed size. - Perf evidence: generic counters were captured; use the perf chart and CSV for IPC/cache-miss-rate support. ## Search in Rotated Sorted Array - Question: Search target values in a sorted array that has been rotated. - `naive` at largest completed size `64.0MiB`: `384.8632` ns/element-query. - `cache-aware` at largest completed size `64.0MiB`: `264.8689` ns/element-query. - `SIMD` at largest completed size `64.0MiB`: `1313.2236` ns/element-query. - `cache-aware + SIMD` at largest completed size `64.0MiB`: `464.8578` ns/element-query. - Evidence verdict: timing evidence favors `cache-aware` at the largest completed size. - Perf evidence: generic counters were captured; use the perf chart and CSV for IPC/cache-miss-rate support. ## Sort 0s, 1s, and 2s - Question: Sort an array whose values are only 0, 1, and 2. - `naive` at largest completed size `64.0MiB`: `35.8583` ns/element-query. - `cache-aware` at largest completed size `64.0MiB`: `4.3231` ns/element-query. - `SIMD` at largest completed size `64.0MiB`: `11.2804` ns/element-query. - `cache-aware + SIMD` at largest completed size `64.0MiB`: `1.9068` ns/element-query. - Evidence verdict: timing evidence favors `cache-aware + SIMD` at the largest completed size. - Perf evidence: generic counters were captured; use the perf chart and CSV for IPC/cache-miss-rate support. ## BFS of Graph - Question: Traverse graph vertices in breadth-first order. - `naive` at largest completed size `64.0MiB`: `74.2690` ns/element-query. - `cache-aware` at largest completed size `64.0MiB`: `54.1225` ns/element-query. - `SIMD` at largest completed size `64.0MiB`: `144.3282` ns/element-query. - `cache-aware + SIMD` at largest completed size `64.0MiB`: `65.9072` ns/element-query. - Evidence verdict: timing evidence favors `cache-aware` at the largest completed size. - Perf evidence: generic counters were captured; use the perf chart and CSV for IPC/cache-miss-rate support. ## Transpose of Matrix - Question: Transpose a dense row-major matrix. - `naive` at largest completed size `64.0MiB`: `0.2023` GiB/s. - `cache-aware` at largest completed size `64.0MiB`: `1.5820` GiB/s. - `SIMD` at largest completed size `64.0MiB`: `0.7610` GiB/s. - `cache-aware + SIMD` at largest completed size `64.0MiB`: `2.4765` GiB/s. - Evidence verdict: timing evidence favors `cache-aware + SIMD` at the largest completed size. - Perf evidence: generic counters were captured; use the perf chart and CSV for IPC/cache-miss-rate support. ## Multiply Two Matrices - Question: Multiply two dense square matrices. - `naive` at largest completed size `64.0MiB`: `0.0001` GiB/s. - `cache-aware` at largest completed size `64.0MiB`: `0.0012` GiB/s. - `SIMD` at largest completed size `64.0MiB`: `0.0001` GiB/s. - `cache-aware + SIMD` at largest completed size `64.0MiB`: `0.0094` GiB/s. - Evidence verdict: timing evidence favors `cache-aware + SIMD` at the largest completed size. - Perf evidence: generic counters were captured; use the perf chart and CSV for IPC/cache-miss-rate support.