## Matrix Fill-In

### January 12, 2016

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 the matrix below right:

0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 1 0

Your task is to write a program to fill-in a matrix as described above. 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 the comments below.

## Matrix Fill-In

### January 12, 2016

Since we haven’t done one for a while, today’s exercise is an interview question from Career Cup:

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 the matrix below right:

0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 1 0

Your task is to write a program to fill-in a matrix as described above. 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 the comments below.

## Maximal Prime Gaps

### January 8, 2016

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

At each step the table shows a prime number and the gap to the next prime number; for instance, at prime 7 the gap to the next prime number, 11, is 4. The table only shows those instances where the prime gap increases. Note that the increases are not steady; for instance, a gap of 14 appears before a gap of 10 or 12.

Your task is to write a program that creates the table shown above. 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 the comments below.

## Compatible Numbers

### January 5, 2016

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 the comments below.

## Happy New Year!

### January 1, 2016

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 is the 63rd triangular number? 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 the comments below.

## Merry Christmas

### December 22, 2015

[ 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 “The Nativity of Jesus” by Botticelli and text from Luke 2:8-14 (King James Version). ]

And there were in the same country shepherds abiding in the field, keeping watch over their flock by night. And, lo, the angel of the Lord came upon them, and the glory of the Lord shone round about them: and they were sore afraid. And the angel said unto them, “Fear not; for, behold, I bring you tidings of great joy, which shall be to all people. For unto you is born this day in the city of David a Savior, which is Christ the Lord. And this shall be a sign unto you: Ye shall find the babe wrapped in swaddling clothes, lying in a manger.” And suddenly there was with the angel a multitude of the heavenly host praising God, and saying, “Glory to God in the highest, and on earth peace and goodwill towards men.”

## Two-Part Interview Question

### December 18, 2015

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 even number of times in an unsorted array. For instance, in the array [5, 3, 5, 1, 5, 1, 3], elements 1 and 3 appear an even number of times, and the first of those is 3.

Your task is to write programs that find the first non-repeated element and the first even-appearance elements in an unsorted input array. 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 the comments below.

## Shellsort With Three Increments

### December 15, 2015

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 (*h*, *g*, 1) with *h* ≈ √*n* and *g* ≈ √*h* and *h* coprime to *g* leads to time complexity O(*n*^{3/2}).

Your task is to implement shellsort, as we did in a previous exercise, and test the Janson/Knuth conjecture. 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 the comments below.

## Longest Consecutive Sequence Of Squares

### December 11, 2015

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 a given number, or determines that no such sequence exists. 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 the comments below.

## Hardware Random Number Generator

### December 8, 2015

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 random number generator on their system-on-a-chip; Stewart Russell gives instructions.

If instead of a Raspberry Pi you have a computer based on the Intel Ivy Bridge family of processors, a hardware random number generator is available as `rdrand`

; Linux exposes that as the `/dev/random`

device.

Your task is to explore the hardware random number generators that are available to you; you might want to write a program to generate keypads for the Diana Cryptosystem. 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 the comments below.