input string | output string | thinking string | b list | other string | Polynomial string | beta_b string | delta_c string | gamma_c string | delta_d string | B string | C string | std string |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
Design and implement a highly concurrent, lock-free Skip List in C++20. The skip list must support insert, remove, and search operations for integer keys. Memory safety must be guaranteed using Hazard Pointers to prevent the ABA problem and use-after-free bugs during concurrent access. Provide the full C++ code and a d... | <thinking>
To implement a lock-free skip list in C++20 with hazard pointers, we need to address three main challenges: atomic node linking, safe traversal during concurrent modifications, and safe memory reclamation.
1. Node Structure: Each node contains a key and a vector of atomic pointers to the next node at each l... | null | null | null | null | null | null | null | null | null | null | null |
Implement a basic Projected Entangled Pair State (PEPS) for a 3x3 square lattice with bond dimension D=2 and physical dimension d=2 in Python using numpy. Write a function to compute the exact expectation value of the Pauli-Z operator ($\sigma_z$) at the center site (1,1). The implementation must explicitly construct t... | <thinking>
To implement a 3x3 PEPS with D=2 and d=2, we need 9 tensors, each with 5 legs (up, down, left, right, physical). The boundary legs (up for row 0, down for row 2, left for col 0, right for col 2) must be dummy indices of dimension 1.
We can use `numpy.tensordot` or `numpy.einsum` to contract the network. To ... | null | null | null | null | null | null | null | null | null | null | null |
Implement a minimal purely functional language interpreter in Python. The language supports integers, variables, anonymous functions (lambda x: body), function application, and let bindings. The interpreter must first perform Hindley-Milner type inference (including unification, the occurs check, and let-polymorphism) ... | <thinking>
To build this, we need three main components:
1. AST Definition: Classes for Int, Var, Lam (lambda), App (application), and Let.
2. Hindley-Milner Type Inference: We need Type variables (TVar), Int type (TInt), and Arrow type (TArrow). The algorithm uses a substitution map. We need `unify` with occurs check,... | null | null | null | null | null | null | null | null | null | null | null |
Implement the Ed25519 elliptic curve digital signature algorithm entirely from scratch in Python, without using any external cryptographic libraries. Your implementation must include: (1) modular arithmetic over the prime p = 2^255 - 19; (2) the SHA-512 hashing algorithm; (3) elliptic curve point arithmetic on the twis... | <thinking>
To implement Ed25519 from scratch, we need to break it down into several highly precise mathematical components.
1. **SHA-512**: We need a full SHA-512 implementation (64-byte blocks, 80 rounds, specific K constants).
2. **Field Arithmetic**: Arithmetic modulo $p = 2^{255} - 19$. Since Python handles arbitr... | null | null | null | null | null | null | null | null | null | null | null |
Design and implement a cooperative M:N green thread scheduler in Rust. The scheduler should spawn N OS threads (workers) and schedule M tasks. Tasks are Rust Futures. Each worker maintains a Chase-Lev work-stealing deque. When a worker's local deque is empty, it must attempt to steal tasks from other workers. Provide t... | <thinking>
To build an M:N scheduler in Rust, we need:
1. **Task Abstraction**: A task is a `Pin<Box<dyn Future<Output = ()> + Send>>`.
2. **Chase-Lev Deque**: A lock-free work-stealing deque. It uses an array (or `Vec`) of tasks and atomic indices (`top` and `bottom`). The owner pushes/pops from the `bottom` (LIFO), w... | null | null | null | null | null | null | null | null | null | null | null |
Implement a highly optimized, constant-time Number Theoretic Transform (NTT) in Rust for the lattice-based cryptographic scheme CRYSTALS-Kyber. The implementation must operate in the polynomial ring R_q = Z_q[X]/(X^256 + 1) with q = 3329. Your deliverable must include: 1. A detailed mathematical derivation of why q=332... | <think>
To solve this, we analyze the algebraic structure of CRYSTALS-Kyber. The ring is R_q = Z_q[X]/(X^256 + 1) with q = 3329.
1. Incomplete NTT derivation: For X^n + 1 to split completely modulo q, we need q = 1 (mod 2n). Here n=256, so we need q = 1 (mod 512). However, 3329 mod 512 = 257. Thus, X^256 + 1 does not s... | null | null | null | null | null | null | null | null | null | null | null |
Design and implement an advanced stochastic task scheduler for a heterogeneous distributed computing environment. The system must schedule a Directed Acyclic Graph (DAG) of tasks where execution times are not deterministic but follow known probabilistic distributions (e.g., log-normal). The objective is to minimize the... | <think>
1. Mathematical Formulation: Given DAG G=(V,E), each task v has execution time T_v ~ Lognormal(mu_v, sigma_v^2) on processor p. Let C(v) be completion time. The makespan is max C(v). We want to minimize E[C_max] subject to P(C_max > D) < epsilon.
2. Algorithm Design: Standard HEFT computes average execution tim... | null | null | null | null | null | null | null | null | null | null | null |
Implement a full type-checker and evaluator for a small kernel of the Calculus of Constructions (CoC), a dependent type theory that serves as the foundation for proof assistants like Coq and Lean. Your implementation must support: 1. Dependent function types (Pi-types), dependent pair types (Sigma-types), an infinite h... | <think>
CoC requires handling terms: Sort i, Var n, App t1 t2, Lam t1 t2, Pi t1 t2. We use de Bruijn indices for variables to easily handle alpha-equivalence.
For NbE, we need two domains: Term (syntactic) and Value (semantic). Values can be VSort, VNeutral (stuck terms), VLam (closure), VPi (closure).
The type checker... | null | null | null | null | null | null | null | null | null | null | null |
Develop a robust and highly optimized continuous-space motion planning framework for a 7-Degree-of-Freedom (7-DOF) robotic arm navigating a 3D environment with complex static obstacles. The framework must combine: 1. A custom implementation of a Kinodynamic Rapidly-exploring Random Tree (RRT*) that operates directly in... | <think>
1. Forward Kinematics: 7 DOF arm. DH parameters map joint angles theta to 4x4 transformation matrices T_i = Rot_z(theta_i) * Trans_z(d_i) * Trans_x(a_i) * Rot_x(alpha_i). The end-effector pose is T_0^7 = T_0^1 * ... * T_6^7. Each link i is bounded by an OBB in its local frame.
2. OBB and SAT: An OBB has a cente... | null | null | null | null | null | null | null | null | null | null | null |
Derive and implement the Adjoint Sensitivity Method (also known as the continuous backpropagation algorithm) for Neural Ordinary Differential Equations (Neural ODEs) entirely in CUDA C++. The implementation must be self-contained and include: 1. A rigorous mathematical derivation of the adjoint state equations: proving... | <think>
1. Mathematical Derivation: The ODE is dz/dt = f(z, t, theta). The solution is z(t1) = z(t0) + integral f. Loss L(z(t1)). We want dL/dz(t0) and dL/dtheta. Define adjoint a(t) = dL/dz(t). By differentiating the exact solution and applying the chain rule, we get the adjoint ODE: da/dt = -a(t)^T * df/dz. The gradi... | null | null | null | null | null | null | null | null | null | null | null |
You are tasked with designing and implementing a distributed transactional key-value store from scratch. The system must guarantee Strict Serializability (Linearizability + Total Order) across a distributed cluster, even under network partitions and node crashes. You must use a combination of Multi-Paxos for consensus ... | <think>To solve this advanced distributed systems problem, I need to carefully integrate distributed consensus (Multi-Paxos) with local concurrency control (MVCC). Strict Serializability requires that the observed order of transactions is equivalent to a sequential execution, and that the real-time order of transaction... | null | null | null | null | null | null | null | null | null | null | null |
Implement a complete quantum circuit compiler and simulator in Python from scratch. Your system must parse a simplified QASM-like string, perform circuit optimization (specifically canceling adjacent identical single-qubit gates and merging adjacent CNOTs where applicable), and simulate the circuit using a dense densit... | <think>To build this, I need a pipeline:
1. Parser: Parse QASM into an Abstract Syntax Tree (AST) representing the quantum circuit.
2. Optimizer: Traverse the AST and apply optimizations. The most common is canceling adjacent H H (which equals Identity) or X X.
3. Simulator: Use a density matrix rho = |psi><psi|. For N... | null | null | null | null | null | null | null | null | null | null | null |
Implement the core mechanics of a zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) system from scratch. Specifically, implement the transformation of an arithmetic circuit into a Rank-1 Constraint System (R1CS), the conversion of R1CS into a Quadratic Arithmetic Program (QAP), and the KZG polyno... | <think>1. Arithmetic Circuit: For x^3 + x + 5 = y, we introduce intermediate variables v1 = x, v2 = x^2, v3 = x^3, v4 = x^3 + x, v5 = x^3 + x + 5 = y.
Wait, R1CS requires quadratic constraints.
v2 = v1 * v1
v3 = v2 * v1
v4 = v3 + v1
v5 = v4 + 5
Flattened to R1CS:
Constraint 1: v2 = v1 * v1
Constraint 2: v3 = v2 * v1
C... | null | null | null | null | null | null | null | null | null | null | null |
Design and implement a wait-free, NUMA-aware memory allocator in C++20. The allocator must satisfy the following constraints: 1) Wait-free execution: every thread can allocate or free memory in a bounded number of steps, regardless of other threads. 2) NUMA-awareness: Memory is allocated on the local NUMA node of the r... | <think>Wait-free allocation is notoriously hard. We can achieve wait-freedom by using a thread-local slab allocator backed by a global lock-free queue for fetching new slabs. Wait-free reclamation can be achieved using Hazard Pointers.
To make it NUMA-aware, we can use numa_alloc_onnode or mmap with mbind. Since C++20 ... | null | null | null | null | null | null | null | null | null | null | null |
Build a custom reverse-mode automatic differentiation engine in C++17 that natively supports sparse tensors in COO (Coordinate) format. The engine must support topological sorting for gradient computation. Your task is to implement a specialized fused operation for Sparse Matrix-Matrix Multiplication (SpMM) and its bac... | <think>Reverse-mode autograd requires a computational graph. I'll create a Node base class with a forward and backward method. Tensors will be SparseTensor and DenseTensor.
For SpMM, C = A * B. A is sparse (M x K), B is dense (K x N), C is dense (M x N).
Forward pass: For each non-zero element (i, k) in A with value v,... | null | null | null | null | null | null | null | null | null | null | null |
Implement the SA-IS (Suffix Array Induced Sorting) algorithm in C++17 that runs in O(n) time and O(n) space for an arbitrary integer alphabet (values in [0, σ)). Specifically: (1) Build the suffix array of a string s of length n (1 ≤ n ≤ 10^7) in linear time, where s[i] ∈ [0, σ) for i < n and the implicit sentinel s[n-... | Below is a complete, tested C++17 implementation of SA-IS with a formal proof sketch, complexity analysis, LCP construction via Kasai, and a stress-test harness.
---
## Formal proof (sketch)
### 1. L/S type classification
Define t[i] ∈ {L,S}. The last position n−1 is S by convention (the sentinel). For 0 ≤ i < n−1:
-... | <think>
SA-IS is a recursive algorithm. Let me carefully plan the components:
1. Type classification: Scan right-to-left. The last position (n-1) is S-type by convention (the sentinel position). For i < n-1, position i is S-type if s[i] < s[i+1], or s[i] == s[i+1] and i+1 is S-type; L-type otherwise. An LMS position i... | null | null | null | null | null | null | null | null | null | null |
Implement Sleator and Tarjan's Link-Cut Tree (LCT) data structure in C++17 with the splay-tree representation of preferred paths. Required operations on a forest of rooted trees with N nodes (1 ≤ N ≤ 2×10^5) and Q queries (1 ≤ Q ≤ 2×10^5):
• `link(u, v)`: make u (currently a root) a child of v.
• `cut(u)`: remove t... | Below is a complete C++17 Link-Cut Tree implementation, formal proof of amortized complexity, correctness arguments, and a randomized stress test against a naive baseline.
---
## Formal proof (sketch)
### Representation
A forest of rooted trees is represented as a set of **preferred paths**, each stored in a splay tr... | <think>
Link-Cut trees store a represented forest as a collection of splay trees, one per preferred path. A preferred path is a maximal chain where each node's preferred child is the one most recently accessed. Each splay node has: parent (splay-tree parent OR path-parent if it's the root of its splay tree), left/right... | null | null | null | null | null | null | null | null | null | null |
End of preview. Expand in Data Studio
Dataset Description
GLM-5.3-DeepThink-Max-50x is a reasoning/knowledge distillation dataset containing a total of 50 deep, long, and advanced code reasoning traces all extracted from the GLM 5.3 model on DeepThink Max Reasoning Effort. The average trace size is around 28kb, and it is important to note that the trace size heavily varies between different traces going from 8kb up to 60kb+ in certain traces. The format is a basic input output format where the output includes the thinking process and final output and the input includes... the input.
Dataset Details
- Curated by: MoreThought
- Funded by: MoreThought
- Shared by: MoreThought
- License: apache 2.0
Uses
- Reasoning/Knowledge distillation from GLM 5.3
- SFT on SLMs and LLMs with long context
- Finetuning non-coding or basic models on code reasoning traces
- Downloads last month
- 44