## 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, findx,yandzsuch thatx y z=nandx+y+zis minimal; for instance, givenn= 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

bagis 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.

## 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.

## 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.