Algorithms (18) · Arithmetic (2) · Astronomy (11) · Classic Algorithms (6) · Computational Geometry (2) · Cryptography (26) · Data Processing (7) · Data Structures (5) · Fundamentals of Computing (16) · Games (24) · Graphs (8) · Guest Authors (10) · Historical Computing (14) · Interview Question (1) · Interview Questions (36) · Logic (4) · Mathematics (55) · Number Theory (1) · Parsing (13) · Prime Numbers (67) · Puzzles (17) · Random Number Generators (9) · Recreational Mathematics (51) · Simulation (11) · Sorting and Searching (47) · Spelling (7) · Strings (11) · Text Processing (2) · Unix V7 (24) · Word Games (12)
| Algorithms | |||||
| 391 | 16 Nov 2012 | List Intersection And Union: Two algorithms on linked lists, with multiple solutions | exercise solution codepad | ||
| 392 | 20 Nov 2012 | List Difference: Another algorithm on linked lists | exercise solution codepad | ||
| 395 | 30 Nov 2012 | Selection, Revisited: A guaranteed linear-time algorithm for selection | exercise solution codepad | ||
| 396 | 04 Dec 2012 | Median Of Five: A very fast method to compute the median of five items | exercise solution codepad | ||
| 397 | 07 Dec 2012 | Wirth Problem 15.12: Compute a sequence of numbers defined by Wirth | exercise solution codepad | ||
| 398 | 11 Dec 2012 | Stepwise Program Development: A Heuristic Algorithm: A backtracking solution to a problem of Wirth | exercise solution codepad | ||
| 426 | 26 Mar 2013 | Google Code Jam Qualification Round Africa 2010, Revisited: Four solutions to a Google programming exercise, with various time complexities | exercise solution codepad | ||
| 430 | 09 Apr 2013 | Cyclic Equality: Determine if two cyclic lists are equal | exercise solution codepad | ||
| 431 | 12 Apr 2013 | Booth’s Algorithm: Determine of two cyclic lists are equal | exercise solution codepad | ||
| 437 | 03 May 2013 | Pairing Students: Create sets of students, each paired to the other only once | exercise solution codepad | ||
| 438 | 07 May 2013 | Three List Exercises: Three simple exercises on lists, for beginning programmers | exercise solution codepad | ||
| 441 | 17 May 2013 | Coin Change, Part 1: Classic problem to count the ways to make change | exercise solution codepad | ||
| 442 | 21 May 2013 | Coin Change, Part 2: A variant on the classic coin change problem | exercise solution codepad | ||
| 443 | 24 May 2013 | Coin Change, Part 3: Another variant on the classic coin change problem | exercise solution codepad | ||
| 447 | 07 Jun 2013 | Sets: A classic data structure and associated algorithms | exercise solution codepad | ||
| 483 | 18 Oct 2013 | Binary Tree Traversal: Traverse a binary tree in pre-order and post-order | exercise solution codepad | ||
| 484 | 22 Oct 2013 | David Gries’ Coffee Can Problem: Simulate the process of extracting beans from a coffee can | exercise solution codepad | ||
| 485 | 25 Oct 2013 | Pessimal Algorithms And Simplexity Analysis: The slowsort algorithm using the multiply and surrender algorithms | exercise solution codepad | ||
| Arithmetic | |||||
| 433 | 19 Apr 2013 | Integer Roots: Calculate square roots and higher roots in integer arithmetic | exercise solution codepad | ||
| 444 | 28 May 2013 | Modular Multiplication Without Overflow: Perform modular multiplication without overflowing an integer datatype | exercise solution codepad | ||
| Astronomy | |||||
| 10 | 24 Feb 2009 | Mardi Gras: Compute the date of Easter | exercise solution codepad | ||
| 15 | 13 Mar 2009 | Friday, the Thirteenth: A small calendar library, and a simple use of it | exercise solution codepad | ||
| 88 | 24 Nov 2009 | Sunrise, Sunset: Calculate the times of sunrise and sunset on any day anywhere in the world | exercise solution codepad | ||
| 98 | 01 Jan 2010 | Cal: Print a twelve-month calendar | exercise solution codepad | ||
| 104 | 22 Jan 2010 | Phases Of The Moon: Calculate the number of days since the last new moon | exercise solution codepad | ||
| 123 | 30 Mar 2010 | Passover: Calculate the dates of the Jewish holidays Rosh Hashanah and Passover | exercise solution codepad | ||
| 174 | 08 Oct 2010 | Zeller’s Congruence: Calculate the day of the week for a given date | exercise solution codepad | ||
| 248 | 24 Jun 2011 | Thank God It’s Friday!: Three methods to calculate the day of the week | exercise solution codepad | ||
| 312 | 07 Feb 2012 | Solar Compass: Determine North by sighting the Sun | exercise solution codepad | ||
| 370 | 31 Aug 2012 | Once In A Blue Moon: Find months with two full moons | exercise solution codepad | ||
| 376 | 21 Sep 2012 | Autumn Equinox: Calculate the length of the day; provides a time-handling library | exercise solution codepad | ||
| Classic Algorithms | |||||
| 265 | 23 Aug 2011 | Knapsack: Fill a knapsack to maximize the value of its contents | exercise solution codepad | ||
| 279 | 11 Oct 2011 | Tower Of Hanoi: Classic demonstration of recursion | exercise solution codepad | ||
| 340 | 15 May 2012 | Streaming Knapsack: Find first possible combination from a stream that sums to a given integer | exercise solution codepad | ||
| 358 | 20 Jul 2012 | Infix Expression Evaluation: Write a parser to evaluate arithmetic expressions | exercise solution codepad | ||
| 420 | 05 Mar 2013 | Dutch National Flag: Classic ternary sort by Edsgar Dijkstra | exercise solution codepad | ||
| 450 | 18 Jun 2013 | 3SUM: A classic of computer science: find three numbers in an array that sum to zero | exercise solution codepad | ||
| Computational Geometry | |||||
| 405 | 02 Jan 2013 | Four Points Determine A Square: Determine if four given points form a square | exercise solution codepad | ||
| 408 | 18 Jan 2013 | Triangle Trilemma: Determine if three points form a triangle, and classify it | exercise solution codepad | ||
| Cryptography | |||||
| 6 | 20 Feb 2009 | ROT13: A simple Caesar-shift cipher | exercise solution codepad | ||
| 12 | 03 Mar 2009 | Creation: Cryptanalysis of a Vigenère cipher | exercise solution codepad | ||
| 20 | 31 Mar 2009 | Rail-Fence Cipher: A simple transposition cipher | exercise solution codepad | ||
| 37 | 29 May 2009 | Double Transposition Cipher: A simple and effective cipher, easy to perform by hand | exercise solution codepad | ||
| 47 | 03 Jul 2009 | The Playfair Cipher: A classic military field cipher | exercise solution codepad | ||
| 50 | 14 Jul 2009 | The Daily Cryptogram: Solve a monoalphabetic substitution cipher | exercise solution codepad | ||
| 57 | 07 Aug 2009 | ADFGX: A classic German military field cipher from the First World War | exercise solution codepad | ||
| 60 | 18 Aug 2009 | Blum Blum Shub: Stream cipher based on a cryptographically secure pseudo-random number generator | exercise solution codepad | ||
| 65 | 04 Sep 2009 | Ron’s Cipher #4: Stream cipher by Ron Rivest that underlies the SSL and WEP protocols | exercise solution codepad | ||
| 76 | 13 Oct 2009 | Bifid: A simple but effective fractionating cipher, never used militarily | exercise solution codepad | ||
| 91 | 04 Dec 2009 | Autokey: A cipher in which the input text forms part of the key | exercise solution codepad | ||
| 94 | 15 Dec 2009 | Affine-Shift Cipher: A cryptographically weak but mathematically interesting cipher | exercise solution codepad | ||
| 106 | 29 Jan 2010 | Straddling Checkerboard: An alternative to the Polybius square for ciphers that must convert letters to digits | exercise solution codepad | ||
| 147 | 06 Jul 2010 | Chaocipher: First look at a ninety-two year old autokey-type cipher | exercise solution codepad | ||
| 163 | 31 Aug 2010 | Data Encryption Standard: Part 1: Basic block enciphering and deciphering using DES | exercise solution codepad | ||
| 164 | 03 Sep 2010 | Data Encryption Standard: Part 2: ECB, CBC, CFB and OFB block modes for DES and other block ciphers | exercise solution codepad | ||
| 165 | 07 Sep 2010 | Data Encryption Standard: Part 3: Triple DES and cryptographic hashing | exercise solution codepad | ||
| 166 | 10 Sep 2010 | Data Encryption Standard: Part 4: DES driver program | exercise solution codepad | ||
| 185 | 16 Nov 2010 | RSA Cryptography: The original public-key cryptographic system, still in wide use | exercise solution codepad | ||
| 203 | 18 Jan 2011 | Solitaire Cipher: Bruce Schneier’s strong cryptography based on a deck of playing cards | exercise solution codepad | ||
| 244 | 10 Jun 2011 | Steganography: A hand-operable system that combines cryptography and steganography | exercise solution codepad | ||
| 246 | 17 Jun 2011 | Adi Shamir’s Threshold Scheme: Use cryptography to share a secret, by Graham Enos | exercise solution codepad | ||
| 290 | 22 Nov 2011 | Rabin’s Cryptosystem: Public-key cryptosystem, similar to RSA | exercise solution codepad | ||
| 320 | 06 Mar 2012 | Union Route Cipher: Military cipher used successfully by Union forces in the American Civil War | exercise solution codepad | ||
| 324 | 20 Mar 2012 | Factoring Multiple RSA Keys: Exploit a key-generation weakness to factor RSA keys | exercise solution codepad | ||
| 473 | 12 Sep 2013 | Diffie Hellman Key Exchange: Manage secure exchanges on an insecure communications channel | exercise solution codepad | ||
| Data Processing | |||||
| 16 | 17 Mar 2009 | Comma-Separated Values: Retrieve records from a comma-separated values file using a finite-state machine | exercise solution codepad | ||
| 74 | 06 Oct 2009 | MapReduce: Google’s famous system for parallelizing computations expressed as a programming idiom | exercise solution codepad | ||
| 141 | 15 Jun 2010 | Natural Join: The fundamental relational database operator | exercise solution codepad | ||
| 177 | 19 Oct 2010 | Text File Databases: Part 1: Functions to read records with fields in various formats | exercise solution codepad | ||
| 178 | 22 Oct 2010 | Text File Databases: Part 2: Various functions to process records with fields | exercise solution codepad | ||
| 189 | 30 Nov 2010 | Form Letters: Merge a schema and a data file to write form letters | exercise solution codepad | ||
| 296 | 13 Dec 2011 | Validating Telephone Numbers: An exercise in input validation | exercise solution codepad | ||
| Data Structures | |||||
| 480 | 08 Oct 2013 | Functional-Style Linked Lists: A library of functions on functional-style lists made from immutable pairs | exercise solution codepad | ||
| 481 | 11 Oct 2013 | Imperative-Style Linked Lists: A library of functions on imperative-style lists made from mutable pairs | exercise solution codepad | ||
| 489 | 29 Oct 2013 | Queues: Implement a basic data structure | exercise solution codepad | ||
| 490 | 05 Nov 2013 | Two Queues Make A Stack: Implement a stack using two queues | exercise solution codepad | ||
| 491 | 08 Nov 2013 | Two Stacks Make A Queue: Implement a queue using two stacks | exercise solution codepad | ||
| Fundamentals of Computing | |||||
| 19 | 27 Mar 2009 | A Turing Machine Simulator: An interpreter for a single-tape, multi-symbol turing machine | exercise solution codepad | ||
| 21 | 03 Apr 2009 | Programming the Turing Machine: A turing-machine program to multiply two numbers | exercise solution codepad | ||
| 33 | 15 May 2009 | Cellular Automata: Linear cellular automata as described by Stephen Wolfram in his book A New Kind of Science | exercise solution codepad | ||
| 277 | 04 Oct 2011 | Brainfuck: Interpreter for a Turing-line language | exercise solution codepad | ||
| 284 | 01 Nov 2011 | RIP John McCarthy: Implementation of the “Maxwell’s equations of software” from the LISP 1.5 Programmer’s Manual | exercise solution codepad | ||
| 326 | 27 Mar 2012 | Subset Sum: Solve a classic NP problem using dynamic programming | exercise solution codepad | ||
| 327 | 30 Mar 2012 | Subset Sum, Meet In The Middle: An improved solution to the classic NP problem | exercise solution codepad | ||
| 333 | 20 Apr 2012 | John Horton Conway’s Game Of Life: The classic cellular automata | exercise solution codepad | ||
| 342 | 22 May 2012 | Hamming Codes: Send messages over a noisy channel without error | exercise solution codepad | ||
| 344 | 25 May 2012 | Streaming Median: Find the medians of a set of numbers as they arrive in a stream | exercise solution codepad | ||
| 356 | 13 Jul 2012 | The Evolution Of Flibs: Use genetic programming to build a finite state machine | exercise solution codepad | ||
| 358 | 20 Jul 2012 | Infix Expression Evaluation: Write a parser to evaluate arithmetic expressions | exercise solution codepad | ||
| 464 | 09 Aug 2013 | Bit Hacks: A time-honored tradition, and useful | exercise solution codepad | ||
| 467 | 20 Aug 2013 | More Bit Hacks: A time-honored tradition, and useful | exercise solution codepad | ||
| 471 | 03 Sep 2013 | Yet More Bit Hacks: A time-honored tradition, and useful | exercise solution codepad | ||
| 475 | 20 Sep 2013 | McCarthy’s 91 Function: A recursive function designed as a test case for formal verification | exercise solution codepad | ||
| Games | |||||
| 3 | 19 Feb 2009 | Bingo: Calculate the probability of winning at Bingo | exercise solution codepad | ||
| 4 | 19 Feb 2009 | Sudoku: A backtracking solution to everybody’s favorite puzzle | exercise solution codepad | ||
| 11 | 27 Feb 2009 | Mark V. Shaney: Generate parodies of a text using a Markov chain | exercise solution codepad | ||
| 17 | 20 Mar 2009 | Dodgson's Doublets: A word game invented by the author of Alice in Wonderland | exercise solution codepad | ||
| 36 | 26 May 2009 | Word Search Solver: A computerized implementation of a popular time-waster | exercise solution codepad | ||
| 38 | 02 Jun 2009 | Pig Latin: A simple exercise to solve a children’s game | exercise solution codepad | ||
| 86 | 17 Nov 2009 | Master Mind, Part 1: Referee a two-player game of deductive logic | exercise solution codepad | ||
| 87 | 20 Nov 2009 | Master Mind, Part 2: Solve a Master Mind puzzle in five probes or less | exercise solution codepad | ||
| 100 | 08 Jan 2010 | Nim: A two-player game of mathematical logic | exercise solution codepad | ||
| 121 | 23 Mar 2010 | Texas Hold ‘Em: Find the best poker hand | exercise solution codepad | ||
| 133 | 04 May 2010 | Spectacular Seven: Compute the odds at jai alai | exercise solution codepad | ||
| 145 | 29 Jun 2010 | World Cup Prognostication: Simulate the knockout stage using elo ratings | exercise solution codepad | ||
| 153 | 27 Jul 2010 | HAMURABI.BAS: Manage grain and land in ancient Sumeria | exercise solution codepad | ||
| 196 | 24 Dec 2010 | Tracking Santa: How far does Santa travel on his annual journey? | exercise solution codepad | ||
| 198 | 31 Dec 2010 | Arithmetic Drill: Repetitious drill for children learning basic arithmetic | exercise solution codepad | ||
| 202 | 14 Jan 2011 | Slots: Simulate a slot machine | exercise solution codepad | ||
| 216 | 04 Mar 2011 | Chutes And Ladders: Simulate a child’s game, and compute its statistics | exercise solution codepad | ||
| 225 | 05 Apr 2011 | Fortune: Print a random aphorism from a file | exercise solution codepad | ||
| 285 | 04 Nov 2011 | Craps: Simulate a popular game of gambling with dice | exercise solution codepad | ||
| 298 | 20 Dec 2011 | Hangman: Classic Unix V7 game for guessing words | exercise solution codepad | ||
| 300 | 27 Dec 2011 | Cheating Hangman: A version of Hangman that nearly always wins | exercise solution codepad | ||
| 306 | 17 Jan 2012 | Guess The Number: Number-guessing game for children learning arithmetic | exercise solution codepad | ||
| 400 | 18 Dec 2012 | Petals Around The Rose: A game to celebrate our 400th exercise | exercise solution codepad | ||
| 427 | 29 Mar 2013 | One Million Hits: Celebrating our one-millionth hit! | exercise solution codepad | ||
| Graphs | |||||
| 118 | 12 Mar 2010 | Traveling Salesman: Brute Force: Examine all possible permutations to find the least-cost tour | exercise solution codepad | ||
| 119 | 16 Mar 2010 | Traveling Salesman: Nearest Neighbor: A greedy heuristic that builds a path by always choosing the nearest unvisited point | exercise solution codepad | ||
| 125 | 06 Apr 2010 | Minimum Spanning Tree: Kruskal’s Algorithm: Find the minimum-cost tree that includes all the nodes in a graph | exercise solution codepad | ||
| 126 | 09 Apr 2010 | Minimum Spanning Tree: Prim’s Algorithm: Find the minimum-cost tree that includes all the nodes in a graph | exercise solution codepad | ||
| 127 | 13 Apr 2010 | Traveling Salesman: Minimum Spanning Tree: Heuristic guarantees solution within factor of two of optimal tour | exercise solution codepad | ||
| 186 | 19 Nov 2010 | Topological Sort: Order the edges of a graph by their precedence relationship | exercise solution codepad | ||
| 199 | 04 Jan 2011 | Dijkstra’s Algorithm: Find the shortest path to all vertices of a graph from a single source, guest written by Graham Enos | exercise solution codepad | ||
| 445 | 31 May 2013 | The Seven Bridges of Königsberg: A classic graph puzzle due to Leonhard Euler | exercise solution codepad | ||
| Guest Authors | |||||
| 101 | 12 Jan 2010 | Calculating Sines: Calculate sines using Taylor series and the triple-angle formula, by Bill Cruise | exercise solution codepad | ||
| 103 | 19 Jan 2010 | Flight Planning: Computing the navigation triangle, by Jos Koot | exercise solution codepad | ||
| 199 | 04 Jan 2011 | Dijkstra’s Algorithm: Find the shortest path to all vertices of a graph from a single source, guest written by Graham Enos | exercise solution codepad | ||
| 229 | 19 Apr 2011 | Same Five Digits: A math puzzle from New Scientist, solved by guest author Bob Miller | exercise solution codepad | ||
| 246 | 17 Jun 2011 | Adi Shamir’s Threshold Scheme: Use cryptography to share a secret, by Graham Enos | exercise solution codepad | ||
| 293 | 02 Dec 2011 | Knight Rider: Classic problem of the knight’s tour | exercise solution codepad | ||
| 356 | 13 Jul 2012 | The Evolution Of Flibs: Use genetic programming to build a finite state machine | exercise solution codepad | ||
| 417 | 22 Feb 2013 | Floupia: Make change in a strange currency | exercise solution codepad | ||
| 421 | 08 Mar 2013 | Knight Moves: Move a knight around a chess board | exercise solution codepad | ||
| 465 | 13 Aug 2013 | Unix Paths: Convert relative Unix path to absolute, by Robert Fisher | exercise solution codepad | ||
| Historical Computing | |||||
| 2 | 19 Feb 2009 | Sieve of Eratosthenes: A Scheme implementation of an ancient algorithm | exercise solution codepad | ||
| 34 | 19 May 2009 | Fermat’s Method: Integer factorization by Fermat’s algorithm | exercise solution codepad | ||
| 75 | 09 Oct 2009 | Calculating Pi: Calculate the value of π by monte-carlo methods and by an Archimedean method | exercise solution codepad | ||
| 95 | 18 Dec 2009 | Calculating Logarithms: Use the methods of Newton and Euler to calculate square roots and logarithms | exercise solution codepad | ||
| 102 | 15 Jan 2010 | Three Binary Algorithms: Multiplication, division and greatest common divisor using binary arithmetic | exercise solution codepad | ||
| 167 | 14 Sep 2010 | The Factorization Of F7: Part 1: Our fortieth anniversary celebration of Morrison and Brillhart’s method of integer factorization by continued fractions | exercise solution codepad | ||
| 168 | 17 Sep 2010 | The Factorization Of F7: Part 2: Our fortieth anniversary celebration of Morrison and Brillhart’s method of integer factorization by continued fractions | exercise solution codepad | ||
| 209 | 08 Feb 2011 | The First Computer Program: Ada Lovelace’s program to compute Bernoulli numbers for Charles Babbage’s Analytical Engine | exercise solution codepad | ||
| 215 | 01 Mar 2011 | An Early LISP Program: A program to flatten a list, from the March 1960 LISP I manual | exercise solution codepad | ||
| 233 | 03 May 2011 | Squaring The Bishop: Charles Babbage’s game of word squares | exercise solution codepad | ||
| 256 | 22 Jul 2011 | Counting Primes Using Legendre’s Formula: Recreate Legendre’s two-century old calculation of the number of primes less than a million | exercise solution codepad | ||
| 338 | 08 May 2012 | Factor Tables: Table of factors of integers | exercise solution codepad | ||
| 344 | 01 Jun 2012 | Square Roots: Four methods to compute square roots, including one from antiquity | exercise solution codepad | ||
| 446 | 04 Jun 2013 | Egyptian Fractions: An ancient method of representing fractions | exercise solution codepad | ||
| Interview Question | |||||
| 418 | 26 Feb 2013 | An Odd Way To Square: Square a number without using multiplication or exponentiation | exercise solution codepad | ||
| Interview Questions | |||||
| 46 | 30 Jun 2009 | Steve Yegge’s Phone-Screen Coding Exercises: A simple set of programming exercises based on a blog entry by Steve Yegge | exercise solution codepad | ||
| 137 | 01 Jun 2010 | Unwrapping A Spiral: An exercise in recursion | exercise solution codepad | ||
| 152 | 23 Jul 2010 | Happy Numbers: Iterating the sum of the squares of the digits terminates with one | exercise solution codepad | ||
| 169 | 21 Sep 2010 | Kaprekar Numbers: Square the number and add the digits in halves | exercise solution codepad | ||
| 187 | 23 Nov 2010 | String Subsets: Determine if one string is a subset of another | exercise solution codepad | ||
| 206 | 28 Jan 2011 | Population Count: Count the number of set bits (1-bits) in the binary representation of an integer | exercise solution codepad | ||
| 211 | 15 Feb 2011 | Google Code Jam Qualification Round Africa 2010: Three simple exercises | exercise solution codepad | ||
| 213 | 22 Feb 2011 | Sliding Window Minimum: List of minimums sliding across an input list | exercise solution codepad | ||
| 217 | 08 Mar 2011 | Reverse Words: Reverse the words in an input string | exercise solution codepad | ||
| 218 | 11 Mar 2011 | Lowest Common Ancestor: Find the lowest node in a binary search tree that is a common ancestor to two given nodes | exercise solution codepad | ||
| 220 | 18 Mar 2011 | Loopy Loops: Print the numbers from 1 to 1000 without using loops or conditionals | exercise solution codepad | ||
| 224 | 01 Apr 2011 | Maximum Difference In An Array: Find maximum Xj &minus Xi, with i ≤ j | exercise solution codepad | ||
| 231 | 26 Apr 2011 | Miscellanea: FizzBuzz, Prime Words, and Split A List | exercise solution codepad | ||
| 255 | 19 Jul 2011 | Sum Of Two Integers: Determine if two integers in a list sum to a target | exercise solution codepad | ||
| 262 | 12 Aug 2011 | Word Breaks: Insert spaces between words: applepie => apple pie | exercise solution codepad | ||
| 263 | 16 Aug 2011 | Insert Into A Cyclic Sorted List: Insert a new element into a cyclic list, in order | exercise solution codepad | ||
| 264 | 19 Aug 2011 | First Non-Repeating Character: Find the first character in a string that doesn’t repeat later in the string | exercise solution codepad | ||
| 266 | 26 Aug 2011 | Reverse Every K Nodes Of A Linked List: Reverse the elements of a sub-list | exercise solution codepad | ||
| 268 | 02 Sep 2011 | Two String Exercises: Remove duplicate characters, and squish adjacent blanks | exercise solution codepad | ||
| 274 | 23 Sep 2011 | Array Duplicates: Find the duplicate integer in a large array | exercise solution codepad | ||
| 301 | 30 Dec 2011 | Split: Split a list in two halves using the tortoise-and-hare algorithm | exercise solution codepad | ||
| 307 | 20 Jan 2012 | Knights On A Keypad: Count the number of knight paths on a keypad | exercise solution codepad | ||
| 310 | 31 Jan 2012 | String Rotation: Determine if two strings are rotations of each other | exercise solution codepad | ||
| 313 | 10 Feb 2012 | Search In An Ascending Matrix: Find a number in a matrix where both rows and columns are sorted in ascending order | exercise solution codepad | ||
| 337 | 04 May 2012 | Even-Odd Partition: Partition an array so all even integers precede all odd integers | exercise solution codepad | ||
| 360 | 27 Jul 2012 | Min Stack: Provide push and pop operations and find the minimum element in linear time | exercise solution codepad | ||
| 365 | 14 Aug 2012 | 4SUM: Find four numbers in an array that sum to zero | exercise solution codepad | ||
| 389 | 09 Nov 2012 | Taxicab Numbers: Confirm an interesting observation of Srinivasa Ramanujan | exercise solution codepad | ||
| 394 | 27 Nov 2012 | Amazon Interview Question: Find the hundred points of a million closest to the origin | exercise solution codepad | ||
| 429 | 05 Apr 2013 | Last Non-Zero Digit Of A Factorial: Find the last non-zero digit of a factorial | exercise solution codepad | ||
| 436 | 30 Apr 2013 | First Unrepeated Character In A String: Find the first character that appears only once in a string | exercise solution codepad | ||
| 448 | 11 Jun 2013 | Longest Substring Of Two Unique Characters: Longest run of consecutive characters in a string that contains only two unique characters | exercise solution codepad | ||
| 452 | 25 Jun 2013 | Swap List Nodes: Swap the kth node from the beginning of a list with the kth node from the end of a list | exercise solution codepad | ||
| 460 | 26 Jul 2013 | Find X[i] = i In An Array: Find an array element equal to its index | exercise solution codepad | ||
| 468 | 23 Aug 2013 | Three Interview Questions: Three interview questions | exercise solution codepad | ||
| 482 | 15 Oct 2013 | Find The Minimum Difference: Find the minimum difference between any item from on list and any item from another list | exercise solution codepad | ||
| Logic | |||||
| 7 | 20 Feb 2009 | Multiple Dwellings: A simple logic puzzle, solved with the amb non-deterministic operator |
exercise solution codepad | ||
| 41 | 12 Jun 2009 | Feynman’s Puzzle: A simple logic puzzle | exercise solution codepad | ||
| 42 | 16 Jun 2009 | Who Owns The Zebra?: A logic puzzle, solved by embedding a Prolog-like logic system in Scheme | exercise solution codepad | ||
| 79 | 23 Oct 2009 | Mr. S. and Mr. P.: A logic puzzle popularized by John McCarthy | exercise solution codepad | ||
| Mathematics | |||||
| 8 | 20 Feb 2009 | The Digits of Pi: A spigot algorithm to calculate the digits of pi | exercise solution codepad | ||
| 48 | 07 Jul 2009 | Modular Arithmetic: A function library for performing modular addition, subtraction, multiplication, division, and square root | exercise solution codepad | ||
| 49 | 10 Jul 2009 | The Golden Ratio: Evaluate a continued fraction, based on my daughter’s math homework | exercise solution codepad | ||
| 54 | 28 Jul 2009 | Elliptic Curves: Library of basic functions on elliptic curves | exercise solution codepad | ||
| 72 | 29 Sep 2009 | Green Eyes: A counting problem from high-school math | exercise solution codepad | ||
| 75 | 09 Oct 2009 | Calculating Pi: Calculate the value of π by monte-carlo methods and by an Archimedean method | exercise solution codepad | ||
| 95 | 18 Dec 2009 | Calculating Logarithms: Use the methods of Newton and Euler to calculate square roots and logarithms | exercise solution codepad | ||
| 101 | 12 Jan 2010 | Calculating Sines: Calculate sines using Taylor series and the triple-angle formula, by Bill Cruise | exercise solution codepad | ||
| 102 | 15 Jan 2010 | Three Binary Algorithms: Multiplication, division and greatest common divisor using binary arithmetic | exercise solution codepad | ||
| 109 | 09 Feb 2010 | Numerical Integration: Quadrature by the rectangular, trapezoidal and Simpson’s method, including adaptive quadrature | exercise solution codepad | ||
| 134 | 07 May 2010 | Integer Logarithms: An improved algorithm is O(log n) instead of O(n) | exercise solution codepad | ||
| 143 | 22 Jun 2010 | Matrix Operations: Matrix addition, scalar multiplication, multiplication and transposition | exercise solution codepad | ||
| 151 | 20 Jul 2010 | Solving Systems Of Linear Equations: Matrix operations LU-decomposition and LUP-decomposition | exercise solution codepad | ||
| 154 | 30 Jul 2010 | Fibonacci Numbers: Three algorithms taking exponential time, linear time, and logarithmic time | exercise solution codepad | ||
| 156 | 06 Aug 2010 | Two Powering Predicates: Determine if a number is a square or a prime power | exercise solution codepad | ||
| 162 | 27 Aug 2010 | Chinese Remainders: An ancient application of modular inverses | exercise solution codepad | ||
| 179 | 26 Oct 2010 | Benford’s Law: A useful mathematical oddity, and an example of text file databases | exercise solution codepad | ||
| 181 | 02 Nov 2010 | Emirps: Prime numbers that are prime when their digits are reversed, but not palindromic | exercise solution codepad | ||
| 188 | 26 Nov 2010 | Divisors And Totatives: The number-theoretic functions divisors, numdivs, sumdivs, totatives, and totient | exercise solution codepad | ||
| 195 | 21 Dec 2010 | Interval Arithmetic: An exercise from SICP | exercise solution codepad | ||
| 197 | 28 Dec 2010 | Carmichael Numbers: Composite numbers such that an-1 ≡ 1 (mod n) if a is prime to n | exercise solution codepad | ||
| 201 | 11 Jan 2011 | Two Integrals: The exponential and logarithmic integral, and an approximation for prime-pi | exercise solution codepad | ||
| 209 | 08 Feb 2011 | The First Computer Program: Ada Lovelace’s program to compute Bernoulli numbers for Charles Babbage’s Analytical Engine | exercise solution codepad | ||
| 210 | 11 Feb 2011 | Sums Of Powers: Use Bernoulli numbers to quickly compute sums of powers | exercise solution codepad | ||
| 228 | 15 Apr 2011 | Partition Numbers: Calculate the partition numbers, using memoization via growing arrays | exercise solution codepad | ||
| 239 | 24 May 2011 | Big Numbers: Getting Started: A library for big integers: representation, comparison, simple functions | exercise solution codepad | ||
| 241 | 31 May 2011 | Big Numbers: Addition, Subtraction And Multiplication: A library for big integers: grade-school algorithms for addition, subtraction, and multiplication | exercise solution codepad | ||
| 243 | 07 Jun 2011 | Big Numbers: Division: A library for big integers: the grade-school algorithm for long division | exercise solution codepad | ||
| 245 | 14 Jun 2011 | Big Numbers: Input And Output: A library for big integers: input and output with radix conversion | exercise solution codepad | ||
| 247 | 21 Jun 2011 | Big Numbers: Testing: A library for big integers: testing | exercise solution codepad | ||
| 249 | 28 Jun 2011 | Big Numbers: Functions: A library for big integers: gcd, powering, square root, random numbers | exercise solution codepad | ||
| 251 | 05 Jul 2011 | Big Numbers: Examples: A library for big integers: display factorials to 50, determine if a number is prime, and compute its prime factors | exercise solution codepad | ||
| 252 | 08 Jul 2011 | Vedic Divisibility: Use a method of testing divisibility using the method of osculators developed in India | exercise solution codepad | ||
| 267 | 30 Aug 2011 | Hamming Numbers: List the numbers with no factors greater than 5, a classic problem popularized by Dijkstra | exercise solution codepad | ||
| 276 | 30 Sep 2011 | Logarithm Tables: Print old-fashioned tables of logarithms and anti-logarithms | exercise solution codepad | ||
| 294 | 06 Dec 2011 | Pascal’s Triangle: Display the binomial coefficients | exercise solution codepad | ||
| 305 | 13 Jan 2012 | Excel’s XIRR Function: Numerical calculation of a derivative | exercise solution codepad | ||
| 315 | 17 Feb 2012 | Hailstones: Examine the Collatz sequence | exercise solution codepad | ||
| 322 | 13 Mar 2012 | Perfect Power Predicate: Given a positive integer n, determine if there exists a b and e for which be = n | exercise solution codepad | ||
| 328 | 03 Apr 2012 | Cornacchia’s Algorithm: Find solutions to quadratic diophantine equations | exercise solution codepad | ||
| 331 | 13 Apr 2012 | McNugget Numbers, Revisited: The classic coin problem in disguise, how to count the number of ways to make change | exercise solution codepad | ||
| 338 | 08 May 2012 | Factor Tables: Table of factors of integers | exercise solution codepad | ||
| 339 | 11 May 2012 | partitions: Sets of integers that sum to a given integer | exercise solution codepad | ||
| 344 | 01 Jun 2012 | Square Roots: Four methods to compute square roots, including one from antiquity | exercise solution codepad | ||
| 349 | 19 Jun 2012 | Digits Of E: Two algorithms that compute the digits of e, one bounded, the other unbounded | exercise solution codepad | ||
| 374 | 14 Sep 2012 | Tribonacci Numbers: A variant of fibonacci numbers | exercise solution codepad | ||
| 375 | 18 Sep 2012 | ABC Conjecture: Demonstrate a recently-proved conjecture of number theory | exercise solution codepad | ||
| 381 | 12 Oct 2012 | Birthday Paradox: Use simulation to demonstrate the birthday paradox | exercise solution codepad | ||
| 383 | 19 Oct 2012 | Prime Partitions: Compute the number of ways to sum primes to a target | exercise solution codepad | ||
| 385 | 26 Oct 2012 | Pythatorean Triples: Generate primitive pythagorean triples by an ancient algorithm | exercise solution codepad | ||
| 393 | 23 Nov 2012 | Tonelli-Shanks Algorithm: Compute modular square roots | exercise solution codepad | ||
| 446 | 04 Jun 2013 | Egyptian Fractions: An ancient method of representing fractions | exercise solution codepad | ||
| 449 | 14 Jun 2013 | The Digits of Pi, Again: Chudnovsky’s algorithm for the digits of pi | exercise solution codepad | ||
| 478 | 01 Oct 2013 | Lucas Sequences: Fast methods for calculating Lucas sequences, similar to Fibonacci sequences | exercise solution codepad | ||
| 479 | 04 Oct 2013 | Calculating Statistics: Read a file of integers and calculate mean, median and mode | exercise solution codepad | ||
| Number Theory | |||||
| 389 | 09 Nov 2012 | Taxicab Numbers: Confirm an interesting observation of Srinivasa Ramanujan | exercise solution codepad | ||
| Parsing | |||||
| 0 | 19 Feb 2009 | RPN Calculator: Evaluate numeric expressions at the command line | exercise solution codepad | ||
| 16 | 17 Mar 2009 | Comma-Separated Values: Retrieve records from a comma-separated values file using a finite-state machine | exercise solution codepad | ||
| 67 | 11 Sep 2009 | Beautiful Code: A simple regular-expression matcher by Rob Pike | exercise solution codepad | ||
| 68 | 15 Sep 2009 | Regular Expressions, Part 1: A parser for regular expressions | exercise solution codepad | ||
| 69 | 18 Sep 2009 | Regular Expressions, Part 2: The corresponding matcher | exercise solution codepad | ||
| 70 | 22 Sep 2009 | Regular Expressions, Part 3: A regular expression test suite | exercise solution codepad | ||
| 71 | 25 Sep 2009 | Grep: Simple version of the classic unix regular-expression matching utility | exercise solution codepad | ||
| 128 | 16 Apr 2010 | Expression Evaluation: Parse and evaluate an arithmetic expression with plus, minus, times, divide and parentheses | exercise solution codepad | ||
| 253 | 12 Jul 2011 | JSON: Parsing Input: Parse JSON input | exercise solution codepad | ||
| 254 | 15 Jul 2011 | JSON: Writing Output: The other side of JSAON | exercise solution codepad | ||
| 319 | 02 Mar 2012 | Balanced Delimiters: Determine if nested delimiters are properly balanced | exercise solution codepad | ||
| 358 | 20 Jul 2012 | Infix Expression Evaluation: Write a parser to evaluate arithmetic expressions | exercise solution codepad | ||
| 407 | 15 Jan 2013 | Translate CSV To Html: Convert between tabular storage forms | exercise solution codepad | ||
| Prime Numbers | |||||
| 2 | 19 Feb 2009 | Sieve of Eratosthenes: A Scheme implementation of an ancient algorithm | exercise solution codepad | ||
| 24 | 14 Apr 2009 | Google Treasure Hunt 2008 Puzzle 4: A prime-number puzzle | exercise solution codepad | ||
| 29 | 01 May 2009 | Primality Checking: A probabilistic primality checker by Gary Miller and Michael Rabin | exercise solution codepad | ||
| 31 | 08 May 2009 | Wheel Factorization: Find the factors of a number by a variant of trial division | exercise solution codepad | ||
| 34 | 19 May 2009 | Fermat’s Method: Integer factorization by Fermat’s algorithm | exercise solution codepad | ||
| 43 | 19 Jun 2009 | Monte Carlo Factorization: Integer factorization via Pollard’s rho algorithm | exercise solution codepad | ||
| 52 | 21 Jul 2009 | Pollard’s P−1 Factorization Algorithm: A simple factorization algorithm by John Pollard | exercise solution codepad | ||
| 55 | 31 Jul 2009 | Elliptic Curve Factorization: A very simple implementation of elliptic curve factorization | exercise solution codepad | ||
| 56 | 04 Aug 2009 | Lenstra’s Algorithm: Hendrik Lenstra’s original algorithm for elliptic curve factorization | exercise solution codepad | ||
| 105 | 26 Jan 2010 | Primality Checking, Revisited: The Baillie-Wagstaff algorithm for primality checking | exercise solution codepad | ||
| 107 | 02 Feb 2010 | Proving Primality: A deterministic, not probabilistic, method of checking primality | exercise solution codepad | ||
| 108 | 05 Feb 2010 | Segmented Sieve Of Eratosthenes: Extend the Sieve of Eratosthenes to large ranges of integers | exercise solution codepad | ||
| 109 | 09 Feb 2010 | Numerical Integration: Quadrature by the rectangular, trapezoidal and Simpson’s method, including adaptive quadrature | exercise solution codepad | ||
| 110 | 12 Feb 2010 | Sieve of Atkin: A modern alternative to the Sieve of Eratosthenes for computing prime numbers | exercise solution codepad | ||
| 112 | 19 Feb 2010 | Sieve Of Atkin, Improved: A faster version of the Sieve of Atkin | exercise solution codepad | ||
| 115 | 02 Mar 2010 | Goldbach’s Conjecture: Every even number greater than two can be written as the sum of two primes | exercise solution codepad | ||
| 120 | 19 Mar 2010 | Extending Pollard’s P−1 Factorization Algorithm: Add a second stage to allow larger factorizations | exercise solution codepad | ||
| 122 | 26 Mar 2010 | The Next Prime: Efficiently find the next prime number larger than a given number | exercise solution codepad | ||
| 130 | 23 Apr 2010 | Modern Elliptic Curve Factorization, Part 1: Elliptic arithmetic using Montgomery’s parameterization | exercise solution codepad | ||
| 131 | 27 Apr 2010 | Modern Elliptic Curve Factorization, Part 2: Elliptic arithmetic using Montgomery’s parameterization | exercise solution codepad | ||
| 132 | 30 Apr 2010 | Integer Factorization: Combine trial division, Pollard’s rho and p−1 methods, and elliptic curves into a single factorization program | exercise solution codepad | ||
| 138 | 04 Jun 2010 | Williams’ P+1 Factorization Algorithm: A factorization algorithm, similar to Pollard’s p−1 algorithm | exercise solution codepad | ||
| 161 | 24 Aug 2010 | Daniel Shanks’ Square Form Factorization Algorithm: A simple and very fast factorization algorithm for integers between 105 and 1020 | exercise solution codepad | ||
| 162 | 27 Aug 2010 | Chinese Remainders: An ancient application of modular inverses | exercise solution codepad | ||
| 167 | 14 Sep 2010 | The Factorization Of F7: Part 1: Our fortieth anniversary celebration of Morrison and Brillhart’s method of integer factorization by continued fractions | exercise solution codepad | ||
| 168 | 17 Sep 2010 | The Factorization Of F7: Part 2: Our fortieth anniversary celebration of Morrison and Brillhart’s method of integer factorization by continued fractions | exercise solution codepad | ||
| 180 | 29 Oct 2010 | Fibonacci Primes: Find primes among the fibonacci numbers; includes the Park-Miller random number generator and Miller-Rabin primality checker | exercise solution codepad | ||
| 181 | 02 Nov 2010 | Emirps: Prime numbers that are prime when their digits are reversed, but not palindromic | exercise solution codepad | ||
| 184 | 12 Nov 2010 | Rowland’s Prime-Generating Function: A sequence of ones and primes | exercise solution codepad | ||
| 188 | 26 Nov 2010 | Divisors And Totatives: The number-theoretic functions divisors, numdivs, sumdivs, totatives, and totient | exercise solution codepad | ||
| 197 | 28 Dec 2010 | Carmichael Numbers: Composite numbers such that an-1 ≡ 1 (mod n) if a is prime to n | exercise solution codepad | ||
| 200 | 07 Jan 2011 | Counting Primes: The prime counting function and nth-prime function | exercise solution codepad | ||
| 204 | 21 Jan 2011 | Pollard Rho, Revisited: Richard Brent’s variant of John Pollard’s rho algorithm for integer factorization | exercise solution codepad | ||
| 212 | 18 Feb 2011 | Two Factoring Games: Home primes and the Euclid-Mullin sequence | exercise solution codepad | ||
| 214 | 25 Feb 2011 | Sieve Of Euler: An alternate, and slow, method of sieving for primes | exercise solution codepad | ||
| 236 | 13 May 2011 | Dixon’s Factorization Algorithm: A slow, but theoretically important, algorithm for integer factorization | exercise solution codepad | ||
| 242 | 03 Jun 2011 | Mersenne Primes: The Lucas-Lehmer test for identifying primes of the form 2n−1 | exercise solution codepad | ||
| 251 | 05 Jul 2011 | Big Numbers: Examples: A library for big integers: display factorials to 50, determine if a number is prime, and compute its prime factors | exercise solution codepad | ||
| 256 | 22 Jul 2011 | Counting Primes Using Legendre’s Formula: Recreate Legendre’s two-century old calculation of the number of primes less than a million | exercise solution codepad | ||
| 257 | 26 Jul 2011 | More Prime-Counting Functions: Prime counting functions by Meissel and Lehmer, based on Legendre’s sum | exercise solution codepad | ||
| 258 | 29 Jul 2011 | Approximating Pi: Approximating pi with the logarithmic integral and Riemann’s R function | exercise solution codepad | ||
| 259 | 02 Aug 2011 | The Nth Prime: The n prime, counting from p1 = 2 | exercise solution codepad | ||
| 272 | 16 Sep 2011 | Pollard’s P−1 Factorization Algoritihm, Revisited: An improved second stage that is much faster than the original | exercise solution codepad | ||
| 273 | 20 Sep 2011 | Project Euler Problem 3: Thorough explanation of integer factorization by trial division | exercise solution codepad | ||
| 278 | 07 Oct 2011 | Sieve of Sundaram: Sieving for prime numbers using a method from India | exercise solution codepad | ||
| 279 | 14 Oct 2011 | The First N Primes: Embedding the Sieve of Eratosthenes in a priority queue instead of an array | exercise solution codepad | ||
| 286 | 08 Nov 2011 | Improved Standard Continuation: An improved version of elliptic curve factorization, widely used in current practice | exercise solution codepad | ||
| 303 | 06 Jan 2012 | Pritchard’s Wheel Sieve: An alternative to the Sieve of Eratosthenes with a faster asymptotic time complexity | exercise solution codepad | ||
| 314 | 14 Feb 2012 | Divisors: Find divisors using a sieve | exercise solution codepad | ||
| 324 | 20 Mar 2012 | Factoring Multiple RSA Keys: Exploit a key-generation weakness to factor RSA keys | exercise solution codepad | ||
| 332 | 17 Apr 2012 | Twin Primes: A variant of the Sieve of Eratosthenes to find pairs of primes that differ by two | exercise solution codepad | ||
| 338 | 08 May 2012 | Factor Tables: Table of factors of integers | exercise solution codepad | ||
| 355 | 10 Jul 2012 | Sieve For Totients: Find the totients of a large range of integers using a sieve | exercise solution codepad | ||
| 373 | 11 Sep 2012 | The Sum Of The First Billion Primes: Write a prime generator, and use it | exercise solution codepad | ||
| 377 | 28 Sep 2012 | Pocklington’s N−1 Primality Prover: Prove n prime if n−1 can be partially factored | exercise solution codepad | ||
| 378 | 02 Oct 2012 | AKS Primality Prover, Part 1: Two functions used by the AKS primality prover | exercise solution codepad | ||
| 379 | 05 Oct 2012 | AKS Primality Prover, Part 2: The primality prover of Agrawal, Kayal and Saxena | exercise solution codepad | ||
| 390 | 13 Nov 2012 | Frobenius Primality Test: A pseudoprimality test, stronger than Miller-Rabin | exercise solution codepad | ||
| 393 | 23 Nov 2012 | Tonelli-Shanks Algorithm: Compute modular square roots | exercise solution codepad | ||
| 401 | 21 Dec 2012 | Building Primes: Build the largest prime with all right-most subsequences also prime | exercise solution codepad | ||
| 413 | 08 Feb 2013 | The Biggest Prime: Print all 17-million digits of the largest known prime number | exercise solution codepad | ||
| 419 | 01 Mar 2013 | Baillie-Wagstaff Pseudoprimality Tester: Primality test, an improvement over the Miller-Rabin test | exercise solution codepad | ||
| 424 | 19 Mar 2013 | Quadratic Sieve: Basic version of a powerful factoring algorithm | exercise solution codepad | ||
| 428 | 02 Apr 2013 | Quadratic Sieve With Large Primes: A (slightly) improved version of the basic quadratic sieve | exercise solution codepad | ||
| 451 | 21 Jun 2013 | Multiple Polynomial Quadratic Sieve: A greatly improved version of the basic quadratic sieve | exercise solution codepad | ||
| 463 | 06 Aug 2013 | Sophie Germain Primes: Primes p such that 2p+1 is also prime | exercise solution codepad | ||
| 469 | 27 Aug 2013 | Two Sieving Problems: Use sieves to answer two prime-number questions | exercise solution codepad | ||
| Puzzles | |||||
| 7 | 20 Feb 2009 | Multiple Dwellings: A simple logic puzzle, solved with the amb non-deterministic operator |
exercise solution codepad | ||
| 24 | 14 Apr 2009 | Google Treasure Hunt 2008 Puzzle 4: A prime-number puzzle | exercise solution codepad | ||
| 42 | 16 Jun 2009 | Who Owns The Zebra?: A logic puzzle, solved by embedding a Prolog-like logic system in Scheme | exercise solution codepad | ||
| 51 | 17 Jul 2009 | International Mathematical Olympiad: Three exercises from 1960s math competitions | exercise solution codepad | ||
| 79 | 23 Oct 2009 | Mr. S. and Mr. P.: A logic puzzle popularized by John McCarthy | exercise solution codepad | ||
| 89 | 27 Nov 2009 | $7.11: A math puzzle: a+b+c+d = a×b×c×d = 7.11 | exercise solution codepad | ||
| 129 | 20 Apr 2010 | 145 Puzzle: Build and evaluate expressions using the digits one through nine and the simple arithmetic operators | exercise solution codepad | ||
| 162 | 27 Aug 2010 | Chinese Remainders: An ancient application of modular inverses | exercise solution codepad | ||
| 180 | 29 Oct 2010 | Fibonacci Primes: Find primes among the fibonacci numbers; includes the Park-Miller random number generator and Miller-Rabin primality checker | exercise solution codepad | ||
| 183 | 09 Nov 2010 | Subset Sums: Third level of the Greplin Programming Challenge, using dynamic programming and memoization | exercise solution codepad | ||
| 191 | 07 Dec 2010 | Ullman’s Puzzle: It never hurts to sort | exercise solution codepad | ||
| 416 | 19 Feb 2013 | NPR Sunday Puzzle: Find two words containing the letters a, b, c, d, e and f | exercise solution codepad | ||
| 418 | 26 Feb 2013 | An Odd Way To Square: Square a number without using multiplication or exponentiation | exercise solution codepad | ||
| 425 | 22 Mar 2013 | Jumping Jack: Jump in increasing sizes along the number line | exercise solution codepad | ||
| 439 | 10 May 2013 | MindCipher: Three exercises from the MindCipher puzzle website | exercise solution codepad | ||
| 453 | 28 Jun 2013 | A Programming Puzzle: Write a function f so that f(f(n)) = -n for all integers n. | exercise solution codepad | ||
| 476 | 24 Sep 2013 | Finding Digit Strings In Powers Of Two: A simple exercise from one of the competitive programming sites | exercise solution codepad | ||
| Random Number Generators | |||||
| 135 | 25 May 2010 | GB_FLIP: Donald Knuth’s portable, high-quality random-number generator from the Stanford Graphbase | exercise solution codepad | ||
| 173 | 05 Oct 2010 | George Marsaglia’s Random Number Generators: Nine high-quality RNGs in nineteen lines of code | exercise solution codepad | ||
| 180 | 29 Oct 2010 | Fibonacci Primes: Find primes among the fibonacci numbers; includes the Park-Miller random number generator and Miller-Rabin primality checker | exercise solution codepad | ||
| 232 | 29 Apr 2011 | Rule 30 RNG: The random number generator from Mathematica, based on Stephen Wolfram’s Rule 30 cellular automata | exercise solution codepad | ||
| 270 | 09 Sep 2011 | Mersenne Twister: Random number generator with very long period, useful for simulations | exercise solution codepad | ||
| 366 | 17 Aug 2012 | Two Random Exercises: Two exercises involving random numbers | exercise solution codepad | ||
| 367 | 21 Aug 2012 | Two More Random Exercises: Two bad random number generators, the middle-square method and RANDU | exercise solution codepad | ||
| 434 | 23 Apr 2013 | Correct Horse Battery Staple: Randall Munro’s passphrase generator | exercise solution codepad | ||
| 435 | 26 Apr 2013 | Correct Horse Battery Staple, Improved: Fix a horrible bug in the original version | exercise solution codepad | ||
| Recreational Mathematics | |||||
| 41 | 12 Jun 2009 | Feynman’s Puzzle: A simple logic puzzle | exercise solution codepad | ||
| 51 | 17 Jul 2009 | International Mathematical Olympiad: Three exercises from 1960s math competitions | exercise solution codepad | ||
| 89 | 27 Nov 2009 | $7.11: A math puzzle: a+b+c+d = a×b×c×d = 7.11 | exercise solution codepad | ||
| 99 | 05 Jan 2010 | The Sum Of Two Squares: A math puzzle with a solution by Dijkstra | exercise solution codepad | ||
| 129 | 20 Apr 2010 | 145 Puzzle: Build and evaluate expressions using the digits one through nine and the simple arithmetic operators | exercise solution codepad | ||
| 158 | 13 Aug 2010 | E: A simple simulation with a surprising ending | exercise solution codepad | ||
| 172 | 01 Oct 2010 | Oban Numbers: Numbers that omit the letter “o” when spelled, and a function to convert numbers to words | exercise solution codepad | ||
| 180 | 29 Oct 2010 | Fibonacci Primes: Find primes among the fibonacci numbers; includes the Park-Miller random number generator and Miller-Rabin primality checker | exercise solution codepad | ||
| 191 | 07 Dec 2010 | Ullman’s Puzzle: It never hurts to sort | exercise solution codepad | ||
| 194 | 17 Dec 2010 | Polite Numbers: Write numbers as the sum of two or more consecutive integers | exercise solution codepad | ||
| 212 | 18 Feb 2011 | Two Factoring Games: Home primes and the Euclid-Mullin sequence | exercise solution codepad | ||
| 219 | 15 Mar 2011 | Look And Say: Calculate John Horton Conway’s "Look and Say" sequence | exercise solution codepad | ||
| 221 | 22 Mar 2011 | Two Kaprekar Exercises: Kaprekar chains and Kaprekar numbers, from the Indian mathematician Dattaraya Ramchandra Kaprekar | exercise solution codepad | ||
| 223 | 28 Mar 2011 | Look And Say, Revisited: Compute Conway’s constant | exercise solution codepad | ||
| 229 | 19 Apr 2011 | Same Five Digits: A math puzzle from New Scientist, solved by guest author Bob Miller | exercise solution codepad | ||
| 240 | 27 May 2011 | Upside Up: Numbers that read the same upside down | exercise solution codepad | ||
| 271 | 13 Sep 2011 | Tetrahedral Numbers: Find the base of the tetrahedron that contains 169179692512835000 balls | exercise solution codepad | ||
| 288 | 15 Nov 2011 | Phil Harvey’s Puzle: partition {1,…,16} into two sets of equal size so each subset has the same sum, sum of squares and sum of cubes | exercise solution codepad | ||
| 289 | 18 Nov 2011 | Grade School Multiplication: Display the steps in the grade school multiplication algorithm | exercise solution codepad | ||
| 293 | 02 Dec 2011 | Knight Rider: Classic problem of the knight’s tour | exercise solution codepad | ||
| 295 | 09 Dec 2011 | McNugget Numbers: A simple problem, worked out on a napkin | exercise solution codepad | ||
| 304 | 10 Jan 2012 | Thirteen Anagram: 12+1=11+2 and “twelve plus one equals eleven plus two” are both anagrams | exercise solution codepad | ||
| 315 | 17 Feb 2012 | Hailstones: Examine the Collatz sequence | exercise solution codepad | ||
| 329 | 06 Apr 2012 | Voters: Watch voting blocks migrate on the screen | exercise solution codepad | ||
| 330 | 10 Apr 2012 | Galton: Simulate a marble-drop that forms a bell-shaped curve | exercise solution codepad | ||
| 333 | 20 Apr 2012 | John Horton Conway’s Game Of Life: The classic cellular automata | exercise solution codepad | ||
| 348 | 15 Jun 2012 | Counting Ones: Count the number of 1-digits in the numbers less than n | exercise solution codepad | ||
| 350 | 22 Jun 2012 | Billboard Challenge, Part 1: First part of a Google recruiting challenge | exercise solution codepad | ||
| 351 | 26 Jun 2012 | Billboard Challenge, Part 2: Second part of a Google recruiting challenge | exercise solution codepad | ||
| 354 | 06 Jul 2012 | Fractran: Write an interpreter for John Horton Conway’s language Fractran | exercise solution codepad | ||
| 359 | 24 Jul 2012 | Zeckendorf Representation: Find the fibonacci numbers that sum to a given number | exercise solution codepad | ||
| 361 | 31 Jul 2012 | SEND + MORE = MONEY, Part 1: Two slow solutions to a classic problem of recreational mathematics | exercise solution codepad | ||
| 362 | 03 Aug 2012 | SEND + MORE = MONEY, Part 2: Two hill-climbing solutions to a classic problem of recreational mathematics | exercise solution codepad | ||
| 364 | 10 Aug 2012 | Minimum Scalar Product: A simple exercise from the practice round of Google Code Jam 2008 | exercise solution codepad | ||
| 365 | 14 Aug 2012 | 4SUM: Find four numbers in an array that sum to zero | exercise solution codepad | ||
| 386 | 30 Oct 2012 | Pandigital Numbers: Find sums that include all ten digits | exercise solution codepad | ||
| 389 | 09 Nov 2012 | Taxicab Numbers: Confirm an interesting observation of Srinivasa Ramanujan | exercise solution codepad | ||
| 399 | 14 Dec 2012 | 115132219018763992565095597973971522401: Calculate the sequence of narcissistic numbers | exercise solution codepad | ||
| 402 | 25 Dec 2012 | The Twelve Days of Christmas: Count the gifts of Christmas | exercise solution codepad | ||
| 403 | 28 Dec 2012 | Three Wise Men: Find the prices of their gifts | exercise solution codepad | ||
| 404 | 01 Jan 2013 | Happy New Year!: Find expressions that evaluate to 2013 | exercise solution codepad | ||
| 411 | 01 Feb 2013 | Hofstadter’s Sequence: An infinite figure-figure sequence | exercise solution codepad | ||
| 412 | 05 Feb 2013 | The 147 Puzzle: Compute all the solutions to 1/a + 1/b + 1/c + 1/d + 1/e = 1 in integers | exercise solution codepad | ||
| 415 | 15 Feb 2013 | Facebook Hacker Cup 2013, Round 1, Problem 1: Count the ways to win a card game | exercise solution codepad | ||
| 417 | 22 Feb 2013 | Floupia: Make change in a strange currency | exercise solution codepad | ||
| 421 | 08 Mar 2013 | Knight Moves: Move a knight around a chess board | exercise solution codepad | ||
| 457 | 16 Jul 2013 | Vampire Numbers: Numbers x * y that consist of the digits of x and y | exercise solution codepad | ||
| 461 | 30 Jul 2013 | Who Buys The Croissants?: Simulate an important Friday-morning question | exercise solution codepad | ||
| 466 | 16 Aug 2013 | Monkey Grid Puzzle: How many points can the monkey access? | exercise solution codepad | ||
| 474 | 17 Sep 2013 | Smallest Consecutive Four-Factor Composites: Find consecutive numbers with four factors | exercise solution codepad | ||
| 486 | 29 Oct 2013 | The 16 Game: Determine the odds in a scratch-off game | exercise solution codepad | ||
| Simulation | |||||
| 3 | 19 Feb 2009 | Bingo: Calculate the probability of winning at Bingo | exercise solution codepad | ||
| 53 | 24 Jul 2009 | Let’s Make A Deal!: Simulate a tricky probability calculation | exercise solution codepad | ||
| 75 | 09 Oct 2009 | Calculating Pi: Calculate the value of π by monte-carlo methods and by an Archimedean method | exercise solution codepad | ||
| 133 | 04 May 2010 | Spectacular Seven: Compute the odds at jai alai | exercise solution codepad | ||
| 145 | 29 Jun 2010 | World Cup Prognostication: Simulate the knockout stage using elo ratings | exercise solution codepad | ||
| 158 | 13 Aug 2010 | E: A simple simulation with a surprising ending | exercise solution codepad | ||
| 216 | 04 Mar 2011 | Chutes And Ladders: Simulate a child’s game, and compute its statistics | exercise solution codepad | ||
| 285 | 04 Nov 2011 | Craps: Simulate a popular game of gambling with dice | exercise solution codepad | ||
| 381 | 12 Oct 2012 | Birthday Paradox: Use simulation to demonstrate the birthday paradox | exercise solution codepad | ||
| 423 | 15 Mar 2013 | Buffon’s Needle: Compute the value of π with a simulation | exercise solution codepad | ||
| 461 | 30 Jul 2013 | Who Buys The Croissants?: Simulate an important Friday-morning question | exercise solution codepad | ||
| Sorting and Searching | |||||
| 18 | 23 Mar 2009 | Binary Search: A simple task, easy to get wrong | exercise solution codepad | ||
| 22 | 07 Apr 2009 | Flipping Pancakes: A sorting method analyzed by Bill Gates | exercise solution codepad | ||
| 25 | 17 Apr 2009 | Spell Checking: A spell-checker in a trie-based dictionary | exercise solution codepad | ||
| 26 | 21 Apr 2009 | Probabilistic Spell Checking: A probabilistic spell-checker based on a Bloom filter | exercise solution codepad | ||
| 30 | 05 May 2009 | Priority Queues: A simple library implementation of the priority queue data structure | exercise solution codepad | ||
| 39 | 05 Jun 2009 | Ternary Search Tries: Build a function library for handling ternary search tries | exercise solution codepad | ||
| 45 | 26 Jun 2009 | Treaps: A randomized dictionary data structure, provides in-order access to key | exercise solution codepad | ||
| 59 | 14 Aug 2009 | Pairing Heaps: A standard algorithm for maintaining priority queues | exercise solution codepad | ||
| 73 | 02 Oct 2009 | Red-Black Trees: A purely functional dictionary data structure based on approximately-balanced trees | exercise solution codepad | ||
| 77 | 16 Oct 2009 | Growable Arrays: Arrays that grow and shrink at run-time, with O(log n) complexity per operation | exercise solution codepad | ||
| 78 | 20 Oct 2009 | Shuffle: Create random permutations of an array or linked list | exercise solution codepad | ||
| 80 | 27 Oct 2009 | Three Quadratic Sorts: Bubble sort, selection sort and insertion sort | exercise solution codepad | ||
| 81 | 30 Oct 2009 | Two Sub-Quadratic Sorts: Comb sort and shell sort | exercise solution codepad | ||
| 82 | 03 Nov 2009 | Quick Sort: Tony Hoare’s divide-and-conquer sorting algorithm | exercise solution codepad | ||
| 83 | 06 Nov 2009 | Heap Sort: A guaranteed O(log n) sorting method based on priority queues | exercise solution codepad | ||
| 84 | 10 Nov 2009 | Merge Sort: A fast, stable sorting algorithm, especially well-suited to linked lists | exercise solution codepad | ||
| 85 | 13 Nov 2009 | Two linear sorts: Count sort and radix sort exploit the structure of integer keys | exercise solution codepad | ||
| 93 | 11 Dec 2009 | Selection: Find the kth-largest item in a list | exercise solution codepad | ||
| 96 | 22 Dec 2009 | Permuted Index: David Parnas’ classic deconstruction of the keyword-in-context index | exercise solution codepad | ||
| 111 | 16 Feb 2010 | Soundex: An algorithm to assign people’s last names to equivalence classes based on similar spelling | exercise solution codepad | ||
| 113 | 23 Feb 2010 | Engineering A Sort Function: A high-performance quicksort by Jon Bentley and Doug McIlroy | exercise solution codepad | ||
| 116 | 05 Mar 2010 | Binary Search Tree: Classic data structure, providing insert, delete and lookup for ordered datatypes | exercise solution codepad | ||
| 160 | 20 Aug 2010 | Marriage Sort: A sub-quadratic sort similar to shell sort or comb sort | exercise solution codepad | ||
| 171 | 28 Sep 2010 | Maxiphobic Heaps: A priority-queue data structure, similar to leftist heaps, due to Chris Okasaki | exercise solution codepad | ||
| 186 | 19 Nov 2010 | Topological Sort: Order the edges of a graph by their precedence relationship | exercise solution codepad | ||
| 207 | 01 Feb 2011 | Cuckoo Hashing: A hashing system with guaranteed constant-time lookup and amortized constant-time insertion | exercise solution codepad | ||
| 228 | 15 Apr 2011 | Partition Numbers: Calculate the partition numbers, using memoization via growing arrays | exercise solution codepad | ||
| 237 | 17 May 2011 | Two Bad Sorts: Stooge sort and bogosort are worse than quadratic | exercise solution codepad | ||
| 269 | 06 Sep 2011 | Deques: Library implementation of double-ended queues | exercise solution codepad | ||
| 291 | 25 Nov 2011 | AVL Trees: Basic implementation of the original balanced-tree algorithm | exercise solution codepad | ||
| 292 | 29 Nov 2011 | AVL Trees, Extended: Add additional functionality to AVL trees | exercise solution codepad | ||
| 321 | 09 Mar 2012 | Sparse Sets: Clever data structure for storing sparse sets of small integers | exercise solution codepad | ||
| 345 | 05 Jun 2012 | Binomial Heaps: Another algorithm for maintaining priority queues | exercise solution codepad | ||
| 347 | 12 Jun 2012 | Ordered Maps: A key/value dictionary that supports an ordering relationship | exercise solution codepad | ||
| 368 | 24 Aug 2012 | Hash Tables With Open Addressing: An alternative to hash tables with chaining for collision resolution | exercise solution codepad | ||
| 369 | 28 Aug 2012 | Random Access Lists: A clever data structure that provides O(log n) access to items in a sequential list, along with cons, head and tail | exercise solution codepad | ||
| 395 | 30 Nov 2012 | Selection, Revisited: A guaranteed linear-time algorithm for selection | exercise solution codepad | ||
| 396 | 04 Dec 2012 | Median Of Five: A very fast method to compute the median of five items | exercise solution codepad | ||
| 409 | 22 Jan 2013 | Splay Heaps: Yet another implementation of priority queues | exercise solution codepad | ||
| 410 | 25 Jan 2013 | Imperative Heaps: The classing implementation of priority queues embedded in an array | exercise solution codepad | ||
| 414 | 12 Feb 2013 | Binary Search Tree: In-Order Predecessor And Successor: Find the previous and next items in a tree | exercise solution codepad | ||
| 420 | 05 Mar 2013 | Dutch National Flag: Classic ternary sort by Edsgar Dijkstra | exercise solution codepad | ||
| 422 | 12 Mar 2013 | An Array Of Two Symbols: A learning experience for binary search | exercise solution codepad | ||
| 447 | 07 Jun 2013 | Sets: A classic data structure and associated algorithms | exercise solution codepad | ||
| 456 | 12 Jul 2013 | Dynamic Hash Tables: Hash tables that grow and contract automatically to maintain a constant load factor | exercise solution codepad | ||
| 462 | 02 Aug 2013 | Ordered Hash Tables: Knuth’s improvement to simple hash tables | exercise solution codepad | ||
| 477 | 27 Sep 2013 | Double-Ended Priority Queues: Priority queues that permit access at both ends | exercise solution codepad | ||
| Spelling | |||||
| 23 | 10 Apr 2009 | Anagrams: Find anagrams in a dictionary | exercise solution codepad | ||
| 25 | 17 Apr 2009 | Spell Checking: A spell-checker in a trie-based dictionary | exercise solution codepad | ||
| 26 | 21 Apr 2009 | Probabilistic Spell Checking: A probabilistic spell-checker based on a Bloom filter | exercise solution codepad | ||
| 27 | 24 Apr 2009 | Word Hy-phen-a-tion By Com-pu-ter: Frank Liang’s hyphenation algorithm, used in TeX | exercise solution codepad | ||
| 66 | 08 Sep 2009 | Porter Stemming: Martin Porter’s algorithm for removing suffices from word stems | exercise solution codepad | ||
| 97 | 29 Dec 2009 | A Statisticle Speling Korrecter: Peter Norvig’s version of the Google spelling suggester | exercise solution codepad | ||
| 334 | 24 Apr 2012 | Rhyming Dictionary: Find rhyming words for poets | exercise solution codepad | ||
| Strings | |||||
| 61 | 21 Aug 2009 | String Search: Brute Force: Search for a pattern in a text by comparing the pattern to the text at all possible positions | exercise solution codepad | ||
| 62 | 25 Aug 2009 | String Search: Knuth-Morris-Pratt: Search for a pattern in a text using an O(n) algorithm | exercise solution codepad | ||
| 63 | 28 Aug 2009 | String Search: Boyer-Moore: Search for a pattern in a text using a fast and simple algorithm | exercise solution codepad | ||
| 64 | 01 Sep 2009 | String Search: Rabin-Karp: Our final classic string-search algorithm | exercise solution codepad | ||
| 67 | 11 Sep 2009 | Beautiful Code: A simple regular-expression matcher by Rob Pike | exercise solution codepad | ||
| 68 | 15 Sep 2009 | Regular Expressions, Part 1: A parser for regular expressions | exercise solution codepad | ||
| 69 | 18 Sep 2009 | Regular Expressions, Part 2: The corresponding matcher | exercise solution codepad | ||
| 70 | 22 Sep 2009 | Regular Expressions, Part 3: A regular expression test suite | exercise solution codepad | ||
| 71 | 25 Sep 2009 | Grep: Simple version of the classic unix regular-expression matching utility | exercise solution codepad | ||
| 193 | 14 Dec 2010 | Longest Duplicated Substring: Use a sorted suffix list | exercise solution codepad | ||
| 317 | 24 Feb 2012 | Remove Characters From A String: Remove from one string any character in a second string | exercise solution codepad | ||
| Text Processing | |||||
| 14 | 10 Mar 2009 | Word Frequencies: Our interpretation of a problem solved by a classic unix pipeline | exercise solution codepad | ||
| 159 | 17 Aug 2010 | Cut: Select fields or characters from input lines | exercise solution codepad | ||
| Unix V7 | |||||
| 14 | 10 Mar 2009 | Word Frequencies: Our interpretation of a problem solved by a classic unix pipeline | exercise solution codepad | ||
| 25 | 17 Apr 2009 | Spell Checking: A spell-checker in a trie-based dictionary | exercise solution codepad | ||
| 26 | 21 Apr 2009 | Probabilistic Spell Checking: A probabilistic spell-checker based on a Bloom filter | exercise solution codepad | ||
| 71 | 25 Sep 2009 | Grep: Simple version of the classic unix regular-expression matching utility | exercise solution codepad | ||
| 92 | 08 Dec 2009 | Word Count: An implementation of the unix wc program |
exercise solution codepad | ||
| 98 | 01 Jan 2010 | Cal: Print a twelve-month calendar | exercise solution codepad | ||
| 136 | 28 May 2010 | Printing Files: A simple program to list files, similar to the unix pr program | exercise solution codepad | ||
| 139 | 08 Jun 2010 | Diff: Find the differences between two text files | exercise solution codepad | ||
| 141 | 15 Jun 2010 | Natural Join: The fundamental relational database operator | exercise solution codepad | ||
| 142 | 18 Jun 2010 | Parsing Command-Line Arguments: An old-style getopt function | exercise solution codepad | ||
| 159 | 17 Aug 2010 | Cut: Select fields or characters from input lines | exercise solution codepad | ||
| 222 | 25 Mar 2011 | Sum: The standard Unix V7 file-checksum command | exercise solution codepad | ||
| 225 | 05 Apr 2011 | Fortune: Print a random aphorism from a file | exercise solution codepad | ||
| 234 | 06 May 2011 | Entab And Detab: expand tabs into spaces, and replace spaces with tabs | exercise solution codepad | ||
| 235 | 10 May 2011 | Comm: select or reject lines common to two sorted files | exercise solution codepad | ||
| 281 | 21 Oct 2011 | Sum, Revisited: SysV and Berkeley versions of the Unix V7 sum command | exercise solution codepad | ||
| 282 | 25 Oct 2011 | Cksum: Unix checksum utility | exercise solution codepad | ||
| 298 | 20 Dec 2011 | Hangman: Classic Unix V7 game for guessing words | exercise solution codepad | ||
| 346 | 08 Jun 2012 | Cat: The Unix V7 utility to catenate and print | exercise solution codepad | ||
| 363 | 07 Aug 2012 | Make: The classic Unix utility for managing file dependencies | exercise solution codepad | ||
| 382 | 16 Oct 2012 | Version Control: Economically store multiple versions of text files | exercise solution codepad | ||
| 432 | 16 Apr 2013 | Date Formatting: Neatly write a date in a variety of formats | exercise solution codepad | ||
| 459 | 23 Jul 2013 | Telephone Lookup: A directory-assistance program by Mike Lesk | exercise solution codepad | ||
| 465 | 13 Aug 2013 | Unix Paths: Convert relative Unix path to absolute, by Robert Fisher | exercise solution codepad | ||
| Word Games | |||||
| 11 | 27 Feb 2009 | Mark V. Shaney: Generate parodies of a text using a Markov chain | exercise solution codepad | ||
| 17 | 20 Mar 2009 | Dodgson's Doublets: A word game invented by the author of Alice in Wonderland | exercise solution codepad | ||
| 23 | 10 Apr 2009 | Anagrams: Find anagrams in a dictionary | exercise solution codepad | ||
| 149 | 13 Jul 2010 | Word Cube: A game to form words from a given set of letters | exercise solution codepad | ||
| 233 | 03 May 2011 | Squaring The Bishop: Charles Babbage’s game of word squares | exercise solution codepad | ||
| 309 | 27 Jan 2012 | Anagram Phrases: “Gin grammar prop six” is an anagram for “Programming Praxis” | exercise solution codepad | ||
| 334 | 24 Apr 2012 | Rhyming Dictionary: Find rhyming words for poets | exercise solution codepad | ||
| 353 | 03 Jul 2012 | Chopping Words: Form a chain of words by removing letters one at a time | exercise solution codepad | ||
| 380 | 09 Oct 2012 | Two Word Games: Find words in a dictionary | exercise solution codepad | ||
| 440 | 14 May 2013 | Optimal Alphabetical Order: Redefine the alphabet to improve alphabetical ordering | exercise solution codepad | ||
| 454 | 02 Jul 2013 | Decoding Text-Speak: Expnd txt wth only intl vwls and n dbld ltrs | exercise solution codepad | ||
| 458 | 19 Jul 2013 | J K Rowling: Identify an author using forensic linguistics | exercise solution codepad | ||
Programming Praxis 