Exercises In Chronological Order

1 19 Feb 2009 RPN Calculator: Evaluate numeric expressions at the command line exercise solution codepad
2 19 Feb 2009 Sieve of Eratosthenes: A Scheme implementation of an ancient algorithm exercise solution codepad
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
5 19 Feb 2009 Flavius Josephus: Programming a cyclical list exercise solution codepad
6 20 Feb 2009 ROT13: A simple Caesar-shift cipher exercise solution codepad
7 20 Feb 2009 Multiple Dwellings: A simple logic puzzle, solved with the amb non-deterministic operator exercise solution codepad
8 20 Feb 2009 The Digits of Pi: A spigot algorithm to calculate the digits of pi exercise solution codepad
9 20 Feb 2009 A Self-Reproducing Program: The quintessential quine exercise solution codepad
10 24 Feb 2009 Mardi Gras: Compute the date of Easter exercise solution codepad
11 27 Feb 2009 Mark V. Shaney: Generate parodies of a text using a Markov chain exercise solution codepad
12 03 Mar 2009 Creation: Cryptanalysis of a Vigenère cipher exercise solution codepad
13 06 Mar 2009 Roman Numerals: A library to read and write Roman numerals exercise solution codepad
14 10 Mar 2009 Word Frequencies: Our interpretation of a problem solved by a classic unix pipeline exercise solution codepad
15 13 Mar 2009 Friday, the Thirteenth: A small calendar library, and a simple use of it 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
17 20 Mar 2009 Dodgson's Doublets: A word game invented by the author of Alice in Wonderland exercise solution codepad
18 23 Mar 2009 Binary Search: A simple task, easy to get wrong exercise solution codepad
19 27 Mar 2009 A Turing Machine Simulator: An interpreter for a single-tape, multi-symbol turing machine exercise solution codepad
20 31 Mar 2009 Rail-Fence Cipher: A simple transposition cipher exercise solution codepad
21 03 Apr 2009 Programming the Turing Machine: A turing-machine program to multiply two numbers exercise solution codepad
22 07 Apr 2009 Flipping Pancakes: A sorting method analyzed by Bill Gates exercise solution codepad
23 10 Apr 2009 Anagrams: Find anagrams in a dictionary exercise solution codepad
24 14 Apr 2009 Google Treasure Hunt 2008 Puzzle 4: A prime-number puzzle 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
28 28 Apr 2009 Morse Code: Translating the dots-and-dashes of Samuel Finley Breese Morse’s telegraph code exercise solution codepad
29 01 May 2009 Primality Checking: A probabilistic primality checker by Gary Miller and Michael Rabin exercise solution codepad
30 05 May 2009 Priority Queues: A simple library implementation of the priority queue data structure exercise solution codepad
31 08 May 2009 Wheel Factorization: Find the factors of a number by a variant of trial division exercise solution codepad
32 12 May 2009 Loan Amortization: Calculate and print a simple loan amortization table 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
34 19 May 2009 Fermat’s Method: Integer factorization by Fermat’s algorithm exercise solution codepad
35 22 May 2009 The Next Palindrome: Find the next palindromic number greater than the input number exercise solution codepad
36 26 May 2009 Word Search Solver: A computerized implementation of a popular time-waster exercise solution codepad
37 29 May 2009 Double Transposition Cipher: A simple and effective cipher, easy to perform by hand exercise solution codepad
38 02 Jun 2009 Pig Latin: A simple exercise to solve a children’s game exercise solution codepad
39 05 Jun 2009 Ternary Search Tries: Build a function library for handling ternary search tries exercise solution codepad
40 09 Jun 2009 Longest Common Subsequence: A classic programming algorithm, with a solution that dates to folklore 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
43 19 Jun 2009 Monte Carlo Factorization: Integer factorization via Pollard’s rho algorithm exercise solution codepad
44 23 Jun 2009 The Mod Out System: Expand a series of ranges exercise solution codepad
45 26 Jun 2009 Treaps: A randomized dictionary data structure, provides in-order access to key exercise solution codepad
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
47 03 Jul 2009 The Playfair Cipher: A classic military field cipher 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
50 14 Jul 2009 The Daily Cryptogram: Solve a monoalphabetic substitution cipher exercise solution codepad
51 17 Jul 2009 International Mathematical Olympiad: Three exercises from 1960s math competitions exercise solution codepad
52 21 Jul 2009 Pollard’s P−1 Factorization Algorithm: A simple factorization algorithm by John Pollard exercise solution codepad
53 24 Jul 2009 Let’s Make A Deal!: Simulate a tricky probability calculation exercise solution codepad
54 28 Jul 2009 Elliptic Curves: Library of basic functions on elliptic curves 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
57 07 Aug 2009 ADFGX: A classic German military field cipher from the First World War exercise solution codepad
58 11 Aug 2009 Uncle Bob’s Bowling Game Kata: Use pattern-matching on lists to solve a classic object-oriented programming exercise exercise solution codepad
59 14 Aug 2009 Pairing Heaps: A standard algorithm for maintaining priority queues exercise solution codepad
60 18 Aug 2009 Blum Blum Shub: Stream cipher based on a cryptographically secure pseudo-random number generator exercise solution codepad
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
65 04 Sep 2009 Ron’s Cipher #4: Stream cipher by Ron Rivest that underlies the SSL and WEP protocols exercise solution codepad
66 08 Sep 2009 Porter Stemming: Martin Porter’s algorithm for removing suffices from word stems 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
72 29 Sep 2009 Green Eyes: A counting problem from high-school math exercise solution codepad
73 02 Oct 2009 Red-Black Trees: A purely functional dictionary data structure based on approximately-balanced trees exercise solution codepad
74 06 Oct 2009 MapReduce: Google’s famous system for parallelizing computations expressed as a programming idiom 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
76 13 Oct 2009 Bifid: A simple but effective fractionating cipher, never used militarily 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
79 23 Oct 2009 Mr. S. and Mr. P.: A logic puzzle popularized by John McCarthy 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
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
88 24 Nov 2009 Sunrise, Sunset: Calculate the times of sunrise and sunset on any day anywhere in the world 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
90 01 Dec 2009 Wolves And Rabbits: Analyze population dynamics using the Lotka-Volterra equations exercise solution codepad
91 04 Dec 2009 Autokey: A cipher in which the input text forms part of the key exercise solution codepad
92 08 Dec 2009 Word Count: An implementation of the unix wc program exercise solution codepad
93 11 Dec 2009 Selection: Find the kth-largest item in a list exercise solution codepad
94 15 Dec 2009 Affine-Shift Cipher: A cryptographically weak but mathematically interesting cipher 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
96 22 Dec 2009 Permuted Index: David Parnas’ classic deconstruction of the keyword-in-context index exercise solution codepad
97 29 Dec 2009 A Statisticle Speling Korrecter: Peter Norvig’s version of the Google spelling suggester exercise solution codepad
98 01 Jan 2010 Cal: Print a twelve-month calendar exercise solution codepad
99 05 Jan 2010 The Sum Of Two Squares: A math puzzle with a solution by Dijkstra exercise solution codepad
100 08 Jan 2010 Nim: A two-player game of mathematical logic 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
103 19 Jan 2010 Flight Planning: Computing the navigation triangle, by Jos Koot exercise solution codepad
104 22 Jan 2010 Phases Of The Moon: Calculate the number of days since the last new moon exercise solution codepad
105 26 Jan 2010 Primality Checking, Revisited: The Baillie-Wagstaff algorithm for primality checking 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
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
111 16 Feb 2010 Soundex: An algorithm to assign people’s last names to equivalence classes based on similar spelling exercise solution codepad
112 19 Feb 2010 Sieve Of Atkin, Improved: A faster version of the Sieve of Atkin exercise solution codepad
113 23 Feb 2010 Engineering A Sort Function: A high-performance quicksort by Jon Bentley and Doug McIlroy exercise solution codepad
114 26 Feb 2010 Run Length Encoding: A simple compression method for text files 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
116 05 Mar 2010 Binary Search Tree: Classic data structure, providing insert, delete and lookup for ordered datatypes exercise solution codepad
117 09 Mar 2010 Lexicographic Permutations: Continually generate the next permutation using an algorithm by Dijkstra exercise solution codepad
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
120 19 Mar 2010 Extending Pollard’s P−1 Factorization Algorithm: Add a second stage to allow larger factorizations exercise solution codepad
121 23 Mar 2010 Texas Hold ‘Em: Find the best poker hand exercise solution codepad
122 26 Mar 2010 The Next Prime: Efficiently find the next prime number larger than a given number exercise solution codepad
123 30 Mar 2010 Passover: Calculate the dates of the Jewish holidays Rosh Hashanah and Passover exercise solution codepad
124 02 Apr 2010 Disjoint Sets: A data structure for storing sets of items in disjoint partitions 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
128 16 Apr 2010 Expression Evaluation: Parse and evaluate an arithmetic expression with plus, minus, times, divide and parentheses 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
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
133 04 May 2010 Spectacular Seven: Compute the odds at jai alai exercise solution codepad
134 07 May 2010 Integer Logarithms: An improved algorithm is O(log n) instead of O(n) exercise solution codepad
135 25 May 2010 GB_FLIP: Donald Knuth’s portable, high-quality random-number generator from the Stanford Graphbase exercise solution codepad
136 28 May 2010 Printing Files: A simple program to list files, similar to the unix pr program exercise solution codepad
137 01 Jun 2010 Unwrapping A Spiral: An exercise in recursion 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
139 08 Jun 2010 Diff: Find the differences between two text files exercise solution codepad
140 11 Jun 2010 N-Queens: Our version of a classic algorithmic exercise 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
143 22 Jun 2010 Matrix Operations: Matrix addition, scalar multiplication, multiplication and transposition exercise solution codepad
144 25 Jun 2010 Learn A New Language: Solve the exercise of your choice in an unfamiliar language exercise solution codepad
145 29 Jun 2010 World Cup Prognostication: Simulate the knockout stage using elo ratings exercise solution codepad
146 02 Jul 2010 Contents: Chronological Listing Of Exercises: Blog management exercise solution codepad
147 06 Jul 2010 Chaocipher: First look at a ninety-two year old autokey-type cipher exercise solution codepad
148 09 Jul 2010 Contents: Permuted Table Of Contents: Blog management exercise solution codepad
149 13 Jul 2010 Word Cube: A game to form words from a given set of letters exercise solution codepad
150 16 Jul 2010 Contents: Themes: Blog Management exercise solution codepad
151 20 Jul 2010 Solving Systems Of Linear Equations: Matrix operations LU-decomposition and LUP-decomposition exercise solution codepad
152 23 Jul 2010 Happy Numbers: Iterating the sum of the squares of the digits terminates with one exercise solution codepad
153 27 Jul 2010 HAMURABI.BAS: Manage grain and land in ancient Sumeria exercise solution codepad
154 30 Jul 2010 Fibonacci Numbers: Three algorithms taking exponential time, linear time, and logarithmic time exercise solution codepad
155 03 Aug 2010 Carl Hewitt’s Same-Fringe Problem: Do two trees have the same leaves, solved with streams (lazy lists) exercise solution codepad
156 06 Aug 2010 Two Powering Predicates: Determine if a number is a square or a prime power exercise solution codepad
157 10 Aug 2010 Literate Programming: Structured documentation in the style of Donald Knuth exercise solution codepad
158 13 Aug 2010 E: A simple simulation with a surprising ending exercise solution codepad
159 17 Aug 2010 Cut: Select fields or characters from input lines exercise solution codepad
160 20 Aug 2010 Marriage Sort: A sub-quadratic sort similar to shell sort or comb sort 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
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