pow(n, m) would never terminate for m > 0

The following code was shown in today's lecture as one of the alternatives to single-call recursion on pow(n, m):

0. def pow(n, m)
1.     if m == 0: return 1
2.     else:      return pow(n, Floor(m / 2)) * pow(n, Ceiling(m / 2))

Since we used floors and ceilings, I take it that m is an integer. Then for an m > 0, a call to pow(n, m) would execute line 2. But Ceiling(m / 2) will never be 0 for an integer m > 0, so line 2 would get executed indefinitely on pow(n, Ceiling(m / 2)'s recursive call, causing the program to never terminate.

I think that adding "else if m == 1: return n" before the last else branch would fix this problem.

PS3 - G(n) induction step

I got my third problem set back today, and I noticed that the marker made a note on my induction step. Here is the beginning of my proof by complete induction:

      Let P(n): G(n) = S(i from 0 to n) 3^i
         Claim: for any natural number n, P(n)

 Base case n=0: G(0) = 1 (by definition of G)
                S(i from 0 to 0) 3^i = 3^0 = 1
                Then P(0) holds.

Induction Step: Let n be part of N\{0} and assume P(0) /\ ... /\ P(n-1)

The marker asked why can't n=0 be in the induction step? They mentioned that I need this, but then wouldn't P(n-1) = P(-1) for n=0? The claim was only about P being true for natural numbers, so I am a little confused. Indeed I needed n=0, but I specifically handled that in the base case.

N-finder for Problem Set 2

The N we found in last week's lecture was determined after calculating the 6th possible combination of stamps. Not too much work, but with numbers as ugly as 5 and 11 I figured that manually finding it would be more time consuming than just asking a Pentium 3 to find it for me :-)

Here's a small C program that calculates the first few possible combinations of 5- and 11-cent stamps, and finds the first combination that starts the series of consecutive values. It can be used for any stamp values, provided you adjust the STAMP_1, STAMP_2, and SIZE constants.

#include <stdio.h>
#include <stdlib.h>

#define STAMP_1 5  // STAMP_1 must be smaller than STAMP_2
#define STAMP_2 11

#define SIZE 50

struct DATA {
    int total;  // the total value
    int five;   // the factor of 5-cent stamps
    int eleven; // the factor of 11-cent stamps
};

int order(const void* a, const void* b)
{
    return ((struct DATA*)a)->total - ((struct DATA*)b)->total;
}

int main(int argc, char* argv[])
{
    struct DATA* data = calloc(SIZE * SIZE, sizeof(struct DATA));
    struct DATA* Data = calloc(SIZE * SIZE, sizeof(struct DATA));

    int i, j;
    
    // calculate many different combinations of 5 and 11 cents
    for(i = 0; i < SIZE; i++) {     // for every 5-cent stamp
        for(j = 0; j < SIZE; j++) { // for every 11-cent stamp
            data[i * SIZE + j] = (struct DATA) {
                i * STAMP_1 + j * STAMP_2, i, j
            };
        }
    }
    
    // sort them in ascending order
    qsort(data, SIZE * SIZE, sizeof(struct DATA), order);
    
    // remove duplicate totals
    for(i = 0, j = 0; i < SIZE * SIZE - 1 && j < SIZE * SIZE; j++) {
        do {
            i++;
        } while(i < SIZE * SIZE - 1 && data[i].total == data[i + 1].total);

        Data[j] = data[i];
    }
    
    int entries = j;
    int consecutive = 0;
    
    // search for 5 consecutive total values
    for(i = 0; i < entries - STAMP_1; i++) {
        consecutive = 1;
        
        for(j = i; j < i + STAMP_1 - 1; j++) {
            if(Data[j].total + 1 != Data[j + 1].total) {
                consecutive = 0;
                break;
            }
        }
        
        if(consecutive) {
            consecutive = i;
            break;
        }
    }

    if(consecutive > 0) {
        printf("The first batch of %d consecutive total values occurs at:\n\n",
        STAMP_1);

        printf("%d = %d * (%d) + %d * (%d)  --  unique combination #%d\n\n",
        Data[consecutive].total,
        Data[consecutive].five, STAMP_1,
        Data[consecutive].eleven, STAMP_2,
        consecutive + 1);
        
        for(i = 1; i < STAMP_1; i++) {
            printf("%d = %d * (%d) + %d * (%d)\n",
            Data[consecutive + i].total,
            Data[consecutive + i].five, STAMP_1,
            Data[consecutive + i].eleven, STAMP_2);
        }
        
        printf("\nThen N = %d. ", Data[consecutive].total - 1);
    } else {
        printf("No batch of %d consecutive total values found!\n", STAMP_1);
        printf("Try a total data size larger than %d * %d = %d.\n\n",
        SIZE, SIZE, SIZE * SIZE);
    }
    
    free(data);
    free(Data);
    
    printf("Press RETURN to exit\n");
    getchar();

    return 0;
}

It turns out that N was derived from the 20th possible combination. I noticed a potential pattern in the combinations, and if I'll have the time I'll devise a prettier algorithm to replace the brute-force approach sometime before the course ends.