# Blog Profile / Programming Praxis

URL : http://programmingpraxis.com/ Academics / Mathematics 537 1.2 August 9, 2009

## Blog Post Archive

### Compare Strings With One Error

I don’t know if today’s exercise comes from an interview question or from somebody’s homework, but it’s a good exercise: Given two strings, determine if they are the same except for exactly one difference. Two identical strings fail to match. Two strings that differ in two or more characters fail to match. Two strings with […]

### Higher-Order String Functions

Scheme provides the higher-order functions map, for-each and fold that operate on lists. In today’s exercise we will write versions of those functions that operate on strings: (string-map proc str) applies proc to each character in str, replacing the character with the output of proc. proc takes a single character and returns a single character. […]

### Entropy

The Shannon entropy of a file is a measure of the information content in the file; higher entropy implies more information. Shannon entropy is computed as H = -1 sum(pi log2(pi)) where pi is the frequency of each symbol i in the input (frequency is the percentage of the total number of symbols). […]

### RSA Encryption Backdoor

There has been much ado recently about a law-enforcement backdoor to encryption that would enable authorized access to private encrypted communications: FBI director James Comey and British Prime Minister David Cameron have both come out strongly in favor of an encryption backdoor as a tool in the fight against terrorists, while the EFF and cryptography […]

### Dobble

Dobble is a French card game that uses 55 cards, each with 8 symbols; any pair of cards have exactly one symbol in common. The game is played by dealing one card to each player and placing the remaining cards face-up in the center of the table; the first player to spot the symbol that […]

### Matrix Fill-In

Since we haven’t done one for a while, today’s exercise is an interview question: Given a matrix of cells containing 0 or 1, modify the matrix so all cells in the same row or column as a cell containing a 1 also contain a 1. For instance, the matrix below left should be converted to […]

### Maximal Prime Gaps

Although the prime numbers are fascinating in their own right, sometimes it is interesting and instructive to look at the gaps between successive prime numbers. For instance, here is a table that shows how the maximal prime gap grows: 2 1 3 2 7 4 23 6 89 8 113 14 523 18 887 20 […]

### Compatible Numbers

Two numbers are compatible if they have the same prime factors, though with possibly different multiplicities. Your task is to write a program to determine if two numbers are compatible. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in […]

### Happy New Year!

The triangular numbers (A000217) are those numbers that can be formed by identical objects arranged in a triangle. For instance, 10 bowling pins can be formed in a triangle with sides of length 4, so the fourth triangular number is 10. Your task is to write a program that computes the n?th triangular number; what […]

### Merry Christmas

[ Merry Christmas to all my readers! And best wishes for you and your families in the coming year! I’ll be taking a few weeks away from the blog to be with family; new exercises will resume the first Tuesday of 2016. In the meantime, enjoy this Christmas card from me to you, with art […]

### Two-Part Interview Question

Today we have a two-part interview question from Amazon: First, find the first non-repeated element in an unsorted array. For instance, in the array [3, 5, 3, 2, 1], element 3 is repeated, elements 5, 2, and 1 are non-repeated, and the first of those is 5. Second, find the first element that appears an […]

### Shellsort With Three Increments

It was a dreary Sunday in St Louis, unseasonably warm, but it rained all day and felt much colder than the actual air temperature, so I sat down to read Donald Knuth’s article, with Svante Janson, Shellsort With Three Increments. After sixteen pages, Janson and Knuth conjecture but do not prove that the gap sequence […]

### Longest Consecutive Sequence Of Squares

Some numbers can be represented as the sum of a sequence of consecutive squares; for instance, 595 = 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2. Other numbers are not so representable. Your task is to write a program that finds the longest consecutive sequence of squares that sums to […]

### Hardware Random Number Generator

We discussed an algorithm due to Lenore Blum, Manuel Blum and Michael Shub that generates cryptographically-secure random numbers in a previous exercise. A better way to generate these random numbers uses an actual hardware source of entropy, such as thermal noise. I recently learned that all models of the Raspberry Pi computer include a hardware […]

### Minimum Split

Today’s task is a simple exercise in list handling: Given a list of integers, find the place where the list can be split in two that minimizes the differences in the sums of the two halves of the list. For instance, given the list [3,7,4,2,1], splitting after the second element of the list gives sums […]

I had too much Thanksgiving; more specifically, the stuffing went bad, and I’ve felt poorly the last few days. In between trips to the bathroom, I picked up my copy of Hofstadter’s GEB and looked again at the FIGURE-FIGURE sequences of Chapter III: 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, … and […]

### Happy Thanksgiving

There will be no exercise today. To all my readers in the United States: Happy Thanksgiving!

### Reversible Random Number Generator

Some applications of random number generators. games, for instance, require that the random sequence be available to run in reverse. This is easy to do with a simple linear congruential random number generator, which is characterized by the formula next = a prev + c (mod m). With a little bit of algebra, that […]

### External Sorting

Sorting the lines of a file that fits in memory is a simple matter of loading the file and calling the sort function. When the file doesn’t fit in memory, however, it must be sorted in pieces, then combined into a single output, which is harder. Your task is to write a program that sorts […]

### File Reversal

Given a file containing lines of text that fits into memory, it is easy to write the file with lines in reverse order: read the lines of text into memory, then write them in reverse. It is harder to reverse the lines of a file if the file is too big to fit into memory. […]

Posts on Regator