Clone wiki

sketch-frontend / Gallery

This is a gallery to showcase sketches for some interesting programming problems.

Benchmark NameBenchmark DescriptionSolution Time
Pollard.skA read-only array with N elements contains the values {1,...,N-1}. This Sketch finds the duplicate entry using only constant extra space.Fast
SetTest.skImplement a TreeSet from a HashSet specification.Fast
compress.skGiven a bit-vector and a bit-mask, the task is select from the bit-vector all the bits selected by the bit-mask and pack them in the beginning of the word.Fast
doublyLinkedList.skSketches a remove method from a doubly linked list.Fast
enqueueSeqSK.skSketches an enqueue method for a Queue represented as a linked list.Fast
isolateRightmost.skSketch to isolate the rightmost 0 index using only bit-vector operations.Fast
jburnim_morton.skSketch to construct 32-bit Morton numbers from two 16-bit inputs.Fast
listReverse.skSketch to reverse a list.Fast
log2.skSketch to compute the logarithm base two of an integer represented as a vector of bits. The number of loop iterations is synthesized by Sketch.Fast
logcount.skCounts the number of ones in a bit-vector in logn steps.Fast
lss.skSketch that takes in an array of signed inputs and returns the maximum value of the sum of any contiguous subarray, in linear time.Fast
parity.skSketch that computes the xor of all the bits in a bit-vector using a strategy similar to log-shifting.Fast
partition.skPartition the range [0, N-1] int P similar partitions.Fast
polynomial.skA toy Sketch to synthesize a polynomial of degree 4.Fast
registerlesSwap.skSketch to swap two bit arrays without using extra storage.Fast
reverse.skSketch to reverse all the bits in a word in log-time using log-shifting.Fast
sort.skSketch of a merge sort implementation.Fast
tableBasedAddition.skImplements an addition of two 4-bit numbers through a table lookup.Fast
tutorial1.skToy benchmark.Fast
tutorial2.skToy benchmark that explores the use of generators.Fast
tutorial3.skToy benchmarks to show complex recursive generators.Fast
xpose.skSketch to transpose a 4X4 matrix of integersFast