Happy Thanksgiving
November 26, 2019
My daughter is visiting this week, so there will be no exercises. The next exercise will be on Tuesday, December 3rd. Enjoy the time with your family.
Three-Way Minimum Sum Partitions
November 22, 2019
I had a lot of fun working on this problem:
Given n, find x, y and z such that x y z = n and x + y + z is minimal; for instance, given n = 1890, the correct answer is (9 14 15).
Your task is to write a program to find x, y and z. 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.
Modified Coin Change
November 19, 2019
We solved the standard coin change problem in two previous exercises. The particular problem given here is to find the minumum number of coins that can be used to create a target amount of money, given an unlimited number of coins of various denominations, and is normally solved by a dynamic programming algorithm.
Today’s task is a variant on that problem: find the minimum number of coins that can be used to create a target amount of money, given an unlimited number of coins of denomination that are powers of 5.
Your task is to write a program to solve the modified coin change problem. 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.
Tri-Partitions
November 15, 2019
We have a fun little task for your Friday lunch hour:
Given an array of integers, rearrange the integers so no two consecutive integers have a sum that is divisible by 3, or indicate that such an arrangement is not possible.
Your task is to write a program to rearrange an array of integers 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.
Reverse A Linked List
November 12, 2019
We’ve done this before, but I saw questions asked about this task on three different beginner-programming forums this weekend (it must that that time in the semester when teachers introduce linked lists), and it never hurts to do some basic drill.
Your task is to write a program that reverses a linked list. 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.
Union Of Two Bags
November 8, 2019
Today’s exercise is somebody’s homework:
A bag is a list of key/count pairs: for instance, a bag containing three of item E, three of item R, and three of item A can be written E3R3A3. The union of two bags is a single bag containing a list of key/count pairs in which each item in each of the two bags has its count combined in a single item: for instance, the union of bags E3R3A3 and B3R3F3 is E3R6A3B3F3. The order of items in the bags is not significant.
Your task is to write three programs to compute the union of two bags, with time complexities O(mn), O((m+n) log (m+n)), and O(m+n), where m and n are the sizes of the two bags. 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.
Encrypting Ed(1)
November 5, 2019
When I introduced the topic crypt(1) last week my actual goal was to write an editing script using ed on an encrypted file; that’s when I realized that crypt(1) was missing and that ed no longer had an -x flag. I didn’t want anything fancy, just basic encryption. I knew the old crypt(1) was no good (actually, it was no good when it was introduced forty years ago) but I was surprised that Unix and Linux had not kept up with some kind of encryption. Humbug!
Your task is to enhance ed by adding the -x encryption flag. 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.
Crypt(1), Again
November 1, 2019
In the previous exercise I tried to write a replacement for the old Unix crypt(1) program, but never did figure out how to enter a password in Chez Scheme. So today I have the program in C.
To answer some questions that came up in the previous exercise: Yes, I know about ccrypt. Yes, I know that I should not rely on any cryptographic code I write. Yes, the original Unix crypt wasn’t very secure, though at least I can claim that my crypt is better now than the Unix crypt was at the time.
You can see my crypt program on the next page.
Programming Praxis 