Programming Praxis

In the previous exercise we implemented the subset sum algorithms of CLRS 35.5. In today’s exercise we solve exercise 35.5-5, which asks us to return the subsets as well as their sums. The algorithm is exactly the same. The difference is that set members are stored along with their partial sums.

Your task is to write a program that solves the subset sum problem 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

We studied the subset sum problem — find the subset of a set of integers that sum to a given target — in two previous exercises; in both cases, we produced an exact answer, but took exponential time to do so. In today’s exercise, we will study a variant of the subset sum problem — find the subset of a set of integers that have the largest sum not exceeding a given target — that admits both exact and approximate answers; the exact answer runs in exponential time, though it is typically quite fast, but the approximate answer runs in linear time in the number of integers in the input set. Our solution is given by CLRS 35.5.

The exact solution uses two auxiliary functions. The function denoted by L + x adds x to each element of a list L. The function merge-lists takes two sorted input lists and returns the merge of the two lists with duplicates removed. Then CLRS gives the algorithm as follows, where S is a sorted list of integers and t is the target:

EXACT-SUBSET-SUM(S,t)
1  n = |S|
2  L₀ = ‹0›
3  for i = 1 to n
4      L_i = MERGE-LISTS(L_i−1, L_i−1 + x)
5      remove from L_i every element that is greater than t
6  return the largest element in L_n

The approximation algorithm adds a trimming step to the exact algorithm. The trimming step removes from the accumulating L list partial sums that are within a factor of 0 < δ < 1 such that any partial sum that is less than 1 + δ times its predecessor is removed. For instance, given L = ‹10, 11, 12, 15, 20, 21, 22, 23, 24, 29› and δ = 0.1, the trimmed L‘ = ‹10, 12, 15, 20, 23, 24›, where 11 is removed because it is within 10% of 10 and 21 and 22 are removed because they are within 10% of 20; trim assumes that L = ‹y₁, y₂,… y_m› is sorted:

TRIM(L,δ)
1  let m be the length of L
2  L‘ = ‹y₁›
3  last = y₁
4  for i = 2 2 m
5      if y_i > last · (1 + δ) // y_i ≥ last because L is sorted
6           append y_i onto the end of L‘
7          last = y_i
8  return L‘

Then the approx-subset-sum algorithm is the same as the exact-subset-sum algorithm except that step L_i = TRIM(L_i, ε/2n) is inserted between steps 4 and 5, where the solution is within 0 < ε < 1 percent of the desired target.

Your task is to implement the two algorithms given 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

We studied amicable chains in the previous exercise. Today we look at aliquot sequences, which are closely related to amicable chains. The aliquot sequence of n is the sequence that starts with n as its zero’th element and s(k−1) as its k‘th element, where s is the sum-of-divisors function of the previous exercise. For instance, the aliquot sequence of 10 is 10, 8, 7, 1, 0 because s(10) = 1 + 2 + 5 = 8, s(8) = 1 + 2 + 4 = 7, s(7) = 1, and s(1) = 0.

In 1888 Eugène Charles Catalan conjectured that all aliquot sequences end either at a prime number (the aliquot sequence for 10 shown above is usually considered to end at the prime 7, since once a member of an aliquot sequence is prime, the next two steps are 1 and 0) or at an amicable chain (either a perfect number which is an amicable chain of length 1, or an amicable pair which is an amicable chain of length 2, or a longer amicable chain). For instance, the aliquot sequence for 95 is 95, 25, 6, 6, …, where 6 is a perfect number. All numbers for which the entire aliquot sequence has been determined fit the conjecture, but there are many numbers for which the entire aliquot sequence is not known, of which the smallest is 276.

Your task is to write a function that computes aliquot sequences; it should return either the prime number or the amicable chain (smallest number first) that terminates the 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.

Pages: 1 2 3

A perfect number is equal to the sum of its proper divisors; for instance, the divisors of 28 are 1, 2, 4, 7, and 14, and 1 + 2 + 4 + 7 + 14 = 28, so 28 is a perfect number. Two numbers m and n form an amicable pair if the sum of the divisors of m equals n and the sum of the divisors of n equals m; for instance, 220 has divisors 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 which sum to 284, and 284 has divisors 1, 2, 4, 71, 142 which sum to 220, so 220 and 284 form an amicable pair. An amicable chain is a list of numbers, each the sum of the divisors of the previous number, that loops so that the sum of the divisors of the last number in the list is the first number in the list; for instance, the numbers 12496, 14288, 15472, 14536, and 14264 form an amicable chain of length 5, since sum-div(12496) = 14288, sum-div(14288) = 15472, sum-div(15472) = 14536, sum-div(14536) = 14264, and sum-div(14264) = 12496. We discussed amicable numbers in a previous exercise.

Your task is to write programs to locate perfect numbers, amicable numbers and amicable chains; use it to find all of those objects for which all of their elements are less than a million. 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

In the early days of automatic garage door openers, all openers shared a single code, so that every garage door opener worked with every garage door; you could open your neighbor’s garage door and walk into his garage whenever you wanted to. The next generation of garage door openers had 8 DIP switches, and thus 256 codes, which solved the problem of casually preventing your neighbor from opening your garage but was hardly a deterrent to thieves.

