Degrees To Radians To Degrees
May 5, 2015
I saw this question on a beginning programmer’s forum a couple of weeks ago. There were several answers, some of them wrong. So we’ll do it right:
Given an angle expressed in degrees, minutes, and seconds, convert it to radians. Given an angle in radians, convert it to degrees, minutes and seconds.
Your task is to write programs that perform the two conversions. 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.
Collatz Primes
May 1, 2015
Today’s exercise comes from the world of recreational mathematics; I found it at Stack Overflow:
The Collatz sequence starting at n continues with n / 2, if n is even, and 3 n + 1 if n is odd. For instance, the Collatz sequence that starts from 19 is 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. It is conjectured that all Collatz sequences eventually end at 1, but has never been proven. The Collatz sequence that starts from 19 contains 7 prime numbers: 19, 29, 11, 17, 13, 5 and 2. Find the smallest starting number for a Collatz sequence that contains 65 or more primes.
Your task is to find the requested Collatz sequence. 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.
Identifying Anagrams
April 28, 2015
Two words are anagrams if they consist of the same letters, with the same number of occurrences, in a different order. For instance, DEPOSIT and DOPIEST are anagrams (aren’t you glad you know that), and OPTS, POTS, TOPS and STOP form an anagram class.
Your task is to write a program that takes two strings as input and determines whether or not they are anagrams; you may assume that the strings consist of only the letters A through Z in upper case. You must provide at least two different algorithms that work in fundamentally different ways. 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.
Minimum Impossible Sum
April 24, 2015
We have today another from our inexhaustible list of interview questions:
Given a list of positive integers, find the smallest number that cannot be calculated as the sum of the integers in the list. For instance, given the integers 4, 13, 2, 3 and 1, the smallest number that cannot be calculated as the sum of the integers in the list is 11.
Your task is to write a program that solves the interview question. 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.
Ordered Cartesian Coordinates
April 21, 2015
Today’s exercise is a simple little interview question:
Generate the pairs of cartesian coordinates within a square bounded by (1,1) and (n,n) ordered by their product in ascending order. For instance, when n is 3, the coordinates are (1,1), (1,2), (2,1), (1,3), (3,1), (2,2), (2,3), (3,2) and (3,3). Can you find a solution with time complexity better than O(n2)?
Your task is to write a program to solve the interview question. 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.
Euler’s Sum Of Powers Conjecture
April 17, 2015
Fermat’s Last Theorem, which dates to the seventeenth century states that there are no solutions in integers to the equation xn + yn = zn for n > 2; the Theorem was finally proved a few years ago by Andres Wiles. In the eighteenth century, Euler conjectured that for any n > 2, it would take at least n terms of the form xin to sum to an n th power. That conjecture held until the age of computers, in 1967, when Lander and Parkin found the counter-example 275 + 845 + 1105 + 1335 = 1445.
Your task is to write a program that finds counter-examples to Euler’s 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.
Balanced Ternary Arithmetic
April 14, 2015
We studied mixed-radix arithmetic in a previous exercise. In today’s exercise we look at a different kind of non-standard positional notation: balanced ternary, which is a base-3 number system that uses -1, 0 and 1 as its “trits” rather than 0, 1 and 2. For instance, the number -47 is written as (-1 1 1 -1 1) in balanced ternary, which is equivalent to -34 + 33 + 32 – 31 + 30. No separate sign is needed when using balanced notation; the sign of the leading trit is the sign of the whole number.
Arithmetic on balanced ternary numbers is done using the grade-school algorithms. Addition is done right-to-left with a carry; it is easy and fun to work out the plus-table. Subtraction is done by adding the negative, which can be computed by changing the sign of every trit. Multiplication works trit-by-trit through the multiplier, shifting at each trit.
Your task is to write functions that perform arithmetic on balanced ternary integers. 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.
Pounds, Shillings, Pence
April 7, 2015
Mixed-radix number systems have a base, or radix, that varies at each position. For instance, the old-style British pounds, shillings and pence form a mixed-radix system where there are twelve pence in a shilling and twenty shillings in a pound, and calendars form a mixed-radix system where there are sixty seconds in a minute, sixty minutes in an hour, twenty-four hours in a day, and seven days in a week.
Your task is to write a program that accepts a definition of a mixed-radix system — for instance, (7 24 60 60) for the calendar mentioned above — and performs addition and subtraction of numbers written in that system. 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.
Reluctant Search
April 3, 2015
Wednesday was April Fools’ Day, and I was feeling frisky, so I implemented the reluctant search algorithm from Pessimal Algorithms and Simplexity Analysis by Andrei Broder and Jorge Stolfi. Their algorithm takes time O(2n), which is worse than the naive brute force O(n), to find the index of a target x in a sorted array. We looked at a different algorithm that paper in a previous exercise. I’ll leave it to you to fetch the paper and enjoy the sincerity of the authors’ pessimality.
Your task is to implement the reluctant search 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.
Identifying Palindromes
March 31, 2015
Today’s task sounds simple but leads to a little bit of complexity.
Given an array, determine if it is a palindrome. Given a linked list, determine if it is a palindrome. Make both tests as efficient, in both time and space, as possible.
Your task is to write two programs to identify palindromes. 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.
Programming Praxis 