Just Showing Off

May 19, 2017

As I have mentioned on several previous occasions, I frequently receive email from students asking for homework help, which I routinely ignore. Less frequently, I receive email from someone who tells me that Scheme is a horrible programming language, they don’t understand it, it is unreadable, there are too many parentheses, blah, blah, blah, and wouldn’t it be better if I wrote my blog in C#. (I don’t know what’s wrong with C# people, but I get more of them than any other language zealots.) Usually I ignore them, too, but the other day I engaged one of those correspondents who singled out macros as a particular wart on the face of Scheme. So I wrote to him and gave him this macro, which I used to calculate fibonacci numbers; the whole story is on the next page:

(define-syntax define-memoized
  (syntax-rules ()
    ((define-memoized (f arg ...) body ...)
      (define f
        (let ((cache (list)))
          (lambda (arg ...)
            (cond ((assoc `(,arg ...) cache) => cdr)
            (else (let ((val (begin body ...)))
                    (set! cache (cons (cons `(,arg ...) val) cache))
                    val)))))))))

When I showed him how to speed up the calculation of fibonacci numbers by memoizing sub-computations, he grudgingly agreed there might be something there, but it wouldn’t translate to C# (I didn’t disagree with that comment).

Your task is to write a program that shows off some special feature of your favorite programming language; tell the story how it makes your language better than any others, and give a real-life example. 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

License Plates

May 16, 2017

A license plate number has form ABC-123, three letters followed by three digits. You are to store the set of license plate numbers, assume you will have about a hundred thousand of them, and be able to answer queries like:

* Is license plate PLB-123 a member of the set?

* How many license plates begin with the letters PLB?

* What is the list of license plates that begin with the letters PLB?

Your task is to write programs to store and query a list of license plate 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 3

I traded several emails this week with a programming student who was having trouble with this assignment:

Write a function that divides two numbers and returns their quotient. Use recursive subtraction to find the quotient.

The student went on to explain that he thought he needed to use a counter variable that he incremented each time the function recurred, but he didn’t know how to do that because the function could only take two arguments; it had to be of the form (define (divide a b) ...).

Your task is to write the function, and explain to the student how it works. 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

Distinct Characters

May 9, 2017

We’ve done similar exercises in the past:

Write a program to determine if all the characters in a string are distinct. For instance, the word “Programming” has two m and two g, so all the characters are not distinct, but the word “Praxis” has six distinct characters.

Your task is to write a program to determine if all the characters in a string are distinct; you should provide three solutions, one that takes time O(n²), one that takes time O(n log n), and one that takes time O(n). 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

I’ve seen this before, and when I ran across it again a few days ago decided to share it with all of you. This is why I like Scheme so much:

In mathematics, the derivative of a function f(x) is f'(x) = \lim_{dx \to 0} \frac{f(x+dx)-f(x)}{dx}. Here’s a simple implementation in Scheme, with an example:

Petite Chez Scheme Version 8.4
Copyright (c) 1985-2011 Cadence Research Systems

> (define dx 0.0000001)
> (define (deriv f)
    (define (f-prime x)
      (/ (- (f (+ x dx)) (f x))
         dx))
    f-prime)
> (define (cube x) (* x x x))
> ((deriv cube) 2)
12.000000584322379
> ((deriv cube) 3)
27.000000848431682
> ((deriv cube) 4)
48.00000141358396

Those results are reasonably close to the actual derivative of 3x^2. The code is identical to the math.

Your task is to write a function to calculate derivatives in your favorite language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution in the comments below.

Pages: 1 2

Base Conversion

May 2, 2017

I continue cleaning out my list of saved homework questions:

Given a number represented as a string in base 2, convert the number to a string in base 4. For instance, the number 110110002 = 31204.

Your task is to write a program that converts numbers from base 2 to base 4; for extra credit, write a program that converts from any base to another. 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

Abbreviated Sentences

April 28, 2017

Sometimes people send me their homework problems and expect me to write programs for them. I ignore such people, but I do collect the tasks and use them in the blog from time to time, always waiting several months until the term has ended. Today’s exercise comes by that route:

Write a program that takes as input a sentence (a sequence of characters) and abbreviates it by replacing each word (a maximal sequence of letters) with the first letter of the word, followed by the number of letters in the middle of the word, followed by the last letter of the word. For instance, Programming Praxis is abbreviated P9g P4s. Any non-letter characters in the input should be retained in their original position in the output.

Your task is to write a program that abbreviates sentences. 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

Etude On A Binary Tree

April 25, 2017

We have today another in our occasional series of exercises on binary trees; the input tree need not necessarily be ordered or balanced:

Given a binary tree containing integers, find the sum of all nodes at an even distance from the root, less the sum of all nodes at an odd distance from the root.

For instance, given the binary tree shown below, the requested sum is 1 – 2 – 3 + 4 + 5 + 6 + 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 = -74:

           1
     2           3
  4     5     6     7 
 8  9 10 11 12 13 14 15

(I’m not an artist; you’ll have to imagine the lines connecting the various levels.)

Your task is to write a program to compute alternate sums and differences of the nodes of a binary tree. 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

Damsel And Suitor

April 21, 2017

Chris Smith tweets mathematical curiosities at @aap03102. This one caught my eye the other day:

This is from 1779: a time when puzzles were written in poetry, solutions were assumed to be integers and answers could be a bit creepy:

Questions proposed in 1779, and answered in 1780.

I. QUESTION 742, by Mr. John Penberthy.

I’m in love with a damsel, the pride of the plain,
Have courted and talk’d in Ovidian strain;
But vain is the rhetoric us’d by my tongue,
She says I’m too old and that she is too young:
From the foll’wing equations, dear ladies, unfold;
If she be too young, or if I be too old.

x3 + xy2 = 4640y
x2yy3 = 537.6x

Where x represents my age, and y the damsel’s.

Your task is to compute the ages of the damsel and her suitor. 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

Longest Line

April 18, 2017

Today’s exercise is simple:

Write a program that prints the longest line in a file. If there is a tie for the longest line, you may print any of the longest lines, or all of them, at your option.

There are lots of ways to solve this problem, and I expect that my fun-loving readers will come up with some outlandish solutions, so to make this a sensible exercise we add two rules: First, if you comment you must provide at least two solutions. Second, at least one of your solutions must be “reasonable” in the sense that you would actually use it in a production environment.

Your task is to write a program to find the longest line in a file. 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