# Wiki

# sketch-frontend / Gallery

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

Benchmark Name | Benchmark Description | Solution Time |
---|---|---|

Pollard.sk | A 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.sk | Implement a TreeSet from a HashSet specification. | Fast |

compress.sk | Given 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.sk | Sketches a remove method from a doubly linked list. | Fast |

enqueueSeqSK.sk | Sketches an enqueue method for a Queue represented as a linked list. | Fast |

isolateRightmost.sk | Sketch to isolate the rightmost 0 index using only bit-vector operations. | Fast |

jburnim_morton.sk | Sketch to construct 32-bit Morton numbers from two 16-bit inputs. | Fast |

karatsuba.sk | Fast | |

listReverse.sk | Sketch to reverse a list. | Fast |

log2.sk | Sketch 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.sk | Counts the number of ones in a bit-vector in logn steps. | Fast |

lss.sk | Sketch 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.sk | Sketch that computes the xor of all the bits in a bit-vector using a strategy similar to log-shifting. | Fast |

partition.sk | Partition the range [0, N-1] int P similar partitions. | Fast |

polynomial.sk | A toy Sketch to synthesize a polynomial of degree 4. | Fast |

registerlesSwap.sk | Sketch to swap two bit arrays without using extra storage. | Fast |

reverse.sk | Sketch to reverse all the bits in a word in log-time using log-shifting. | Fast |

sort.sk | Sketch of a merge sort implementation. | Fast |

stackFreeDFS.sk | Fast | |

tableBasedAddition.sk | Implements an addition of two 4-bit numbers through a table lookup. | Fast |

tutorial1.sk | Toy benchmark. | Fast |

tutorial2.sk | Toy benchmark that explores the use of generators. | Fast |

tutorial3.sk | Toy benchmarks to show complex recursive generators. | Fast |

xpose.sk | Sketch to transpose a 4X4 matrix of integers | Fast |

Updated