Linear Regression

June 10, 2016

Linear regression is a widely-used statistical technique for relating two sets of variables, traditionally called x and y; the goal is to find the line-of-best-fit, y = m x + b, that most closely relates the two sets. The formulas for computing the line of best fit are:

m = (n × Σxy − Σx × Σy) ÷ (n × Σx2 − (Σx)2)

b = (Σym × Σx) ÷ n

You can find those formulas in any statistics textbook. As an example, given the sets of variables

x    y
60   3.1
61   3.6
62   3.8
63   4.0
65   4.1

the line of best fit is y = 0.1878 x − 7.9635, and the estimated value of the missing x = 64 is 4.06.

Your task is to write a program that calculates the slope m and intercept b for two sets of variables x and y. 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.

Pages: 1 2

Christian Goldbach (1690-1764) was a Prussian mathematician and contemporary of Euler. One of the most famous unproven conjectures in number theory is known as Goldbach’s Conjecture, which states that every even number greater than two is the sum of two prime numbers; for example, 28 = 5 + 23. We studied Goldbach’s Conjecture in a previous exercise.

Although it is not as well known, Goldbach made another conjecture as follows: Every odd number greater than two is the sum of a prime number and twice a square; for instance, 27 = 19 + 2 * (2 ** 2). (The conjecture is sometimes stated as every odd composite number is the sum of a prime number and twice a square, since it is trivially true with 0 as the square root for all prime numbers; alternately, it is sometimes limited so that the number being squared must be positive, in which case there are some odd primes that can be so expressed.) Sadly, it is easy to find a counter-example that disproves Goldbach’s other conjecture.

Your task is to write a program that finds the smallest number that disproves Goldbach’s other 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.

Pages: 1 2

A Dozen Lines Of Code

June 3, 2016

Today’s exercise demonstrates that it is sometimes possible to do a lot with a little.

Your task is to write some interesting and useful program in no more than a dozen lines of code. 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.

Pages: 1 2

Learn A New Language

May 31, 2016

It’s fun to learn new programming languages. It’s also useful, even if you never use the new language, because it forces you to think differently about how you do things.

Your task is to write a familiar program in an unfamiliar language. When you are finished, you are welcome to read or run ([1], [2]) a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We studied discrete logarithms in two previous exercises. Today we look at a third algorithm for computing discrete algorithms, invented by John Pollard in the mid 1970s. Our presentation follows that in the book Prime Numbers: A Computational Perspective by Richard Crandall and Carl Pomerance, which differs somewhat from other sources.

Our goal is to compute l (some browsers mess that up; it’s a lower-case ell, for “logarithm”) in the expression glt (mod p); here p is a prime greater than 3, g is an integer generator on the range 1 ≤ g < p, and t is an integer target on the range 1 ≤ g < p. Pollard takes a sequence of integer pairs (ai, bi) modulo (p − 1) and a sequence of integers xi modulo p such that xi = tai gbi (mod p), beginning with a0 = b0 = 0 and x0 = 1. Then the rule for deriving the terms of the various sequences is:

  • If 0 < xi < p/3, then ai+1 = (ai + 1) mod (p − 1), bi+1 = bi, and xi+1 = t xi (mod p).
  • If p/3 < xi < 2p/3, then ai+1 = 2 ai mod (p − 1), bi+1 = 2 bi mod (p − 1), and xi+1 = xi2 mod p.
  • If 2p/3 < xi < p, then ai+1 = ai, bi+1 = (bi + 1) mod (p − 1), and xi+1 = g xi mod p.

Splitting the computation into three pieces “randomizes” the calculation, since the interval in which xi is found has nothing to do with the logarithm. The sequences are computed until some xj = xk, at which point we have taj gbj = tak gbk. Then, if ajaj is coprime to p − 1, we compute the discrete logarithm l as (ajak) lbkbj (mod (p − 1)). However, if the greatest common divisor of ajaj with p − 1 is d > 1, then we compute (ajak) l0bkbj (mod (p − 1) / d), and l = l0 + m (p − 1) / d for some m = 0, 1, …, d − 1, which must all be checked until the discrete logarithm is found.

Thus, Pollard’s rho algorithm consists of iterating the sequences until a match is found, for which we use Floyd’s cycle-finding algorithm, just as in Pollard’s rho algorithm for factoring integers. Here are outlines of the two algorithms, shown side-by-side to highlight the similarities:

# find d such that d | n      # find l such that g**l = t (mod p)
function factor(n)            function dlog(g, t, p)
  func f(x) := (x*x+c) % n      func f(x,a,b) := ... as above ...
  t, h, d := 1, 1, 1            j := (1,0,0); k := f(1,0,0)
  while d == 1                  while j.x <> k.x
    t = f(t)                      j(x,a,b) := f(j.x, j.a, j.b)
    h = f(f(h))                   k(x,a,b) := f(f(k.x, k.a, k.b))
    d = gcd(t-h, n)             d := gcd(j.a-k.a, p-1)
  return d                      return l ... as above ...

Please pardon some abuse of notation; I hope the intent is clear. In the factoring algorithm, it is possible that d is the trivial factor n, in which case you must try again with a different constant in the f function; the logarithm function has no such possibility. Most of the time consumed in the computation is the modular multiplications in the calculations of the x sequence; the algorithm itself is O(sqrt p), the same as the baby-steps, giant-steps algorithm of a previous exercise, but the space requirement is only a small constant, rather than the O(sqrt p) space required of the previous algorithm. In practice, the random split is made into more than 3 pieces, which complicates the code but speeds the computation, as much as a 25% improvement on average.

Your task is to write a program that computes discrete logarithms using Pollard’s rho algorithm. 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.

Pages: 1 2

Test Scores

May 24, 2016

The high school two blocks from me just had their annual picnic, my youngest daughter just graduated from college, and my primarily academic readership suddenly dropped in half (history suggest it will stay low until mid-August), so it seems to be the right season to have a simple data-processing task involving student test scores.

Given a list of student names and test scores, compute the average of the top five scores for each student. You may assume each student has as least five scores.

Your task is to compute student scores 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.

Pages: 1 2

No Exercise Today

May 20, 2016

I’ve been busy at work and haven’t had time to prepare an exercise for today. I apologize.

Your task is to solve a previous exercise that you haven’t yet solved. Have fun!

This is an Amazon interview question:

Given a heap (priority queue), insert an element into the heap if the element is not already present in the heap. Your solution must work in O(n) time, where n is the number of items in the heap.

Your task is to write a program to insert an element into a heap if the element is not already present in the heap, in logarithmic time. 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.

Pages: 1 2

This must be somebody’s homework:

Given an array of integers, rearrange the elements of the array so that elements in even-indexed positions are in ascending order and elements in odd-indexed positions are in descending order. For instance, given the input 0123456789, the desired output is 0927456381, with the even-indexed positions in ascending order 02468 and the odd-indexed positions in descending order 97531.

Your task is to write a program that performs the indicated rearrangement of its input. 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.

Pages: 1 2

Concatenate N N Times

May 10, 2016

A number like 7777777 consists of the number 7 concatenated to itself 7 times. A number like 121212121212121212121212 consists of the number 12 concatenated to itself 12 times.

Your task is to write a program that calculates the number that is concatenated to itself the number of times as the number is (that’s hard to say). 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.

Pages: 1 2