Maximum K Items Out Of N
August 30, 2016
Today’s exercise is to write a program that, given n integers, outputs the list of k integers whose sum is maximum. That looks easy, but there is a catch: You must provide three solutions, one that runs in O(n log n) time, one that runs in O(n log k) time, and one that runs in O(n) time.
Your task is to write three programs 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.
Circular Arrays
August 26, 2016
Today’s exercise is to write a program that provides queues using a circular array. You should provide operations to make a new queue with a user-specified maximum size, determine if a queue is empty, add new elements to the end of the queue, and remove elements from the beginning of the queue.
Your task is to implement a queue 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.
Nearly Square Divisors, Revisited
August 23, 2016
In a recent exercise, we discussed the problem of computing the nearly square divisors of a composite number n = a · b, with a ≥ b, such that the difference a − b is as small as possible. We gave two solutions: The first solution enumerated the divisors one-by-one, by trial division counting from 1, until reaching the square root, which is fast if n is small but slow in general. The second solution factored n, computed the divisors, the picked the two divisors in the middle of the list, which is fast in general but slow if n is highly composite and thus has a large number of divisors.
In a comment on that exercise, Matthew Arcus, who is a regular reader and commentor at Programming Praxis, gave a splendid answer to the problem; it relies on factoring n, but is fast even if n has a large number of divisors. His algorithm reduces the multiplication of the factors to addition of their logarithms, which means that the knapsack algorithm can be used to find the greatest sum less than the logarithm of the square root.
Your task is to implement Matthew’s algorithm to find the nearly-square divisors of a 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.
Diminishing Gap Sort
August 19, 2016
Today’s exercise comes from my friend Dan:
I don’t have time to think about this now (very busy these days), so I’m just throwing the idea at you. I’m sure there’s some sort of mathematical theorem that relates, but I’m sure you’ll probably know off the top of your head.
I was fascinated not too long ago by the consulting firm we’ve hired to re-vamp our website. I think they were given a tip-off that the color selection for the website theme could be a sticky wicket. So their plan was to pull the colors dynamically from the main picture selected on the home page (and/or departmental pages), which could be changed easily or automatically. They were going to develop something that would pick out the most prominent 6 to 10 colors — even if there wasn’t much contrast (and even black & white photos would supposedly work) — which would be then used for the menus and general color scheme.
Anyway, all this got me thinking about sorting a list of numbers (if these were color codes, there could be lots) such that the greatest gaps would float to the top. I’m sure you get the idea, but I’ll give an example anyway — which I figured out in Excel (below):
Given a number set of 5, 12, 14, 15, 80, 121, 134, 144, 256 the descending-by-highest-difference sort would yield: 256, 80, 121, 134, 144, 12, 14, 15, 5. So in this case, the top 3 biggest gaps would be between 80, 121, and 256.
Num Diff Num Diff ---- ---- ---- ---- 256 112 256 112 144 10 80 65 134 13 121 41 121 41 134 13 80 65 144 10 15 1 12 7 14 2 5 5 12 7 14 2 5 5 15 1I have no idea if this makes sense for the colors thing — it just seemed like the type of problem you frequently do on Programming Praxis.
Hope all is well with you and your family!
-Dan-
Your task is to write a program that sorts a set of points in order by the diminishing gaps between them. 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.
Highly Composite Numbers, Revisited
August 16, 2016
In a recent exercise, we used a priority queue to calculate highly composite numbers. That worked, but it was too slow and required too much memory to compute very large highly composite numbers. In today’s exercise we will use the same algorithm but a new data structure that permits us to compute very large highly composite numbers.
We make two changes. First, we record both highly composite numbers and candidates that are being considered as new highly composite numbers in a data structure called number-divisors-exponents, or ndxs for short, which has a number n in its car, the number of divisors d of n in its cadr, and the exponents of the prime factors of n in its cddr; carrying those numbers around rather than recomputing them as needed saves a little bit of time. The second change is more important; we use the distinct priority queue of a previous exercise to eliminate duplicate candidates, which greatly reduced the amount of computation needed to find highly composite numbers (since each candidate is considered only once) and the amount of memory require to store the candidates (because duplicates are not stored).
Your task is to write a program to compute highly composite numbers, 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.
Min-Min-Max
August 12, 2016
My statistics always decline in the summer, but they are starting to pick up, so I guess school must be starting in some places. Here’s a simple homework problem for beginning programmers:
Given an unsorted array of integers, find the smallest number in the array, the largest number in the array, and the smallest number between the two array bounds that is not in the array. For instance, given the array [-1, 4, 5, -23, 24], the smallest number is -23, the largest number is 24, and the smallest number between the array bounds is -22. You may assume the input is well-formed.
Your task is to provide two solutions to the problem, the first a straight forward solution that a beginning programmer might write, and a second solution that is rather more “creative;” feel free to define creative however you wish. 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.
Priority Queues With Distinct Elements
August 9, 2016
I recently needed a priority queue that contains no duplicate elements; if an attempt is made to add an element to the priority queue that is already present in the priority queue, the priority queue remains unchanged. As far as I know, none of the standard priority queue algorithms provide such a feature; they can’t, because they are all based on trees, and any element of the priority queue can be in either branch at any level of the tree.
Your task is to write a program that provides the data structure of priority queues with distinct elements. 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.
Nearly-Square Divisors
August 5, 2016
We have today a fun little problem from number theory:
Given positive integers n, a and b such that n = a · b with a ≥ b, find a and b such that the difference a − b is as small as possible.
For n square, the solution is just the square root of n; for instance, with n = 36, a = b = 6. Otherwise, a and b will be the two divisors nearest the square root; for instance, with n = 60, a = 10 and b = 6.
Your task is to write a program to find a and b as described above; use your program to find the nearly square divisors of n = 224403121196654400. 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.
Keypad Errors
August 2, 2016
[ Programming Praxis passed 2 million lifetime hits over the weekend. Gracious thanks to all my readers who have taken it so far. I can still remember being ecstatic when I got to a thousand hits. Thank you all. — Phil ]
Sometimes one key on a keyboard gets stuck, so some keys that are struck do not register. For instance, you may be trying to type 18684 on a numeric keypad, but if the 8 key is stuck, the keyboard registers you typing 164 instead. Assume the only input allowed is the digits 0 through 9.
Your task is to write a program that takes a target number, say a PIN, and a keyboard input, and determines if the keyboard input matches the target number assuming a single key is stuck. 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 