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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

Crypt(1)

October 29, 2019

I was surprised to learn recently that modern Linux systems do not provide a crypt command, which was common in older Unix systems. So I decided to write one.

The interface to crypt is simple: it reads from standard input and writes to standard output, requesting a key from the console using a method that doesn’t echo the key to the screen. The program has no command-line arguments.

The cipher is symmetric, so encryption and decryption use the same key; the ciphering algorithm I choose is <a href="“>RC4-drop512, which isn’t exactly state-of-the-art encryption, but is simple and good enough for casual use. The base algorithm is RC4; dropping the first 512 characters of the generated keystream eliminates a potential weakness in the bas RC4 key scheduling algorithm.

Your task is to write a crypt program as described above. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

IBAN

October 25, 2019

The International Bank Account Number (IBAN) is an internationally agreed standard of identifying bank accounts with a hash number to reduce errors. The first two characters of an IBAN are the two-letter country code, the next two characters are a two-digit hash, and the remaining characters identify the bank routing number and depositor account number. For instance, here is a fictition British IBAN: GB82 WEST 1234 5698 7654 32. The full IBAN standard specifies the range of valid bank account numbers and depositor account numbers for each country; we are interested only in the hash code.

In the code shown above, the hash code consists of the two digits 82, which are validated as follows:

1) Move the first four characters from the beginning of the string to the end: WEST 1234 5698 7654 32GB 82.

2) Replace letters with two-digit numbers according to the scheme A = 10, …, Z = 35:
3214 2829 1234 5698 7654 3216 1182.

3) Treating the string as a large integer, divide by 97 and calculate the remainder.

4) If the remainder is not 1, the IBAN is not valid.

To generate a hash code, perform the same procedure as above with the two hash digits initially set to 00, then subtract the hash code from 98 and insert it in the IBAN.

Your task is to write functions to validate existing IBAN numbers and generate hash codes for new IBAN numbers. 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 Silly Task

October 22, 2019

Today’s task is silly:

Your task is to write a program that, when executed, writes to the output in words the number of characters in the program. 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

Anagrams, Again

October 18, 2019

The previous exercise showed a probabilistic method for determining if two strings are anagrams, and some users pointed out collisions in the method that falsely concluded two strings were anagrams when in fact they were not.

Your task is to write a program that recognizes anagrams without possibility of error. 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