Nowadays garage door openers and car lock keychain fobs use rolling codes, sometimes called hopping codes, for security. Each fob has a unique serial number; each garage door opener or car lock is programmed to recognize only signals from specific fobs. The signals themselves are randomized and encrypted by the rolling code.

It works like this: Each time a button on the fob is pressed, the requested signal is sent to the receiver along with the serial number of the fob and the rolling code, which is an encrypted random number. The receiver ensures the fob has a recognized serial number, decrypts the rolling code, compares it to the receiver’s synchronized random number generator, and performs the requested action if everything agrees or denies the requested action if it doesn’t.

It’s possible for the fob to send a signal when it is out of range of the receiver. To allow that, the receiver checks the next 256 numbers in the random sequence, instead of just one number, and accepts the signal if any of the 256 numbers agree. Additionally, in case the fob sends more than 256 consecutive signals out of range, the receiver performs the requested action and resynchronizes its copy of the random number sequence if the fob sends two successive numbers from the random sequence.

Your task is to write programs that simulate the actions of the fob and the receiver. 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

One of the sites that I watch from time to time is Career Cup, which publishes coding questions that have been asked in actual job interviews. These questions came through this morning:

1) Consider a sorted singly-linked list having the following nodes: 10 -> 30 -> 50 -> 70 -> NULL. You are given a pointer to node 50 and a new node having the value 40. Can you insert node 40 correctly in the list maintaining the ascending order?

2) Given a linked list 5 -> 4 -> 3 -> 2 -> 1 produce a linked list 4 -> 2 -> 0 -> 2 -> 1 by subtracting the last node of the list from the first, the next-to-last node from the second, and so on, stopping at the midpoint of the list.

3) Write a program to output the number of consecutive trailing zeros in the factorial of a number. For example, if the number is 5, then 5! = 120, and there is one trailing zero.

Your task is to write programs to answer the three interview questions posed 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

Clustering is the process of collecting in groups all of the items from an input collection that share some common feature; for instance, the GROUP BY operator of SQL performs clustering. We will define cluster(proc, lt?, lst) as a function that takes an input list and returns a list of lists; proc computes a signature of each item in the input list, and each sub-list in the output list contains all those elements of the input list with identical signatures, with sub-lists in increasing order of signature according to lt?. The type of cluster is (α → β) × (β × β → boolean) × (list α) → (list (list α)).

Your task is to write the function cluster. 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

Packed ascii is a method for compressing a useful subset of ascii characters in 6 bits, used in HART-enabled devices. The characters that may be transmitted are the space character, the 26 upper-case letters, the 10 digits, and the following punctuation characters: ! " # $ % & ' ( ) * + , - . / : ; ? @ [ \ ] ^ _. Omitted are the 26 lower-case letters, the rubout character, and the following punctuation characters: ` { | } ~.

Compression is achieved by keeping only the six low-order bits of each ascii character. Compressed characters are expanded to their original character by adding a high-order bit that is the complement of the compressed high-order bit. For instance, the string “PRAXIS” is compressed as the six 6-bit binary numbers 010000 010010 000001 011000 001001 010011.

A string of characters is compressed to 6-bit characters, then transmitted as 8-bit bytes by packing the bits from high-order to low-order, so that four characters are transmitted in three bytes, achieving a 25% compression. If the message length is not an even multiple of four, space characters are added to the end of the string as padding. Thus, the six 6-bit binary numbers representing “PRAXIS” would be padded with two space characters and transmitted as the six 8-bit binary numbers 01000001 00100000 01011000 00100101 00111000 00100000, which corresponds to the string “A X%8 “.

Your task is to write functions that compress and expand strings in packed ascii format. 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

An n-bit Gray sequence is a sequence of 2ⁿ values, starting from 0, in which each differs from its predecessor by a single bit. There are always 2ⁿ⁻¹ n-bit Gray sequences; for instance, the two 2-bit Gray sequences are 0, 1, 3, 2 and 0, 2, 3, 1. It is easier to see the Gray sequences when they are written in binary; the two 2-bit Gray sequences written in binary are 00, 01, 11, 10 and 0,0 10, 11, 01, where it is clear that each element of the sequence differs from the previous one by only one bit.

Although there are many possible Gray sequences for any given number of bits, there is one Gray sequence, known as the binary reflected gray code BRGC, that is almost always the Gray sequence that is being discussed. Such sequences are generated recursively from the next-smaller sequence by reversing the sequence, prefixing the entries of the original sequence with a 0-bit, prefixing the entries of the reversed sequence with a 1-bit, then concatenating the two sequences. For instance, given the 2-bit Gray sequence 00, 01, 11, 10, its reversal is 10, 11, 01, 00, adding a 0-bit to the original gives 000, 001, 011, 010, adding a 1-bit to the reversal gives 110, 111, 101, 100, and concatenating the two gives 000, 001, 011, 010, 110, 111, 101, 100, which is 0, 1, 3, 2, 6, 7, 5, 4.

Your task is to write a function that generates an n-bit binary reflected Gray 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.

Pages: 1 2